TI Politala Matdis 1C

Graph Isomorfik

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 :

1. Memiliki jumlah simpul yang sama
2. Memiliki jumlah garis yang sama
3. 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 :

1. Graf sederhana G₁ = (V₁, E₁) dan G₂ = (V₂, E₂) adalah  isomorfis jika ada sebuah fungsi bijektif (fungsi satu-ke-satu dan on to) dari V₁ ke V₂ dengan sifat kepemilikan bahwa jika a dan b adalah tetangga pada G₁ jika dan hanya jika  f(a) dan f(b) adalah tetangga di G₂, untuk seluruh  a dan b di V₁.
2. 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₂.
3. G₁ dan G₂ adalah isomorfis jika simpul-simpulnya dapat diurut  dengan cara sedemikian rupa sehingga matriks adjacensy M_G1 dan M_G2 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 G₁ dan G₂

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 G₁ dan G₂:

Terlihat bahwa kedua graf  tersebut  memiliki  matriks  ketetanggaan  yang  sama,   yaitu  M_G1 =  M_G2.

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