MAKALAH MATEMATIKA DISKRIT

“Graph Dual dan Graph Polyhedral”

DOSEN PENGAMPU :
Dra. Susda Heleni, [Link]

DISUSUN OLEH :
KELOMPOK 2
HAFIZAH SYAHRANI SUBEKTI 1905124572
HAFSHOH 1905156467
HELA AZZAHRA 1905112347
RAHMADILLA 1905112152
ROSMAYANTI PURBA 1930010

PENDIDIKAN MATEMATIKA
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS RIAU
2021
 KATA PENGANTAR
Puji syukur kami ucapkan terhadap Tuhan Yang Maha Esa yang telah memberi
Kami Rahmat dan Hidayah-Nya sehingga kami dapat menyelesaikan makalah
mengenai “Graph Dual dan Graph Polyhedral”
Selain untuk menambah wawasan penyusun, makalah ini disusun untuk
memenuhi tugas Mata Kuliah Matematika Diskrit. Makalah ini diharapkan dapat
membantu para pembaca dalam memenuhi harapan dan tuntutan.
Kiranya tak ada gading yang tak retak, demikian juga dengan makalah ini.
Kami menyadari makalah ini jauh dari sempurna, maka dari itu kami mohon
maklum atas kesalahan yang terdapat pada makalah ini. Selanjutnya kami
ucapkan terima kasih kepada para pembaca dan seluruh pihak terkait dalam
pembuatan makalah ini. Semoga makalah ini bermanfaat bagi kita.

Pekanbaru, 10 November 2021

Penyusun

i
 BAB I
PENDAHULUAN

