Penyajian Graf, Graf Isomorfik, dan Graf Planar

1. Matriks Ketetanggaan (Adjacency Matrix)

A. Matriks ketetanggaan graf tidak berbobot

Matriks ketetanggaan adalah representasi graf yang paling umum. Misalkan G = (V, E) adalah graf dengan n titik, n ≥ 1. Matriks ketetanggaan G adalah matriks dwimatra yang berukuran n × n. Bila matriks tersebut dinamakan A = [aᵢⱼ], maka aᵢⱼ = 1 jika simpul i dan j bertetangga, sebaliknya aᵢⱼ = 0 jika simpul i dan j tidak bertetangga.

Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain dengan angka 0 dan 1, elemen matriks dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true (menyatakan 1). Perhatikanlah bahwa matriks ketetanggaan didasarkan pada pengurutan nomor titik. Di sini, terdapat n! cara pengurutan nomor titik, yang berarti ada n! matriks ketetanggaan berbeda untuk graf dengan n titik.

Matriks ketetanggaan untuk graf sederhana dan tidak berarah selalu simetri, sedangkan untuk graf berarah matriks ketetanggaannya belum tentu simetri (akan simetri jika berupa graf berarah lengkap). Selain itu, diagonal utamanya selalu nol karena tidak ada sisi loop.

Sayangnya, matriks ketetanggaan nol-satu tidak dapat digunakan untuk merepresentasikan graf yang mempunyai sisi rangkap (graf ganda). Untuk menyiasatinya, maka elemen aᵢⱼ pada matriks ketetanggaan sama dengan banyak sisi yang berasosiasi dengan (vᵢ, vⱼ). Matriks ketetanggaannya tentu bukan lagi matriks nol-satu. Untuk graf semu, loop pada titik vᵢ dinyatakan dengan nilai 1 pada posisi (i, i) di matriks ketetanggaannya.

Keuntungan representasi dengan matriks ketetanggaan adalah elemen matriksnya dapat diakses langsung melalui indeks. Selain itu, kita juga dapat menentukan dengan langsung apakah titik i dan simpul j bertetangga.

Derajat tiap titik i dapat dihitung dari matriks ketetanggaan. Untuk graf tak-berarah tanpa loop,

untuk graf tak-berarah dengan loop,

sedangkan untuk graf berarah:

B. Matriks ketetanggaan graf berbobot

Untuk graf berbobot, aᵢⱼ menyatakan bobot tiap sisi yang menghubungkan titik i dengan titik j, sedangkan untuk dua titik yang tidak terhubung aᵢⱼ diberi nilai ∞.

C. Teorema perpangkatan matriks adjacency

Misal G = (V, E) graf tidak berbobot dengan V = {v₁ + v₂ + ... + vₙ} dan A merupakan matriks adjacency dari G. Elemen yang terletak di baris ke-i dan kolom ke-j dari matriks Aᵏ, k ∈ ℕ, menyatakan banyaknya jalan di G dengan panjang k yang menghubungkan titik vᵢ dan vⱼ.

2. Matriks Bersisian (Incidency Matrix)

Bila matriks ketetanggaan menyatakan ketetanggaan titik-titik di dalam graf, maka matriks bersisian menyatakan kebersisian titik dengan sisi. Misalkan G = (V, E) adalah graf dengan n titik dan m sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran n × m. Baris menunjukkan label titik, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut dinamakan M = [mᵢⱼ], maka mᵢⱼ = 1 jika titik i bersisian dengan sisi j, sebaliknya mᵢⱼ = 0 jika titik i tidak bersisian dengan sisi j.

Matriks bersisian dapat digunakan untuk merepresentasikan graf yang mengandung sisi rangkap atau sisi loop.

Derajat setiap titik i dapat dihitung dengan menghitung jumlah seluruh elemen pada baris i (kecuali pada graf yang mengandung loop).

3. Graf Isomorfik

A. Definisi Isomorfik

