GRAF

Graf Isomorfik

(Isomorphic Graph)

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

Namun, ketiga syarat ini ternyata belum cukup menjamin. Pemeriksaan secara visual perlu dilakukan.

Apa itu graph??

(a) Dua buah graf isomorfik, (b) tiga buah graf isomorfik

Graph Isomorfik (Isomorphic Graph)

• Graph merupakan struktur diskrit yang terdiri dari himpunan objek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul tersebut.

• Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

Graf Isomorfik (Isomorphic Graph)

• 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 sisi-sisi 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.

GRAF (Graph)

Graf Isomorfik (Isomorphic Graph)

Graf (a) dan graf (b) isomorfik

Gambar 6.35 G1 isomorfik dengan G2, tetapi G1 tidak isomorfik dengan G3

Membuktikan Graf Isomorfik

Lihatlah mereka, badan mereka beda, ada yang tinggi dan yang pendek, ada yang gemuk dan yang kurus, tapi mereka punya pola bentuk tubuh yang sama. Dan kami katakan, bahwa mereka

beda tapi sama

Kenapa kami mengatakan seperti itu?

Karena kami memandang mereka dari segi graf. Andaikan di badan mereka kita letakkan titik-titik simpul yang bersesuaian, maka kita akan menemukan graf yang sama meskipun secara geometris mereka nampak berbeda.

designed by Péter Puklus for Prezi

Tugas yang di berikan oleh :

Ibu Vivi Aida

Imam Rofi'i

Rudi Hartono

Beta Ahsaniah

STMIK - STIE ASIA MALANG