A. Latar Belakang
Teori graph dari matematika diskrit yang banyak digunakan sebagai
alat untuk menggambarkan atau menyatakan suatu persoalan agar lebih
mudah dimengerti dan diselesaikan. Banyak perosoalan akan lebih jelas untuk
diterangkan bila dapat dipresentasikan dalam bentuk graph
Suatu Graph G(V(G), E(G) terdiri atas suatu himpunan tak kosong dan
berhingga V(G) yang anggotanya disebut simpul, dan suatu himpunan
berhingga E(G) dengan anggota yang saling berbeda yang disebut busur,
dimana busur tersebut merupakan pasangan tak-terurut dari simpul-simpul
yang berbeda pada V(G). Maka dari penjelasan graf di sini kita akan bahas
graph dual dan contoh contohnya.

B. Rumusan Masalah
1. Apa yang dimaksud dengan Graph Dual?
2. Apa yang dimaksud dengan Graph Polyhedral?

C. Tujuan
Tujuan yang berangkat dari permasalahan di atas adalah :
1. Untuk mengetahui definisi graph dual
2. Untuk mengetahui definis graph Polyhedral
3. Untuk mengetahui keterkaitan graph dual dan graph pokyhedral terhadap
graph planar

1
 BAB II
ISI
4.5 Graph Dual
Definisi 4.5.1 : Misal G graph bidang konstruksi sebuah graph G* sedemikian
hingga :
i. Setiap titik G* berkorespondensi dengan sebuah muka dari
G.
ii. Jika sebuah sisi e membatasi muka f_1dan f_2 di G maka
titik-titik G*
yang berkorespondensi dengan f_1 dan f_2 dihubungka
dengan sebuah sisi.
Graph G* yang dikonstruksi seperti ini disebut graph dual dari
G (graph sejodoh) dari G.

Contoh 10 :

Graph G pada gambar 4.8 yang digambar “tebal”, sedangkan dual dari
G(G*) adalah graph yang digambar dengan garis putus-putus.
Berdasarkan uraian diatas, terdapat korespondensi satu-satu antara unsur-
unsur graph G dan G* sebagai berikut :
a. Sebuah muka G berkorespondensi dengan sebuah titik G*.
Akibatnya |F(G)|=|V(G"∗")|

2
 b. Sebuah sisi G berkorespondensi dengan sebuah sisi G*.
Jadi |E(G)|=|E(G"∗" )|
c. Sebuah muka berderajat k di G berkorespondensi dengan sebuah titik
berderajat k di G* sehingga :

∑ 𝑑(𝑓) = ∑ 𝑑(𝑣)
𝑓∈𝐹(𝐺) 𝑣∈𝑉(𝐺∗)

(dengan catatan G tidak memuat loop dan titik berderajat satu)

d. Sebuah sisi yang terkait dengan sebuah titik yang berderajat satu di G,
berkorespondensi dengan sebuah gelung(loop) di G*.
e. Sebuah titik berderajat dua di G, berkorespondensi dengan sepasang sisi
rangkap di G*

Jika G dan H adalah graph planar yang isomorfik, maka belum tentu G* dan
graph H* isomorfik

Contoh 11 :
Graph G dan H berikut isomorfik

Graph G
Graph H

3
 Graph G* Graph H*

Perhatikan bahwa G* memuat sebuah titik berderajat 5, sedangkan H*

tidak memuat titik berderajat 5. Jadi G* dan H* tidak isomorfik.
Definisi 4.5.2 : Sebuah graph planar yang isomorfik dengan dualnya disebut
graph dual diri (self dual graph)

Contoh 12 :

𝑓4
𝑓2 𝑓3
𝑓1

𝑓1

𝑓2 𝑓3
𝑓4
Graph G Graph G*

Perhatikan bahwa G ≅ G*

Teorema 4.5.1: Jika G∗ Adalah dual dari graph planar dan G ≅ G∗ Maka:
E(G) │= 2 (│V(G) │- 1 )

Bukti:
Karena G ≅ G∗ maka G terhubung, karena G graph planar dan terhubung maka
menurut teorema Euler berlaku:

│V(G) │- │ E(G) │+ │F(G) │= 2 ………………….(1)

Karena G∗ adalah dual dari graph G, maka:
│F(G) │= │V(G∗ ) │………………………………….(2)
Karena G isomorfik dengan G∗ (G ≅ G∗ ) maka:

4
 │V(G) │- │V(G∗ ) │……………………………….…(3)
Persamaan 3 dan 2 disubsitusikan ke persamaan (1) maka diperoleh:
│V(G) │- │ E(G) │+ │F(G) │= 2
│V(G) │- │ E(G) │+ │V(G∗ ) │= 2
│V(G) │- │ E(G) │+ │V(G) │= 2
2 │V(G) │- │ E(G) │= 2
│ E(G) │= 2 │V(G) │- 2
= 2 │V(G) │- 1 terbukti

4.6 Graph Polyhedral

Defenisi 4.6.1: Bangun ruang dimensi 3 yang dibatasi oleh permukaan-
permukaan yang berupa bidang datar polygonal (bidang datar
segi-n, n ≥3) disebut polyhedron.

Defenisi 4.6.2: Jika setiap dua titik interior polyhedron dihubungkan dengan
sebuah ruas garis dan ternyata keseluruhan ruas garis tersebut
terletak di interior polyhedron tersebut disebut polyhedron
konveks.

Defenisi 4.6.3 : Polyhedron konveks yang setiap permukaannya berupa bidang-

bidang datar polygonal beraturan yang kongruen disebut
polyhedron beraturan.

Contoh 13 : Balok adalah polyhedron dan kubus adalah polyhedron beraturan.

Titik – titik dan sisi – sisi dari sebuah polyhedron (skeleton) membentuk
sebuah graph sederhana diruang dimensi 3. Jika polyhedron itu konveks, maka
kerangkanya (skeleton) berupa graph bidang (planar) sederhana dan terhubung
yang disebut graph polyhedral.
Perhatikan bahwa dalam graph polyhedral, derajat setiap titik paling
sedikit 3, begitu pula derajat setiap muka paling sedikit 3.

5
Contoh 14 :

Polyhedron Graph Polyhedral

kubus kubus

Berikut akan diperlihatkan ada 5 macam polyhedron beraturan.

Misalkan G adalah graph bidang (planar). Derajat dari setiap titik G adalah
k ≥ 3 dan derajat dari setiap muka G adalah m ≥ 3. Menurut lemma jabat tangan,
diperoleh :
∑𝑣𝜖𝑉(𝐺) 𝑑(𝑉) = 2|𝐸(𝐺)| atau
1
|𝐸(𝐺)| = ∑𝑣𝜖𝑉(𝐺) 𝑑(𝑉)
2
1
= ∑𝑣𝜖𝑉(𝐺) 𝑘
2
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|….(1)
2

Karena setiap sisi membatasi tepat dua muka, maka :

∑𝑓𝜖𝐹(𝐺) 𝑑(𝑓) = 2|𝐸(𝐺)|…(2)
1
Karena setiap 𝑑(𝑓) = 𝑚, ∀ 𝑓 ∈ 𝐹(𝐺) dan |𝐸(𝐺)| = 2 𝑘|𝑉(𝐺)| maka

diperoleh ∑𝑓𝜖𝐹(𝐺) 𝑑(𝑓) = 2|𝐸(𝐺)|

6
 𝑚 |𝐹(𝐺)| = 𝑘|𝑉(𝐺)|
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| = …(3)
𝑚

Menurut teorema Euler :

|𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = 2…(4)
Dari persamaan (1), (3), dan (4) diperoleh :
|𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = 2
1 𝑘|𝑉(𝐺)|
|𝑉(𝐺)| − 𝑘|𝑉(𝐺)| + =2
2 𝑀
2𝑚|𝑉(𝐺)|−𝑘𝑚|𝑉(𝐺)|+2𝑘|𝑉(𝐺)|
=2
2𝑚

|𝑉(𝐺)|{(2𝑚 − 𝑘𝑚 + 2𝑘)} = 4𝑚
4𝑚
|𝑉(𝐺)| = …(5)
2𝑚−𝑘𝑚+2𝑘

Karena |𝑉(𝐺)| > 0 dan 4𝑚 > 0, maka :

Persamaan 5 menjadi:
2𝑚 − 𝑘𝑚 + 2𝑘 > 0
(𝑘 − 2)(𝑚 − 2) < 4…(6)
Karena k dan m bilangan bulat k ≥ 3 dan m ≥ 3, maka kemungkinan
semua nilai – nilai k dan m yang memenuhi (6) adalah :
k = 3 dan m = 3 atau
k = 3 dan m = 4 atau
k = 3 dan m = 5 atau
k = 4 dan m = 3 atau
k = 5 dan m = 3
Karena ada 5 kemungkinan nilai – nilai k dan m, maka terbukti hanya ada
5 graph polyhedron beraturan.

1) Untuk k = 3 dan m = 3 didapat :

