Ngebuktiin Graf Isomorfik

6 08 2012

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.


Apa yang akan kita bahas?

Kali ini kita akan membahas tentang cara ngebuktiin bahwa dua graf saling isomorfik ataupun tidak saling isomorfik. Maka dari itu, sebelum membaca postingan ini teman-teman perlu terlebih dahulu mempelajari tentang Graf.


Definisi Graf Isomorfik

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 berkoresponden di G2 juga harus bersisian dengan simpul u’ dan v’.


Contoh Graf yang saling isomorfik seperti apa?

Perhatikan gambar di bawah ini. Dengan sedikit sentuhan kita akan dapati bahwa mereka adalah sama. Bayangkan! Tarik titik C menuju titik A, mirip kan? A bersesuaian dengan E, B bersesuaian dengan F, C bersesuaian dengan G, dan D bersesuaian dengan H.


Syarat dua graf saling isomorfik

Kalau baca dibuku, hanya diberitahukan tiga syarat agar dua graf dikatakan saling isomorfik, yaitu:

  1. Mempunyai jumlah simpul yang sama
  2. Mempunyai jumlah sisi yang sama
  3. Mempunyai jumlah simpul yang sama berderajat tertentu

Gambar 1 memenuhi ketiga syarat di atas. Namun setelah kami telusuri lebih jauh, ternyata tiga syarat tersebut tidak cukup untuk menetapkan bahwa dua graf saling isomorfik. Contohnya:


Ternyata Gambar 2 juga memenuhi ketiga syarat di atas. Yaitu :

  • Terdapat 6 buah simpul
  • Terdapat 5 buah sisi
  • Terdapat 3 simpul brderajat satu, 2 simpul berderajat dua, 1 simpul berderajat tiga

Tapi D tidak bersesuaian dengan I karena D adjacent dengan dua simpul berderajat 1 dan satu simpul berderajat 2, sedangkan I adjacent dengan satu simpul berderajat 1 dan dua simpul berderajat 2. Beda bukan? Sampai kapan pun kedua graf ini tidak akan isomorfik.
Dan syarat ke empat yang kami tambahkan adalah:

“Mempunyai jumlah simpul yang sama yang memiliki adjensi (ketetanggan) tertentu”


Ngebuktiin Graf Isomorfik

Akan kita buktikan bahwa kedua graf di bawah ini isomorfik!

Kedua graf tersebut sudah memenuhi tiga syarat pertama, maka sekarang kita tinggal membuktikan bahwa kedua graf tersebut juga memenuhi syarat yang keempat.

A berderajat 3                                                             E berderajat 3

B berderajat 2                                                              F berderajat 2

C berderajat 3                                                             G berderajat 3

D berderajat 2                                                             H berderajat 2

Karena kami belum menemukan (baca: belum nyari) simbol yang tepat untuk menyatakan adjensi sebuah simpul, jadi kami pakai simbol adjensi ‘ala’ mathbest.

A adjacent dengan dua simpul berderajat 2 dan satu simpul berderajat 3. Disimbolkan dengan . Beturut-turut kita dapatkan:

                                                      

                                                             

                                                      

                                                             

Karena kedua graf tersebut Mempunyai jumlah simpul yang sama yang memiliki adjensi (ketetanggan) tertentu, maka kedua graf tersebut isomorfik alias sama.

Saatnya kita katakan Terbukti ^^

Hal yang sama bisa kita lakukan untuk membuktikan dua graf tidak isomorfik. Dan kami memperoleh hipotesis bahwa “Cukup dengan memenuhi syarat ke empat, maka dua graf saling isomorfik”. Kalau ada yang penasaran dengan hipotesis kami ini, silahkan ditelusuri. Bisa saja kami yang keliru😀

Semoga bermanfaat, jangan lupa bagi ke teman-temannya ya ^^

::Indahnya Berbagi Ilmu::


Aksi

Information

2 responses

19 11 2012
1102105

hanya koreksi redaksi,
“Ternyata Gambar 2 juga memenuhi ketiga syarat di atas. Yaitu :

Terdapat 6 buah simpul
Terdapat 5 buah sisi
Terdapat 3 simpul brderajat satu, 2 simpul berderajat dua, 1 simpul berderajat 1 (seharusnya berderajat 3)”
^_^

20 11 2012
adminmathbest

Wah terima kasih ya atas koreksinya..lgsg kita koreksi nih..maklumlah, human error🙂 sering2 mampir ya🙂

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s




%d blogger menyukai ini: