Matematika Diskrit : Isomorfisme dan Graf Isomorfik

Isomorfisme

Diketahui matriks ketetanggaan (adjacency matrices) dari sebuah graf tidak berarah. Gambarkan dua buah graf yang yang bersesuaian dengan matriks tersebut.

Jawaban:

Graf Isomorfik

Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik.

Dua buah graf, G₁ dan G₂ 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 G₁, maka sisi e’ yang berkoresponden di G₂ harus bersisian dengan simpul u’ dan v’ yang di G₂.

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.

Keterangan: G₁ isomorfik dengan G₂, tetapi G₁ tidak isomorfik dengan G₃

Keterangan: Graf (a) dan graf (b) isomorfik

Keterangan: (a) Dua buah graf isomorfik (b) tiga buah graf isomorfik

Dari definisi graf isomorfik dapat dikemukakan bahwa dua buah graf isomorfik memenuhi ketiga syarat berikut:

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.

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.

Tonton juga video pilihan dari kami berikut ini