Dua buah graf, G₁ dan G₂ dikatakan isomorfik jika terdapat korespondensi satu-satu antara titik-titik keduanya dan antara sisi-sisi keduanya sedemikian sehingga jika sisi e bersisian dengan titik u dan v di G₁, maka sisi e' yang berkorespon di G₂ juga harus bersisian dengan titik u' dan v' di G₂.

Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan titik dan sisinya saja yang berbeda. Ini benar karena sebuah graf dapat digambarkan dalam banyak cara (meski berbeda secara geometris).

Perhatikan gambar berikut:

Diberikan dua graf G dan H keduanya isomorfik, karena sisi-sisi yang bersesuaian selalu incident dengan titik-titik yang bersesuaian.

B. Syarat Isomorfik

Tidak mudah menentukan apakah dua buah graf isomorfik hanya dengan melihat gambarnya saja. Dari definisi isomorfik kita menyimpulkan dua buah graf isomorfik memenuhi ketiga tiga syarat berikut:

• Mempunyai banyak titik yang sama

• Mempunyai banyak sisi yang sama

• Mempunyai banyak titik yang sama berderajat tertentu

Namun, ketiga syarat ini ternyata belum cukup menjamin keisomorfikan. Pemeriksaan secara visual masih tetap diperlukan.

Sebagai contoh, perhatikan gambar berikut:

Kedua graf ini memenuhi ketiga syarat, yaitu:

🔜 Terdapat 6 buah tiik

🔜 Terdapat 5 buah sisi

🔜 Terdapat 3 titik brderajat satu, 2 titik berderajat dua, 1 titik berderajat tiga

akan tetapi keduanya tidak isomorfik, dimana x adjacent dengan 2 pendant, tetapi y hanya adjacent dengan 1 pendant.

Untuk mengatasinya, terdapat syarat ke-4, yaitu "mempunyai banyak titik yang sama yang memiliki adjasensi (ketetanggaan) tertentu".

Jadi, ada 4 syarat agar dua graf isomorfik:

• Mempunyai banyak titik yang sama

• Mempunyai banyak sisi yang sama

• Mempunyai banyak titik yang sama berderajat tertentu

• Mempunyai banyak titik yang sama yang memiliki adjasensi (ketetanggan) tertentu

Terdapat dugaan (oleh Farhan Firmansyah Kasim) bahwa untuk mengecek dua graf isomorfik cukup dengan mengecek syarat keempat.

C. Fungsi Isomorfisma

Isomorfisma graf dari G ke H adalah fungsi yang memetakan dari suatu graf G ke graf H yang isomorfik dengan G, oleh karena itu mengawetkan sifat-sifat berikut:

• Banyak titik dan banyak sisi

Karena pada dua graf yang isomorfik terdapat korespondensi satu-satu antara himpunan titik dari kedua graf, maka banyaknya titik dan banyaknya sisi dari kedua graf akan sama.

• Derajat titik dan adjasensi (ketetanggaan)

Karena pada dua graf yang isomorfik setiap pasang titik u dan v bersebelahan jika dan hanya jika f(u) dan f(v) bersebelahan, maka kedua graf akan memiliki sama banyaknya titik pada setiap derajatnya, juga ketetanggaannya.

Sifat yang diawetkan oleh isomorfisma graf dikatakan invarian graf. Sesuai dengan 4 syarat isomorfik, suatu fungsi isomorfisma mengawetkan 4 sifat tersebut.

D. Matriks Adjasensi

Diantara cara untuk mengecek dua graf isomorfik, bisa dengan matriks adjasensi, dimana selama ditemukan matriks adjasensi yang sama, dapat dipastikan kedua graf isomorfik.

Perhatikan gambar berikut:

Kedua graf G dan H isomorfik, karena ditemukan matriks adjasensi yang sama dari kedua graf, meski urutan indeks titik-titiknya berbeda:

4. Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph)

A. Graf Planar (Planar Graph)

Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan) disebut sebagai graf planar, jika tidak, maka ia disebut graf tak-planar.

Perlu diperhatikan bahwa belum tentu suatu graf yang secara kasat mata terlihat sisi-sisinya saling berpotongan tidak planar. Graf tersebut mungkin saja planar, karena graf tersebut dapat digambar kembali dengan cara berbeda yang sisi-sisinya tidak saling berpotongan.

Sebagai contoh, K₄ merupakan graf planar.

