Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas konsep isomorfisma graf, di mana dua graf dianggap sama jika memiliki himpunan simpul dan busur yang identik meskipun gambarnya berbeda. Isomorfisma terjadi ketika terdapat fungsi satu-satu antara himpunan simpul graf pertama dan kedua. Dalam contoh graf yang berbeda namun isomorfis, perlu dipastikan bahwa pasangan simpul memiliki keterkaitan yang sama. Validasi isomorfisma dilakukan dengan memeriksa keberadaan busur pada setiap pasangan simpul. Selain itu, syarat isomorfisma antara dua graf juga melibatkan kesamaan jumlah simpul dan busur, serta kesamaan derajat simpul di kedua graf tersebut.

Pada saat membahas tentang graf lingkaran, waktu itu saya sudah memperlihatkan bahwa si C4 itu bisa digambarkan dalam bentuk yang berbeda.

Yang pertama adalah yang gambar seperti kotak begitu dengan empat simpul bisa juga kita lihat atau direpresentasikan dengan gambar yang berbeda.

Konsep ini kita sebut dua graf ini sama tapi gambarnya atau representasinya berbeda itu kita sebut sebagai isomorfisma antara graf.

Jadi kalau kita lihat dua graf itu dianggap sama jika punya himpunan simpul dan busur yang sama meskipun gambarnya berbeda.

Jadi kalau kita lihat ini yang di sebelah kiri adalah K33 gitu ya graf lengkap 33 itu bisa digambarkan dengan graf yang di sebelah kanan.

Ini bukan graf roda ya karena di tengah-tengah ini sebetulnya tidak ada simpulnya.

Jadi kita bisa menggambarkan dalam berbagai bentuk tapi asal himpunan simpul dan himpunan busurnya sama itu dua graf itu akan kita sebut sebagai graf yang sama.

Nah secara matematis dua graf yang sama tapi bentuk gambarnya berbeda tadi itu kita sebut isomorfis

kalau ada fungsi satu-satu dari himpunan simpul graf yang pertama ke himpunan simpul yang kedua disini dinotasikan sebagai V dan V aksen.

Sehingga untuk setiap simpul-simpul di V itu UV-nya itu kalau ada di graf yang pertama jadi UV-nya itu anggota E,

maka F U F V-nya itu ada di E aksen, ada di graf yang kedua.

Begitu juga sebaliknya, jadi ini bolak-balik.

F-nya ini kita sebut sebagai isomorfisma antara si graf G dengan graf G aksen.

Jadi kita lihat disini contohnya kita punya dua graf yang gambarnya itu berbeda tapi sebetulnya ini menyatakan graf yang sama.

Kenapa? Kita lihat disini himpunan simpulnya itu ada 5.

Nah sekarang kita harus membuat fungsi satu-satu dari himpunan V1, V2, V3, V4, V5 di gambar yang pertama ke U1, U2, U3, U4, dan U5.

Nah sekarang kita perhatikan kalau kita mau membuat pemetaan si V1 ke U,

kita harus lihat bahwa ini kan kaitannya kalau ada busur di graf yang pertama harus ada busur juga di graf kedua.

Jadi kita lihat disini degree-nya, degree-nya 3 artinya V1 terhubung ke 3 simpul yang lain.

Berarti kita harus pasangkan ke simpul yang juga degree-nya 3.

Karena kalau kita misalkan pasangkan dengan U5 udah jelas nggak jalan,

karena nanti busur yang ada di graf yang sebelah kiri si G-nya itu tidak ada di G-aksen-nya.

Jadi ini nggak mungkin kalau dipasangkan ke simpul yang derajatnya berbeda.

Nah sekarang kita lihat di graf yang kedua itu ada U1, kemudian disini U2 yang derajatnya adalah 3.

Berarti kemungkinan V1 itu dipetakannya ke U1 atau ke U3.

Terus kita lihat si V1 tetangganya, V1 itu tetangganya ada V2, V4, V5.

Jadi tetangganya itu ada yang derajatnya 2, ada yang derajatnya 3.

Kita lihat disini U1 itu ada yang derajatnya 3 dan juga ada yang derajatnya 2.

Jadi hampir sama kita bisa coba pasangkan dari V1 ke U1.

Jadi disini kita punya V1, V2, V3, V4, V5.

Kita harus pasangkan satu-satu tapi dengan catatan nanti si busurnya juga harus terkait.

Jadi misalnya saya pasangkan V1 dengan U1.

Terus si U2 disini ini derajatnya 3 berarti dia pasangannya ke V4.

Nah sekarang si V5 itu tetangganya V1 sama V4.

Nah disini yang tetangganya tadi pasangannya U1, U5 itu siapa?

U4 berarti disini V5 itu dipasangkan dengan U4.

Berikutnya lagi V2, V2 itu tetangganya V1 tapi bukan tetangganya V4.

Berarti kita cari yang tetangganya U1 tapi bukan tetangganya U2.

Jadi disini kita lihat U3 jadi V2 itu dipasangkan ke U3.

Nah nanti V3 tinggal sisanya ya dipasangkan ke U5.

Sekarang kita sudah dapat fungsi satu-satu tapi ini belum menjamin dia isomorfisma.

Kita harus cek dulu apakah kalau ada busur di G maka hasil petanya juga ada busurnya.

Jadi misalnya disini kita punya V1, V2 apakah FV1 dan FV2 itu ada busurnya?

Jadi disini kita lihat U1 ke U3 itu ada busur nggak?

Kita lihat disini ya U1 dengan U3 ternyata ada busur jadi oke.

Dan itu harus kita periksa di setiap pasangan disini.

Jadi disini ada 6 busur berarti kita harus cek 6-6 nya.

Jadi kalau itu terpenuhi maka kita bilang 2 graf itu isomorfisma.

Untuk mengecek apakah 2 graf isomorfisma itu kan nggak mudah.

Jadi sekarang kita lihat dulu sebelum kita periksa tadi di petakan segala macam

itu kita lihat banyaknya simpul sama banyaknya busur sama nggak?

Kalau udah nggak sama ya udah nggak usah diperiksa.

Jadi itu syarat pertama karena akibat di isomorfisma itu

banyaknya simpul dengan banyaknya busur harus sama.

Terus sifat yang berikutnya adalah derajat simpul-simpul yang di G

itu harus sama dengan derajat simpul-simpul di G aksen.

Jadi kita lihat ini di graf G nya kita punya 3 simpul berajat 2 dan 2 simpul berajat 3.

Maka di G aksen juga harus sama kita punya 3 simpul berajat 2 dan 2 simpul berajat 3.