Dua buah graf dikatakan isomorfis jika mereka mempunyai struktur yang
sama dan kebanyakan, mereka berbeda cara pemberian label titik-titik dan sisi-
sisinya, atau cara menggambarkannya. Untuk memperjelas maksud kalimat terse-
but, kita akan mendefinisikan dua graf G1 dan G2 isomorfiss jika ada suatu fungsi
Á : V (G) ¡! V (G) sedemikian hingga uv 2 (Gi) () Á(u)Á(v) 2 E(G2). Fungsi
Á dinamakan sebuah fungsi isomorfis. Jika dua graf G1 dan G2 isomor¯s, maka
dituliskan G1»=G2.Sampai saat ini untuk menentukan apakah dua graf G1 dan
G2 isomor¯s atau tidak belum ada teori yang dapat dipakai . Tetapi, jika graf
G1 dan G2 isomorfis, maka kedua graf tersebut selalu memenuhi 4 syarat sebagai
berikut :
1. jumlah titik G1 = jumlah titik G2 (jumlah titik yang sama),
2. jumlah sisi G1 = jumlah sisi G2 (jumlah sisi yang sama),
3. jumlah sisi yang mempunyai derajat tertentu dalam graf G1 dan G2 sama
(mempunyai jumlah titik yang sama berderajat tertentu),
sama dan kebanyakan, mereka berbeda cara pemberian label titik-titik dan sisi-
sisinya, atau cara menggambarkannya. Untuk memperjelas maksud kalimat terse-
but, kita akan mendefinisikan dua graf G1 dan G2 isomorfiss jika ada suatu fungsi
Á : V (G) ¡! V (G) sedemikian hingga uv 2 (Gi) () Á(u)Á(v) 2 E(G2). Fungsi
Á dinamakan sebuah fungsi isomorfis. Jika dua graf G1 dan G2 isomor¯s, maka
dituliskan G1»=G2.Sampai saat ini untuk menentukan apakah dua graf G1 dan
G2 isomor¯s atau tidak belum ada teori yang dapat dipakai . Tetapi, jika graf
G1 dan G2 isomorfis, maka kedua graf tersebut selalu memenuhi 4 syarat sebagai
berikut :
1. jumlah titik G1 = jumlah titik G2 (jumlah titik yang sama),
2. jumlah sisi G1 = jumlah sisi G2 (jumlah sisi yang sama),
3. jumlah sisi yang mempunyai derajat tertentu dalam graf G1 dan G2 sama
(mempunyai jumlah titik yang sama berderajat tertentu),
4. Graf G1 dan G2 mempunyai girth(panjang siklus terpendek) yang sama.
Keempat syarat tersebut belum cukup menjamin bahwa kedua graf isomorfis. Untuk menunjukkan bahwa kedua graf G1 dan G2 isomorfis, maka dapat
dilihat dari matriks ketetanggaan kedua graf tersebut sama. Keisomorfisan graf
dapat dilihat pada Gambar 2.16. Graf G1 dan G3 tidak isomorfis karena G3 men-
gandung siklus dengan panjang 3 sementara G1 tidak mengandung siklus dengan
panjang 3 dan tidak mungkin mengandung pemetaan satu-satu dari G1 ke G3.
Keempat syarat tersebut belum cukup menjamin bahwa kedua graf isomorfis. Untuk menunjukkan bahwa kedua graf G1 dan G2 isomorfis, maka dapat
dilihat dari matriks ketetanggaan kedua graf tersebut sama. Keisomorfisan graf
dapat dilihat pada Gambar 2.16. Graf G1 dan G3 tidak isomorfis karena G3 men-
gandung siklus dengan panjang 3 sementara G1 tidak mengandung siklus dengan
panjang 3 dan tidak mungkin mengandung pemetaan satu-satu dari G1 ke G3.
