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.

\[ \begin{bmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix} \]

Jawaban:


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

Keterangan: G1 isomorfik dengan G2, tetapi G1 tidak isomorfik dengan G3

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

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up