Merepresentasikan Graf Dan Graf Isomorphism

MEREPRESENTASIKAN GRAF DAN GRAF ISOMORPHISM Nama kelompok 3 :

1. Rika Aprilianti 2. Sindy Wahyuningrum 3. Saika Jalqrwati 4. Rifky Andrian

REPRESENTASI GRAF • Ada banyak cara bermanfaat untuk merepresentasikan graf. Salah satu cara untuk merepresentasikan graf tanpa banyak sisi adalah dengan mencantumkan semua tepi graf ini. Cara lain untuk merepresentasikan graf tanpa tepi ganda adalah dengan menggunakan adjacency list, yang menentukan simpul yang berdekatan dengan setiap titik dari grafik.

CONTOH SOAL ADJACENCY LIST • Contoh : • Gunakan adjacency list untuk

menggambarkan grafik sederhana yang diberikan pada Gambar 1 • Solusi : • Tabel 1 mencantumkan simpul-simpul yang berdekatan dengan masing-masing simpul grafik.

MATRIKS ADJACENCY • Menjalankan algoritma graf menggunakan representasi graf berdasarkan daftar sisi, atau daftar kedekatan, dapat menjadi rumit jika ada banyak sisi dalam graf. Untuk menyederhanakan komputasi, graf dapat direpresentasikan menggunakan matriks. • Misalkan G = (V, E) adalah graf sederhana di mana | V | = n. Misalkan simpul-simpul dari G terdaftar secara acak sebagai 𝑣1 , 𝑣3 , . . ., 𝑣𝑛 . Matriks adjacency A dari G, sehubungan dengan daftar ini dari simpul, adalah n x n nol-satu matriks dengan 1 sebagai entri (i, j) th ketika 𝑣𝑖 dan 𝑣𝑗 berdekatan, dan 0 sebagai nya (i , j) entri ketika mereka tidak berdekatan. Dengan kata lain, jika matriks adjacency A=[ 𝑎𝑖𝑗 ], • 𝑎𝑖𝑗

1 , 𝑗𝑖𝑘𝑎 [𝑣𝑖 , 𝑣𝑗 ] 𝑎𝑑𝑎𝑙𝑎ℎ 𝑡𝑒𝑝𝑖 𝑑𝑎𝑟𝑖 𝐺 ቊ 0, 𝑠𝑒𝑏𝑎𝑙𝑖𝑘𝑛𝑦𝑎

CONTOH MATRIKS ADJACENCY • Contoh : • Gunakan matriks adjacency untuk merepresentasikan graf yang ditunjukkan pada Gambar 3.

• Solusi :

MATRIKS BERSISIAN ATAU INCIDENCY MATRIKS • Cara umum lain untuk merepresentasikan graf adalah dengan menggunakan matriks bersisian. Biarkan G = (V, E) menjadi graf tidak terarah. Misalkan 𝑣1 , 𝑣2 , . . . , 𝑣𝑛 adalah simpul dan 𝑒1 , 𝑒2 , . . . , 𝑒𝑚 adalah tepi dari G. Kemudian, matriks kejadian sehubungan dengan pemesanan V dan E ini adalah matriks n × m • M = [ 𝑚𝑖𝑗 ], di mana 1, 𝐾𝑒𝑡𝑖𝑘𝑎 𝑒𝑑𝑔𝑒 𝑒𝑗 𝑡𝑒𝑟𝑗𝑎𝑑𝑖 𝑑𝑒𝑛𝑔𝑎𝑛 𝑣𝑖 • 𝑚𝑖𝑗 ቊ 0, 𝑠𝑒𝑏𝑎𝑙𝑖𝑘𝑛𝑦𝑎

CONTOH MATRIKS BERSISIAN • Contoh : • Gunakan matriks bersisian untuk merepresentasikan graf yang ditunjukkan pada Gambar 6. • Solusi :

• Matriks insiden juga dapat digunakan untuk mewakili beberapa sisi dan loop. Beberapa sisi diwakili dalam matriks kejadian menggunakan kolom dengan entri yang identik, karena tepi ini adalah insiden dengan pasangan simpul yang sama. Loop diwakili menggunakan kolom dengan tepat satu entri sama dengan 1, sesuai dengan simpul yang terjadi dengan loop ini.

