skripsi graph cantik imam rofiki 043214013
DESCRIPTION
Graph merupakan ilmu matematika yang banyak sekali aplikasinya dalam kehidupan sehari-hari. Misalnya: untuk menentukan lintasan terpendek, pengiriman surat, transportasi, dan sebagainya.TRANSCRIPT
GRAPH CANTIK
SKRIPSI
Oleh:
IMAM ROFIKI
043214013
UNIVERSITAS NEGERI SURABAYA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
JURUSAN MATEMATIKA
2008
GRAPH CANTIK
SKRIPSI
Diajukan Untuk Memenuhi Persyaratan
Memperoleh Gelar Sarjana Sains
Oleh:
IMAM ROFIKI
043214013
UNIVERSITAS NEGERI SURABAYA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
JURUSAN MATEMATIKA
2008
ii
GRAPH CANTIK
Telah layak untuk diujikan sebagai
persyaratan mendapatkan Gelar Sarjana Sains
IMAM ROFIKI
043214013
PEMBIMBING TANDA TANGAN
Prof. I Ketut Budayasa, Ph.D. ________________
NIP. 132085319 Tanggal 20 Juni 2008
iii
GRAPH CANTIK
SKRIPSI
Telah diuji
Pada tanggal: 30 Juni 2008
PENGUJI TANDA TANGAN
1. Prof. I Ketut Budayasa, Ph.D. ________________
NIP. 132085319
2. Dr. Agung Lukito, M.S. ________________
NIP. 131948773
3. Budi Rahadjeng, S.Si., M.Si. ________________
NIP. 132163907
Mengetahui:
Dekan FMIPA
Universitas Negeri Surabaya
Prof. Dr. dr. Tjandrakirana, M.S., Sp.And.
NIP. 130368622
iv
KATA PENGANTAR
Segala puji syukur penulis panjatkan kehadirat Allah SWT atas limpahan
rahmat, hidayah, dan anugerah-Nya sehingga penulis dapat menyelesaikan skripsi
yang berjudul “GRAPH CANTIK” dengan lancar.
Penyusunan skripsi ini bertujuan untuk memenuhi salah satu persyaratan
memperoleh gelar sarjana sains di bidang matematika murni pada Fakultas
Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Surabaya.
Keberhasilan Penulis dalam menyusun skripsi ini tidak lepas dari
bimbingan dan bantuan dari berbagai pihak. Untuk itu penulis menyampaikan
terima kasih yang sebesar-besarnya kepada:
1. Ibu Prof. Dr. dr. Tjandrakirana, M.S., Sp.And. selaku Dekan FMIPA Unesa.
2. Bapak Dr. Tatag Yuli Eko Siswono, M.Pd., selaku Ketua Jurusan Matematika
Unesa.
3. Bapak Dr. Abadi, M.Sc., selaku Dosen Penasehat Akademik.
4. Bapak Prof. I Ketut Budayasa, Ph.D., selaku Dosen Pembimbing skripsi yang
telah dengan sabar memberikan bimbingan, motivasi dan nasehat sehingga
skripsi ini dapat terselesaikan dengan lancar.
5. Semua bapak dan ibu dosen jurusan Matematika yang telah memberikan
ilmunya kepada penulis.
6. Ayah, ibu serta adikku “Fendi” dan “Dina” tersayang, yang tak henti-hentinya
memberikan nasehat, doa, dan kasih sayang.
v
7. Sobat-sobatku: (Argo, Chubeb, Chocky, Fahmi) dan rekan bimbinganku
Marta, Salisa, Titin canda tawa kalian akan selalu penulis kenang.
8. Adik-adikku di Himatrika (Dani, Fibriana, Fitri, Hadi, Ilmi, Saiful, Umu, dan
Yulianti), kalian telah menjadi teman curahan hatiku.
9. Teman-teman seperjuanganku khususnya angkatan 2004B.
10. Dan semua pihak yang telah membantu terselesainya skripsi ini.
Penulis menyadari masih banyak kekurangan dan kelemahan pada skripsi
ini, untuk itu penulis mengharapkan kritik dan saran yang bersifat membangun
demi kesempurnaan skripsi ini. Akhirnya penulis berharap, semoga skripsi ini
bermanfaat bagi semua pihak.
Surabaya, 20 Juni 2008
Penulis
vi
GRAPH CANTIK
Imam Rofiki
ABSTRAK
Semua graph yang dibicarakan dalam skripsi ini adalah graph sederhana.
Graph cantik didefinisikan sebagai graph yang memuat sebuah sikel dengan
panjang 0 modulo 3. Sedangkan graph yang tidak memuat sebuah sikel dengan
panjang 0 modulo 3 disebut graph tak cantik. Dalam skripsi ini, kita tunjukkan
bahwa setiap subdivisi dari graph kubik terhubung-3 dengan n ≥ 10 titik
merupakan graph cantik. Ditunjukkan juga bahwa setiap graph kubik merupakan
graph cantik. Akhirnya, ditunjukkan bahwa setiap subdivisi dari graph komplit
dengan 5 titik merupakan graph cantik.
Kata kunci: Graph cantik, Subdivisi.
vii
GOOD GRAPH
Imam Rofiki
ABSTRACT
All graphs considered in this report are simple graphs. Good graph is
defined as a graph which contains a cycle of length 0 modulo 3. While graph
which does not contains a cycle of length 0 modulo 3 is called bad graph. In this
report, we show that every subdivisions of 3-connected cubic graph with n ≥ 10
vertices is a good graph. It is also shown that every cubic graph is a good graph.
Finally, it is shown that every subdivisions of complete graph on five vertices is a
good graph.
Key words: Good graph, Subdivisions.
viii
DAFTAR SIMBOL
Simbol Arti
V(G) Himpunan titik dari graph G
)(GV Banyaknya titik dari graph G
E(G) Himpunan sisi dari graph G
)(GE Banyaknya sisi dari graph G
dG(v) atau d(v) Derajat titik v di G
δ (G) Derajat minimum dari graph G
∆ (G) Derajat maksimum dari graph G
H ⊆ G H subgraph dari G
G[V] Graph bagian dari G yang dibangun oleh V
Ck Sikel dengan panjang k
Kn Graph komplit dengan n titik
Z+ Himpunan bilangan bulat positif
dG(u,v) atau d(u,v) Jarak dari titik u ke titik v
NG(v) atau N(v) Persekitaran titik v pada graph G
H ∩ G H irisan G
H ∪ G H gabungan G
G – e Penghapusan sisi e dari G
G.e Pengkonstraksian sisi e dari G
)(Gκ Konektivitas titik G
)(' Gκ Konektivitas sisi G
∧
G Pasangan G
ix
DAFTAR ISI
HALAMAN JUDUL..................................................................................... i
HALAMAN PERSETUJUAN ...................................................................... ii
HALAMAN PENGESAHAN ....................................................................... iii
KATA PENGANTAR................................................................................... iv
ABSTRAK.................................................................................................... vi
ABSTRACT ................................................................................................. vii
DAFTAR SIMBOL....................................................................................... viii
DAFTAR ISI ................................................................................................ ix
BAB I PENDAHULUAN .......................................................................... 1
BAB II KAJIAN PUSTAKA ...................................................................... 3
BAB III PEMBAHASAN............................................................................. 18
BAB IV PENUTUP...................................................................................... 44
DAFTAR PUSTAKA ................................................................................... 45
1
BAB I
PENDAHULUAN
Banyaknya permasalahan dalam kehidupan sehari-hari mendorong
manusia untuk mencari solusi yang secara tidak langsung permasalahan tersebut
mendorong berkembangnya ilmu pengetahuan dan teknologi. Matematika adalah
salah satu ilmu yang banyak memberikan alternatif dalam menyelesaikan
permasalahan di segala bidang. Salah satu cabang ilmu matematika yang dapat
menyelesaikan suatu permasalahan adalah teori graph.
Teori graph mengalami perkembangan yang sangat pesat karena
aplikasinya yang sangat luas dalam kehidupan sehari-hari. Misalnya dalam
pencarian lintasan terpendek, permasalahan pengiriman surat, transportasi,
komunikasi, perlokasian, desain komputer dan sebagainya. Sebuah graph G berisi
dua himpunan yaitu himpunan berhingga tak kosong V(G) yang elemen-
elemennya disebut titik dan himpunan berhingga (mungkin kosong) E(G) yang
elemen-elemennya disebut sisi sedemikian hingga setiap elemen e dalam E(G)
merupakan pasangan tak berurutan dari titik-titik di V(G). Karena struktur graph
yang sangat sederhana, maka hal inilah yang mengakibatkan banyak
permasalahan nyata yang dapat dimodelkan dalam bentuk graph. Misalnya titik
menyatakan stasiun maka sisi menyatakan rel yang menghubungkan antar stasiun,
jika titik menyatakan orang maka sisi menyatakan hubungan yang ada diantara
orang tersebut, dan masih banyak lagi pemodelan yang lainnya.
1
2
Dalam skripsi ini tidak dimaksudkan untuk membahas aplikasi dari teori
graph tetapi skripsi ini membahas suatu materi atau teoritis dalam teori graph
yaitu graph cantik. Graph yang memuat sebuah sikel dengan panjang 0 modulo 3
disebut graph cantik. Sedangkan graph yang tidak memuat sebuah sikel dengan
panjang 0 modulo 3 disebut graph tak cantik.
Tujuan dari penulisan skripsi ini adalah untuk membahas kelas-kelas
graph cantik.
Metodologi yang penulis gunakan adalah metodologi studi literatur.
Secara garis besar sistematika penulisan skripsi ini dibagi dalam 4 BAB, yaitu
BAB I tentang pendahuluan yang berisi tujuan dan garis besar isi skripsi, BAB II
tentang kajian pustaka yang berisi beberapa definisi dan teorema yang akan
digunakan dalam pembahasan, BAB III membahas tentang kelas-kelas graph
cantik, dan BAB IV berisi tentang simpulan.
3
BAB II
KAJIAN PUSTAKA
Dalam bab ini akan diuraikan beberapa definisi dan teorema yang disertai
dengan contoh-contoh yang digunakan dalam Bab III Pembahasan. Definisi dan
teorema yang digunakan dalam skripsi ini mengacu pada Budayasa [2] dan
Chartrand [4].
Definisi 2.1:
Sebuah graph G berisikan dua himpunan yaitu himpunan berhingga tak
kosong V(G) dari obyek-obyek yang disebut titik dan himpunan berhingga
(mungkin kosong) E(G) yang elemen-elemennya disebut sisi sedemikian hingga
setiap elemen e dalam E(G) merupakan pasangan tak berurutan dari titik-titik di
V(G). Himpunan V(G) disebut himpunan titik G dan himpunan E(G) disebut
himpunan sisi G. Misalkan u dan v adalah dua titik di G dan e = {u, v} (sering
ditulis e = uv) adalah sebuah sisi di G. Maka titik u dan titik v disebut
berhubungan langsung (adjacent) di G atau sisi e terkait (incident) dengan titik u
dan juga titik v. Jika G tidak memiliki sisi, maka G disebut graph kosong.
Sebuah graph G dapat direpresentasikan dalam bentuk diagram (gambar),
dimana setiap titik di G digambarkan dengan sebuah noktah dan setiap sisi yang
menghubungkan dua titik di G digambarkan dengan sebuah kurva sederhana
(ruas garis) dengan titik-titik akhir di kedua titik tersebut.
3
4
Contoh 2.1:
Perhatikan Gambar 2.1. G1 adalah graph dengan V(G1) = {v1, v2, v3, v4,
v5} dan E(G1) = {e1, e2,, e3, e4, e5, e6, e7} dengan e1 = v1v2, e2 = v1v3, e3 = v1v4, e4 =
v2v4, e5 = v3v4, e6 = v4v5 dan e7 = v3v5. Titik v1 dan v2 berhubungan langsung, sisi
e1 terkait dengan titik v1 dan v2. Karena E(G2) = φ , maka G2 adalah graph kosong.
Definisi 2.2:
Sebuah sisi graph G yang menghubungan sebuah titik dengan dirinya
sendiri disebut gelung (loop). Jika terdapat lebih dari satu sisi yang
menghubungkan dua titik u dan v di G, maka sisi-sisi tersebut disebut sisi
rangkap. Sebuah graph yang tidak memiliki gelung (loop) dan tidak memiliki sisi
rangkap disebut graph sederhana.
Contoh 2.2:
Gambar 2.1
v3
v1 v2
G2
v1
v2 v4
v5 v3
e1
e2
e3
e4
e5 e6
G1
e7
G1
v2
v1
v3
e5
e2 e1
e3
e4
Gambar 2.2
G2
v2
v5 v3
v4
v1
e1
e2
e3
e4 e5
5
Perhatikan Gambar 2.2. G1 bukan graph sederhana karena memiliki gelung
yaitu sisi e5 dan memiliki sisi rangkap yaitu e1 dan e2. G2 merupakan graph
sederhana.
Definisi 2.3:
Sebuah graph komplit adalah graph sederhana sedemikian hingga setiap
dua titik yang berbeda dihubungkan oleh sebuah sisi. Graph komplit dengan n
titik dilambangkan dengan Kn, dimana n adalah bilangan asli.
Contoh 2.3:
Gambar 2.3: Graph komplit dengan 5 titik (K5)
Definisi 2.4:
Misalkan G sebuah graph dan v sebuah titik G. Derajat titik v,
dilambangkan dengan dG(v) atau d(v), adalah banyaknya sisi G yang terkait
dengan titik v (dengan catatan setiap gelung dihitung dua kali).
Derajat minimum dan maksimum dari graph G berturut-turut
dilambangkan dengan δ (G) dan ∆(G), didefinisikan sebagai berikut:
δ (G) = minimum {d(v) | v ∈V(G)}
∆(G) = maksimum {d(v) | v ∈V(G)}
v4
v5
v2 v1
v3
6
Contoh 2.4:
Gambar 2.4
Perhatikan graph G pada Gambar 2.4. Untuk setiap titik v di G derajat
titiknya adalah d(v1) = 3, d(v2) = 3, dan d(v3) = 6. Sehingga δ (G) = 3 dan ∆(G) =
6.
Definisi 2.5:
Jika setiap titik di G berderajat k, maka G disebut graph beraturan-k.
Graph komplit Kn adalah graph beraturan-(n-1). Karena setiap titik pada graph
komplit berderajat (n-1).
Contoh 2.5:
Gambar 2.5: Graph beraturan-3
v1
v3
v4
v2
v3
v1 v2
G
7
Definisi 2.6:
Misalkan G adalah sebuah graph. Sebuah jalan (walk) di G adalah sebuah
barisan berhingga (tak kosong) W = {v0, e1, v1, e2, v2, … ,vi-1, ei, vi, … , vk-1, ek, vk}
yang suku-sukunya bergantian titik dan sisi, sedemikian hingga vi-1 dan vi adalah
titik-titik akhir dari sisi ei, untuk ki ≤≤1 . Kita katakan W adalah sebuah jalan
dari titik v0 ke titik vk, atau jalan-(v0,vk). Titik v0 dan titik vk berturut-turut disebut
titik awal dan titik akhir W. Sedangkan titik-titik v1, v2, . . . , vk-1 disebut titik-titik
internal W; dan k disebut panjang jalan W. Perhatikan bahwa panjang jalan W
adalah banyaknya sisi dalam W. Sebuah titik G, mungkin saja muncul lebih dari
satu kali dalam jalan W, begitu juga dengan sebuah sisi G, boleh muncul lebih
dari satu kali pada jalan W. Jika titik awal dan titik akhir sama maka W disebut
jalan tertutup, sebaliknya jika titik awal dan titik akhir berbeda maka W disebut
jalan terbuka. Jika semua sisi dalam jalan W berbeda, maka W disebut jejak
(trail). Jika semua titik dan semua sisi dalam jalan W berbeda, maka W disebut
lintasan (path). Lintasan dari titik u ke titik v dapat ditulis sebagai lintasan-(u, v).
Jejak tertutup disebut sirkit. Sikel (cycle) adalah sebuah jejak tertutup yang titik
awal dan semua titik internalnya berbeda. Banyaknya sisi dalam suatu sikel
disebut panjang dari sikel tersebut. Sikel dengan panjang k (memuat sebanyak k
sisi) disebut k-sikel, disimbolkan dengan Ck.
Contoh 2.6:
Gambar 2.6
v0
v1 v2
v4 v3
e1
e4
e3
e2
e6 e8
e5
e7
G
8
Perhatikan graph G pada Gambar 2.6.
1) Barisan (v0, e1, v1, e2, v2, e6, v3, e7, v4, e7, v3) adalah sebuah jalan di G dengan
panjang 5.
2) Barisan (v0, e1, v1, e2, v2, e6, v3, e7, v4, e8, v2) adalah sebuah jejak buka di G
dengan panjang 5.
3) Barisan (v0, e1, v1, e2, v2, e8, v4, e7, v3) adalah sebuah lintasan di G dengan
panjang 4.
4) Barisan (v0, e1, v1, e5, v3, e6, v2, e8, v4, e7, v3, e4, v0) adalah sebuah sirkit di G
dengan panjang 6.
5) Barisan (v0, e1, v1, e2, v2, e6, v3, e4, v0) adalah sebuah sikel di G dengan
panjang 4.
Catatan:
Jika G graph sederhana, label sisi biasanya tidak ditulis dalam barisan.
Misalnya lintasan (v0, e4, v3, e6, v2, e8, v4) pada graph G di Gambar 2.6 biasanya
ditulis lintasan (v0, v3, v2, v4).
Definisi 2.7:
Sebuah graph H disebut graph bagian (subgraph) dari graph G, ditulis
GH ⊆ , jika )()( GVHV ⊆ dan )()( GEHE ⊆ . Jika GH ⊆ dan )()( GVHV = ,
maka H disebut graph bagian rentang (spanning subgraph) dari G. Misalkan
)()( GVHV ⊆ . Graph bagian dari G yang dibangun (diinduksi) oleh V,
dilambangkan dengan G[V], adalah sebuah graph bagian dari G yang himpunan
titiknya adalah V dan himpunan sisinya beranggotakan semua sisi G yang
mempunyai titik-titik akhir di V.
9
Contoh 2.7:
Gambar 2.7
Perhatikan Gambar 2.7. H1 adalah graph bagian G. H2 adalah graph bagian
rentang dari G. H3 adalah graph bagian G yang dibangun oleh V = {v1, v3, v4}.
Definisi 2.8:
Sebuah graph G dikatakan terhubung (connected) jika untuk setiap dua
titik u dan v yang berbeda di G terdapat sebuah lintasan yang menghubungkan
kedua titik tersebut. Sebaliknya, jika hal tersebut tidak dipenuhi maka graph G
disebut tak terhubung (disconnected).
Sebuah komponen graph G adalah sebuah graph bagian terhubung
maksimal (titik dan sisi) dari G. Graph H dikatakan graph bagian terhubung
maksimal dari graph G, jika tidak ada graph bagian lain dari G yang terhubung
dan memuat H. Jadi setiap graph terhubung memiliki tepat satu komponen
sedangkan graph tak terhubung memiliki paling sedikit dua komponen.
v3
v4
v2
v1
G
v3
v1
v2
H1
v4
v3 v2
v1
H2
v3
v4 v1
H3
10
Contoh 2.8:
Perhatikan Gambar 2.8. G adalah graph terhubung dan H adalah graph tak
terhubung dengan tiga komponen yaitu G1, G2, dan G3.
Catatan:
Sebuah komponen dari graph G yang hanya berupa satu titik disebut
komponen trivial. Sedangkan komponen dari graph G yang memiliki minimal satu
sisi disebut komponen nontrivial. Perhatikan graph H pada Gambar 2.8,
komponen trivial dari graph H adalah G3 dan komponen nontrivial dari graph H
adalah G1 dan G2.
Definisi 2.9:
Misalkan G sebuah graph terhubung dan V1⊂V(G). Himpunan V1 disebut
himpunan titik pemutus G, jika G–V1 graph tak terhubung atau graph trivial
(graph dengan hanya satu titik). Minimum |V1| sedemikian hingga V1 himpunan
titik pemutus G disebut konektivitas titik G, disimbolkan dengan ).(Gκ Dengan
kata lain, konektivitas titik graph G atau )(Gκ adalah minimum banyaknya titik
G yang harus dihapus agar graph yang baru tak terhubung atau graph trivial.
G
v3
v1
v2 v4
v5
v2 v1
v3
G1
v1
G3
H
v2 v1
v3
G2
Gambar 2.8
11
Definisi 2.10: (Keterhubungan Titik)
Graph G dikatakan graph terhubung-k, jika penghapusan sebanyak kurang
dari k titik G, menghasilkan graph baru yang tetap terhubung. Kiranya jelas
bahwa graph G terhubung-k jika dan hanya jika .)( kG ≥κ
Catatan :
Jika G dikatakan graph terhubung-3, maka G juga merupakan graph
terhubung-2 dan graph terhubung-1, tetapi sebaliknya tidak berlaku.
Contoh 2.9:
Gambar 2.9
Perhatikan graph pada Gambar 2.9. G1 dikatakan graph terhubung-3
karena banyaknya titik yang dihapus itu kurang dari tiga sedemikian hingga graph
tersebut tetap terhubung. Sedangkan G2 dikatakan graph terhubung-2 karena
banyaknya titik yang dihapus itu kurang dari dua sedemikian hingga graph
tersebut tetap terhubung.
Graph terhubung-3
G1
Graph terhubung-2
G2
12
Definisi 2.11:
Misalkan G sebuah graph terhubung dan E1⊂E(G). Himpunan E1 disebut
himpunan sisi pemutus G, jika G–E1 graph tak terhubung. Minimum |E1|
sedemikian hingga E1 himpunan sisi pemutus G disebut konektivitas sisi G,
disimbolkan dengan )(' Gκ . Dengan kata lain, konektivitas sisi suatu graph adalah
minimum banyaknya sisi graph tersebut yang harus dihapus agar dihasilkan graph
tak terhubung.
Contoh 2.10:
Gambar 2.10: Graph G dengan )(Gκ = )(' Gκ = 3
Perhatikan graph G pada Gambar 2.10. Konektivitas titik dan konektivitas
sisi dari graph tersebut bernilai sama yaitu 3. Dengan kata lain, )(Gκ = )(' Gκ = 3.
Dalam hal ini, himpunan {v2, v3, v4} adalah sebuah himpunan titik pemutus
minimum G, sedangkan {e4, e5, e6} adalah sebuah himpunan sisi pemutus
minimum G.
G v1
v4
v3
v2 v5
v6
v7
v8
e4
e2
e1 e7
e5 e8
e3
e6
e9
13
Definisi 2.12:
Graph G disebut graph kubik jika setiap titik di G berderajat 3.
Contoh 2.11:
Perhatikan graph G pada Gambar 2.11. G adalah graph kubik karena setiap
titik di G berderajat 3.
Teorema 2.1:
Jika G graph kubik, maka ).(')( GG κκ =
Bukti: (Lihat [4], hal. 119)
Definisi 2.13:
Misalkan u dan v dua titik di graph G. Jarak dari titik u ke titik v,
dinotasikan dengan dG(u, v) atau d(u, v), didefinisikan sebagai panjang lintasan
terpendek antara titik u dan titik v di G.
Contoh 2.12:
v1 v2
v3
v4
G
Gambar 2.11
u
q
s
r
p
t
G
e5
e4
e3
e2
e1
e6
Gambar 2.12: d(u, t) = 3
14
Perhatikan graph G pada Gambar 2.12. Lintasan (u, p, q, t) adalah lintasan
terpendek di graph G dengan panjang 3. Sehingga d(u, t) = 3.
Definisi 2.14:
Misalkan G sebuah graph. Himpunan lintasan di G disebut disjoin-internal
jika titik-titik internalnya tidak ada yang bersekutu atau sama.
Teorema 2.2:
Misalkan G sebuah graph dengan paling sedikit 3 titik. Graph G
terhubung-2 jika dan hanya jika setiap dua titik G dihubungkan oleh paling sedikit
dua lintasan disjoin-internal.
Bukti:
Jika setiap dua titik G dihubungkan oleh paling sedikit dua lintasan
disjoin-internal, maka jelas G terhubung dan tidak memiliki satu titik pemutus.
Jadi G terhubung-2.
Konversinya, dibuktikan dengan induksi pada jarak antara dua titik pada
graph. Misalkan G graph terhubung-2. Pertama-tama misalkan d(u, v) = 1. Karena
G terhubung-2, maka sisi uv bukan sisi pemutus G. Sehingga sisi uv terletak pada
suatu sikel G. Ini berarti u dan v dihubungkan oleh dua lintasan disjoin-internal
pada graph G. Sekarang, misalkan d(u, v) = k ≥ 2. Asumsikan pernyataan dalam
teorema benar untuk setiap dua titik pada G yang berjarak kurang dari k. Pikirkan
sebuah lintasan-(u, v) dengan panjang k di graph G dan misalkan w titik persis
sebelum v pada lintasan tersebut. Karena d(u, w) = k-1, berdasarkan asumsi, maka
terdapat dua lintasan-(u, w) disjoin-internal di graph G. Namakan lintasan tersebut
15
P dan Q. Karena G terhubung-2, maka graph G-w terhubung. Sehingga terdapat
lintasan-(u, v) pada graph G-w dan namakan lintasan ini dengan R. Misalkan x
adalah titik terakhir di R yang juga terletak di P∪Q. Tanpa menghilangkan
keumuman, misalkan titik x terletak di lintasan P (lihat Gambar 2.13).
Maka graph G memuat dua lintasan disjoin-internal, yaitu: lintasan pertama terdiri
dari bagian lintasan P dari titik u ke titik x, kemudian dilanjutkan dengan bagian
lintasan R dari titik x ke titik v; lintasan kedua terdiri dari lintasan Q dari titik u ke
titik w dan dilanjutkan lintasan (sisi) wv. Dengan demikian lengkaplah bukti
teorema.
Definisi 2.15:
Graph terhubung dan tidak memiliki sikel disebut pohon.
Contoh 2.13:
v2 v1
v4
v3
G
Gambar 2.14: Graph G sebuah pohon
Gambar 2.13
u
x
v w
P
Q
R
G
16
Definisi 2.16:
Sebuah blok dari graph G adalah graph bagian maksimal G yang tidak
memiliki titik pemutus.
Contoh 2.14:
Definisi 2.17:
Persekitaran titik v pada graph G, dinotasikan dengan NG(v) atau N(v)
didefinisikan sebagai NG(v) = { )(|)( GEuvGVu ∈∈ }.
Contoh 2.15:
Gambar 2.16: NG(v1) = {v2, v3, v4}
v1
v4
v3
v7
v5 v6
G
v2
G
K4 C2 C3
Gambar 2.15: Graph G dengan 3 blok yaitu C3, C2, dan K4
17
Definisi 2.18:
Misalkan G sebuah graph dan e = uv sebuah sisi di G. Pengkonstraksian
sisi e dari G adalah penghapusan sisi e dari G dan menyatukan titik u dan titik v.
Graph baru yang diperoleh dilambangkan dengan G.e. Misalnya, graph G dan
graph G.e dapat dilihat pada Gambar 2.17 berikut.
Contoh 2.16:
Gambar 2.17: Graph G dan graph G.e
Definisi 2.19:
Misalkan m bilangan bulat positif dengan 1>m untuk suatu a, b anggota
himpunan bilangan bulat. Dikatakan a kongruen dengan b modulo m dan biasa
ditulis ba ≡ (modulo m) jika m | (a – b) atau ekuivalen dengan kmba += untuk
sebarang k anggota himpunan bilangan bulat.
G
e
G.e
18
BAB III
PEMBAHASAN
Pada bab ini akan diawali dengan membahas definisi graph cantik dan
subdivisi dari sebuah graph terlebih dahulu yang kemudian dilanjutkan dengan
membahas kelas-kelas graph cantik. Selanjutnya semua graph yang dibicarakan
adalah graph yang tidak memiliki sisi rangkap dan tidak memiliki loop. Berikut
ini akan dibahas lebih lanjut mengenai graph cantik.
Definisi 3.1:
Graph yang memuat sebuah sikel dengan panjang 0 modulo 3 disebut
graph cantik (good). Sedangkan graph yang tidak memuat sebuah sikel dengan
panjang 0 modulo 3 disebut graph tak cantik (bad).
Contoh 3.1:
Misalnya graph G1 pada Gambar 3.1 merupakan graph cantik karena
memuat sikel dengan panjang 3 ≡ 0 (modulo 3) yaitu sikel (v1, v2, v3, v1).
Sedangkan graph G2 memuat sikel-sikel dengan panjang 5 dan 8, sehingga G2
merupakan graph tak cantik.
v5 v4
v1
v6 v3
v2
G1
v8
v7
v6 v5
v4
v3
v2 v1
G2
Gambar 3.1: G1 adalah graph cantik dan G2 adalah graph tak cantik
18
19
Berikut ini akan ditunjukkan bahwa setiap graph cantik, subgraphnya juga
cantik.
Teorema 3.1:
Graph G tak cantik jika dan hanya jika setiap subgraph G tak cantik.
Bukti:
Misalkan graph G tak cantik. Berdasarkan Definisi 3.1, maka graph G
tidak memuat sebuah sikel dengan panjang 0 modulo 3. Sehingga setiap subgraph
G tidak memuat sebuah sikel dengan panjang 0 modulo 3. Jadi setiap subgraph G
tak cantik.
Konversinya, misalkan setiap subgraph G tak cantik. Andaikan graph G
cantik. Berdasarkan Definisi 3.1, maka graph G memuat sebuah sikel dengan
panjang 0 modulo 3. Sehingga, ada subgraph G yang memuat sebuah sikel dengan
panjang 0 modulo 3 yang disebut subgraph G cantik. Kontradiksi bahwa setiap
subgraph G tak cantik. Dengan demikian bukti teorema lengkap.
Untuk selanjutnya akan dibahas graph subdivisi dari sebuah graph.
Definisi 3.2:
Misalkan G sebuah graph. Jika graph H dibentuk dari G dengan cara
menyisipkan beberapa (mungkin nol) titik pada beberapa sisi G, maka graph H
disebut graph subdivisi dari G.
Contoh 3.2:
Perhatikan Gambar 3.2 berikut. Graph H1 dan H2 masing-masing
merupakan graph subdivisi dari G. Perhatikan bahwa operasi penyisipan titik pada
beberapa sisi graph, dapat mengubah sifat "cantik" suatu graph. Artinya, jika G
20
graph cantik, maka subdivisi dari G mungkin tak cantik. Sebagai contoh G graph
cantik, tetapi H2 sebuah subdivisi dari G adalah tak cantik.
Perhatikan bahwa, jika pada beberapa sisi disisipkan cukup banyak titik,
maka jelas bahwa pada graph subdivisinya akan memiliki titik yang cukup
banyak. Sehingga kita akan mengalami kesulitan untuk menggambar graph
tersebut. Untuk mengatasi masalah ini dapat digunakan teknik pelabelan sisi yang
dijelaskan berikut ini.
Misalkan uve = sebuah sisi graph G. Jika pada sisi e disisipkan sebanyak
a buah titik yang berbeda, maka sisi e akan terpartisi menjadi 1+a sisi. Karena
dalam pembahasan skripsi ini kita tertarik pada bilangan 0 modulo 3 maka untuk
menggambar subdivisi dari G sebanyak a buah titik yang disisipkan pada sisi e
tidak perlu digambar, tetapi cukup dilabel dengan bilangan x dimana
xa ≡+1 (modulo3).
Misalnya dari Contoh 3.2 graph H1 dan H2 yang merupakan subdivisi dari
G dapat digambar dengan pelabelan berikut.
G H1 H2
Gambar 3.2: H1 dan H2 adalah graph-graph subdivisi dari G
21
Perhatikan bahwa, sebagai akibat dari definisi pelabelan tersebut, sangat
mungkin beberapa subdivisi dari graph G bisa direpresentasikan dengan pelabelan
yang sama. Misalnya graph H3 dan H4 pada gambar berikut merupakan subdivisi-
subdivisi dari graph G.
Jika graph H3 dan H4 direpresentasikan dengan teknik pelabelan sisi, maka
akan diperoleh representasi yang sama yaitu pelabelan H1.
1
1
0
1
2
H1
1
0
1
0
0
H2
Gambar 3.3: Pelabelan H1 dan H2
H3 H4
Gambar 3.4
1
1
0
1
2
H1
Gambar 3.5: Pelabelan H1
22
Definisi 3.3:
Misalkan H sebuah subdivisi dari graph G yang direpresentasikan dalam
bentuk pelabelan sisi. Jika setiap label sisi H dikalikan dengan 2 modulo 3, maka
akan diperoleh pelabelan baru yang disebut pasangan H yang selanjutnya
disimbolkan dengan .∧
H
Contoh 3.3:
Perhatikan graph H1 pada Gambar 3.6. Sisi ux berlabel 1 di H1, jika
dikalikan 2 maka labelnya menjadi 2 ≡ 2 (modulo 3), sehingga pada graph 1
∧
H
sisi ux berlabel 2. Sisi vw berlabel 2 di H1, jika dikalikan 2 maka labelnya
menjadi 14 ≡ (modulo 3), sehingga pada graph 1
∧
H sisi vw berlabel 1. Jika
dilakukan untuk semua sisi, maka akan diperoleh graph 1
∧
H seperti terlihat pada
Gambar 3.6.
Perhatikan bahwa, 1
∧
H merupakan sebuah subdivisi dari graph G pada
Gambar 3.2. Graph H1 maupun 1
∧
H adalah graph cantik. Ternyata ini berlaku
secara umum. Kita buktikan hal tersebut pada teorema berikut.
1
1
0
1
2
H1 u
v
x
w
2
2
0
2
1
1
∧
H u w
x
v
Gambar 3.6: 1
∧
H adalah pasangan H1
23
Teorema 3.2:
Graph G cantik jika dan hanya jika pasangan G cantik.
Bukti:
Jika G graph cantik, maka graph G memuat sebuah sikel C dengan panjang
0 modulo 3. Berarti panjang sikel C adalah 3k, untuk suatu k∈Z+. Graph
∧
G
diperoleh dengan mengalikan label setiap sisi di G dengan 2 modulo 3 sehingga
diperoleh pelabelan baru. Maka panjang sikel C pada graph ∧
G adalah 6k, untuk
suatu k∈Z+. Karena 6k ≡ 0 (modulo 3), maka
∧
G graph cantik.
Konversinya, misalkan graph G tak cantik. Maka graph G tidak memuat
sikel dengan panjang 0 modulo 3 atau panjang sikel bukan kelipatan 3. Dengan
demikian setiap sikel di G panjangnya p dengan:
p = 3m + 1, untuk suatu m∈Z+
atau
p = 3m + 2, untuk suatu m∈Z+.
(i) Untuk p = 3m + 1.
Panjang sikel ∧
G = 2 x (3m + 1)
= 6m + 2
= 2(3m) + 2 (bukan kelipatan 3).
(ii) Untuk p = 3m + 2.
Panjang sikel ∧
G = 2 x (3m + 2)
= 6m + 4
= 2(3m) + 4 (bukan kelipatan 3).
24
Dari (i) dan (ii), diperoleh ∧
G tidak memuat sikel dengan panjang 0 modulo 3.
Sehingga ∧
G graph tak cantik. Dengan demikian bukti teorema lengkap.
Perhatikan bahwa teorema di atas memberikan kita suatu cara untuk
mengkonstruksi sebuah graph cantik baru dari suatu graph cantik tertentu.
Selanjutnya akan ditunjukkan bahwa setiap subdivisi dari graph kubik
terhubung-3 dengan titik yang cukup banyak pasti merupakan graph cantik.
Namun tidak demikian halnya dengan subdivisi dari graph kubik terhubung-2.
Sebagai contoh berikut ini diberikan sebuah subdivisi dari graph kubik terhubung-
2 ternyata merupakan graph tak cantik.
Contoh 3.4:
Perhatikan bahwa, graph tersebut subdivisi dari graph kubik terhubung-2
dan memuat m jiplakan dari K4 - e, dimana m adalah bilangan bulat positif yang
bukan kelipatan 3. Perhatikan sikel C = (v11, v21, v31, v12, v22, v32, ... , v1m, v2m,
v3m, v11) pada G. Panjang sikel C adalah t, dengan
t = 2m + 3(m-1) + 3
G
v11
v21
v41
v31
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1 0
0
… v12
v22
v42
v32 v1m
v4m
v2m
v3m 0
Gambar 3.7: Subdivisi dari graph kubik terhubung-2 yang tak cantik
25
= 2m + 3m – 3 + 3
= 5m, untuk suatu m ∉3Z+.
Jadi panjang sikel C bukan kelipatan 3. Perhatikan setiap blok G memuat 3 sikel.
Misalkan pada blok ke-i, 1≤ i ≤ m, terdapat:
1) sikel (v1i, v2i, v3i, v4i, v1i) dengan panjang 4 ≡ 1 (modulo 3)
2) sikel (v1i, v2i, v4i, v1i) dengan panjang 2 ≡ 2 (modulo 3)
3) sikel (v2i, v3i, v4i, v2i) dengan panjang 2 ≡ 2 (modulo 3).
Sehingga graph G tak cantik.
Sebelum kita buktikan hasil utama, maka kita tinjau beberapa fakta
berikut.
Fakta 3.1:
Setiap graph kubik dengan n ≤ 14 titik merupakan graph cantik.
Berikut ini diberikan beberapa contoh graph kubik dengan n ≤ 14 titik
ternyata merupakan graph cantik.
Tabel 3.1: Graph kubik dengan n ≤ 14 titik
No Titik Graph Kubik
n = 4 1
26
n = 6 2
n = 8 3
n = 10 4
n = 12 5
27
Untuk lebih lengkapnya daftar semua graph kubik dengan n ≤ 14 titik
dapat dilihat pada Bussemaker [3].
Subdivisi graph kubik belum tentu merupakan graph cantik. Berikut
khusus untuk n ≤ 8 titik, diberikan daftar graph tak cantik yang merupakan
subdivisi dari graph kubik.
Fakta 3.2:
Daftar semua subdivisi graph kubik terhubung-3 dengan n ≤ 8 titik
merupakan graph tak cantik dapat dilihat pada Gambar 3.8 berikut.
0 1 0
1 1
2
1 0 1
1 1
0
1 0 1
1 1
2
2
1 1
1
0
1
2 2
1
2
2 0
2
0
1
1 1
1
n = 14 6
28
1
1 0
0
0
1
1 1
1
2
1 1
0
0
0
1 1
0
1
0 1
0
0
1
1 1
0
1
0
1 1 1 1
0
0
1 1
0
1 0 0 1
1
1
0 0
0
0
1 1
0
1
1
1
1
0
0
1
0
0
1 1
0 0
0
1
0
1
1
2
0
1
1 1
1 1
0
2
0
1
1
2
0
1
1 1
2
1
2
0
0
0
1
1
0
0
1 1
1
2
1
0
1
1
2
1
0
2
1 2
1
1
1
0
2
2
1
0
0
1
0
0 1
0
1
1
1
1
0
Gambar 3.8: Subdivisi graph kubik terhubung-3 dengan n ≤ 8 titik yang tak cantik
29
Berikut ini akan ditunjukkan bahwa setiap subdivisi graph kubik
terhubung-3 dengan 10 titik merupakan graph cantik.
Subdivisi dari graph kubik terhubung-3 dengan 10 titik, diperoleh dari
subdivisi graph kubik terhubung-3 dengan 8 titik yang tak cantik dengan
menambahkan dua titik yang disisipkan pada 2 sisi sebarang yang berbeda dan
menghubungkan dua titik itu dengan sebuah sisi baru. Pada Gambar 3.8 diberikan
daftar semua graph kubik terhubung-3 dengan 8 titik yang tak cantik. Padahal
penambahan dua titik pada dua sisi yang berbeda dengan menghubungkan kedua
titik tersebut dengan sebuah sisi baru, akan diperoleh graph terhubung-3 dengan
10 titik dan ternyata setiap graph yang diperoleh merupakan graph cantik. Seperti
diperlihatkan oleh beberapa contoh berikut (lihat Gambar 3.9). Untuk lebih
lengkapnya dapat dilihat pada Bussemaker [3].
v5
1
0
0
1 1
0 0
1
0
1
1
1
0
v1
v2
v3
v4
v6
v7
v8
v9
v10
0
1
1
0
0
1 1
0 0
1
0
1
0
1
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
1
v10
1
0
0
1 1
0 0
1
0
1
2
1
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
2
1
1
0
0
1 1
0 0
0
1
0
1
1
0
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
1
0
0
1 1
0 0
0
1
0
1
1
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
1
0
0
1 1
0 0
0
1
0
1
1
2
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v10
v10
30
0
1
2
2
0
0
1
1
1
1
2
2
0
0
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
2
2
0
2
1
1
0
1
2
2
0
0
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
2
2
0
1
1
1
2
1
2
2
0
0
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
0
1 2
0
1
1 1
2
1
2
0
0
0
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
1 2
0
1
1 1
2
1
2
0
0
0
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
0
1 2
0
1
1 1
2
1
2
0
0
0
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
0
1
1 1
1 1
2
0
1
0
1
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
0
v10
2
0
1
1 1
1 1
2
0
1
1
1
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
1
1
v10
2
0
1
1 1
1 1
2
0
1
1
1
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
2
2
2
0
1
1 1
1 1
0
2
0
1
1
1
1
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
0
1
1 1
1 1
0
2
0
2
2
2
1
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
0
1
1 1
1 1
0
2
0
1
0
2
1
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
31
0
2
1 0
1
0
0 1
0
1
1
1
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
0
1 0
1
0
0 1
0
1
1
1
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
1 0
1
0
0 1
0
1
1
1
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
0
0
1
1
0
1
0
1
1
2
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
0
0
1
0
0
1
2
1
1
2
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
0
0
1
1
0
1
1
1
1
2
1
0
0
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
1
1
0
0
2
2
0
1
1
0
2
2
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
1
1
0
0
2
2
1
1
1
1
2
2
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
1
1
0
2
2
2
0
1
1
1
2
2
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
2
0 1
0
0
1 1
1
2
1
0
1
1
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
0 1
0
0
1 1
1
2
1
0
1
1
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
2
2 1
0
0
1 1
1
2
1
0
1
1
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
32
Gambar 3.9: Subdivisi dari graph kubik terhubung-3 dengan10 titik
Dari uraian di atas, dapat disimpulkan fakta berikut.
Fakta 3.3:
Setiap subdivisi graph kubik terhubung-3 dengan 10 titik merupakan graph
cantik.
Berikut ini akan ditunjukkan bahwa jika G graph terhubung-3 dengan titik
yang cukup banyak, maka G memuat sisi e sedemikian hingga graph G.e adalah
graph terhubung-3 dan G - e merupakan subdivisi graph terhubung-3.
Lemma 3.1:
Misalkan G sebuah graph terhubung-3 dengan 5)( ≥GV . Maka G
memuat sisi e sedemikian hingga graph G.e merupakan graph terhubung-3 dan
eG − merupakan subdivisi dari graph terhubung-3.
0
0
1 1
0
2
1 2
1
1
1
0
2
2
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
1
0
2 1
0
2
1 2
1
1
1
0
2
2
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
2
0
2 1
0
2
1 2
1
1
1
0
2
2
1
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
1
1
0
0
0
1
2
2
1
1
1
1
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
1
1
0
0
0
1
0
2
1
1
1
1
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
0
1
1
1
0
2
0
1
2
2
1
1
1
1
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
33
Bukti:
Andaikan bahwa untuk setiap e di E(G), graph G.e tak terhubung-3.
Karena G.e tak terhubung-3, maka ada 2 titik di G.e, misalkan titik u dan titik v
sedemikian hingga G.e – {u,v} graph tak terhubung dan himpunan titik pemutus
tersebut pasti memuat sebuah titik di G.e yang diperoleh dengan mengkontraksi
sisi e = xy. Tanpa menghilangkan keumuman, misalkan titik uxy ='' maka {x, y,
v} adalah himpunan titik pemutus di G. Dengan kata lain G - {x, y, v} merupakan
graph tak terhubung. Misalkan H adalah sebuah komponen dari G - {x, y, v} yang
memiliki titik sebanyak mungkin dan 'H adalah sebuah komponen yang lain dari
G - {x, y, v} (lihat Gambar 3.10).
Karena G terhubung-3, maka {x, y, v} merupakan titik pemutus minimal di G.
Sehingga setiap titik tersebut memiliki persekitaran di H dan 'H . Misalkan a
sebuah titik persekitaran v di H. Misalkan b sebuah titik di G sedemikian hingga
{v, a, b} merupakan himpunan titik pemutus di G. Jelas bahwa graph bagian G
yang dibangun oleh },{)( yxHV ∪ atau [ ]},{)( yxHVG ∪ adalah graph
terhubung. Jika b adalah sebuah titik di [ ]},{)( yxHVG ∪ , maka
[ ]},{)( yxHVG ∪ - {b} adalah graph terhubung, sebab jika tidak, maka G - {v, b}
v
Gambar 3.10
x
y
G
34
tak terhubung. Hal ini kontradiksi dengan G terhubung-3. Oleh sebab itu
[ ]},{)( yxHVG ∪ - {b} adalah sebuah komponen dari G - {v, a, b} yang memiliki
titik melebihi titiknya H. Hal ini kontradiksi dengan H memiliki titik sebanyak
mungkin.
Misalkan sisi e menghubungkan titik s dan titik t di G. Karena G - e, maka
derajat titik s dan titik t di G - e paling sedikit 2. Jadi G - e merupakan subdivisi
dari graph terhubung-3. Dengan demikian lemma terbukti.
Berikut ini akan ditunjukkan hasil utama bahwa setiap subdivisi dari graph
kubik terhubung-3 dengan titik yang cukup banyak merupakan graph cantik.
Teorema 3.3:
Setiap subdivisi dari graph kubik G terhubung-3 dengan n ≥ 10 titik
merupakan graph cantik.
Bukti:
Kita buktikan dengan induksi pada n. Berdasarkan Fakta 3.2, G
merupakan graph cantik untuk n = 10. Asumsikan, pernyataan benar untuk graph
G < n titik. Artinya, setiap subdivisi dari graph kubik G terhubung-3 kurang dari n
titik, maka G merupakan graph cantik. Selanjutnya, akan ditunjukkan bahwa
pernyataan benar untuk graph G dengan n titik, n ≥ 12. Misalkan G merupakan
subdivisi dari graph terhubung-3 dengan n titik. Andaikan G graph tak cantik.
Berdasarkan Lemma 3.1, maka ada sisi e = uv di G sedemikian hingga G-e
merupakan subdivisi dari graph kubik terhubung-3. Misalkan sisi uv di G dan P
berkorespondensi dengan lintasan-(u, v) di G. Maka komponen nontrivial dari G-
35
E(P) merupakan subdivisi dari graph kubik terhubung-3 yang tak cantik dengan
paling banyak n – 2 ≥ 10 titik. Hal ini kontradiksi dengan hipotesis induksi.
Dengan demikian teorema terbukti.
Lemma 3.2:
Jika G sebuah graph kubik terhubung-2, maka G memuat subgraph Hi
untuk suatu i = 1, 2 yang memenuhi:
(i) V(H1)∩V(H2) = φ
(ii) Hi memuat dua titik ui dan vi berderajat 2 dan semua titik yang lainnya
masing-masing berderajat 3
(iii) )(GEvu ii ∉
(iv) G memuat dua lintasan disjoin-internal yaitu lintasan-Pu = (u1, u2) dan
lintasan-Pv = (v1, v2) sedemikian hingga (V(Pu)∪V(Pv))∩V(Hi)= {ui, vi}
(v) .3)( =+ iii vuHκ
Bukti:
Karena G graph kubik, berdasarkan Teorema 2.1, ).(')( GG κκ = Karena
2)( =Gκ , maka .2)(' =Gκ Misalkan { 21 ',' ee } merupakan himpunan sisi
pemutus di G dan misalkan iH ' untuk suatu i = 1, 2 adalah komponen-komponen
dari G - { 21 ',' ee }. Dari semua kemungkinan subgraph iH ' , yang mungkin
diperoleh sebagai sebuah komponen dari G - { 2,1, , ii ee } untuk suatu
)(, 2,1, GEee ii ∈ . Misalkan Hi adalah komponen yang memiliki titik sesedikit
mungkin. Jelas Hi memenuhi (i) dan (ii). Karena G graph kubik, maka Hi
36
memenuhi (iii) (lihat Gambar 3.11). Karena G graph terhubung-2, berdasarkan
Teorema 2.2, G memuat dua lintasan disjoin-internal yaitu lintasan-Pu = (u1, u2)
dan lintasan-Pv = (v1, v2) sedemikian hingga (V(Pu)∪V(Pv))∩V(Hi)= {ui, vi}.
Karena Hi minimalitas (titik paling sedikit), maka himpunan sisi-sisi dari Hi tidak
memuat sisi pemutus di G. Akibatnya, jika Hi ditambahkan sebuah sisi yang
menghubungkan titik ui dan titik vi, maka Hi merupakan graph terhubung-3.
Sehingga .3)( =+ iii vuHκ Dengan demikian bukti lemma lengkap.
Gambar 3.11: Subgraph Hi
Berikut ini akan ditunjukkan bahwa setiap graph kubik merupakan graph
cantik.
Teorema 3.4:
Setiap graph kubik G merupakan graph cantik.
Bukti:
Kita tinjau 3 kasus yaitu 3)( =Gκ , 2)( =Gκ , dan .1)( =Gκ
Kasus 1. .3)( =Gκ
Berdasarkan Fakta 3.1 dan Teorema 3.3, maka graph kubik G merupakan
graph cantik.
u2 u1
v2 v1
H1 H2
37
Kasus 2. .2)( =Gκ
Andaikan G graph tak cantik. Maka graph Hi + uivi untuk suatu i = 1, 2,
dideskripsikan pada Lemma 3.2 merupakan subdivisi dari graph kubik terhubung-
3 yang tak cantik ketika diberi label sebagai berikut. Setiap sisi kecuali uivi diberi
label 1. Label sisi uivi adalah label sebarang lintasan-(ui, vi) di G yang memuat u3-i
dan v3-i. Oleh karena itu, graph Hi + uivi merupakan subdivisi dari graph kubik
terhubung-3 yang tak cantik dengan sisi uivi mempunyai label kecuali 1 modulo 3.
Berdasarkan Fakta 3.2 dan Teorema 3.3, tidak ada graph yang demikian. Kita
simpulkan bahwa G merupakan graph cantik.
Kasus 3. .1)( =Gκ
Misalkan H blok terakhir G dan misalkan v titik pemutus G di V(H).
Asumsikan u dan w dua titik di H berhubungan langsung dengan v.
Subkasus 3.1.
Jika titik u dan titik w berhubungan langsung di G, maka sikel (u, v, w, u)
mempunyai panjang 3 ≡ 0 (modulo 3) di G. Sehingga G graph cantik.
Subkasus 3.2.
Jika titik u dan titik w tidak berhubungan langsung di G, maka
berdasarkan Lemma 3.2 graph H – v + uw memiliki κ ( H – v + uw) = 3.
Sehingga graph H – v + uw merupakan graph kubik terhubung-3. Andaikan graph
G tak cantik. Maka graph H – v + uw merupakan subdivisi dari graph kubik
terhubung-3 yang tak cantik ketika diberi label sebagai berikut. Setiap sisi kecuali
uw diberi label 1. Label sisi uw adalah label sebarang lintasan-(u, w) di G. Oleh
karena itu, graph H – v + uw merupakan subdivisi dari graph kubik terhubung-3
38
yang tak cantik dengan sisi uw mempunyai label kecuali 1 modulo 3.
Berdasarkan Fakta 3.2 dan Teorema 3.3, tidak ada graph yang demikian. Kita
simpulkan bahwa G merupakan graph cantik. Dengan demikian bukti teorema
lengkap.
Teorema 3.3 menunjukkan bahwa setiap subdivisi dari graph kubik
terhubung-3 dengan titik yang cukup banyak adalah graph cantik. Tetapi, jika kata
kubik dihilangkan belum tentu graph subdivisinya merupakan graph cantik.
Misalkan T sebuah pohon dengan n – 2 ≥ 2 titik. Misalkan graph Gn dibentuk dari
T dengan menambahkan dua titik baru x dan y diluar T dengan cara
menghubungkan titik x dan titik y ke setiap titik di T dan titik x dan y
dihubungkan oleh sebuah sisi. Karena graph Gn mempunyai n ≥ 4 titik, jelas Gn
merupakan graph terhubung-3. Misalkan subdivisi dari Gn diperoleh dengan cara
pelabelan berikut: Setiap sisi Gn di T diberi label 0; setiap sisi yang
menghubungkan titik x ke setiap titik T diberi label 1; setiap sisi yang
menghubungkan titik y ke setiap titik T diberi label 1; dan sisi xy diberi label 0.
Maka dapat ditunjukkan subdivisi graph tersebut merupakan graph tak cantik.
Ambil 2 titik u dan v di T. Karena T pohon, maka u dan v dihubungkan oleh
sebuah lintasan P = (u = z0, z1, z2, . . . , v = zk) di T. Karena u dan v masing-
masing berhubungan langsung dengan x dan y, dan x dan y berhubungan
langsung, maka terdapat 4 jenis sikel di Gn yaitu:
1) (x, zi, zi + 1, . . . , zt, x) dengan 0 ≤ i ≤ k; 0 ≤ t ≤ k ; i < t merupakan
sikel dengan panjang 2 modulo 3.
39
2) (y, zi, zi + 1, . . . , zt, y) dengan 0 ≤ i ≤ k; 0 ≤ t ≤ k ; i < t merupakan
sikel dengan panjang 2 modulo 3.
3) (x, zi, zi + 1, . . . , zt, y, x) dengan 0 ≤ i ≤ k; 0 ≤ t ≤ k ; i < t merupakan
sikel dengan panjang 2 modulo 3.
4) (x, zi, y, zt, x) dengan 0 ≤ i ≤ k; 0 ≤ t ≤ k ; i ≠ t merupakan sikel
dengan panjang 4 ≡ 1 (modulo 3).
Jadi dari uraian di atas menunjukkan bahwa subdivisi dari graph Gn tidak
memuat sikel dengan panjang 0 modulo 3. Sehingga subdivisi dari graph Gn
merupakan graph tak cantik.
Berikut ini akan ditunjukkan bahwa subdivisi dari graph Gn merupakan
graph tak cantik maksimal. Artinya, tidak ada graph lain yang memuat subdivisi
graph Gn yang tak cantik.
Teorema 3.5:
Jika subdivisi graph Gn yang diperoleh dengan cara pelabelan berikut:
setiap sisi T di Gn dan sisi xy diberi label 0; sedangkan setiap sisi yang lain diberi
label 1, maka subdivisi dari graph Gn yang demikian merupakan graph tak cantik
maksimal.
1
1
T 0
y
x
Gn :
Gambar 3.12: Subdivisi dari graph terhubung-3 yang tak cantik dengan n titik
40
Bukti:
Perhatikan subdivisi dari graph Gn pada Gambar 3.12. Subdivisi dari graph
Gn merupakan graph tak cantik. Jika graph G dibentuk dari subdivisi graph Gn
dengan menambahkan sebuah sisi baru yang menghubungkan dua titik T yang
tidak berhubungan langsung, maka graph G dapat ditunjukkan merupakan graph
cantik. Misalkan sisi baru tersebut adalah e = uv dan lintasan P = (u = z0, z1, z2, ...
, v = zk) di T. Ada tiga kemungkinan melabel sisi e tersebut yaitu 0, 1, atau 2
modulo 3.
Kasus 1. Sisi e = uv dilabel 0 modulo 3.
Graph G memuat sebuah sikel (u, z1, z2, . . . , v, u) dengan panjang 0
modulo 3. Sehingga G merupakan graph cantik.
Kasus 2. Sisi e = uv dilabel 1 modulo 3.
Graph G memuat sebuah sikel (u, v, x, u) dengan panjang 3 ≡ 0 (modulo
3). Sehingga G merupakan graph cantik.
Kasus 3. Sisi e = uv dilabel 2 modulo 3.
Graph G memuat sebuah sikel (u, v, y, zi, x, u), 0 < i < k dengan panjang
06 ≡ (modulo 3). Sehingga G merupakan graph cantik.
Jadi untuk semua kemungkinan didapat G merupakan graph cantik dan memuat
subdivisi dari graph Gn. Dengan demikian teorema terbukti.
41
Berikut ini akan ditunjukkan bahwa setiap subdivisi dari K5 merupakan
graph cantik.
Fakta 3.4:
Setiap subdivisi dari K5 merupakan graph cantik.
Bukti:
Berdasarkan Fakta 3.2, daftar semua subdivisi dari K4 merupakan graph
tak cantik dapat dilihat pada Gambar 3.8. Misalkan Graph G = K5 – e. Perhatikan
bahwa G dikurangi titik v2 adalah graph K4 (lihat Gambar 3.13).
Padahal pada Fakta 3.2, setiap subdivisi dari K4 adalah graph tak cantik.
Penghapusan titik v2 pada G mengakibatkan 3 sisi yang terkait dengan titik v2
terhapus yaitu sisi v1v2, v2v3, dan v2v4. Kemudian setiap sisi mungkin dilabel
dengan 3 cara yaitu 0, 1, atau 2 modulo 3. Sehingga seluruhnya terdapat 33 = 27
kemungkinan melabel ketiga sisi tersebut. Dari semua kemungkinan tersebut
hanya pelabelan berikut yang mengakibatkan subdivisi dari graph G yang tak
cantik.
v5
v1 v3
v4
v2
G = K5 – e
Gambar 3.13: G adalah graph K5 – e
42
Selanjutnya, jika titik v2 dan v5 di G1, G2, maupun G3 dihubungkan oleh
sebuah sisi baru, maka akan terbentuk K5. Kemudian sisi baru tersebut, dilabel
dengan 3 cara yaitu 0, 1, atau 2 modulo 3. Setiap kemungkinan akan diperoleh
sebuah sikel dengan panjang 0 modulo 3 seperti terlihat pada Gambar 3.15
berikut.
v5
v1 v3
v4
v2
1 1 0
0
1 1
1 1 0
G1
v5
v1 v3
v4
v2
1 1 0
2
1 1
1 1 0
G2
v5
v1 v3
v4
v2
0 0 1
2
1 1
1 1 0
G3
Gambar 3.14: Subdivisi dari K5 - e yang tak cantik
v5
v1 v3
v4
v2
1 1 0
0
1 1
1 1 0
G11
0
v5
v1 v3
v4
v2
1 1 0
2
1 1
1 1 0
G21
0
v5
v1 v3
v4
v2
0 0 1
2
1 1
1 1 0
G31
0
v5
v1 v3
v4
v2
1 1 0
0
1 1
1 1 0
G12
1
v5
v1 v3
v4
v2
1 1 0
2
1 1
1 1 0
G22
1
v5
v1 v3
v4
v2
0 0 1
2
1 1
1 1 0
G32
1
43
Perhatikan Gambar 3.15. Misalnya pada graph G11 terdapat sikel (v2, v4,
v5, v2) dengan panjang 0 modulo 3. Sehingga G11 adalah graph cantik. Misalnya
pada graph G12 terdapat sikel (v1, v2, v5, v1) dengan panjang 3 ≡ 0 (modulo 3).
Sehingga G12 adalah graph cantik. Misalnya pada graph G13 terdapat sikel (v1, v2,
v5, v3, v4, v1) dengan panjang 6 ≡ 0 (modulo 3). Sehingga G13 adalah graph
cantik. Misalnya pada graph G21 terdapat sikel (v2, v4, v5, v2) dengan panjang 0
modulo 3. Sehingga G21 adalah graph cantik. Misalnya pada graph G22 terdapat
sikel (v2, v4, v3, v5, v2) dengan panjang 3 ≡ 0 (modulo 3). Sehingga G22 adalah
graph cantik. Misalnya pada graph G23 terdapat sikel (v1, v3, v2, v5, v1) dengan
panjang 6 ≡ 0 (modulo 3). Sehingga G23 adalah graph cantik. Misalnya pada
graph G31 terdapat sikel (v2, v5, v3, v4, v1, v2) dengan panjang 3 ≡ 0 (modulo 3).
Sehingga G31 adalah graph cantik. Misalnya pada graph G32 terdapat sikel (v4, v5,
v2, v3, v1, v4) dengan panjang 6 ≡ 0 (modulo 3). Sehingga G32 adalah graph
cantik. Misalnya pada graph G33 terdapat sikel (v2, v3, v5, v2) dengan panjang 3 ≡
0 (modulo 3). Sehingga G33 adalah graph cantik. Dari semua kemungkinan
tersebut dapat disimpulkan bahwa setiap subdivisi dari K5 merupakan graph
cantik.
v5
v1 v3
v4
v2
1 1 0
0
1 1
1 1 0
G13
2
v5
v1 v3
v4
v2
1 1 0
2
1 1
1 1 0
G23
2
v5
v1 v3
v4
v2
0 0 1
2
1 1
1 1 0
G33
2
Gambar 3.15
44
BAB IV
PENUTUP
Dari hasil pembahasan pada BAB III, dapat disimpulkan bahwa:
1. Graph G tak cantik jika dan hanya jika setiap subgraph G tak cantik.
2. Graph G cantik jika dan hanya jika pasangan G cantik.
3. Setiap subdivisi dari graph kubik terhubung-3 dengan n ≥ 10 titik merupakan
graph cantik.
4. Setiap graph kubik merupakan graph cantik.
5. Misalkan T sebuah pohon dengan n – 2 ≥ 2 titik. Misalkan graph Gn dibentuk
dari T dengan menambahkan dua titik baru x dan y diluar T dengan cara
menghubungkan titik x dan titik y ke setiap titik di T dan titik x dan y
dihubungkan oleh sebuah sisi. Jika subdivisi graph Gn yang diperoleh dengan
cara pelabelan berikut: setiap sisi T di Gn dan sisi xy diberi label 0; sedangkan
setiap sisi yang lain diberi label 1, maka subdivisi dari graph Gn yang
demikian merupakan graph tak cantik maksimal.
6. Setiap subdivisi dari K5 merupakan graph cantik.
44
45
DAFTAR PUSTAKA
[1] Barefoot, C. A. dkk. 1991. Cycle of Length 0 Modulo 3 in Graphs. Graph
Theory Combinatorics and Applications. Vol. 1: 87-101. Newyork/
Chichester/ Brisbane/ Toronto/ Singapore: John Wiley & Sons, Inc.
[2] Budayasa, Ketut. 2007. Teori Graph dan Aplikasinya. Surabaya: Unesa
University Press Surabaya.
[3] Bussemaker, F.C. dkk. 1976. Computer Investigation of Cubic Graphs. T. H.
Report 76-WSK-01 (Online), (http://www.sciencedirect.com, diakses pada
17 April 2008).
[4] Chartrand, Gary dan Ping Zhang. 2005. Introduction to Graph Theory.
Newyork: The McGraw Hill Companies, Inc.
45
46
PERNYATAAN KEASLIAN SKRIPSI
Saya yang bertanda tangan dibawah ini:
Nama : Imam Rofiki
No. Registrasi : 043214013
Program Studi : S-1
Jurusan : Matematika
Fakultas : Matematika dan Ilmu Pengetahuan Alam
Menyatakan dengan sebenarnya dan sungguh-sungguh bahwa skripsi yang saya
tulis ini benar-benar merupakan hasil karya saya sendiri; bukan merupakan
pengambil-alihan tulisan atau pikiran orang lain yang saya akui sebagai hasil
tulisan atau pikiran saya sendiri.
Apabila di kemudian hari terbukti atau dapat dibuktikan skripsi ini hasil jiplakan
atau ada pihak yang mengajukan gugatan, maka saya bersedia menerima seluruh
sanksi atas perbuatan tersebut, termasuk pembatalan ijazah yang saya peroleh dari
Universitas Negeri Surabaya.
Surabaya, 20 Juni 2008
Yang membuat pernyataan,
Imam Rofiki