Representasi Graph

 

Bila graf akan diproses dalam program komputer, maka graf harus direpresentasikan didalam memori. Terdapat beberapa representasi yang mungkin untuk graf. Disini hanya diberikan tiga macam representasi yang sering digunakan, yaitu

1. Matriks Ketetanggaan (adjacency matrix)

2. Matriks Bersisian (incidency matrix)

3. Senarai Ketetanggaan (adjacency list)

 

1.        Matriks Ketetanggaan (adjacency matrix)

A = [a_ij],

a_ij = 1, jika simpul i dan j bertetangga    

a_ij = 0, jika simpul i dan j tidak bertetangga      

 

2. Matriks Bersisian (incidency matrix)

Matriks bersisian dapat digunakan untuk merepresentasikan graf yang mengandung sisi ganda

A = [a_ij],

a_ij  = 1,  jika simpul i bersisian dengan sisi j              

a_ij =  0,   jika simpul i tidak bersisian dengan sisi j

 

3. Senarai Ketetanggaan (adjacency list)

Kelemahan matriks ketetanggaan adalah bila graf memiliki jumlah sisi relatif sedikit, karena matriksnya bersifat jarang, yaitu banyak mengandung elemen nol. Ditinjau dari implementasinya di dalam komputer, kebutuhan ruang memori untuk matriks jarang boros karena komputer menyimpan elemen nol yang tidak perlu. Senarai ketetanggaan mengenumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf

GRAPH ISOMORFIK (ISOMORPHIC GRAPH)

 

n  Dua buah graph yang sama tetapi secara geometri berbeda disebut graph yang saling isomorfik.

n  Dua buah graph, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.

n  Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.

n  Dua buah graph yang isomorfik adalah graph yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda.  Ini benar karena sebuah graph dapat digambarkan dalam banyak cara.

 

Dari definisi graph isomorfik dapat dikemukakan bahwa dua buah graph isomorfik memenuhi ketiga syarat berikut

1. Mempunyai jumlah simpul yang sama.

2. Mempunyai jumlah sisi yang sama

3. Mempunyai jumlah simpul yang sama berderajat tertentu

Ketiga syarat ini ternyata belum cukup menjamin. Pemeriksaan secara visual perlu dilakukan.

GRAG PLANAR DAN GRAF BIDANG

 

Defenisi 8.17. 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 digambarkan kembali dengan cara berbeda yang sisi-sisinya tidak saling berpotongan.

Contoh 8.31

Graf K4 adalah graf planar, biasanya digambarkan dengan sisi yang bersilangan seperti ditunjukkan pada Gambar berikut. Kita dapat menggambarkan graf itu kembali tanpa  ada sisi-sisi yang berpotongan, seperti  pada gambar berikut. K5 pada gambar bukan graf planar.

Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph). Pada gambar 8.46, ketiga buah graf adalah graf planar, tetapi graf(a) bukan graf bidang, sedangkan graf (b) dan (c) adalah graf bidang. Ketiga graf ini adalah 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)

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

 

 

Rumus Euler

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

            n – e + f = 2                                        

yang dalam hal ini,

f = jumlah wilayah

e = jumlah sisi

n = jumlah simpul

 

Contoh. Graf K_3,3 pada Gambar 6.43(a) memenuhi ketidaksamaan e£ 2n – 6, karena

                        e = 9, n = 6

                        9 £ (2)(6) – 4 = 8                     (salah)

yang berarti K_3,3 bukan graf planar.

 

TeoremaKuratoswki

Berikut ini diberikan teorema dari Kuratowski yang memungkinkan kita menentukan dengan tegas keplanaran suatu graf.

Dalam literatur tentang graf, dikenal dua buah graf tidak-planar  yang khusus yaitu graf Kuratowski, setelah matematikawan Polandia, Kasimir Kuratowski, menemukan sifatnya yang unik [ DE074 ]

1.      Graf Kuratowski pertama, yaitu graf lengkap yang mempunyai lima buah simpul (K5), adalah graf tidak planar.

2.      Graf Kuratowski Kedua, yaitu graf terhubung teratur  dengan 6 buah simpul dan 9 buah sisi (K3,3) adalah graf tidak planar.

 

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 menyebabkannya menjadi graf planar.