GRAF ISOMORPHISM • Grafik sederhana G1 = (V1, E1) dan G2 = (V2, E2) adalah isomorfik jika ada satu-ke-satu dan ke fungsi f dari V1 ke V2 dengan properti yang a dan b berdekatan di G1 jika dan hanya jika f (a) dan f (b) berdekatan dalam G2, untuk semua a dan b di V1. Fungsi seperti itu disebut f sebuah isomorfisme. Dua grafik sederhana yang bukan isomorfis disebut nonisomorfik Dengan kata lain, ketika dua grafik sederhana isomorfis, ada korespondensi satu-kesatu antara simpul dari dua grafik yang mempertahankan hubungan kedekatan. Isomorfisme dari grafik sederhana adalah hubungan ekivalensi.

CONTOH GRAP ISOMORPHISM • Contoh : • Tunjukkan bahwa grafik G = (V, E) dan H = (W, F), ditampilkan pada Gambar , adalah isomorfik. • Solusi : • : Fungsi f dengan f (𝑢1 ) = 𝑣1 , f (𝑢2 ) = 𝑣4 , f (𝑢3 ) = 𝑣3 , dan f (𝑢4 ) = 𝑣2 adalah satu-ke-satu korespondensi antara V dan W. Untuk melihat bahwa korespondensi ini mempertahankan kedekatan, perhatikan bahwa simpul yang berdekatan di G adalah u1 dan u2, u1 dan u3, u2 dan u4, dan u3 dan u4, dan masing-masing pasangan f (u1) = v1 dan f (u2) = v4, f (u1) = v1 dan f (u3) = v3, f (u2) = v4 dan f (u4) = v2, dan f (u3) = v3 dan f (u4) = v2 terdiri dari dua simpul yang berdekatan di H.

MENENTUKAN APAKAH DUA GRAF SEDERHANA ADALAH ISOMORFIK • Syarat dua buah graf dikatakan isomorfik, yaitu : • Memiliki jumlah simpul yang sama. • Memiliki jumlah garis yang sama. • Memiliki derajat yang sama dari simpul-simpulnya. • Kesimpulan : • Apabila dua graf yang berbeda tidak memiliki salah satu syarat diatas sudah pasti keduanya graf tersebut tidak isomorfik, tetapi walaupun keduanya grafik tersebut memiliki seluruh syarat diatas belum tentu juga keduanya isomorfik.

CONTOH • Tunjukkan bahwa graf yang ditampilkan pada Gambar 9 tidak isomorfik. • Solusi : • keduanya G dan H memiliki lima simpul dan enam sisi. Namun, H memiliki titik puncak derajat satu, yaitu, e, sedangkan G tidak memiliki simpul derajat satu. Oleh karena itu G dan H tidak bersifat isomorfik.

ALGORITMA UNTUK GRAF ISOMORFISMA • Algoritma terbaik yang diketahui untuk menentukan apakah dua graf isomorfik memiliki kompleksitas waktu kasus terburuk eksponensial (dalam angka simpul dari grafik). Namun, algoritma kompleksitas waktu rata-rata linier diketahui yang memecahkan masalah ini, dan ada beberapa harapan, tetapi juga skeptisisme, bahwa suatu algoritma dengan kompleksitas waktu kasus polinomial terburuk untuk menentukan apakah dua graf adalah isomorfik dapat ditemukan. • Algoritma praktis untuk menentukan apakah dua grafik bersifat isomorfik ada untuk grafik yang dibatasi di berbagai cara, seperti ketika derajat maksimum simpul kecil. Masalah penentuan apakah dua grafik adalah isomorfik adalah kepentingan khusus karena ini adalah salah satu dari hanya sedikit masalah.

APLIKASI DARI GRAF ISOMORFISMA • Kimiawan menggunakan multigraf, yang dikenal sebagai grafik molekuler, untuk memodelkan senyawa kimia. Dalam ini graf, simpul mewakili atom dan ujung melambangkan ikatan kimia antara atom-atom ini. Dua isomer struktural, molekul dengan rumus molekul identik tetapi dengan atom berikatan berbeda, memiliki grafik molekuler non-ekomorfik. Ketika senyawa kimia yang berpotensi baru disintesis, database grafik molekuler diperiksa untuk melihat apakah grafik molekuler dari senyawa itu sama dengan yang sudah dikenal.

TERIMA KASIH