2
dari elemen graf yang disebut verteks (node, point), sedangkan , atau biasa disebut ( ), adalah himpunan pasangan tak terurut yang menghubungkan dua elemen subset dari yang disebut sisi (edge, line). Setiap sisi { , } pada biasanya dinotasikan dengan atau . (Chartrand & Zhang 2009)
merupakan himpunan sisi-sisi tidak berarah pada . (Yaoyuenyong et al. 2002)
:
1
7 5
8
2
6
9
Definisi 2 (Order dan size graf) Banyaknya verteks dari suatu graf disebut order dan banyaknya sisi pada suatu graf disebut size dari graf.
3 4
Gambar 3 Graf campuran.
:
Pada Gambar 3, sisi 1 , 9 , 4 dan 6 merupakan sisi berarah, sisi 2 , 3 , 5 , 7 , dan 8 merupakan sisi yang tidak berarah. Gambar 1 Graf
= ( , ).
Pada Gambar 1 diperlihatkan bahwa = , , , dan = {{ , }, { , }, { , }}. Order dari graf pada Gambar 1 ialah 4 dan size-nya ialah 3. Definisi 3 (Graf berarah/digraf) Graf berarah adalah pasangan terurut ( , ) dengan himpunan takkosong yang hingga, dan himpunan pasangan terurut yang menghubungkan elemen-elemen di . Elemen-elemen dari disebut sisi berarah (arc). Sisi berarah ( , ) dinyatakan dengan garis berarah dari ke .
Definisi 5 (Graf/digraf berbobot) Suatu graf = , atau digraf = , dikatakan berbobot jika terdapat sebuah fungsi : atau : (dengan adalah himpunan bilangan real) yang memberikan sebuah bilangan real, disebut bobot, pada setiap sisi di atau sisi berarah di . Setiap bobot dengan atau dinotasikan dengan . (Foulds 1992)
:
8 7
12 10
(Chartrand & Zhang 2009) Gambar 4 Graf berbobot.
:
Bobot tiap sisi untuk graf pada Gambar 4 adalah = 8, = 12, = 7, = 10.
Gambar 2 Graf berarah
= ( , ).
Pada Gambar 2 diperlihatkan bahwa = , , , dan = {( , ), ( , ), ( , )}. Definisi 4 (Graf campuran) Graf campuran = ( , ) merupakan graf yang memiliki dua jenis sisi, yakni sisi yang berarah dan tidak berarah. merupakan himpunan sisi-sisi berarah pada dan
Definisi 6 (Adjacent dan incident) Misalkan dan verteks pada graf . Verteks dikatakan tetangga (adjacent) dari jika ada sisi yang menghubungkan verteks dan , yaitu = . Himpunan semua tetangga dari verteks dinotasikan dengan ( ). Jika = adalah sisi pada graf maka dikatakan incident dengan verteks dan . (Chartrand & Zhang 2009)
3
:
:
2 3
1 6
4 5
Gambar 7 Multidigraf. Gambar 5 Adjacent dan incident. Ilustrasi adjacent dan incident diperlihatkan pada Gambar 5. Verteks adjacent dengan , , dan . Verteks incident dengan 2 tetapi tidak incident dengan 4 . Definisi 7 (Graf lengkap) Suatu graf yang ber-order dengan setiap verteks pada adjacent dengan verteks lainnya disebut graf lengkap, dinotasikan dengan . (Chartrand & Oellermann 1993)
Definisi 9 (Derajat/degree) Derajat suatu verteks adalah banyaknya sisi yang incident dengan verteks , dan dinotasikan dengan deg atau ( ). Jika banyaknya simpul yang incident dengan verteks adalah bilangan ganjil, maka dikatakan berderajat ganjil. Jika banyaknya simpul yang incident dengan verteks adalah bilangan genap, maka dikatakan berderajat genap. (Vasudev 2006)
:
Pada Gambar 5 diperlihatkan bahwa setiap verteks adjacent dengan verteks lainnya, sehingga graf pada Gambar 5 merupakan graf lengkap. Definisi 8 (Multigraf/multidigraf) Suatu graf/digraf dikatakan multigraf atau multidigraf bila graf/digraf tersebut memiliki lebih dari satu sisi/sisi berarah yang incident dengan satu pasang verteks. (Foulds 1992) Ilustrasi multigraf dapat dilihat pada Gambar 6 berikut.
Gambar 8 Ilustrasi derajat pada graf. Pada Gambar 8 terlihat bahwa verteks , , dan berderajat genap, sedangkan verteks dan berderajat ganjil. Definisi 10 (Graf genap) Suatu graf dikatakan graf genap, jika setiap verteksnya berderajat genap. (Eiselt et al. 1995)
: :
Gambar 9 Graf genap. Gambar 6 Multigraf. Gambar 6 merupakan contoh multigraf karena verteks dan dihubungkan oleh lebih dari satu sisi. Ilustrasi multidigraf bisa dilihat pada Gambar 7 berikut.
Ilustrasi graf genap bisa dilihat pada Gambar 9, karena pada Gambar 9 setiap verteks berderajat genap. Definisi 11 (Derajat masuk/in-degree) Pada graf berarah, in-degree suatu verteks , yang dinotasikan dengan ( ), adalah
4
banyaknya sisi berarah yang berakhir di verteks . (Vasudev 2006) Pada Gambar 2 diperlihatkan derajat masuk tiap verteksnya = 0, = 1, = 1, = 1. Definisi 12 (Derajat keluar/out-degree) Pada graf berarah, out-degree suatu verteks , yang dinotasikan dengan + ( ), adalah banyaknya sisi berarah yang dimulai pada verteks . (Vasudev 2006) Pada Gambar 2 diperlihatkan derajat keluar tiap verteksnya + = 2, + = + + 0, = 0, = 1. Definisi 13 (Digraf balans) Suatu digraf dikatakan balans jika setiap verteks pada digraf tersebut memiliki = 0, dengan adalah selisih dari derajat masuk dengan derajat keluar verteks . (Diestel 1997)
:
Definisi 15 (Graf campuran genap) Suatu graf campuran dikatakan graf genap jika underlying graph-nya berupa graf genap. (Assad & Golden 1995)
:
Gambar 11 Graf campuran. Pada Gambar 11, graf tersebut berupa graf genap dengan underlying graph-nya bisa dilihat pada Gambar 9. Definisi 16 (Jalan/walk) Walk pada suatu graf adalah barisan berhingga, = atau +1 +1 = yang dimulai dari +1 suatu verteks dan berakhir pada suatu verteks juga, sehingga setiap sisi di dalam barisan harus incident dengan verteks sebelum dan sesudahnya. (Chartrand & Zhang 2009) Definisi 17 (Walk berarah) Walk berarah pada suatu digraf adalah walk yang sesuai dengan arah sisinya atau tidak berlawanan arah. (Vasudev 2006)
: Gambar 10 Ilustrasi digraf balans.
2 3
1 4
Digraf pada Gambar 10 adalah digraf balans karena setiap verteks memiliki = 0. Definisi 14 (Underlying graph) Jika suatu graf didapat dengan cara menghapus semua arah dari sisi berarah pada digraf , maka graf tersebut adalah underlying graph dari digraf . (Vasudev 2006) Ilustrasi underlying graph bisa dilihat dari Gambar 9 dan Gambar 10. Graf pada Gambar 9 merupakan underlying graph dari digraf pada Gambar 10.
5
Gambar 12 Graf berarah. Ilustrasi walk berarah pada suatu digraf bisa dilihat pada Gambar 12. = 2 4 adalah walk berarah. Definisi 18 (Trail) Trail pada suatu graf adalah walk dengan semua sisi dalam barisannya tidak berulang. (Chartrand & Zhang 2009) Ilustrasi trail bisa dilihat pada Gambar 5, = adalah trail. 3 5 4
5
Definisi 19 (Path) Path pada suatu graf adalah walk yang setiap verteks pada barisannya hanya muncul satu kali. (Vasudev 2006) Ilustrasi path bisa dilihat pada Gambar 5, yaitu = 2 4 5 . Definisi 20 (Path berarah) Path berarah pada suatu digraf adalah walk berarah dengan semua verteks dalam barisannya tidak berulang. (Vasudev 2006)
Ilustrasi cycle bisa dilihat pada Gambar 8. Graf pada Gambar 8 memiliki cycle = . Definisi 25 (Terhubung/connected) Suatu graf disebut terhubung (connected) jika untuk setiap verteks dari terhubung. Verteks dengan dikatakan terhubung jika ada setidaknya satu path dari verteks ke verteks . (Vasudev 2006)
Ilustrasi path berarah bisa dilihat pada Gambar 12. = adalah path 2 4 5 berarah.
Definisi 26 (Digraf terhubung) Suatu digraf dikatakan terhubung (connected) jika underlying graph-nya terhubung. (Chartrand & Oellermann 1993)
Definisi 21 (Sirkuit) Pada graf tidak berarah, sirkuit adalah trail tertutup yang takkosong. (Chartrand & Zhang 2009)
Definisi 27 (Subgraf) Suatu graf dikatakan subgraf dari graf jika ( ) ( ) dan ( ) ( ). (Chartrand & Oellermann 1993)
Ilustrasi sirkuit bisa dilihat pada Gambar 5, yaitu = 3 6 2 .
Graf pada Gambar 1 merupakan subgraf dari graf pada Gambar 8.
Definisi 22 (Sirkuit berarah) Pada suatu digraf, sirkuit berarah adalah walk berarah yang tertutup sehingga barisannya dimulai dan diakhiri pada verteks yang sama dan tidak ada sisi yang diulang. (Vasudev 2006)
Definisi 28 (Spanning subgraph) Suatu subgraf dikatakan spanning subgraph jika subgraf tersebut mengandung semua verteks pada graf . (Vasudev 2006)
Ilustrasi sirkuit berarah bisa dilihat pada Gambar 12, yaitu = 2 1 3 . Definisi 23 (Semisirkuit) Pada suatu digraf, semisirkuit adalah sirkuit pada underlying graph , tetapi bukan merupakan sirkuit berarah pada digraf tersebut. (Vasudev 2006)
Graf pada Gambar 1 merupakan spanning subgraph dari graf pada Gambar 4. Definisi 29 (Tree pada graf) Suatu graf terhubung yang tidak memiliki cycle disebut tree. (Chartrand & Zhang 2009) Graf pada Gambar 1 merupakan tree.
Ilustrasi semisirkuit bisa dilihat pada Gambar 12, yaitu = 3 1 2 .
Definisi 30 (Tree pada digraf) Suatu digraf terhubung yang tidak memiliki cycle disebut tree pada digraf. (Chartrand & Zhang 2009)
Definisi 24 (Cycle) Pada graf tidak berarah, cycle adalah path tertutup yang takkosong. (Chartrand & Zhang 2009)
Ilustrasi tree untuk digraf dapat dilihat pada Gambar 2.
6
Definisi 31 (Spanning tree) Suatu spanning tree adalah spanning subgraph yang merupakan tree. (Vasudev 2006)
:
2 3
1 4
15 merupakan spanning arborescence dari digraf pada Gambar 7, dengan akar arborescence-nya di .
Definisi 34 (Graf r-regular) Sebuah graf merupakan graf r-regular, atau graf regular berderajat r, jika setiap verteks pada memiliki derajat r. (Chartrand & Oellermann 1993)
5
Gambar 13 Graf berarah.
:
:
2
4 5
Gambar 14 Spanning tree. Digraf pada Gambar 14 adalah spanning tree dari digraf pada Gambar 13. Definisi 32 (Arborescence) Graf berarah disebut arborescence jika a.
tidak memiliki sirkuit berarah maupun semisirkuit. b. Pada terdapat tepat satu verteks yang memiliki = 0.
Gambar 16 Graf 2-regular. Pada Gambar 16, setiap verteks memiliki derajat 2 atau graf regular berderajat 2. Definisi 35 (Matching) Matching pada sebuah graf merupakan subgraf 1-regular, yaitu berupa himpunan sisi-sisi yang tidak adjacent. (Chartrand & Oellermann 1993)
: 4
1 7
Verteks
disebut akar arborescence. (Vasudev 2006)
2
3 6 5
Definisi 33 (Spanning arborescence) Spanning arborescence pada digraf adalah spanning tree yang berupa arborescence. (Vasudev 2006)
Gambar 17 Graf untuk ilustrasi matching. = { 1 , 2 , 3 } adalah salah satu matching pada graf di Gambar 17. Definisi 36 (Matching yang Perfect) Jika adalah sebuah graf ber-order yang memiliki matching berkardinalitas /2, maka matching tersebut dikatakan matching yang perfect. (Chartrand & Oellermann 1993)
:
Gambar 15 Spanning arborescence. Ilustrasi spanning arborescence bisa dilihat pada Gambar 15. Digraf pada Gambar
7
pada , maka = ( , )= adalah kapasitas sisi berarah . (Chartrand & Oellermann 1993)
: 2
1
: 3
5
2
2
5
3
4
2
Gambar 18 Graf untuk ilustrasi matching yang perfect.
Gambar 20 Network.
Graf pada Gambar 18 ber-order 6 dan = { 1 , 3 , 5 } merupakan matching yang berkardinalitas 3, sehingga adalah matching yang perfect.
Network pada Gambar 20 menunjukkan bahwa , =5 dan , = 2. Source ( ) pada Gambar 20 memiliki derajat masuk nol dan sink ( ) pada Gambar 20 memiliki derajat keluar nol.
Definisi 37 (Matching berbobot minimum) Matching berbobot minimum merupakan matching dengan jumlah bobot pada sisinya adalah minimum. (Chartrand & Oellermann 1993)
: 6
2
Definisi 39 (Flow / arus) Suatu flow pada suatu network dengan digraf = ( , ) adalah suatu + pemadanan {0} yang memadankan setiap sisi = ( , ) dengan bilangan real taknegatif, sehingga memenuhi kondisi sebagai berikut : 1.
2 1
3 1 2
Gambar 19 Graf berbobot. Matching yang perfect pada graf Gambar 19 hanya 1 = { , , . , , } dengan bobot 10 dan , , , } 2 = { , , dengan bobot 6. Jadi, 2 adalah matching yang perfect dengan bobot minimum. Definisi 38 (Network) Secara umum, network merupakan sebuah digraf atau graf berarah =( , ) dengan dua verteks spesial yaitu verteks yang disebut source dan verteks yang disebut sink, serta memiliki fungsi pada yang bernilai integer taknegatif yang disebut kapasitas. Jika = ( , ) adalah sebuah arc
6
( ) ( ) untuk setiap sisi di dinamakan kendala kapasitas.
2.
(, )= { :( , )
}
yang
(, ) { :( , )
}
untuk semua , yang dinamakan kendala konservasi. (Chartrand & Oellermann 1993) Nilai = (, )= pada sisi dapat dipandang sebagai banyaknya komoditas yang diangkut pada sisi tersebut, sedangkan kendala konservasi menyatakan bahwa total arus yang masuk ke suatu verteksantara (yaitu verteks selain verteks dan ) sama dengan total arus yang keluar dari verteks tersebut.
8
berkaitan dengan graf Euler yang digunakan dalam karya ilmiah ini.
: (2,1)
(3,2) (2,5)
(5,3) (5,2)
Gambar 21
(6,5)
Network dengan kapasitas dan flow.
Definisi 41 (Sirkuit Euler) Sirkuit Euler adalah sirkuit yang melewati semua sisi pada graf tepat satu kali. (Vasudev 2006)
:
1
Pada Gambar 21 diberikan contoh network berikut kapasitas dan flow sisi berarah ( , ). Sebagai contoh, sisi berarah ( , ) memiliki kapasitas 5 dan flow 2.
2
3
4
5 6
Gambar 22 Graf Euler. Definisi 40 (Minimum Cost Flow) Diberikan network dengan digraf = , . Misalkan adalah biaya yang diperlukan yang melalui arc ( , ) dan adalah kapasitas yang melalui arc ( , ) . Minimum cost flow merupakan suatu permasalahan dalam menentukan flow dengan biaya minimum pada suatu graf berarah. Formulasi matematikanya secara umum sebagai berikut min
= (, )
Kendala = () { :( , )
}
0
{ :( , )
}
(, ) (Ahuja et al. 1993)
Nilai ( ) menyatakan banyaknya penawaran (bila ( ) > 0) atau permintaan (bila ( ) < 0), dengan . 2.2 Graf Euler Leonhard Euler (1707-1783) adalah seorang peneliti yang lahir di Swiss. Ia dipandang sebagai salah satu matematikawan terbesar sepanjang masa. Leonhard Euler menyumbangkan berbagai penemuan penting di bidang yang beragam seperti kalkulus dan teori graf. Dalam penelitiannya di bidang teori graf, Euler mengenalkan penemuan yang paling terkenal yaitu graf Euler. Berikut ini akan dijelaskan beberapa definisi dan teorema yang
Ilustrasi sirkuit Euler bisa dilihat pada Gambar 22. Sirkuit Euler pada graf salah satunya = 1 3 4 6 5 2 . Definisi 42 (Graf/digraf Euler) Graf atau digraf yang memiliki sirkuit Euler disebut graf atau digraf Euler. (Vasudev 2006) Graf pada Gambar 22 merupakan graf Euler, karena graf tersebut memiliki sirkuit Euler. Teorema 1 campuran)
(Graf
Euler
pada
graf
Misalkan diberikan graf campuran =( , ), dengan himpunan sisi tak berarah dan himpunan sisi berarah. Graf campuran memiliki sirkuit Euler jika dan hanya jika a. terhubung dan genap b. untuk setiap ( ), berlaku |
,
,
|
,
dengan , adalah banyaknya sisi berarah yang berawal dari suatu verteks di dan berakhir di suatu verteks di , sedangkan , merupakan banyaknya sisi tidak berarah yang menghubungkan verteks di dengan verteks di , dan = \ . (Assad & Golden 1995) Graf pada Gambar 23 berikut tidak memiliki sirkuit Euler, walaupun syarat (a) sudah terpenuhi, namun syarat (b) tidak terpenuhi.
9
Misalkan = 1 , maka = 2,3,4,5,6 , sehingga nilai , = 0, , = 2, , = 0, dan , , = 0 2 >0= , , berarti terdapat ( ), sehingga berlaku , , > , Jadi syarat (b) tidak dipenuhi.
:
Banyak algoritme yang dapat digunakan dalam pencarian sirkuit Euler dalam suatu digraf. Salah satu dari algoritme itu adalah algoritme van Aardenne-Ehrenfest & de Bruijn (Balakrishnan 1997). Berikut ini akan dibahas langkah-langkah algoritme tersebut. Langkah 0. Diberikan digraf .
4 5
3
2.3 Algoritme van Aardenne-Ehrenfest & de Bruijn
Langkah 1. Dibangun sebuah spanning arborescence dari digraf yang berakar di . 6
1
2
Langkah 2. Sisi berarah yang keluar dari dan verteks-verteks lain diurutkan dan dilabeli sedemikian hingga sisi berarah terakhir yang dilabeli adalah sisi berarah pada arborescence.
Gambar 23 Graf campuran yang bukan graf Euler. Graf pada Gambar 24 berikut merupakan graf terhubung dan genap (syarat (a) terpenuhi).
: 1
3
2
Gambar 24 Graf Euler.
Langkah 3. Dimulai dari sembarang verteks, sisi berarah dengan label terendah yang belum dilewati dipilih untuk sampai ke verteks berikutnya. Prosedur ini dilanjutkan hingga semua sisi berarah telah dilewati. Berikut ini contoh sederhana untuk mengimplementasikan algoritme van Aardenne-Ehrenfest & de Bruijn pada sebuah digraf Euler. Langkah 0. Diberikan digraf Euler seperti pada Gambar 25.
Tabel 1 Penentuan syarat (b) berdasarkan graf pada Gambar 24 , {1} {2} {3} {1,2} 1,3 {2,3} {1,2,3}
{2,3} {1,3} {1,2} {3} {2} {1} {1,2,3}
0 1 1 1 0 1 0 0
, 1 0 1 1 1 0 0 0
Dari Tabel 1, dapat disimpulkan bahwa untuk setiap ( ), berlaku | , , | , . Jadi kriteria (b) pada Teorema 1 juga dipenuhi. Akibatnya mempunyai sirkuit Euler dan contoh sirkuit Eulernya adalah 2 3 1 2.
2
1
4
, 1 1 0 0 1 1 0 0
3
1
2
3
2
3
2 4
2
5
Gambar 25 Digraf Euler. Langkah 1. Spanning arborescence dari graf pada Gambar 25 yang berawal di verteks 1 adalah sebagai berikut : 1
2
3
5
4
Gambar 26 Spanning arborescence.
10
Langkah 2. Semua sisi berarah diurutkan dan dilabeli dimulai dari verteks 1 secara sembarang dengan label terakhir adalah label untuk sisi berarah yang dipakai di arborescence, sehingga label digraf menjadi seperti berikut. L2 1
2
L1 L2
L1
L1
L2 L1
L2 5
3
c. ditentukan = min{ ( )| }. Jika yang dipilih sebagai verteks dengan = , maka merupakan jarak antara 0 dengan , dan +1 , d. { +1 } dan { +1 }, e. + 1. Jika = 1, proses dihentikan; lainnya kembali ke langkah b. (Chartrand & Oellermann 1993) Berikut ini diberikan contoh penggunaan algoritme Dijkstra pada graf tidak berarah.
L2 4
Gambar 27 Pelabelan pada sisi berarah.
Diberikan graf berbobot berikut :
:
Langkah 3. Sirkuit Euler yang diperoleh, misalkan dimulai dari verteks 1, adalah : 1 4 2 5 1 2 3 4 5 1, dengan total bobot 21.
5 6
4
2
7
4
12
8
4
2
2 8
1
4
Solusi sirkuit Euler yang diperoleh tidak hanya seperti di atas. Jika dimulai dari verteks lain, maka yang dilaluinya pun berbeda namun dengan total bobot yang sama. 2.4 Algoritme Dijkstra Algoritme ini bisa digunakan untuk mencari path terpendek atau jarak terpendek pada graf atau digraf atau graf campuran yang tidak berbobot maupun yang berbobot pada graf ber-order . Misalkan diberikan graf berbobot = ( , ) dengan himpunan = {1,2,3, . } dan bobot pada tiap verteksnya taknegatif. Pada setiap langkah dalam algoritme didefinisikan sebuah variabel PARENT(v) yang menyatakan verteks yang mendahului verteks v pada path terpendek yang telah diperoleh. Variabel PARENT(v) diperbaharui jika ditemukan path yang lebih pendek. Misalkan adalah himpunan semua verteks dari yang jaraknya dengan 0 sudah ditentukan. Langkah-langkah algoritme penentuan path terpendek yang dimulai dari verteks ialah sebagai berikut.
1
5
6
5
6 3
2
3
Gambar 28 Graf contoh algoritme Dijkstra. Akan ditentukan jarak terpendek dari satu verteks ke verteks lainnya. Misalkan verteks awalnya adalah verteks 3, maka dengan algoritme Dijkstra akan diperoleh path terpendek dari verteks 3 menuju verteks lain seperti pada Gambar 29 (penghitungan lebih lengkap dapat dilihat pada Lampiran 1).
: 1
5
6 7
4
2 4
1 8
8 a. inisialisasikan sebuah verteks awal 0 dengan jarak 0), 0 = 0, ( { 0 }, { 0 }, dan jarak verteks lainnya bernilai untuk semua { 0 }, PARENT 0 ; jika = 1, maka proses dihentikan; lainnya, proses dilanjutkan. b. untuk setiap , sehingga ( ), diperiksa: Jika + ( ), maka proses dilanjutkan; lainnya, + ( ) dan PARENT( ) ,
6
2
3
5
3 Gambar 29 Solusi path terpendek algoritme Dijkstra dengan verteks awal 3. Misalkan dicari jarak terdekat dari verteks 3 ke verteks 1 pada graf Gambar 29, maka path-nya adalah = 3 4 1 dengan jarak 8.
