BAB II LANDASAN TEORI
2.1. Definisi Graf Secara matematis, graf G didefinisikan sebagai pasangan himpunan (V,E) ditulis dengan notasi G = (V, E), yang dalam hal ini: V = himpunan tidak-kosong dari simpul-simpul (vertices) = { v 1 , v 2 , ... , v n } E = himpunan sisi (edges) yang menghubungkan sepasang simpul = {e 1 , e 2 , ... , e n } Definisi graf diatas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buahpun, tetapi simpulnya harus ada, minimal satu graf. (Rinaldi, 2005) 1
1 e1
2
3
e2
2 e5
e3
1 e4
e1 3
e6
e5
e7
4
4
(a) G 1
(b)G 2
e2
2
e3
e4
e6
3
e8
e7 4
(c)G 3
Gambar 2. 1 (a) graf sederhana, (b) graf ganda, dan (c) graf semu
Pada Gambar 2.1 (a) G 1 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) } (b) G 2 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
Universitas Sumatera Utara
= { e1 , e2 , e3 , e4 , e5 , e6, e7 } (c) G 3 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) } = { e1 , e2 , e3 , e4 , e5 , e6, e7 , e8 } Pada G 2 , sisi e 3 = (1, 3) dan sisi e 4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G 3 , sisi e 8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.
2.2 Jenis-Jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori (jenis) bergantung pada sudut pandang pengelompokkannya. Pengelompokan graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul,berdasarkan orientasi arah pada sisi atau berdasarkan keterhubungan simpul. (Rinaldi, 2005) Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: 1.
Graf sederhana (simple graph). Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G 1 (pada gambar 2.1) adalah contoh graf sederhana
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 adalalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. Dapat juga di definisikan graf ganda G =(V,E) terdiri dari himpunan tidak kosong simpul-simpul V dan E adalah himpunan ganda (multiset) yang mengandung sisi ganda. Graf semu adalah graf yang mengandung gelang (loop). G 3 adalah graf semu (termasuk bila memiliki sisi ganda sekalipun). G 2 dan G 3 (pada Gambar 2.1) adalah contoh graf tak sederhana (Rinaldi, 2005)
Universitas Sumatera Utara
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.
2.
Graf tak-berhingga (unlimited graph) Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas dua 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 (u,v) = (v,u) adalah sisi yang sama. Tiga buah graf (pada gambar 2.1) adalah graf tak berarah.
2.
Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Pada graph ini, (u,v) dan (v,u) menyatakan dua buah busur yang berbeda. Dengan kata lain (u,v) ≠ (v,u). Untuk busur (u,v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex).
1
2
1
3
4
2
3
4
Dua buah graf (pada gambar 2.2 ) adalah graf berarah. (a) G 4
(b) G 5
Gambar 2.2 (a) graf berarah, (b) graf ganda berarah
Universitas Sumatera Utara
Berdasarkan keterhubungan simpul pada suatu graf, maka graf digolongkan menjadi dua jenis: 1.
Graph terhubung (Connected graph) Graph dikatakan terhubung bila dan hanya bila ada 2 (dua) titik dalam G terhubung.
2.
Graph tidak terhubung (Unconnected graph) Graph dikatakan tidak terhubung bila dan hanya bila ada 2 (dua) titik dalam G yang tidak terhubung.
2.3. Terminologi Dasar Graf Kita akan sering menggunakan terminologi (istilah) yang berkaitan dengan graf. Dibawah ini didefinisikan beberapa terminologi yang sering dipakai. Contoh graf pada gambar 2.3 akan digunakan untuk memperjelas terminologi yang kita definisikan. Graf yang pertama G 1 adalah graf sederhana, G 2 adalah graf semu yang mengandung sisi ganda maupun gelang, sedangkan G 3 adalah graf dengan sebuah simpul terpisah dari simpul yang lainnya. 1
1
1
e2
2
4
e3
e1
3
2
G1
e4
5
3
e5
3 2
G2
4
G3
Gambar 2.3 Graf yang digunakan untuk menjelaskan terminologi pada graf
1. Ketetanggaan (Adjacent) Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Tinjau graf G 1 : simpul 1 bertetangga dengan simpul 2 dan 3, simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian (Incidency) Untuk sembarang sisi e = (v j , v k ) dikatakan e bersisian dengan simpul v j , atau
Universitas Sumatera Utara
e bersisian dengan simpul v k Tinjau graf G 1 : sisi (2, 3) bersisian dengan simpul 2 dan simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan simpul 4, tetapi sisi (1, 2) tidak bersisian dengan simpul 4.
3. Simpul Terpencil (Isolated Vertex) Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. Tinjau graf G 2 : simpul 5 adalah simpul terpencil. 4. Graf Kosong (null graph atau empty graph) Graf yang himpunan sisinya E merupakan himpunan kosong disebut sebagai graf kosong dan ditulis sebagai (N n ) yang dalam hal ini n adalah jumlah simpul. 1
4
2 5
3
Gambar 2.4 Graf kosong N 5
5. Derajat (Degree) Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: d(v) Tinjau graf G 1 : d(1) = d(4) = 2 d(2) = d(3) = 3 Tinjau graf G 3 : d(5) = 0
simpul terpencil
d(4) = 1 Tinjau graf G 2 : d(1) = 3
simpul anting-anting (pendant vertex)
bersisian dengan sisi ganda
d(2) = 4
bersisian dengan sisi gelang (loop)
Lemma Jabat Tangan. Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka
Universitas Sumatera Utara
∑ d (v ) = 2 E v∈V
Tinjau graf G 1 : d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10 = 2 × jumlah sisi = 2 × 5 Tinjau graf G 2 : d(1) + d(2) + d(3) = 3 + 3 + 4 = 10 = 2 × jumlah sisi = 2 × 5 Tinjau graf G 3 : d(1) + d(2) + d(3) + d(4) + d(5) =2+2+3+1+0=8 = 2 × jumlah sisi = 2 × 4
6. Upagraf (Subgraph) Misalkan G = (V, E) adalah sebuah graf. G 1 = (V 1 , E 1 ) adalah upagraf (subgraph) dari G jika V 1 termasuk V dan E 1 termasuk E.
7. Graf Berbobot (Weighted Graph) Graf berlabel (weighted graph) adalah suatu graf yang setiap garisnya berhubungan dengan suatu bilangan riil tak negatif yang menyatakan bobot garis tersebut. Bobot garis e biasanya diberi simbol w(e). Jumlah bobot semua garis disebut total bobot. a 10 e 15 d
12 8
11 14
b 9
c
Gambar 2.5 Graf Berbobot (Weighted Graph)
2.4. Representasi Graf Bila graf akan diproses dengan komputer, maka graf harus direpresentasikan di dalam memori. Terdapat beberapa representasi yang mungkin untuk graf. Disini hanya akan diberikan dua macam representasi yang sering digunakan, yaitu matriks ketetanggaan dan matriks bersisian.
Universitas Sumatera Utara
1. Matriks Ketetanggaan atau matriks hubung (adjacency matrix) Matriks ketetanggan atau matriks hubung adalah representasi graf paling umum. Misalkan G = (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan G adalah matriks dwimatra yang berukuran n x n. Bila matriks tersebut dinamakan A = [a ij ], maka : a ij = (1, jika simpul i dan j bertetangga) a ij = (0, jika simpul i dan j tidak bertetangga) Karena matriks ketanggaan 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 nol) dan true (menyatakan 1)
Gambar
dibawah
memperlihatkan
graf
sederhana
dengan
matriks
ketetanggaannya, masing-masing graf terhubung, graf tak terhubung dan graf berarah.
1
2
5
3
1 2 3 4 0 1 1 0
1 0 1 1
3
2
4
1 2 3 4
1
1
1 1 0 1
(a)
0 1 1 0
2
3
4
4
1 2 3 4 5 1 0 2 1 3 1 4 0 5 0
1 0 1 0 0
1 1 0 1 0
(b)
0 0 1 0 0
0 0 0 0 0
1 2 3 4 1 2 3 4
0 1 1 0
1 0 0 1
0 1 0 1
0 1 0 0
(c)
Gambar 2.6 Tiga buah graf dengan matriks ketetanggaannya masing-masing
Universitas Sumatera Utara
Matriks ketetanggaan untuk graf sederhana dan tidak berarah selalu simetri, sedangkan utuk graf berarah matriks ketetanggaannya belum tentu simetri (akan simetri jika berupa graf berarah lengkap).
2. Matriks Bersisian (incidency matrix) Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalkan G = (V,E) adalah graf dengan n simpul dan m buah sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran m x m baris. Baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut dinamakan A = [a ij ], maka a ij = (1, jika simpul i bersisian dengan sisi j ) a ij = {0, jika simpul i tidak bersisian dengan sisi j )
e1 1
2 e4
e2
e3 3
e5 4
e1 e2 e3 e4 e5 1 2 3 4
1 1 0 0
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1
Gambar 2.7 Graf (atas) dan matriks bersisiannya (bawah)
Universitas Sumatera Utara
2.5. Pohon (Tree) Diantara sekian banyak konsep dalam teori graf, konsep pohon (tree) merupakan konsep yang paling populer dan penting karena konsep ini mampu mendukung pemecahan masalah dalam berbagai terapan graf. Dalam kehidupan sehari-hari, orang telah lama menggunakan pohon untuk menggambarkan hirarkhi. Misalnya, pohon silsilah keluarga, struktur organisasi dan lain sebagainya. Konsep pohon digunakan sejak tahun 1857 oleh seorang matematikawan Inggris bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.
2.5.1. Definisi Pohon Pohon dapat didefinisikan sebagai graf tak-berarah terhubung yang tidak mengandung sirkuit. (Rinaldi, 2005). Menurut definisi diatas, ada dua sifat penting pada pohon yaitu terhubung dan tidak mengandung sirkuit. Pohon dinotasikan dengan T = (V,E) Keterangan : T : Tree V : Vertices atau node atau vertex atau simpul, V merupakan himpunan tidak kosong. V = {v 1 ,v 2 ,…,v n } E : Edges atau Arcs atau sisi yang menghubungkan simpul E = {e 1 ,e 2 ,…,e n } Pada gambar 2.8 dibawah ini, hanya G 1 dan G 2 yang pohon, sedangkan G 3 dan G 4 bukan pohon. G 3 bukan pohon karena mengandung sirkuit a, d, f dan a, sedangkan G 4 bukan pohon karena tidak terhubung (persilangan dua sisi, sisi (a,f) dan sisi (b,e) karena titik silangnya bukan menyatakan simpul) a
b
a
b
a
b
a
b
c
d
c
d
c
d
c
d
e
f
G1
e
f
G2
e
f
G3
e
f
G4
Universitas Sumatera Utara
Gambar 2.8 G 1 dan G 2 adalah pohon, sedangkan G 3 dan G 4 bukan pohon
2.5.2. Sifat-sifat Pohon Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen:
1. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal. 2. G terhubung dan memiliki m = n – 1 buah sisi. 3. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi. 4. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit.
2.5.3. Pohon Merentang (Spanning Tree) Di dalam konsep pohon sendiri, terdapat banyak jenis pohon yang digunakan sebagai cara untuk mencari solusi dari masalah dalam dunia terapan graf. Dan yang akan dibahas disini adalah penggunaan pohon merentang atau lebih dikenal dengan Spanning Tree. Misalkan G = (V,E) adalah graf tidak berarah terhubung yang bukan pohon yang berarti di G terdapat beberapa sirkuit. G dapat diubah menjadi pohon T = (V 1 ,E 1 ) dengan cara memutuskan sirkuit-sirkuit yang ada. Caranya mula-mula dipilih sebuah sirkuit, lalu hapus satu buah sisi dari sirkuit ini. G akan tetap terhubung dan jumlah sirkuitnya berkurang satu. Bila proses ini dilakukan berulang-ulang sampai semua sirkit di G hilang, maka G menjadi sebuah pohon T, yang dinamakan pohon merentang (spanning tree). Disebut pohon merentang karena semua simpul pada pohon T sama dengan semua simpul pada graf G dan sisi-sisi pada pohon T ⊆ sisi-sisi pada graf G. Dengan kata lain V 1 = V dan E 1 ⊆ E. Jadi pohon merentang (spanning tree) suatu graf G terhubung adalah upagraf G merentang yang berupa pohon dan memuat semua titik dalam G. Dibawah ini adalah contoh pembentukan pohon merentang.
f
T1
Gambar 2.9 G adalah Graf, T 1 dan T 2 adalah Pohon Merentang dari Graf G
Universitas Sumatera Utara
Keterangan :
1.
T 1 dan T 2 merupakan pohon merentang dari graf G
2.
Pohon merentang T 1 dibentuk dengan cara menghapus sisi {(a,c),(b,c),(b,d),(c,d),(e,f)} dari graf G.
3.
Pohon merentang T 2 dibentuk dengan cara menghapus sisi {(a,f),(a,b),(b,c),(b,e),(c,d)} dari graf G.
2.5.4. Pohon Merentang Minimum (Minimum Spanning Tree) Jika G pada gambar 2.10 merupakan graf berbobot, maka bobot pohon merentang T 1 atau T 2 didefinisikan sebagai jumlah bobot semua sisi di T 1 atau T 2 . Diantara pohon merentang yang ada pada G, yang paling penting adalah pohon merentang dengan jumlah bobot sisi e minimum. Pohon merentang dengan jumlah bobot sisi e minimum ini disebut dengan pohon merentang minimum atau Minimum Spanning Tree (MST). Contoh aplikasi MST yang digunakan dalam penulisan skripsi ini adalah masalah pemasangan jaringan kabel
listrik menggunakan graf. MST
digunakan untuk memilih jalur dengan jumlah bobot terkecil yang akan meminimalkan biaya pemasangan kabel listrik
30
45
f 25
55 15 T1
Gambar 2.10. G adalah Graf Berbobot, T 1 dan T 2 adalah Pohon Merentang Berbobot dari Graf G.
Dari graf berbobot G, kita harus menentukan pohon merentang mana yang paling minimum. Apakah T 1 atau T 2 , hal tersebut yang akan dicari dengan membangun pohon merentang yang mempunyai jumlah jalur terpendek, dengan kata lain harus dicari pohon merentang minimum. Cara yang paling sederhana adalah dengan mendaftarkan semua pohon merentang berbobot yang mungkin dibuat (dalam hal ini T 1 dan T 2 ) dan menghitung total bobot tiap-tiap pohon merentang. Selanjutnya dipilih pohon merentang dengan total bobot sisi e yang paling kecil. Metode ini tidak
Universitas Sumatera Utara
efisien, terutama pada graf cukup besar karena terdapat banyak sekali pohon merentang yang dapat dibuat.
2.5.5. Algoritma Prim Pada tahun 1956 seorang computer scientist Robert C Prim berhasil menyusun algoritma untuk membuat pohon merentang minimum secara efisien. Algoritma Prim membentuk MST langkah per langkah. Pada setiap langkah dipilih sisi e dari graf G yang mempunyai bobot minimum dan bersisian dengan simpul-simpul di dalam T tetapi e tidak membentuk sirkuit didalam T. Ada 3 (tiga) langkah yang dilakukan pada algoritma Prim, yaitu : 1.
Pilih sisi graf G yang berbobot paling minimum dan masukkan ke dalam T
2.
Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e tidak membentuk sirkuit di T, lalu masukkan e ke dalam T.
3.
Ulangi langkah ke-dua sebanyak n-2 kali.
Jumlah langkah seluruhnya didalam algoritma Prim adalah 1 + ( n – 2 ) = n - 1 yaitu sebanyak jumlah sisi didalam pohon merentang dengan n buah simpul.
Universitas Sumatera Utara
