MATEMATIKA DISKRIT
“ KETEBALAN SEBUAH GRAPH DAN GRAPH POLYHEDRAL”
DOSEN PEMANGKU:
Aulia Sthephani, [Link]
OLEH:
KELOMPOK 3:
1. Fanny Rahmawati (166410)
2. Hasanah Ritonga (166410)
3. Novian ()
4. Rahmayuli (166410981)
5. Trinadila Irawan (166410)
Ketebalan Dari Sebuag Graph
Definisi 4.4.1 :
Ketebalan (thickness) dari sebuah graph G adalah minimum dari bilangan yang
menyatakan banyaknya graph bagian planar dari G yang gabungannya sama dengan G.
Ketebalan sebuah graph G dinotasikan dengan 𝜃(𝐺).
Defenisi 4.4.2 :
Ggabungan dari dua buah graph G dan H, ditulisa 𝐺 ∪ 𝐻, adalah grapj yang himpunan
titiknya 𝑉(𝐺) ∪ 𝑉(𝐻) dan himpunan sisinya 𝐸(𝐺) ∪ 𝐸(𝐻).
Contoh : 𝜃(𝑘5 ) adalah 2
k5 subgraph planar dari k5
Contoh : 𝜃(𝑘33 ) adalah 2
Catatan :
Setiap graph planar G mempunyai ketebalan 1. Menentukan nilai 𝜃(𝐺) untuk
sembarang graph G, sampai dewasa ini belum ada formula eksak untuk 𝜃(𝐺), kecuali
mungkin untuk graph-graph G tertentu. Tetapi, dengan menggunakan teorema sebelumnya,
dengan mudah dapat ditentukan batas bawah dari 𝜃(𝐺), untuk sembarang graph sederhana G.
Tteorema 4.4.1 : jika G sederhana dengan |𝑉(𝐺)| ≠ 2, maka :
|𝐸(𝐺)|
𝜃(𝐺) ≥ [ ]
3|𝑉(𝐺) − 6|
Bukti
Untuk |𝑉(𝐺)| = 1 diperoleh |𝐸(𝐺)| = 0 dan 𝜃(𝐺) = 1 sehingga :
|𝐸(𝐺)|
𝜃(𝐺) ≥ [ ]
3|𝑉(𝐺) − 6|
Untuk |𝑉(𝐺)| ≥ 3.
Karena setiap subgraph dari G mempunyai paling banyak 3|𝑉(𝐺)| − 6 sisi (teorema
4.3.2), sedangkan banyaknay sisi G adalah |𝐸(𝐺)|, maka banyaknya graph bagian
planar (subgraph planar) dari G yang gabungannya sama dengan G, paling sedikit
|𝐸(𝐺)|
[3|𝑉(𝐺)−6|]
|𝐸(𝐺)|
Karena 𝜃(𝐺) bilanagn bulat, maka 𝜃(𝐺) ≥ [3|𝑉(𝐺)−6|] Terbukti.
Catatan :
1
1. Untuk graph komplit 𝑘𝑛 dengan n titik, 𝑛 ≠ 2 mempunyai banyak sisi 2 𝑛 (𝑛 − 1),
diperoleh :
𝑛(𝑛 − 1) 𝑛(𝑛 − 1)
+ 3(𝑛 − 2) − 1
𝜃(𝑘𝑛 ) = [ 2 ]=[ 2 ]
3𝑛 − 6 3(𝑛 − 2)
(𝑛 + 7)(𝑛 − 2)
=[ ]
6(𝑛 − 2)
𝑛+7
=[ ]
6
2. Untuk 𝑛 ≠ 4, oleh Beineke ditunjukkan bahwa ketebalan dari graph komplit
sebagai berikut :
𝑛+7
𝜃(𝑘𝑛 ) = ⌊ ⌋
6
3. Untuk graph sederhana G yang tidak memuat sikel dengan panajng 3, memenuhi
hubungan berikut :
|𝐸(𝐺)| ≤ 2|𝑉(𝐺)| − 4, sehingga graph bipartisi komplit 𝐾𝑚,𝑛 memenuhi
hubungan berikut :
𝑚𝑛
𝜃(𝑘𝑚,𝑛 ) = ⌊ ⌋
2(𝑚 + 𝑛 − 2)
Graph Polyhedral
Defenisi 4.6.1 :
Bangun ruang dimensi 3 yang dibatasi oleh permukaan-permukaan yang berupa
bidang datar polygonal (bidang datar segi-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.
Definisi 4.6.3 :
Polyhedron konveks yang setiap permukaannya berupa bidang-bidang datar polygonal
beraturan yang kongruen disebut polyhedron beraturan.
Titik-titik dan sisi-sisi dari sebuah polyhedron (skeleton) membentuk sebuah graph
sederhana di ruang 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.
Contoh :
Polyhedron Kubus Graph Polyhedral Kubus
Berikut akan diperlihatkan ada 5 macam polyhedral beraturan.
Misalkan G adalah graph bidang (planar). Derajat dari setiap titik G adalah 𝑘 ≥ 3 dan
derajat dari setiap muka G adalah 𝑚 ≥ 3. Menurut lemma jabat tangan, diperoleh :
∑ 𝑑(𝑣) = 2|𝐸(𝐺)| 𝑎𝑡𝑎𝑢
𝑣∈𝑉(𝐺)
1
|𝐸(𝐺)| = ∑ 𝑑(𝑣)
2
𝑣∈𝑉(𝐺)
1
= ∑ 𝑑(𝑣)
2
𝑣∈𝑉(𝐺)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)| … (1)
2
Karena setiap sisi membatasi tepat dua muka, maka :
∑ 𝑑(𝑓) = 2|𝐸(𝐺)| … (2)
𝑓∈𝐹(𝐺)
1
Karena 𝑑(𝑓) = 𝑚, ∀ 𝑓 ∈ 𝐹(𝐺)𝑑𝑎𝑛 |𝐸(𝐺)| = 2 𝑘|𝑉(𝐺)| maka diperoleh :
∑ 𝑑(𝑓) = 2|𝐸(𝐺)|
𝑓∈𝐹(𝐺)
1
∑ 𝑚 = 2 𝑘|𝑉(𝐺)|
2
𝑓∈𝐹(𝐺)
𝑚|𝐹(𝐺)| = 𝑘|𝑉(𝐺)|
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| = … (3)
𝑚
Menurut teorema Euler :
|𝑉(𝐺)| − |𝐸(𝐺)| + |𝐹(𝐺)| = … (4)
1 𝑘|𝑉(𝐺)|
|𝑉(𝐺)| − 𝑘|𝑉(𝐺)| + =2
2 𝑚
2𝑚|𝑉(𝐺)| − 𝑘𝑚|𝑉(𝐺)| + 2𝑘|𝑉(𝐺)|
=2
2𝑚
|𝑉(𝐺)|{(2𝑚 − 𝑘𝑚 + 2𝑘)} = 4𝑚
4𝑚
|𝑉(𝐺)| = … (5)
2𝑚 − 𝑘𝑚 + 2𝑘
Karena |𝑉(𝐺)| > 0 𝑑𝑎𝑛 4𝑚 > 0, maka :
Persamaan (5) menjadi :
2𝑚 − 𝑘𝑚 + 2𝑘 > 0
(𝑘 − 2)(𝑚 − 2) < 4 … (6)
Karena k dan m bilangan bulat dengan 𝑘 ≥ 3 𝑑𝑎𝑛 𝑚 ≥ 3, maka kemungkinan semua
nilai-nilai k dan m yang memenuhi (6) adalah :
𝑘 = 3 𝑑𝑎𝑛 𝑚 = 3
𝑘 = 3 𝑑𝑎𝑛 𝑚 = 4
𝑘 = 3 𝑑𝑎𝑛 𝑚 = 5 𝑎𝑡𝑎𝑢
𝑘 = 4 𝑑𝑎𝑛 𝑚 = 3 𝑎𝑡𝑎𝑢
𝑘 = 5 𝑑𝑎𝑛 𝑚 = 3
Karena hanya ada 5 kemungkinan nilai-nilai k dan m, maka terbukti hanya ada 5 graph yang
polyhedral beraturan
1) Untuk 𝑘 = 3 𝑑𝑎𝑛 𝑚 = 3diperoleh :
4𝑚 4.3
|𝑉(𝐺)| = = =4
2𝑚 − 𝑘𝑚 + 2𝑘 2(3) − 3(3) + 2(3)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 3(4)
2
= 6 𝑑𝑎𝑛
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
3.4
=
3
=4
Sehingga diperoleh polyhedral beraturan yang disebut Tetrahedron.
Tetrahedron
2) Untuk 𝑘 = 3 𝑑𝑎𝑛 𝑚 = 4 , diperoleh :
4𝑚 4.4
|𝑉(𝐺)| = = =4
2𝑚 − 𝑘𝑚 + 2𝑘 2(4) − 3(4) + 2(3)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 3(8)
2
= 12 𝑑𝑎𝑛
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
3.8
=
4
=6
Sehingga diperoleh polyhedron beraturan disebut kubus.
Kubus
3) Untuk 𝑘 = 3 𝑑𝑎𝑛 𝑚 = 5 , diperoleh :
4𝑚 4.4
|𝑉(𝐺)| = = = 20
2𝑚 − 𝑘𝑚 + 2𝑘 2(5) − 3(5) + 2(3)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 3(20)
2
= 30 𝑑𝑎𝑛
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
3.20
=
5
= 12
Sehingga diperoleh polyhedron beraturan yang disebut dodecahedron.
Dodecahedron
4) Untuk 𝑘 = 4 𝑑𝑎𝑛 𝑚 = 3 , diperoleh :
4𝑚 4.3
|𝑉(𝐺)| = = =6
2𝑚 − 𝑘𝑚 + 2𝑘 2(3) − 4(3) + 2(4)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 4(6)
2
= 12 𝑑𝑎𝑛
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
4.6
=
3
=8
Sehingga diperoleh polyhedron beraturan yang disebut octahedron.
Oktahedron
5) Untuk 𝑘 = 5 𝑑𝑎𝑛 𝑚 = 3 , diperoleh :
4𝑚 4.3
|𝑉(𝐺)| = = = 12
2𝑚 − 𝑘𝑚 + 2𝑘 2(5) − 5(3) + 2(5)
1
|𝐸(𝐺)| = 𝑘|𝑉(𝐺)|
2
1
= 5(12)
2
= 30 𝑑𝑎𝑛
𝑘|𝑉(𝐺)|
|𝐹(𝐺)| =
𝑚
5.12
=
3
= 20
Sehingga diperoleh polyhedron beraturan yang disebut isocahedron.
Isocahedron