GRAF
Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)
·
Graf yang dapat
digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong
(bersilangan) disebut graf planar,
·
jika tidak, maka ia
disebut graf tak-planar.
·
K4 adalah graf planar:
·
K5 adalah graf tidak
planar:
Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan
disebut graf bidang (plane graph).
Aplikasi Graf Planar
·
Persoalan utilitas
(utility problem)
·
Perancangan IC (Integrated Circuit)
·
Tidak boleh ada
kawat-kawat di dalam ICboard yang saling bersilangan dapat menimbulkan
interferensi arus listrik malfunction
·
Perancangan kawat memenuhi prinsip graf planar
Contoh :
1. Misalkan graf sederhana planar
memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar
dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka.
Berapa banyak wilayah yang terbentuk?
Jawaban:
·
Diketahui n = jumlah simpul = 24, maka jumlah
derajat seluruh simpul = 24x4 = 96.
·
Menurut lemma jabat tangan, jumlah derajat =
2x jumlah sisi, sehingga jumlah sisi = e = jumlah derajat/2 = 96/2 = 48
·
Dari rumus Euler, n – e +
f = 2, sehingga f = 2 – n + e = 2 – 24 +
48 = 26 buah.
·
Pada graf planar
sederhana terhubung dengan f buah
wilayah, n buah simpul, dan e buah sisi (e > 2) selalu berlaku: e<= 3n – 6
·
Ketidaksamaan yang
terakhir dinamakan ketidaksamaan Euler,
·
yang dapat digunakan
untuk menunjukkan keplanaran suatu graf sederhana
·
kalau graf planar, maka
ia memenuhi ketidaksamaan Euler, sebaliknya jika tidak planar maka
ketidaksamaan tersebut tidak dipenuhi.
Teorema Kuratoswki
Berguna untuk menentukan dengan tegas keplanaran suat graf.
Gambar
(a) Graf Kuratowski pertama (K5)
(b) Graf Kuratowski kedua (K3, 3)
(c) Graf yang isomorfik dengan graf Kuratowski kedua
Sifat graf Kuratowski adalah:
1. Kedua graf Kuratowski adalah graf teratur.
2. Kedua graf Kuratowski adalah graf tidak-planar
3. Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya menjadi
graf planar.
4. Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul
minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi
minimum.
TEOREMA Kuratowski.
Graf G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang
isomorfik dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic)
dengan salah satu dari keduanya.
Lintasan dan Sirkuit Euler
·
Lintasan Euler ialah
lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.
·
Sirkuit Euler ialah
sirkuit yang melewati masing-masing sisi tepat satu kali.
·
Graf yang mempunyai
sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan
Euler dinamakan juga graf semi-Euler (semi-Eulerian graph)
TEOREMA. Graf tidak berarah memiliki lintasan Euler jika (graf semi-Euler)
dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau
tidak ada simpul berderajat ganjil sama sekali.
TEOREMA. Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler)
jika dan hanya jika setiap simpul berderajat genap.
TEOREMA.
(a) Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung
dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama.
(b) G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap
simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang
pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua
memiliki derajat-masuk satu lebih besar dari derajat-keluar.
Lintasan dan Sirkuit Hamilton
·
Lintasan Hamilton ialah
lintasan yang melalui tiap simpul di dalam graf tepat satu kali.
·
Sirkuit Hamilton ialah
sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul
asal (sekaligus simpul akhir) yang dilalui dua kali.
·
Graf yang memiliki
sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki
lintasan Hamilton disebut graf semi-Hamilton.
TEOREMA. Syarat cukup supaya graf
sederhana G dengan n >= 3) buah simpul adalah graf Hamilton ialah bila
derajat tiap simpul paling sedikit n/2 (yaitu, d(v)>= n/2 untuk setiap
simpul v di G). (coba nyatakan dalam “jika p maka q”)
TEOREMA. Setiap graf lengkap adalah
graf Hamilton.
TEOREMA. Di dalam graf lengkap G dengan n buah simpul (n>= 3), terdapat
(n – 1)!/2 buah sirkuit Hamilton
TEOREMA. Di dalam graf lengkap G dengan n buah simpul (n>= 3 dan n ganjil),
terdapat (n – 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang
beririsan). Jika n genap dan n >= 4, maka di dalam G terdapat (n – 2)/2 buah sirkuit
Hamilton yang saling lepas.
Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton
sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton,
dan sebagainya
Beberapa Aplikasi Graf
·
Lintasan
terpendek (shortest path) (akan dibahas pada kuliah IF3051)
·
Persoalan
pedagang keliling (travelling salesperson problem)
·
Persoalan
tukang pos Cina (chinese postman problem)
·
Pewarnaan graf
(graph colouring)
Persoalan Pedagang Keliling (travelling salesperson problem (TSP)
Diberikan sejumlah kota dan diketahui jarak antar kota. Tentukan tur
terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat
dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali
lagi ke kota asal keberangkatan.
==> menentukan sirkuit Hamilton yang memiliki bobot minimum.
Aplikasi TSP:
1.Pak Pos mengambil surat di kotak pos yang tersebar pada n buah lokasi
di berbagai sudut kota.
2.Lengan robot mengencangkan n buah mur pada beberapa buah peralatan
mesin dalam sebuah jalur perakitan.
3.Produksi n komoditi berbeda dalam sebuah siklus.
Pewarnaan Graf
·
Ada dua macam:
pewarnaan simpul, dan pewarnaan sisi
·
Hanya dibahas
perwarnaan simpul
·
Pewarnaan
simpul: memberi warna pada simpul-simpul graf sedemikian sehingga dua simpul
bertetangga mempunyai warna berbeda.
·
Aplikasi
pewarnaan graf: mewarnai peta.
·
Peta terdiri
atas sejumlah wilayah.
·
Wilayah dapat
menyatakan kecamatan, kabupaten, provinsi, atau negara.
·
Peta diwarnai
sedemikian sehingga dua wilayah bertetangga mempunyai warna berbeda.
·
Nyatakan
wilayah sebagai simpul, dan batas antar dua wilayah bertetangga sebagai sisi.
·
Mewarnai
wilayah pada peta berarti mewarnai simpul pada graf yang berkoresponden.
·
Setiap wilayah
bertetangga harus mempunyai warna berbeda warna setiap simpul harus berbeda.
·
Bilangan
kromatik: jumlah minimum warna yang dibutuhkan untuk mewarnai peta
·
Simbol: x(G).
·
Suatu graf G
yang mempunyai bilangan kromatis k dilambangkan dengan x(G) = k.
·
Graf di bawah
ini memiliki x(G) = 3
·
Graf kosong Nn
memiliki x(G) = 1, karena semua simpul tidak terhubung, jadi untuk mewarnai
semua simpul cukup dibutuhkan satu warna saja.
·
Graf lengkap
Kn memiliki x(G) = n sebab semua simpul saling terhubung sehingga diperlukan n
buah warna.
·
Graf bipartit Km,n
mempunyai x(G) = 2, satu untuk simpul-simpul di himpunan V1 dan satu lagi untuk
simpul-simpul di V2.
·
Graf lingkaran dengan n
ganjil memiliki x(G) = 3, sedangkan jika
n genap maka x(G) = 2.
·
Sembarang pohon T
memiliki x(T) = 2.
·
Untuk graf-graf yang lain
tidak dapat dinyatakan secara umum bilangan kromatiknya
·
Perkembangan teorema
pewarnaan graf:
TEOREMA 1. Bilangan
kromatik graf planar <= 6.
TEOREMA 2. Bilangan
kromatik graf planar <= 5.
TEOREMA 3. Bilangan
kromatik graf planar <= 4.
- Teorema 4 berhasil menjawab persoalan 4-warna (yang diajuka pada abad 19): dapatkah sembarang graf planar diwarnai hanya dengan 4 warna saja?
·
Jawaban dari persoalan
ini ditemukan oleh Appel dan Haken yang menggunakan komputer untuk menganalisis
hampir 2000 graf yang melibatkan jutaan kasus
Komentar
Posting Komentar