BAB 2
LANDASAN TEORI
Sebelum memulai pembahasan lebih lanjut, pertama-tama haruslah dijelaskan apa yang dimaksud dengan traveling salesman problem atau dalam bahasa Indonesia disebut sebagai “persoalan pedagang keliling”. Persoalan ini muncul dari suatu pertanyaan : bila diketahui sejumlah kota dan biaya untuk berpindah dari satu kota ke kota lainnya, bagaimana cara kita untuk bisa mengunjungi tiap kota tersebut tepat sekali kunjungan dan kembali ke kota tempat kita berangkat , dengan biaya yang seminimum mungkin ?
Terdapat
berbagai pengertian dasar dari jaringan yang akan menunjang segala
permasalahan yang ada dalam graph. Pengertian-pengertian dasar tersebut merupakan konsepkonsep yang terdapat pada teori graph karena pada hakekatnya suatu jaringan adalah suatu graf yang mempunyai karakteristik tambahan. Karakteristik tambahan tersebut disebut bobot
2.1. Pengertian Jaringan
Karena jaringan merupakan suatu graf yang mempunyai karakteristik tambahan yang disebut bobot,maka akan diuraikan definisi-definisi formal dari suatu graf beserta definisi definisi lainnya.
Teori dasar graf Graf G adalah pasangan himpunan (V,E) di mana V adalah himpunan dari vertex dan E adalah himpunan dari edge yang menghubungkan sepasang simpul (Johnsonbaugh Richard, 2001; 265)
Atau graf G didefenisikan sebagai pasangan himpunan (V,E) dalam hal ini: V=himpunan tidak kosong dari simpul-simpul (vertex) V={ v1,v2,...,vn } dan E= himpunan sisi (edge) yang menghubungkan sepasang simpul E={ e1,e2,...,en } Atau dapat ditulis singkat notasi G=(V,E) (Munir, 2003) Banyaknya simpul (anggota V) disebut order Graf G, sedangkan banyaknya ruas (anggota E) disebut ukuran (size) Graf G
Definisi 2.1.1. Loop dan Edge Paralel Sebuah edge yang menghubungkan pasangan vertex yang sama yakni (vi,vi) disebut loop dan dua buah atau lebih edge yang mempunyai vertex -vertex ujung yang sama disebut edgeedge yang paralel atau multiple edge. Pada gambar 2.1 dapat dilihat, gambar G1 tidak memiliki loop maupun edge pararel, sedangkan pada gambar G2 tidak memiliki loop tetapi memiliki edge paralel yaitu e3,e4 dan e1,e6. Dan pada gambar G3 memiliki loop yaitu e8 dan edge pararel yaitu e3, e4 dan e1, e6. Defenisi 2.1.2. Graf Sederhana (Simple Graf) Simple graph adalah graf yang tidak memuat loop dan edge-edge yang paralel. V4
e3
V3 e2
e4 V1
e1
V2
Gambar 2.1. graf sederhana Definisi 2.1.3. Ketetanggaan (Adjacent) Dua buah simpul pada graf dikatakan bertetangga bila kedua simpul tersebut terhubung langsung. Atau dapat kita sebut, vj bertetangga dengan vk pada graf G jika (vj,vk) adalah sisi pada sebuah graf G.
Definisi 2.1.4. Bersisian (Incident) Untuk sembarang sisi e = ( vj, vk ) dikatakan e bersisian dengan simpul vj, atau e bersisian dengan simpul vk.
Definisi 2.1.5. Simpul Terpencil (Isolated Vertex ) Simpul yang tidak memiliki sisi yang bersisian dengannya atau tidak bertetangga dengan simpul lainnya disebut dengan simpul terpencil. Definisi 2.1.6. Graf Kosong (Null Graf) Graf yang himpunan sisinya merupakan himpunan kosong (Nn) disebut graf kosong, dimana n adalah jumlah simpul.
1
2
3
4
Gambar 2.2 graf kosong
Definisi 2.1.7 Derajat (Degree) Derajat dari sebuah vertex vi dalam graf G adalah jumlah edge yang bersisian dengan vi, dengan loop dihitung dua kali. Bila jumlah edge yang bersisian dengan jumlah vertex vi adalah n maka degree dari vi adalah n sehingga d(vi) = n. Definisi 2.1.8 Subgraf G‘(V‘, E‘) adalah Subgraf dari G (V, E) bila : V‘ ⊂ V dan E‘ ⊂ E Apabila E‘ mengandung semua ruas di E yang kedua ujungnya di V‘ , maka G‘ adalah Subgraf yang dibentuk oleh V‘ (Spanning Subgraph)
2.2 Jenis jenis graph atau jaringan Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: 1. Graf sederhana (Simple Graf) Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. 2. Graf tak-sederhana (Unsimple-Graf)
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana
(unsimple
graf). Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis: 1. Graf berhingga (Limited Graf) Graf berhingga adalah graf yang jumlah simpulnya n berhingga. 2. Graf tak-berhingga (Unlimited Graf) Graf yang jumlah simpulnya n tidak berhingga banyaknya disebut graf tak berhingga.
Berdasarkan orientasi arah dan bobotnya, maka secara umum graf dibedakan atas 4 jenis: 1. graf berarah dan berbobot Graf yang tiap busurnya mempunyai arah atau anak panah dan berbobot.
Gambar 2.3 Graf berarah dan berbobot
Gambar 2.3 menunjukkan graf berarah dan berbobot yang terdiri dari tujuh titik yaitu titik A,B,C,D,E,F,G. Titik menujukkan arah ke titik B dan titik C, titik B menunjukkan arah ke titik D dan titik C, dan seterusnya. Bobot antar titik A dan titik B pun telah di ketahui.
2. Graf tidak berarah dan berbobot Graf tidak berarah dan berbobot : tiap busur tidak mempunyai anak panah tetapi mempunyai bobot.
Gambar 2.4 Graf tak berarah dan berbobot Gambar 2.4 menunjukkan graf tidak berarah dan berbobot. Graf terdiri dari tujuh titik yaitu titik A,B,C,D,E,F,G. Titik A tidak menunjukkan arah ke titik B atau C, namun bobot antara titik A dan titik B telah diketahui. Begitu juga dengan titik yang lain.
3. Graf berarah dan tidak berbobot Graf berarah dan tidak berbobot adalah graf yang pada setiap busurnya mempunyai arah dan tidak mempunyai bobot.
Gambar 2.5 Graf berarah dan tidak berbobot 4. Graf tidak berarah dan tidak berbobot Graf tidak berarah dan tidak berbobot adalah graf yang pada setiap busurnya tidak mempunyai arah dan tidak mempunyai bobot.
Gambar 2.6 Graf tidak berarah dan tidak berbobot Di dalam situasi yang dinamis, seperti pada komputer digital ataupun pada sistem aliran (flow system), konsep graf berarah lebih sering digunakan dibandingkan dengan konsep graf tak berarah. Suatu graf berarah (Directed Graph, yang dikenal sebagai Digraf) D terdiri dari 2 himpunan : (1). Himp. V, yang elemennya disebut simpul → Vertex / point / titik / node (2). Himp. A, yang merupakan pasangan terurut dari simpul-simpul, disebut ruas berarah → Arc / arkus Sehingga sebuah digraf dinotasikan sebagai D ( V, A )
Contoh : Sebuah graf berarah D(V,A), dengan : 1. V = { 1, 2, 3, 4 }
1
4
2 3
2. A = { (1,4), (2,1), (2,1), (4,2), (4,3), (2,3), (2,2) }
Arc (2,2) disebut gelung (self-loop), sedangkan arc (2,2) muncul 2 kali, disebut arc sejajar atau arc berganda. Apabila arc suatu graf berarah mempunyai suatu bobot, graf berarah tersebut dinamakan suatu jaringan atau network. Beberapa Pengertian dalam graf berarah : •
Derajat ke luar (out degree) suatu simpul adalah banyaknya arc yang mulai / keluar dari simpul tersebut.
•
Derajat ke dalam (in degree) suatu simpul adalah banyaknya arc yang berakhir / masuk ke simpul tersebut.
•
Simpul berderajat ke dalam = 0 disebut sumber (source), sedangkan simpul berderajat ke luar = 0 disebut muara (sink).
•
Pengertian Walk, Trail, Path (Jalur) dan Sirkuit (Cycle) berlaku pula pada graf berarah, dimana harus sesuai dengan arah arc. Kalau tidak sesuai dengan arah arc-nya, maka disebut sebagai semi walk, semi path atau semi trail.
Pada graf berarah terdapat 3 pengertian keterhubungan, yakni : •
Terhubung lemah, jika terdapat suatu semi path antara setiap 2 simpul dari D.
•
Terhubung unilateral, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v atau dari v ke u.
•
Terhubung kuat, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v dan dari v ke u.
A
B
C (a)
A
B
C (b)
A
B
C (c)
Gambar 2.7 (a)Terhubung lemah,(b)terhubung unilateral (c) Terhubung kuat.
2.2.1 lintasan dan sirkuit
Definisi 1 Suatu lintasan dari simpul i ke j adalah sebarisan busur-busur dan simpul-simpul yang dinyatakan dengan {I,(i,p), p, (p,q), q, (q,)…..(z,j),j} atau dengan i
p – q – r - …. – z – j.
Contoh :
Gambar 2.8. Contoh Lintasan
Lintasan pada gambar 2.8. dari simpul 1 ke simpul 8 adalah : 1, (1,3), 3 (3,6), 6, (6,8), 8 atau 1 – 3 – 6 – 8 1, (1,5), 5, (5,4), 4, (4,8), 8 atau 1 – 5 – 4 – 8
Definisi 2 Suatu putaran adalah sebarisan busur-busur dan simpul-simpul dimana simpul awal dan simpul akhir setiap busur berimpit, dinyatakan dengan i, (i,p), p, (p,q), q, (q,r)..,(z,i),i atau dengan I – p – q – r - ….- z- I Jadi, putaran adalah suatu lintasan tertutup.
Contoh : Dari gambar 2.6. yang merupakan putaran dari simpul 4 adalah : 4, (4,5), 5, (5,6), 6, (6,4), 4 atau 4 – 5 – 6 – 4 4, (4,5), 5, (5,3), 3, (3,6), 6, (6,4) atau 4 – 5 – 3 – 6 – 4
Defenisi 3 Suatu sirkuit merupakan sebarisan simpul dari i ke j yang simpul dan busurnya berhubungan tanpa memperhatikan arahnya tetapi simpul i dan j berimpit (simpul kembali ke i). Contoh :
Gambar 2.9. contoh sirkuit
Pada gambar 2.9. merupakan sirkuit dari simpul 3 adalah : 3, (3,5), 5, (5,6), 6 (3,6), 3 atau 3 – 5 – 6 – 3 3, (3,6), 6, (6,8), 8 (3,8), 3 atau 3 – 6 – 8 – 3
2.2.2 Jaringan Terhubung dan Jaringan Tak terhubung
Definisi 1 Definisi Drs.
Suatu jaringan disebut terhubung jika untuk sembarang simpul i dan simpul j yang
berbeda terdapat paling sedikit satu lintasan tertutup yang menghubungkan kedua simpul
tersebut, sedangkan jika tidak terdapat lintasan tertutup yang menghubungkan kedua simpul maka jaringan itu disebut jaringan tak terhubung.
2 5
1
4 6 3
8
7
Gambar 2.10 jaringan tak terhubung
Jaringan pada gambar 2.10 merupakan jaringan tak terhubung. Jaringan tersebut mempunyai 2 buah komponen (2 buah jaringan) yang masing-masing merupakan jaringan terhubung.
2.2.3
Lintasan dan Sirkuit Hamilton
Suatu alur Hamilton adalah suatu alur yang mengunjungi simpul masing masing persisnya sekali, oleh karena itu sirkuit Hamilton merupakan suatu siklus graph yang mengunjungi simpul masing masing tepat sekali (kecuali simpul yang merupakan tujuan awal dan akhir dikunjungi dua kali).
Dalam suatu graph G = (V,E) terdapat suatu pengertian yang oleh Sir William Hamilton yang berkaitan dengan sirkuit. Apabila G suatu graph berarah dan merupakan suatu sirkuit yang melewati setiap simpul-simpul yang ada dan hanya tepat satu kali, maka sirkuit tersebut
dinamakan sirkuit Hamilton. Jadi berdasarkan hal di atas maka Travelling salesman problem hampir bersamaan dengan sirkuit Hamilton.
Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.
1
2
1
2
1
2
4
3
4
3
4
3
A
B
C
Gambar 2.11 (a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4) (b) graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1) (c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton
TEOREMA 1. Syarat cukup (jadi bukan syarat perlu) supaya graf sederhana G dengan n (≥ 3) buah simpul adalah graf Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) ≥ n/2 untuk setiap simpul v di G).
TEOREMA 2. Setiap graf lengkap adalah graf Hamilton.
TEOREMA 3. Di dalam graf lengkap G dengan n buah simpul (n ≥ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.
TEOREMA 4. Di dalam graf 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.
2.3 Representasi matriks dari suatu jaringan
Ada 3 buah representasi matriks dari suatu jaringan, yaitu : a. Matriks Adjasensi b. Matriks insidensi c. Matriks biaya
2.3.1 Matriks Adjasensi (Adjacency matriks)
Defenisi 1: Matriks adjasensi X dari suatu jaringan G = {S,B} merupakan matriks {aij,] dimana : 1 X = [aij] =
jika busur (i,j) mempunyai arah dari
0
S ke simpul
S
dalam hal lain
Bila G merupakan jaringan tak berarah, maka setiap busur (i,j) B dapat dinyatkan sebagai suatu busur dengan dua arah. Dalam hal ini matriks adjasensi X merupakan matriks yang simetris.
Contoh :
Gambar 2.12. Jaringan berarah
Matriks adjasensi dari jaringan berarah dari gambar 2.12. adalah :
1 2 3 4 5 1 0 1 0 1 0 2 0 1 0 1 0 X=
3 0 0 1 0 0 4 0 1 1 0 1 5 0 0 0 0 0
Matriks adjasensi X tidak simetris.
2.3.2. Matriks Insidensi Definisi 2 : Matriks insidensi Z dari suatu jaringan G merupakan matriks (Zi, Zj), dimana :
jika simpul I ε S merupakan
+1
Simpul awal busur Bj ε B Z = [Zij] =
jika simpul I ε S merupakan
-1
Simpul akhir busur Bj ε B 0
dalam hal lain
Contoh :
Matriks insidensi Z dari gambar 2.5. adalah :
b1 b2 b3 b4 b5 b6 b7 Z = [Zij]
1
+1 +1 0
2
-1
3
0
0
0
0
0
-1 +1 0
0
0
0
0
0
0
+1
4
0
-1
+1 0
+1
+1 0
5
0
0
0
0
-1 -1
-1 -1
0
2.3.3. Matriks Biaya (cost)
Defenisi 3 : Suatu jaringan G =(S,B) adalah suatu bobot yang merupakan pemetaan W:
B
R
Atau (i,j)
W (i,j)
Untuk setiap busur (i,j) €R yang selanjutnya sebagai bobot dari busur (I,j) dimana: B adalah himpunan busur R adalah himpunan bilangan real
Dalam masalah sebenarnya bobot dari suatu busur dapat berupa biaya (cost), waktu ataupun jarak. Bila bobot yang diberikan merupakan pernyataan biaya dari setiap busur (i,j) yang berupa biaya pengangkutan barang atau panjang waktu, maka biaya atau panjang waktu minimum dapat dihitung dengan penentuan matriksnya.
Defenisi 4 : Suatu jaringan G = (S,B), [S] = n, matriks biaya C dari suatu jaringan G ersebut merupakan matriks (Cij) dimana Cij merupakan biaya (pengangkutan satu satuan barang) pada busur (i,j) atau waktu yang diperlukan dalam menempuh busur (i,j) i,j € S i = 1,2,3…,n j = 1,2,3,..,n
Pada representasi di atas Cij merupakan bobot W (I,j) matriks biaya C merupakan matriks busursangkar n x n.
Contoh : Jaringan berarah pada gambar berikut, angka disamping busur (I,j) merupakan biaya (bobot busur) pada Cij.
Gambar 2.13. Jaringan G (4,6)
Maka matriks biayanya adalah :
C = [Cij]
1
2
3
4
1
-
8
10
-
2
-
-
4
5
3
-
7
-
2
4
-
-
-
-
Pada jaringan berarah matriks biayanya tidak simetris
2.4 Model Jaringan dari Permasalahan
Travelling salesman problem dapat dinyatakan dengan model jaringan (graph dalam arti khusus). Tempat-tempat yang akan dikunjungi merupakan simpul-simpul, sedangkan jalan-jalan yang dilalui merupakan busur-busur dari jaringan tersebut yang mempunyai bobot dengan satuan panjang (jarak yang ditempuh oleh salesman). Jadi masalah utama terletak pada jalan-jalan yang dilaluinya, yaitu bagaimana agar jarak yang ditempuh oleh wiraniaga tersebut seminimal mungkin. Dari permasalahan di atas dapat disimpulkan bahwa perjalanan itu adalah suatu graph yang berarah dan mempunyai bobot.
