Matematika Diskrit

GRAF

ISOMORFIK

Formal education will make you a living.

SELF EDUCATION will make you a fortune.

- Jim Rohn

   

A. Definisi

         Dua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-sati antara simpul-simpul keduanta dan antara sisi-sisi keduanya sedemikian sehingga jika sisi e bersisihan dengan simpul u da v di G1, maka sisi e' yang berkorespondensi di G2 juga harus bersisihan dengan simpul u' dan v' di G2.

 

 

          Dua buah graf yang isomorfik adalah graf yang sama kecuali penamaan simpul dan sisinya saja yang berbeda.

        Dari definisi siomorfik dapat disimpulkan dua buah graf isomorfik memenuhi ketiga syarat :

    1. Mempunyai jumlah simpul yang sama.

    2. Mempunyai jumlah sisi yang sama.

    3. Mempunyai jumlah simpul yang sama berderajad tertentu.

         Ketiga syarat di atas belum cukup menjamin keisomorfikan. Pemeriksaan secara visual masih tetap diperlukan.

          Untuk memperlihatkan bahwa dua graf isomorfik, kita dapat menunjukkan bahwa matriks ketetanggan kedua graf itu sama.

 B. Graf Planar dan Graf Bidang

          Graf yang dapat di gambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan) disebut graf planar, jika tidak maka di sebut graf tidak planar.

 

 C. Graf Bidang

            Yakni, graf planar yang digambarkan dengan sisi-si yang tidak saling berpotongan.

            Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face). Jumlah wilayah pada graf bidang dapat dihitung dengan mudah.

 D. Rumus Euler

           Jumlah wilayah (f) pada graf planar sederhana juga dapat dihitung dengan rumus Euler sebagai berikut :

n - e + f = 2

atau

f = e - n + 2

          yang dalam hal ini :

                 e = jumlah sisi

                 n = jumlah simpul

E. Teorema Kuratowski

 

             Dalam literatur tentang graf, dikenal 2 buah graf tidak planar khusus, yaitu graf Kuratowski.

      1. Graf Kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah simpul.

      2. Graf Kuratowski kedua, yaitu graf terhubung teratur dengan 6 buah simpul dan 9 

          buah sisi.

             Sifat graf Kuratowski adalah :

1. Kedua graf Kuratowski adalah graf teratur.
2. Kedua graf Kuratowski adalah graf tidak-planar.
3. Penghapusan sisi atau simpul dari graf Kuratowski menyebabkan menjadi graf planar.
4. Graf Kuratowski pertama adala graf tidak-planar dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum. keduanya adalah graf tidak planar paling sederhana.

 Teorema Kuratowski

           Graf G adalah tidak planar jika dan hanya jika ia mengandung upagraf yang isomorfik dengan K5 atau K3.3 atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

 F. Homeomorfik

          Dua graf G1 dan G2 dikatakan homeomorfik jika salah satu dari kedua graf dapat diperoleh dari graf yang lain dengan cara menyisipkan dan atau membuang secara berulang-ulang simpul berderajad 2.

 G. Graf Dual (Dual Graf)

            Misalkan kita mempunyai sebuah graf planar G yang direpresentasikan sebagai graf bidang. KIta dapat membuat suatu graf G* yang secara geometri merupakan dual dari graf planar tersebut dengan cara sebagai berikut :

Pada setiap wilayah atau muka (face) f di G, buatlah simpul v* yang merupakan simpul untuk G*.

Untuk setiap sisi e di G, tariklah sisi e* (yang menjadi sisi untuk G*) yang memotong sisi e tersebut. Sisi e menghubungkan dua buah simpul v1* dan v2* (simul-simpul di G*)cyang berada di dalam muka f1 dan f2 yang dipisahkan oleh sisi e di G. Untuk sisi e yang salah satu simpulnya merupakan simpul berderajad 1 (jadi, sisi e seluruhnya terdapat di dalam sebuah muka), maka sisi e* adalah berupa sisi gelang.

Graf G* yang terbentuk dengan cara penggambaran demikian disebut graf dual (dual geometri) dari graf G. Gambar berikut adalah graf dual G*  dari graf planar G. Sisi-sisi graf G* digambarkan dengan garis putus-putus.

           Jika G adalah graf planar dalam representasi bidang dengan n buah simpul, e buah sisi dan f buah muka, maka graf G* memiliki n* = f buah simpul, e* = e buah sisi dan f* = n buah muka.

           Sebuah graf planar G mempunyai dual yang unik hanya jika representasi bidangnya unik.

Salah satu aplikasi graf dual yang penting adalah mempresentasikan peta (map). Setiap peta pada bidang terdiri dari sejumlah wilayah (region). Wilayah pada peta dapat menyatakan suatu negara, provinsi atau kabupaten. Tiap wilayah pada peta dinyatakan sebagai sebuha simpul, sedangkan sisi menyatakan bahwa dua wilayah berbatasan langsung (bertetangga).