Graf Isomorfik, Graf Planar, Graf Bidang dan Graf Dual PDF

Preview

Summary

Graf Isomorfik,Planar, Bidang dan Dual Kelompok 3 Lysta Chrysmawati Mellda Verayani Myra Amelya I Graf Isomorfik (Isomorphic Graph) DEFINISI Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehin...

Description

Graf Isomorfik,Planar, Bidang dan Dual Kelompok 3 Lysta Chrysmawati Mellda Verayani Myra Amelya I

Graf Isomorfik (Isomorphic Graph) DEFINISI Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkorespon di G2 juga harus bersisian dengan simpul u’ dan v’ di G2.

Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda.

Dari definisi isomorfik dapat disimpulkan dua buah graf isomorfik memenuhi ketiga syarat: 1. Mempunyai jumlah simpul yang sama. 2. Mempunyai jumlah sisi yang sama. 3. Mempunyai jumlah simpul yang sama berderjat tertentu. Ketiga syarat ini belum cukup menjamin keisomorfikan. Pemeriksaan secara visual masih tetap diperlukan.

Untuk memperlihatkan bahwa dua graf isomorfik, kita dapat menunjukkan bahwa matriks ketetanggaan kedua graf itu sama.

a

a b

AG1

c d

e

0 1  1 1  0

b

c

d

e

1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1  0 0 1 0

x

x y

AG 2 w v

z

0 1  1 1  0

y

w

v

z

1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1  0 0 1 0

Graf Planar dan Graf Bidang DEFINISI Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan) disebut sebagai graf planar, jika tidak, maka ia disebut graf tak-planar.

Contoh: Persoalan utilitas: terdapat tiga buah rumah, H1, H2, dan H3, masing-masingnya dihubungkan tiga buah utilitasair(W), gas(G), dan listrik(E) dengan alat pengantar (pipa, kabel,dsb). Graf pada gambar (a) adalah graf bipartit lengkap, K3,3. Jika graf pada gambar (a) digambar ulang, ternyata tidak mungkin menggambar sisi yang tidak saling berpotongan (gambar (b)). Dengan kata lain, persoalan utilitas tidak planar.

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).

Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face). Jumlah wilayah pada graf bidang dapat dihitung dengan mudah. Graf bidang pada gambar terdiri atas 6 wilayah (termasuk wilayah terluar):

Rumus Euler Jumlah wilayah (f) pada graf planar sederhana juga dapat dihitung dengan rumus Euler sebagai berikut : n–e+f=2 atau f=e–n+2 yang dalam hal ini, e = jumlah sisi n = jumlah simpul Contoh:

e=11 dan n=7, maka f=11-7+2=6

Contoh: Misalkan graf sederhana planar dan terhubung 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 ?

Penyelesaian : Diketahui n = jumlah simpul = 24, maka jumlah derajat seluruh simpul = 24 x 4 = 96. Menurut lemma jabat tangan, jumlah derajat = 2 x jumlah sisi, sehingga jumlah sisi = e = jumlah derajat / 2 = 96 / 2= 48 Dari rumus Euler, n – e + f = 2, sehingga f = jumlah wilayah = 2 – n + e = 2 – 24 + 48 = 26 buah.

COROLLARY 1 Jika G adalah graf sederhana terhubung dengan e adalah jumlah sisi dan v adalah jumlah simpul, yang dalam hal ini v ≥ 3, maka berlaku ketidaksamaan Euler e ≤ 3v – 6. Perlihatkan bahwa K,5, tidak planar dengan ketidaksamaan Euler.

Penyelesaian : Pada graf K5, n = 5 dan e = 10. K5 tidak memenuhi ketidaksamaan Euler sebab 10 ≥ 3(5) – 6. Hal ini menunjukkan bahwa K5 tidak planar.

COROLLARY 2 Jika G adalah graf sederhana terhubung dengan e adalah jumlah sisi dan v adalah jumlah simpul, yang dalam hal ini v ≥ 3 dan tidak ada sirkuit yang panjangnya 3, maka berlaku e ≤ 2v – 4.

Graf K3.3 tidak memenuhi ketidaksamaan e ≤ 2n – 4, Karena e = 9, n = 6 9 ≤ (2)(6) – 4 = 8 ( salah ) yang berarti K3.3 bukan graf planar.

Teorema Kuratowski Dalam literatur tentang graf, dikenal dua buah graf tidak planar yang khusus, yaitu graf Kuratowski 1. Graf Kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah simpul ( K5 ), adalah graf tidak-planar. 2. Graf Kuratowski kedua, yaitu graf terhubung teratur dengan 6 buah simpul dan 9 buah sisi ( K3.3 ) adalah graf tidak-planar.

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. Keduanya adalah graf tidak planar paling sederhana.

TEOREMA 8.2 ( Teorema Kuratowski ) : Graf G adalah tidak planar jika dan hanya jika ia mengandung upagraf yang isomorfik dengan K5 atau K3.3 atau homeomorfik ( homeomorphic ) dengan salah satu dari keduanya.

Apa yang dimaksud dengan homeomorfik ? Dua graf G1 dan G2 dikatakan homeomorfik jika salah satu dari kedua graf dapat diperoleh dari graf yang lain dengan cara menyisipkan dan atau membuang secara berulang – ulang simpul berderajat 2.

Contoh Perlihatkan dengan teorema Kuratowski bahwa graf petersen (a) tidak planar !

Graf Dual (Dual Graph) Misalkan kita mempunyai sebuah graf planar G yang direpresentasikan sebagai graf bidang. Kita dapat membuat suatu graf G* yang secara geometri merupakan dual dari graf planar tersebut dengan cara sebagai berikut : 1.

Pada setiap wilayah atau muka (face) f di G, buatlah simpul v* yang merupakan simpul untuk G*.

2.

Untuk setiap sisi e di G, tariklah sisi e* (yang menjadi sisi untuk G*) yang memotong sisi e tersebut. Sisi e* menghubungkan dua buah simpul v1* dan v2* (simpul-simpul di G*) yang berada di dalam muka f1 dan f2 yang dipisahkan oleh sisi e di G. Untuk sisi e yang salah satu simpulnya merupakan simpul berderajat 1 (jadi, sisi e seluruhnya terdapat di dalam sebuah muka), maka sisi e* adalah berupa sisi gelang.

Graf G* yang terbentuk dengan cara penggambaran demikian disebut graf dual (dual geometri) dari graf G. Gambar berikut adalah graf dual G* dari graf planar G. Sisisisi graf G* digambarkan dengan garis putus-putus.

Jika G adalah graf planar dalam representasi bidang dengan n buah simpul, e buah sisi dan f buah muka, maka graf G* memiliki n* = f buah simpul, e* = e buah sisi dan f* = n buah muka. Sebuah graf planar G mempunyai dual yang unik hanya jika repsesentasi bidangnya unik. Dua buah representasi bidang yang berbeda dari graf yang sama

Salah satu aplikasi graf dual yang penting adalah untuk mempresentasikan peta (map). Setiap peta pada bidang terdiri dari sejumlah wilayah (region). Wilayah pada peta dapat menyatakan suatu negara, provinsi, atau kabupaten. Tiap wilayah pada peta dinyatakan sebagai sebuah simpul, sedangkan sisi menyatakan bahwa dua wilayah berbatasan langsung (bertetangga)....