4.      Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum.

 

TEOREMA Kuratowski. Graf G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang sama dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

GRAF DUAL

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

1. Pada setiap wilayah  f di G buatlah sebuah simpul v* yang merupakan symbol 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 simpul  v₁* dan v₂* yang berada  di dalam muka ƒ1 dan ƒ2 yang dipisahkan oleh sisi e di G

 

Sebuah graf mempunyai dual hanya jika graf tersebut planar. Salah Satu aplikasi graf dual yang penting adalah untuk merepresentasikan peta (map). Setiap peta pada bidang datar terdiri dari sejumlah wilayah (region ).

 

LINTASAN DAN SIRKUIT EULER

 

n  Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graph tepat satu kali.

n  Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.

n  Graph yang mempunyai sirkuit Euler disebut graph Euler (Eulerian graph). Graph yang mempunyai lintasan Euler dinamakan juga graph semi-Euler (semi-Eulerian graph).

  

Teorema Lintasan dan Sirkuit Euler

 

n  Graph tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali

n  Graph tidak berarah G adalah graph Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.

n  (Catatlah bahwa graph yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya)

n  Graph berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

LINTASAN DAN SIRKUIT HAMILTON

n  Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graph tepat satu kali.

n  Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graph tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

n  Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton.

Teorema Lintasan dan Sirkuit Hamilton

 

n  Syarat cukup (jadi bukan syarat perlu) supaya graph sederhana G dengan n (³ 3) buah simpul adalah graph Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) ³ n/2 untuk setiap simpul v di  G).

n  Setiap graph lengkap adalah graph Hamilton

n  Di dalam graph lengkap G dengan n buah simpul (n ³ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.

n  Di dalam graph lengkap G dengan n buah simpul (n ³ 3 dan n ganjil), terdapat (n - 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n  ³ 4, maka di dalam G terdapat (n - 2)/2 buah sirkuit Hamilton yang saling lepas.

 

Contoh : (Persoalan pengaturan tempat duduk). Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?

Jumlah pengaturan tempat duduk yang berbeda adalah (9 - 1)/2 = 4.

 

v    Lintasan dan Sirkuit Hamilton/ Euler

n  Beberapa graph dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, mengandung sirkuit Euler dan lintasan Hamilton, mengandung lintsan Euler maupun lintasan Hamilton, tidak mengandung lintasan Euler namun mengandung sirkuit Hamilton, dan sebagainya!).

n  Graph (a) mengandung sirkuit Hamilton maupun sirkuit Euler 

n  graph (b) mengandung sirkuit Hamilton dan lintasan Euler (periksa!).

Beberapa Aplikasi Graf

 
a. Lintasan Terpendek (Shortest Path)

n  graf berbobot (weighted graph),

n  lintasan terpendek: lintasan yang memiliki total bobot minimum.

Contoh aplikasi:

n  Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah  antara dua buah kota

n  Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.

 

Terdapat beberapa jenis persoalan lintasan terpendek, antara lain:

n  Lintasan terpendek antara dua buah simpul tertentu.

n  Lintasan terpendek antara semua pasangan simpul.

n  Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.

n  Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.

       ==> Di dalam kuliah ini kita memilih jenis persoalan 3.

n  Uraian persoalan

n  Diberikan graf berbobot G = (V, E) dan sebuah simpul a. Tentukan lintasan terpendek dari a ke setiap simpul lainnya di G. Asumsi yang kita buat adalah bahwa semua sisi berbobot positif.

Algoritma Dijkstra

Merupakan Algoritma menentukan lintasan terpendek yang terkenal.

Properti algoritma Dijkstra:

1. Matriks ketetanggaan M[m_ij]

                        m_ij = bobot sisi (i, j)   (pada graf tak-berarah m_ij = m_ji )

                        m_ii = 0

                        m_ij = ¥, jika tidak ada sisi dari simpul i ke simpul j

2. Larik S = [s_i] yang dalam hal ini,

            s_i = 1, jika simpul i termasuk ke dalam lintasan terpendek

    s_i = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek

3. Larik/tabel D = [d_i] yang dalam hal ini,

            d_i = panjang lintasan dari simpul awal s ke simpul i