Graf sederhana G1 = (V1, E1) dan G2 = (V2, E2) disebut isomorfis jika ada sebuah fungsi bijektif (satu-ke-satu dan onto) dari V1 ke V2 dengan sifat bahwa a bertetangga dengan b pada G1 jika dan hanya jika f(a) bertetangga dengan f(b) pada G2, untuk seluruh a dan b pada V1.
Fungsi f seperti itu disebut isomorfisme. Dengan kata lain, G1 dan G2 adalah isomorfis jika simpul-simpulnya dapat diurutkan dengan suatu cara sedemikian rupa sehingga matriks kedekatan MG1 dan MG2 adalah identik. Secara visual, dua buah graf, G1 dan G2, isomorfis jika graf-graf tersebut dapat disusun dengan suatu cara sedemikian rupa sehingga tampilannya identik (tentu tanpa merubah ketetanggaan).
Menentukan dua buah graf tidak isomorfis lebih mudah dibandingkan dengan menentukan apakah dua buah graf isomorfis. Untuk dua buah graf sederhana dengan masing-masing simpulnya berjumlah n buah, maka akan ada n! kemungkinan isomorfisme yang harus diperiksa. Untuk itu kita dapat memeriksa invarian, yaitu, sifat yang harus dimiliki oleh dua buah graf sederhana yang isomorfis. Keduanya haruslah :
• memiliki jumlah simpul yang sama, dan • jumlah garis hubung yang sama , dan
• derajat dari simpul-simpulnya sama.
Untuk dapat lebih jelasnya, Anda dapat mendownload disini.
Postingan
Tidak ada komentar:
Posting Komentar
Terima kasih atas komentar Anda :)