B. Graf Bidang
Representasi graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).

Pada gambar ini disajikan tiga alternatif representasi dari K₄, ketiga buah graf adalah graf planar, tetapi graf (a) bukan graf bidang, sedangkan graf (b) dan (c) adalah graf bidang. Ketiga graf ini isomorfik. Untuk selanjutnya, kita tetap menggunakan istilah graf planar baik untuk graf yang dapat digambar (ulang) pada bidang datar tanpa ada sisi-sisi yang berpotongan maupun graf yang memang sudah tergambar tanpa sisi-sisi yang berpotongan (graf bidang).

C. Wilayah (Region) atau Wajah (Face)

Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau wajah (face). Suatu wilayah atau wajah tertutup juga dapat dinyatakan sebagai pasangan tidak terurut dari titik-titik yang incident dengan sisi-sisi pembatasnya, adapun wilayah terbuka dapat dinyatakan sebagai pasangan tidak terurut dari titik-titik terluar, misal diberikan graf berikut:

setiap wilayah tertutup dapat dinyatakan sebagai pasangan tidak terurut berikut:

R₁ = (a, e, f), R₂ = (a, b, f), R₃ = (b, c, f), R₄ = (c, d, g), R₅ = (c, f, g)

adapun R₆ merupakan wilayah terbuka, dikarenakan semua titik pada graf ini merupakan titik terluar, wilayah R₆ dinyatakan sebagai R₆ = (a, b, c, d, e, f, g).

D. Rumus Euler untuk Graf Planar Sederhana

Diberikan graf planar sederhana G dengan V himpunan titik-titik di G, E himpunan sisi-sisi di G, dan F himpunan wilayah-wilayah di G, berikut ini rumus Euler:

|V| – |E| + |F| = 2

E. Ketidaksamaan Euler

Misal diberikan graf planar sederhana dengan v titik, e sisi, dan f wilayah.

Ingat kembali bahwa setiap wilayah pada graf planar dibatasi oleh 3 atau lebih sisi, sedangkan sisi-sisi membatasi paling banyak 2 wilayah, sehingga berlaku ketaksamaan

3f ≤ 2e, bagi masing-masing ruas dengan 3

f ≤ 2e/3

sedangkan menurut rumus Euler

2 = v – e + f ≤ v – e + 2e/3 = v – e/3, kalikan masing-masing ruas dengan 3

6 ≤ 3v – e

e ≤ 3v – 6

Ketidaksamaan yang terakhir dinamakan ketidaksamaan Euler, yang dapat digunakan untuk menunjukkan keplanaran suatu graf sederhana. Ini dinyatakan sebagai berikut:

"Jika G merupakan graf sederhana terhubung dengan e adalah banyak sisi dan v adalah banyak simpul, yang dalam hal ini v ≥ 3, maka berlaku ketidaksamaan Euler e ≤ 3v − 6."

Catatan:

Sad but true, ketidaksamaan Euler hanyalah syarat perlu agar suatu graf dikatakan planar, tetapi bukan syarat cukup. Artinya, meskipun suatu graf planar sederhana memenuhi kedua ketidaksamaan itu, tetapi tidak selalu menjamin keplanaran suatu graf.

Misalnya graf K₃,₃ memenuhi ketidaksamaan Euler tersebut,

e = 9, n = 6

9 ≤ (3)(6) − 6 = 12 (jadi, e ≤ 3n − 6)

padahal graf K₃,₃ bukan graf planar.

5. Graf Kuratowski

A. Dalam literatur tentang graf, dikenal dua buah graf non-planar yang khusus, yaitu graf Kuratowski, setelah matematikawan Polandia, Kasimir Kuratowski, menemukan sifatnya yang unik.

1. Graf Kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah titik (K₅), merupakan graf non-planar.

2. Graf Kuratowski kedua, yaitu graf terhubung teratur dengan 6 buah titik dan 9 buah sisi (K₃,₃) merupakan graf non-planar.

B. Sifat graf Kuratowski adalah:

1. Kedua graf Kuratowski merupakan graf teratur.

2. Kedua graf Kuratowski merupakan graf tidak-planar.

