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

Video ini membahas parameter isomorfisma graf dengan menjelaskan konsep penting seperti ordernya, size-nya, dan degree sequence. Dua graf dengan degree sequence yang sama belum tentu isomorfis, seperti contoh G1 dan G2 yang berbeda meskipun memiliki derajat yang serupa. Terdapat sifat khusus graf isomorfis, misalnya jika G bipartit, maka G aksen juga bipartit. Pemeriksaan isomorfisma graf melibatkan pengecekan banyaknya simpul, degree sequence, dan fitur khusus seperti subgraf berbentuk lingkaran. Algoritma untuk mencari graf-graf isomorfis masih sulit, namun penting untuk aplikasi seperti dalam kimia untuk memahami struktur molekul yang sama namun berbeda representasi grafiknya.

Jadi dari dua graf yang isomorfis tadi, maka kita bisa lihat bahwa ordernya, ukuran atau banyaknya simpulnya,

size-nya atau ukurannya itu banyaknya busur dan derajat simpulnya itu sama semua.

Dan kalau kita lihat degree sequence itu barisan dari derajat-derajat dari simpul-simpul di graf itu, itu juga sama.

Sekarang pertanyaannya, kalau kita melihat degree sequence-nya atau barisan derajat-nya itu sama,

itu grafnya itu sebetulnya isomorfis tidak?

Kita lihat di sini, saya punya dua graf G1 dengan G2 yang bentuknya kalau dilihat dari derajat-nya saja,

kita bisa membentuk barisan derajat-nya itu, ada 2 yang derajat-nya 1, ada 2 yang derajat-nya 2,

dan ada yang berajat 1 itu ada 3, ada 2 yang berajat 2, dan 1 berajat 3.

Untuk G2 juga sama, ada 3 yang berajat 1, ada 2 yang berajat 2, kemudian ada 1 berajat 3.

Tapi kita bisa lihat bahwa di sini dua graf ini berbeda, jadi kita tidak bisa mendapatkan isomorfisma antara G1 dengan G2.

Jadi ini dua graf yang degree sequence-nya sama, tapi dia tidak isomorfis.

Ada beberapa sifat atau jenis graf yang kita bisa dapatkan dari graf yang isomorfis, jadi di sini ada teoremanya.

Kalau G dan G aksen itu isomorfis, nanti kalau G-nya bipartit, G-aksennya juga pasti bipartit dan sebaliknya.

Begitu juga kalau G-nya terhubung, maka G-aksen itu juga terhubung.

Terhubung itu kalau digambar itu nyambung, tapi ada konsep terhubung yang nanti akan kita bahas tersendiri.

Jadi kalau terkait dengan degree sequence, kalau saya punya graf 2C3, ini graf yang tidak terhubung.

Kalau dicari degree sequence-nya, ini ada 2-nya 6 kali karena 6 simpulnya itu berajat 2.

Tapi kalau kita punya C6, maka kita punya graf yang terhubung yang degree sequence-nya juga 2-2-2 6 kali.

Jadi degree sequence-nya sama, tapi graf-nya sangat berbeda, satu terhubung, satu tidak terhubung.

Jadi di sini GK dan hanya GK, jadi kalau mau isomorfis itu yang terhubung pasti sama yang terhubung, yang tak terhubung juga sama yang tak terhubung.

Jadi dengan sifat-sifat itu tadi, pertama kita memeriksa banyaknya simpul sama banyaknya busur sama atau enggak.

Terus kita lihat degree sequence-nya dan kalau tiga hal itu sama, itu baru menjanjikan pemeriksaan berikutnya.

Kalau ada satu saja yang beda, berarti kita enggak usah meneruskan karena itu pasti tidak isomorfis.

Terus kita lihat sifat-sifat atau fitur khusus seperti apakah ada subgraf yang berbentuk lingkaran, misalnya ada subgraf berbentuk C3 enggak di situ.

Kalau ada berarti di graf satunya lagi itu juga ada graf atau subgraf yang berbentuk lingkaran.

Jadi ini adalah dua graf yang mau kita cek, apakah dia isomorfis atau enggak.

Ada yang pendan enggak? Ada di sini C sama tiga di sini.

Kemudian kita lihat yang B, B ini berderajat dua, yang berderajat dua berarti di sini kan harus dipasangkan dengan yang berderajat dua.

Di gambar yang kiri yang misalnya di sini namanya G, yang berderajat dua itu ada dua, si B sama E.

Tapi si H ini di sini cuma ada satu yang berderajat dua, yang lainnya itu berderajat tiga atau satu.

Sehingga kita tidak akan bisa mendapatkan isomorfisma di antara kedua graf yang diberikan di sini.

Ini adalah contoh lain misalnya kalau mau mengecek apakah dua graf berikut isomorfis.

Ini kita lihat, saya tidak akan memberikan sampai bentuk isomorfis atau tidak, tapi cara mengeceknya adalah

ini dua graf ini ada loopnya, berarti si tiga ini harus dihubungkan kalaupun dipasangkan ke E.

Jadi kita lihat di sini yang ada loop itu di luar loopnya itu ada di sini ada lima, di sini juga ada lima.

Kemudian dia bertetangga dengan di sini semua simpul.

Sekarang tetangganya yang derajatnya dua di sini, dia akan mempunyai tetangga yang derajatnya empat.

Dari si E di sini yang punya derajat dua itu adalah A sama D, yang bertetangga dengan yang derajat empat adalah D.

Berarti di sini kalau mau dipasangkan si dua ini harus dipasangkan sama si D dan seterusnya.

Jadi kita lihat apa sifat-sifat khususnya.

Kalau yang bagian B itu juga sama, jadi di sini ada dua yang berderajat tiga berarti kita harus pasangkan ke sini kalau memungkinkan.

Kemudian yang lain yang berderajat dua ini kita akan pasangkan ke yang berderajat dua juga.

Ini bentuk bipartid, jadi kalau yang ini memang isomorfis.

Sekarang kalau kita punya graf tidak ada labelnya, apakah kedua graf berikut isomorfis?

Untuk memeriksa kita kasih label saja, di sini kasih label ABCDEF, kemudian di sini mau dikasih nama yang pakai huruf besar mungkin ABCDEF.

Habis itu kita periksa lagi sifat-sifatnya, yang berderajat empat ada berapa,

ini graf teratur atau bukan, ada cycle tiga atau tidak, dan seterusnya.

Jadi kita cek sifat-sifat khususnya, nanti kalau oke baru kita periksa apakah kita bisa mementuk fungsi satu-satu

antara himpunan simpul graf pertama dengan yang kedua,

kemudian apakah kalau di graf pertama ada busur, nanti hasil petanya juga akan membentuk busur.

Kenapa kita mesti sibuk memeriksa apakah dua graf itu isomorfis atau tidak?

Soalnya meriksa juga tidak gampang, belum ada algoritma yang bisa mencari graf-graf yang isomorfis semuanya,

tapi kalau untuk memeriksa dua graf itu isomorfis atau tidak sudah ada.

Aplikasinya itu antara lain kalau di kimia, molekul itu kalau dipoton secara sekilas,

dia bergerak, jadi posisinya itu bisa beda-beda, tapi itu kan menyatakan molekul yang sama,

jadi kalau digambarkan dalam bentuk graf molekulnya itu nanti dia akan membentuk graf yang digambarkannya beda.