4𝑚 4.3
|𝑉(𝐺)| = = =4
2𝑚 − 𝑘𝑚 + 2𝑘 2(3) − 3(3) + 2(3)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 2 . 3(4)

7
 = 6 dan
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
3.4
= 4

=4
Sehingga diperoleh polyhedron beraturan yang disebut Tetrahedron.

Tetrahedron

Graph
Bangun ruang

2) Untuk k = 3 dan m = 4, diperoleh:

4𝑚 4.4
|𝑉(𝐺)| = = 2(4)−3(4)+2(3) = 8
2𝑚−𝑘𝑚+2𝑘
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 2 . 3(8)

= 12 dan
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
3(8)
= 4

=6
Sehingga diperoleh polyhedron beraturan yang disebut kubus.

Kubus

8
3) Untuk k = 3 dan m = 5, diperoleh:
4𝑚 4.5
|𝑉(𝐺)| = = 2(5)−3(5)+2(3) = 20
2𝑚−𝑘𝑚+2𝑘
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 2 . 3(20)

= 30 dan
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
3(20)
= 5

= 12
Sehingga diperoleh polyhedron beraturan yang disebut dodecahedron.

4) Untuk k = 4 dan m = 3, diperoleh:

4𝑚 4.3
|𝑉(𝐺)| = = 2(3)−4(3)+2(4) = 6
2𝑚−𝑘𝑚+2𝑘
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 2 . 4(6)

= 12 dan
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| = `
𝑚
4(6)
= 3

=8

9
Sehingga diperoleh polyhedron beraturan yang disebut octahedron.

5) Untuk k = 5 dan m = 3, diperoleh:

4𝑚 4.3
|𝑉(𝐺)| = = 2(3)−5(3)+2(5) = 12
2𝑚−𝑘𝑚+2𝑘
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 2 . 5(12)

= 30 dan
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
5(12)
= 3

= 20
Sehingga diperoleh polyhedron beraturan yang disebut isocahedron.

Isocahedron

10
 BAB III
PENUTUP
A. Kesimpulan
Adapun kesimpulan dari makalah ini adalah:
Graph Dual
Defenisi 4.5.1: misalkan G graph bidang konstruksi sebuah graph G∗ sedemikian
sehingga:
(i) Sebuah titik G∗ berkorespondensi dengan sebuah muka dari G
(ii) Jika sebuah sisi e membatasi muka f1 dan f2 di G maka titik-titik
G∗ yang berkorespondensi dengan f1 dan f2 dihubungkan dengan
sebuah sisi
Graph G∗ yang dikonstruksi seperti ini disebut graph dual dari G (Graph sejodoh)
dari G

Graph Polyhedral
Defenisi 4.6.1: Bangun ruang dimensi 3 yang dibatasi oleh permukaan-
permukaan yang berupa bidang datar polygonal (bidang datar
segi-n, n ≥3) disebut polyhedron.
Defenisi 4.6.2: Jika setiap dua titik interior polyhedron dihubungkan dengan
sebuah ruas garis dan ternyata keseluruhan ruas garis tersebut
terletak di interior polyhedron tersebut disebut polyhedron
konveks.
Defenisi 4.6.3 : Polyhedron konveks yang setiap permukaannya berupa bidang-
bidang datar polygonal beraturan yang kongruen disebut
polyhedron beraturan.

11
B. Saran
Kami sebagai penulis, menyadari bahwa makalah ini banyak sekali
kesalahan dan kekurangan dalam penulisan, serta masih jauh dari kata
kesempurnaan tentunya penulis akan terus memperbaiki makalah ini dengan
mengacu pada sumber. Oleh karena itu, penulis mengharapkan kritik dan saran
yang membangun tentang pembahasan makalah ini.

12