Graf Isomorfik dan Graf Planar

 Definisi Graf Isomorfik

Isomorfisme graf adalah fenomena keberadaan graf yang sama dalam lebih dari satu bentuk yang disebut graf isomorfik.

Graf G dan H bersifat isomorfik jika terdapat struktur yang mempertahankan korespondensi satu-satu antara simpul dan sisi. Dengan kata lain, kedua graf tersebut hanya berbeda nama sisi dan simpulnya saja, tetapi secara struktural ekuivalen

Syarat dan Kondisi Dua Graf Isomorfik

Untuk setiap dua grafik menjadi isomorfik, 4 kondisi berikut harus dipenuhi,yaitu:

• Jumlah simpul pada kedua graf harus sama.
• Jumlah rusuk pada kedua graf harus sama.
• Urutan derajat kedua grafik harus sama.
• Jika sebuah siklus dengan panjang k dibentuk oleh simpul { v1 , v2 , ….. , vk } dalam satu graf, maka sebuah siklus dengan panjang k yang sama harus dibentuk oleh simpul { f(v1) , f(v2) , ….. , f(vk) } di grafik lain juga.

4 kondisi di atas hanyalah kondisi yang diperlukan untuk setiap dua grafik menjadi isomorfik. Mereka sama sekali tidak cukup untuk membuktikan tetapi hanya menunjukan bahwa kedua grafik tersebut mungkin isomorfik. Jika keempat syarat tersebut memenuhi, maka tidak dapat dikatakan bahwa graf tersebut pasti isomorfik. Namun, jika ada syarat yang dilanggar, maka dapat dikatakan bahwa graf tersebut pasti tidak isomorfik.

Kondisi berikut adalah kondisi yang cukup untuk membuktikan dua graf isomorfik. Jika salah satu dari kondisi ini memenuhi, maka dapat dikatakan bahwa grafik tersebut pasti isomorfik.

• Dua graf dikatakan isomorfik jika dan hanya jika graf komplemennya isomorfik.
• Dua graf dikatakan isomorfik jika matriks ketetanggaannya sama.
• Dua graf dikatakan isomorfik jika sub-graf yang bersesuaian diperoleh dengan menghapus beberapa simpul dari satu graf dan gambar yang bersesuaian pada graf lainnya adalah isomorfik.

Definisi Graf Planar dan Graf Bidang (Planar Graf)

Suatu graf dikatakan planar jika graf tersebut dapat digambarkan pada suatu bidang tanpa ada sisi yang bersilangan. Gambar seperti itu disebut representasi planar graf.

Ketiga gambar diatas adalah graf K4 dan isomorfiknya merupakan contoh graf planar. Jika diperhatikan graf dikatakan planar jika salah satu isomorfiknya merupakan graf planar. Graf isomorfik yang digambarkan dengan sisi tidak menyilang satu sama lain disebut graf bidang (plane graph). Contoh Graf bidang adalah gambar ke 2 dan 3 dari K4.

Wilayah (Region) pada Graf Planar

Ketika graf planar digambar tanpa sisi-sisi yang bersilangan, sisi-sisi dan simpul-simpul dari graf tersebut membagi bidang menjadi daerah-daerah. Kami akan menyebut setiap wilayah sebagai wajah termasuk diluar graf. Graf K4 terdapat 4 wilayah. Wilayah pada planar disibolkan dengan f

Jumlah wajah tidak berubah bagaimanapun Anda menggambar grafik (selama Anda melakukannya tanpa tepi bersilangan), jadi masuk akal untuk menganggap jumlah wajah sebagai properti grafik planar.

Ada hubungan antara jumlah simpul (v), jumlah sisi (e) dan jumlah daerah (f) pada graf planar yang terhubung.

Untuk setiap graf planar terhubung dengan v simpul, tepi e dan wajah f, kita memiliki v−e+f=2 atau f=2-v+e.

Selain itu terdapat teorema lain yaitu:

Jika G adalah graf planar terhubung dengan e sisi dan v simpul, di mana v≥3, maka e≤3v-6. Juga G tidak dapat memiliki titik yang berderajat lebih dari 5.