Sebelum kita membahas tentang graph isomorfik ada baiknya kita terlebih dahulu mengerti tentang garph.
- 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.
Graph Isomorfik
Dalam geometri, dua gambar disebut kongruen jika keduanya mempunyai sifat-sifat geometri yang sama. Maka dengan cara yang sama, dua graf disebut isomorfis jika keduanya menunjukkan "bentuk" yang sama, kedua graph tersebut hanya berbeda dalam hal pemberian label titik dan garisnya saja.
Syarat dua buah graph dikatakan isomorfik, yaitu :
- Memiliki jumlah simpul yang sama
- Memiliki jumlah garis yang sama
- Memiliki derajat yang sama dari simpul-simpulnya
Catatan : apabila dua graph yang berbeda tidak memiliki salah satu dari syarat diatas sudah pasti kedua graphtersebut tidak isomorfis, tetapi walaupun kedua graph tersebut memiliki seluruh syarat diatas belum tentu juga keduanya isomorfis.
Ada 2 graf yang memenuhi ketiga syarat tersebut, tetapi keduanya tidak isomorfis. Sebagai contoh adalah graf G dan G' pada Gambar di bawah ini :
Dalam G, satu-satunya titik yang berderajat 3 adalah titik x. Titik x dihubungkan dengan 2 titik lain yang berderajat 1 (titik y dan z). Sebaliknya, dalam G', satu-satunya titik yang berderajat 3 adalah c. Satu-satunya titik berderajat 1 yang dihubungkan dengan c hanyalah titik d, sehingga G tidak mungkin isomorfis dengan G'.
Untuk itu ada beberapa syarat tambahan yang wajib kita penuhi apabila ingin menunjukkan apakah kedua graph tersebut isomorfik atau tidak, yaitu :
- Graf sederhana G1 = (V1, E1) dan G2 = (V2, E2) adalah isomorfis jika ada sebuah fungsi bijektif (fungsi satu-ke-satu dan on to) dari V1 ke V2 dengan sifat kepemilikan bahwa jika a dan b adalah tetangga pada G1 jika dan hanya jika f(a) dan f(b) adalah tetangga di G2, untuk seluruh a dan b di V1.
- 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.
- G1 dan G2 adalah isomorfis jika simpul-simpulnya dapat diurut dengan cara sedemikian rupa sehingga matriks adjacensy MG1 dan MG2 adalah identik.
Agar lebih mudah memahami apakah dua graf isomorfik atau tidak, berikut adalah contoh cara menunjukan dua graf yang isomorfik.
CONTOH 1 :
Periksa apakah kedua graf tersebut isomorfik? Jika ya, tentukan simpul-simpul yang saling berkorespondensi antara G1 dan G2
Jawab :
Ya, kedua graf tersebut adalah isomorfik. Terlihat graf tersebut memuat simpul dimana setiap simpulnya masing-masing berderajat tiga. Simpul yang saling berkorespondensi dari kedua graf tersebut adalah :
simpul u1 dengan simpul v1
simpul u2 dengan simpul v3
simpul u3 dengan simpul v5
simpul u4 dengan simpul v6
simpul u5 dengan simpul v4
simpul u6 dengan simpul v2
Pada dua graf yang isomorfik, kedua graf tersebut memiliki matriks ketetanggaan yang sama, tentunya setelah matriks yang berkorespondensi diurutakan dalam urutan yang sama.
Perhatikan matriks ketetanggaan dari kedua graf tersebut. Dibawah ini adalah matriks ketetanggaan dari graf G1 dan G2:
Terlihat bahwa kedua graf tersebut memiliki matriks ketetanggaan yang sama, yaitu MG1 = MG2.
Lintasan dan Sirkuit Euler
Lintasan dan Sirkuit Euler
Lintasan Euler ialah lintasan yang melalui tiap sisi dalam graf tepat sekali
Sirkuit Euler ialah sirkuit yang melalui tiap sisi dalam graf tepat satu kali
Graf yang mempunyai sirkuit Euler disebut graf Euler, sedang graf yang mempunyai lintasan Euler disebut semi Euler
Contoh
a. Apakah Ada Lintasan Euler ?
b. Apakah ada sirkuit Euler ?
Jawab
a. ADA lintasan euler dengan lintasan :
a,b,c,d,e,f,g,b,d,f,a,g
b. Tidak ADA sirkuit Euler.
a. Apakah ada lintasan Euler ?
b. Apakah ada Sirkuit Euler ?
Jawab
a. ADA lintasan Euler dengan lintasan :
a,b,c,d,e,c,h,b,f,h,e,f,g,a
b. Ada sirkuit euler karena berawal dari simpul a dan berakhir di simpul a
Teorema Untuk Lintasan dan sirkuit euler
Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan mempunyai 2 buah simpul berderajat ganjil atau tidak ada simpul berderajad ganjil samasekali
Graf tak berarah G adalah graf Euler jika hanya jika setiap simpul berderajad genap
Graf berarah G memiliki sirkuit Euler jika hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajad masuk dan derajad keluar sama kecuali 2 simpul, yang pertama memiliki derajad keluar satu lebih besar dari derajad masuk, dan yang kedua memiliki derajad masuk satu lebih besar dari derajad keluar
