GRAF PLANNAR

Graf Planar

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

K4 adalah graf planar:

K5 adalah graf tidak planar:

Aplikasi Graf Planar

 Perancangan IC (Integrated Circuit)

Tidak boleh ada kawat-kawat di dalam ICboard yang saling bersilangan -> dapat
menimbulkan interferensi arus listrik -> malfunction

   Perancangan kawat memenuhi prinsip graf planar

Teorema Kuratoswki

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

Berguna untuk menentukan dengan tegas keplanaran suat graf. 

a)     Graf Kuratowski pertama (K5)     

b)     Graf Kuratowski kedua (K3, 3)        

c)      Graf yang isomorfik dengan graf Kuratowski kedua 

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.

GRAF

DEFENISI GRAPH

Graf G = (V, E), yang dalam hal ini:     

V  = himpunan tidak-kosong dari simpul-simpul (vertices)  = { v1 , v2 , ... , vn }   
E = himpunan sisi  (edges) yang menghubungkan sepasang      simpul  = {e1 , e2 , ... , en }
Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

TERMINOLOGI PADA GRAPH

1.        Bertetangga (adjacent)
Dua buah titik, titik u dan titik v pada graph tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, u bertetangga dengan v jika (u,v) adalah sebuah sisi pada graph G.

2.        Bersisian (incident)
Misal sembarang sisi , sisi e dikatakan bersisian dengan titik u dan titik v.

3.        Titik terpencil (isolated vertex)
Titik terpencil adalah titik yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dikatakan bahwa titik terpencil adalah titik yang tidak satupun bertetangga dengan titik-titik lainnya.

4.        Jalan (walk)
Misalkan G adalah sebuah graph. Sebuah jalan (walk) di G adalah sebuah barisan berhingga (tak kosong) yang suku-sukunya bergantian titik dan sisi, sedemikian hingga dan adalah titik-titik akhir sisi ei, untuk . Katakan W adalah sebuah jalan dari titik (titik awal) ke titik (titik akhir), sedangkan titik-titik disebut titik-titik internal W dan k disebut panjang jalan W. Dengan kata lain, jalan (walk) ialah dimana sisi dan titiknya boleh berulang.
Dari gambar, barisan adalah sebuah jalan di graph G yang panjangnya 4.

5.        Jejak (trail)
Jejak adalah jalan yang sisi-sisinya tidak ada yang sama, tetapi titiknya boleh ada yang sama.
Dari gambar, barisan adalah sebuah jejak di graph G dengan panjang 5.

6.        Lintasan (path)
Lintasan adalah jejak yang semua titiknya berbeda (sisi dan titiknya tidak ada yang sama).
Dari gambar, barisan adalah sebuah lintasan di graph G dengan panjang 4.

7.        Sirkit
Sirkit adalah Jejak tertutup.

8.        Siklus/lintasan tertutup (sikel)
Sikel adalah sebuah sirkit yang titik awal dan semua titik internalnya berbeda (titik awal dan titik akhirnya sama dimana titik dan sisinya tidak ada yang berulang).

9.        Terhubung dan tidak terhubung
Suatu graph G dikatakan terhubung jika dan hanya jika setiap 2 titik dalam G terhubung (gambar a), sedangkan suatu graph G dikatakan tidak terhubung jika dan hanya jika ada 2 titik dalam G yang tidak terhubung.

10.    Komplemen
Misalkan G sebuah graph sederhana. Komplemen G dilambangkan dengan , adalah graph sederhana yang himpunan titiknya sama dengan himpunan titik G dan dua titik u dan v di berhubungan langsung jika dan hanya jika di G titik u dan v tidak berhubungan langsung.

Isomorfik
Dua graph G dan H dikatakan isomorfik ditulis , jika:
(i) Terdapat korespondensi satu-satu antara V(G) dan E(G),
(ii) Banyaknya sisi yang menghubungkan dua titik u dan v di G, sama dengan banyaknya sisi yang menghubungkan dua titik di H yang korespondensi dengan titik u dan titik v.
Graph G1 isomorfik dengan graph G2, sedangkan graph G1 tidak isomorfik dengan graph G3.

Jenis-Jenis Graf

Graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut pandang pengelompokannya. Pengelompokan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul, atau berdasarkan orientasi arah pada sisi. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 8.3(a) adalah contoh graf sederhana yang merepresentasikan jaringan komputer. Simpul menyatakan komputer, sedangkan sisi menyatakan saluran telepon untuk berkomunikasi. Saluran telepon dapat beroperasi pada dua arah.

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. G2 pada Gambar 8.3(b) adalah graf-ganda. Sisi ganda pada G2 dapat diandaikan sebagai saluran telepon tambahan apabila beban komunikasi data antar komputer sangat padat. Graf semu adalah graf yang mengandung gelang. G3 adalah graf semu (termasuk bila memiliki sisi ganda sekalipun). Sisi gelang pada G3 dapat dianggap sebagai saluran telelpon tambahan yang menghubungkan komputer dengan dirinya sendiri (mungkin untuk tujuan diagnostik). Graf semu lebih umum daripada graf ganda, karena sisi pada graf semu dapat terhubung ke dirinya sendiri. Jumlah simpul pada graf kita sebut sebagai kardinalitas graf, dan dinyatakan dengan n = V, dan jumlah sisi kita nyatakan dengan m = E. Pada contoh di atas, G1 mempunyai n = 4, dan m = 4, sedangkan G2 mempunyai n = 3 dan m = 4. Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1. Graf berhingga (limited graph)

Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga. Dua buah graf pada Gambar 8.3 adalah contoh graf yang berhingga.

2. Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga. Dua buah graf pada Gambar 8.4 adalah contoh graf yang tidak berhingga. Di dalam buku ini, kita hanya membicarakan graf berhingga saja. Kecuali jika disebut lain, maka istilah “graf” mengacu kepada graf berhingga.

Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf

dibedakan atas 2 jenis:

1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (vj , vk) = (vk , vj) adalah sisi yang sama. Tiga buah graf pada Gambar 6.3 adalah graf tak-berarah.

2. Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Kita lebih suka menyebut sisi berarah dengan sebutan busur (arc). Pada graf berarah, (vj, vk) dan (vk, vj) menyatakan dua buah busur yang berbeda, dengan kata lain (vj, vk) ≠ (vk , vj). Untuk busur (vj, vk), simpul vj dinamakan simpul asal (initial vertex) dan simpul vk dinamakan simpul terminal (terminal vertex). G4 pada Gambar 8.5(a) adalah contoh graf berarah. Pada G4 diandaikan saluran telepon tidak dapat beroperasi pada dua arah. Saluran hanya beroperasi pada arah yang ditunjukkan oleh anak panah. Jadi, sebagai contoh, saluran telepon (1, 2) tidak sama dengan saluran telepon (2, 1). berarah sering dipakai untuk menggambarkan aliran proses, peta lalu lintas suatu kota (jalan searah atau dua arah), dan sebagainya. Pada graf berarah, gelang diperbolehkan, tetapi sisi ganda tidak.

Definisi graf dapat diperluas sehingga mencakup graf-ganda berarah. Pada graf-ganda berarah, gelang dan sisi ganda diperbolehkan ada. G5 pada Gambar 8.5(b) adalah contoh graf-ganda berarah. Tabel 8.1 meringkas perluasan definisi graf. Di dalam buku ini, kita menyebut graf baik sisinya tak-berarah maupun berarah, baik mengandung gelang maupun sisi ganda, baik graf sederhana maupun graf tak-sederhana.