Graf Isomorfik
·
Diketahui matriks ketetanggaan
(adjacency matrices) dari sebuah graf tidak berarah. Gambarkan dua buah graf
yang yang bersesuaian dengan matriks tersebut.
Jawaban:
·
Dua buah graf yang sama (hanya
penggambaran secara geometri berbeda)
è isomorfik!
Graf Isomorfik
·
Dua buah graf yang sama tetapi secara
geometri berbeda disebut graf yang saling isomorfik.
·
Dua buah graf, G1 dan G2 dikatakan
isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya
dan antara sisisisi keduaya sedemikian sehingga hubungan kebersisian tetap
terjaga.
·
Dua buah graf, G1 dan G2 dikatakan
isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya
dan antara sisisisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.
·
Dengan kata lain, misalkan sisi e bersisian
dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 harus
bersisian dengan simpul u’ dan v’ yang di G2.
·
Dua buah graf yang isomorfik adalah graf
yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graf dapat
digambarkan dalam banyak cara.
Dari definisi graf isomorfik dapat
dikemukakan bahwa dua buah graf isomorfik memenuhi ketiga syarat berikut
[DEO74]: 1. Mempunyai jumlah simpul yang sama. 2. Mempunyai jumlah sisi yang
sama 3. Mempunyai jumlah simpul yang sama berderajat tertentu
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.
Graf planar yang digambarkan dengan
sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).
Aplikasi
Graf Planar
Persoalan utilitas (utility
problem)
Aplikasi
Graf Planar
·
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
Teorema
Kuratoswki
Gambar (a) Graf Kuratowski pertama (K5)
(b) Graf Kuratowski kedua (K3, 3)
(c) Graf yang isomorfik dengan graf Kuratowski kedua.
(b) Graf Kuratowski kedua (K3, 3)
(c) Graf yang isomorfik dengan graf Kuratowski kedua.
Kazimierz Kuratowski (February 2, 1896 – June 18,
1980) was a Polish mathematician and logician. He was one of the leading
representatives of the Warsaw School of Mathematics. (Sumber: Wikipedia)
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.
Contoh:
Kita gunakan Teorema Kuratowski untuk memeriksa keplanaran graf. Graf G di
bawah ini bukan graf planar karena ia mengandung upagraf (G1) yang sama dengan
K3,3.
Graf G tidak planar karena ia mengandung upagraf
(G1) yang homeomorfik dengan K5 (dengan membuang simpul-simpul yang berderajat
2 dari G1, diperoleh K5).
Gambar Graf G, upagraf G1 dari G yang homeomorfik
dengan K5.
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).
Contoh. Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4,
1 Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3 Sirkuit Euler
pada graf (c) : 1, 2, 3, 4, 7, 3, 5,
7, 6, 5, 2, 6, 1 Sirkuit Euler pada graf (d)
: a, c, f, e, c, b, d, e, a, d,
f, b, a Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler
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.
Gambar: (a) Graf berarah Euler (a, g, c, b, g, e, d, f,
a)
(b)
Graf berarah semi-Euler (d, a, b, d, c, b)
(c)
Graf berarah bukan Euler maupun semi-Euler
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.
(a) graf yang memiliki lintasan Hamilton (misal: 3,
2, 1, 4)
(b) graf yang memiliki lintasan Hamilton (1, 2, 3,
4, 1)
(c) graf yang tidak memiliki lintasan maupun sirkuit
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.
Contoh.
Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah
meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota
mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari
pengaturan tersebut dapat dilaksanakan?
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.
Aplikasi TSP:
1. 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.
I1 = (a, b, c, d, a) bobot = 10 + 12 + 8 + 15 = 45
I2 = (a, c, d, b, a) bobot = 12 + 5 + 9 + 15 = 41 I3 = (a, c, b, d, a)
bobot = 10 + 5 + 9 + 8 = 32
Sirkuit Hamilton terpendek: I3 = (a, c, b, d, a)
dengan bobot = 10 + 5 + 9 + 8 = 32.
• Jika jumlah simpul n = 20 akan terdapat (19!)/2
sirkuit Hamilton atau sekitar 6 1016 penyelesaian.
Persoalan
Tukang Pos Cina (Chinese Postman Problem)
·
Dikemukakan oleh Mei Gan (berasal dari
Cina) pada tahun 1962.
·
Persoalan: seorang tukang pos akan
mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia
merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali
dan kembali lagi ke tempat awal keberangkatan?
Lintasan yang dilalui tukang pos: A, B, C, D, E, F,
C, E, B, F, A.
·
Jika graf yang merepresentasikan
persoalan adalah graf Euler, maka sirkuit Eulernya mudah ditemukan.
·
Jika grafnya bukan graf Euler, maka
beberapa sisi di dalam graf harus dilalui lebih dari sekali.
·
Jadi, pak pos harus menemukan sirkuit
yang mengunjungi setiap jalan paling sedikit sekali dan mempunyai jarak
terpendek.
Persoalan tukang pos Cina menjadi:
Seorang tukang pos akan mengantar surat ke
alamatalamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute
perjalanannya yang mempunyai jarak terpendek supaya ia melewati setiap jalan
paling sedikit sekali dan kembali lagi ke tempat awal keberangkatan
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.
·
Nyatakan wilayah sebagai simpul, dan
batas antar dua wilayah bertetangga sebagai sisi.
·
Mewarnai wilayah pada peta berarti
mewarnai simpul pada graf yang berkoresponden.
Gambar 8.72
(a)
Peta
(b)
Peta dan graf yang merepresentasikannya,
(c)
Graf yang merepresentasikan peta,
(d)
Pewarnaan simpul, setiap simpul mempunai warna berbeda,
(e)
Empat warna sudah cukup untuk mewarnai 8 simpul
·
Bilangan kromatik: jumlah minimum warna yang
dibutuhkan untuk mewarnai peta.
·
Simbol: ƛ(G).
·
Suatu graf G yang mempunyai bilangan kromatis
k dilambangkan dengan ƛ(G) = k.
·
Graf di bawah ini memiliki ƛ(G) = 3
·
Graf kosong Nn memiliki ƛ(G) = 1, karena
semua simpul tidak terhubung, jadi untuk mewarnai semua simpul cukup dibutuhkan
satu warna saja.
·
Graf lengkap Kn memiliki (G) = n sebab
semua simpul saling terhubung sehingga diperlukan n buah warna.
·
Graf bipartit Km,n mempunyai (G) = 2,
satu untuk simpul-simpul di himpunan V1 dan satu lagi untuk simpul-simpul di
V2.
·
Graf lingkaran dengan n ganjil memiliki
ƛG) = 3, sedangkan jika n genap maka ƛG) = 2.
·
Sembarang pohon T memiliki ƛ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.
·
eorema 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
·
Aplikasi lain pewarnaan graf:
penjadwalan.
Misalkan
terdapat delapan orang mahasiswa (1, 2, …, 8) dan lima buah mata kuliah yang
dapat dipilihnya (A, B, C, D, E). Tabel berikut memperlihatkan matriks lima
mata kuliah dan delapan orang mahasiswa. Angka 1 pada elemen (i, j) berarti
mahasiswa i memilih mata kuliah j,
sedangkan angka 0 menyatakan mahasiswa i tidak memilih mata kuliah j.
Berapa paling sedikit jumlah hari yang dibutuhkan
untuk jadwal ujian tersebut sedemikian sehingga semua mahasiswa dapat mengikuti
ujian mata kuliah yang diambilnya tanpa bertabrakan waktunya dengan jadwal
ujian kuliah lain yang juga diambilnya?
Gambar
8.74.
(a) Graf
persoalan penjadwalan ujian 5 mata kuliah untuk 8 orang mahasiswa
(b) Hasil pewaranan pada simpul-simpul graf
• Bilangan kromatik graf pada Gambar 8.74 adalah 2.
• Jadi, ujian mata kuliah A, E, dan D dapat
dilaksanakan bersamaan, sedangkan ujian mata kuliah B dan C dilakukan bersamaan
tetapi pada waktu yang berbeda dengan mata kuliah A, E, dan D.
Komentar
Posting Komentar