3. Penghapusan sisi atau titik dari Graf Kuratowski menyebabkannya menjadi graf planar.

Graf Kuratowski pertama merupakan graf non-planar dengan banyak titik minimum, dan graf Kuratowski kedua adalah graf non-planar dengan banyak sisi minimum. Keduanya merupakan graf non-planar paling sederhana.

C. Teorema Kuratowski

Graf G non-planar jika dan hanya jika ia mengandung subgraf yang isomorfik dengan K₅ atau K₃,₃ atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

D. Graf Homeomorfik

Dua graf dikatakan homeomorfik jika salahsatu dari keduanya dapat diperoleh dari graf yang lain dengan cara menyisipkan atau menghapus secara berulang-ulang titik berderajat 2.

Perhatikan bahwa ketiga graf ini homeomorfik, dimana menghapus v yang berderajat 2 dari G₁ akan menghasilkan G₂, juga menghapus x dan y dari G₃ akan menghasilkan G₂.

E. Penerapan Teorema Kuratowski

Perhatikanlah bahwa teorema Kuratowski lebih mudah digunakan untuk menentukan bahwa sebuah graf tidak planar. Untuk membuktikan bahwa suatu graf planar relatif lebih sulit, karena kita harus mencoba semua kemungkinan subgraf yang memiliki 5 titik dengan 10 sisi atau subgraf yang memiliki 6 titik dan 9 sisi, dan memeriksa apakah subgraf tersebut sama atau homeomorfik dengan K₅ atau K₃,₃.

Terapan graf planar pada persoalan utilitas dalam merancang jaringan pipa air, pipa gas, dan kabel listrik bawah tanah agar ketiganya tidak saling bersilangan, dan ternyata mustahil karena graf K₃,₃ non-planar. Terapan graf planar lainnya adalah pada perancangan integrated circuit (IC) pada sebuah papan. Kawat-kawat yang menghubungkan simpul-simpul IC harus dirancang sedemikian rupa agar tidak bersilangan, sebab persilangan dua buah kawat yang beraliran listrik dapat menimbulkan interferensi arus, yang mengakibatkan terganggunya fungsi IC tersebut.

6. Graf Dual (Dual Graph)

A. Konstruksi Graf Dual

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:

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

2. Untuk setiap sisi e di G, tariklah sisi e* (yang menjadi sisi untuk G*) yang memotong sisi e tersebut. Sisi e* menghubungkan dua buah titik v₁* dan v₂* (titik-titik di G*) yang berada di dalam muka f₁ dan f₂ yang dipisahkan oleh sisi e di G. Untuk sisi e yang salah satu titiknya merupakan titik berderajat 1 (jadi, sisi e seluruhnya terdapat di dalam sebuah muka), maka sisi e* adalah berupa sisi loop.

Graf G* yang terbentuk dengan cara penggambaran demikian disebut graf dual (atau tepatnya dual geometri) dari graf G. Sisi-sisi graf G* digambarkan dengan garis putus-putus.

B. Sifat Graf Dual

Berapakah banyak sisi, simpul, dan muka (wilayah) dari graf G*? Jika G adalah graf planar dalam representasi bidang dengan v buah titik, e buah sisi dan f buah muka, maka graf G* memiliki v* = f buah titik, e* = e buah sisi dan f* = v buah muka.

Sebuah graf mempunyai dual hanya jika graf tersebut planar. Pertanyaannya, apakah dual dari sebuah graf adalah unik? Dengan kata lain, apakah dual-dual dari sebuah graf planar isomorfik? Jawabannya adalah bahwa sebuah graf planar G mempunyai dual yang unik hanya jika representasi bidangnya unik. Dua graf yang sama (isomorfik), tetapi mempunyai representasi bidang yang berbeda, mengakibatkan dual dari kedua graf yang isomorfik tersebut tidak isomorfik.

C. Graf Peta

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

Sedikit perbedaan dengan graf dual yang telah disebutkan sebelum ini, pada graf yang merepresentasikan peta bidang luar tidak dinyatakan sebagai sebuah titik. Kita akan membahas kembali penggunaan graf yang merepresentasikan peta pada pewarnaan graf.