teori graph
TRANSCRIPT
BAB II
LANDASAN TEORI
2.1 Teori Graf
2.1.1 Defenisi Graf
Graf G didefenisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G =
(V,E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul
(vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang
menghubungkan sepasang simpul (Munir, 2009).
Simpul pada graf dapat dinomori dengan huruf, seperti a,b,c,d, ..., atau dengan
bilangan asli 1,2,3, … atau juga gabungan dengan keduanya. Sedangkan untuk sisi
yang menghubungkan antara simpul u dan v dinyatakan dengan (u,v) atau dapat
dinyatakan dengan lambang e1,e2,e3, … dengan 1,2,3 adalah indeks. Dapat dikatakan
bahwa jika e merupakan sisi yang menghubungkan simpul u dengan v, maka e dapat
ditulis sebagai e = (u,v).
Dalam aplikasinya, setiap simpul pada graf dapat dijadikan sebagai objek kehidupan,
yaitu sebagai objek titik jaringan pesan atau komunikasi, lokasi penempatan kerja,
titik kota, jalur transportasi dan lain sebagainya. Sedangkan untuk sisi graf dijadikan
sebagai bobot jarak, waktu, biaya dan kendala lainnya. Dan juga busur (arcs) adalah
yang menunjukan hubungan atau relasi dari sepasang simpul.
Universitas Sumatera Utara
9
2.1.2 Jenis Graf
Berdasarkan orientasi arah pada sisi dan bobotnya, maka secara umum graf dibedakan
atas empat jenis :
1. Graf tidak berarah dan berbobot (undirected graph)
Graf yang setiap sisinya tidak mempunyai arah anak panah tetapi memiliki bobot pada
setiap sisinya. Urutan pasangan simpul yang terhubung oleh sisi tidak diperhatikan.
Sehingga (u,v) = (v,u) adalah sisi yang sama.
Sehingga graf tak berarah sering dipakai pada jaringan saluran telepon karena
sisi pada graf tak berarah menyatakan bahwa saluran telepon dapat beroperasi pada
dua arah. Perhatikan contoh graf tak berarah pada Gambar 2.1 dengan enam buah
simpul dan sebelas buah sisi.
2. Graf berarah dan berbobot (directed graph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Secara
umum sisi berarah disebut dengan busur (arc). Pada graf berarah (u,v) dan (v,u)
menyatakan dua buah busur yang berbeda, dalam arti kata bahwa (u,v) (v,u). Jadi
Gambar 2.1 Graf tak berarah dan berbobot
5
3
3
6
2
6
10
1
8
C
E
A
F
B
D
7
4
Universitas Sumatera Utara
10
untuk busur (u,v) simpul u dinamakan simpul asal dan simpul v dinamakan simpul
terminal atau simpul tujuan.
Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lintas
kota dan lain sebagainya. Sehingga pada graf berarah gelang atau looping
diperbolehkan tetapi sisi ganda tidak diperbolehkan. Perhatikan contoh graf berarah
pada Gambar 2.2 dengan enam buah simpul dan sebelas buah sisi.
3. Graf tidak berarah dan tidak berbobot
Graf yang setiap sisinya tidak mempunyai arah dan tidak mempunyai bobot apapun.
Perhatikan contoh graf tidak berarah dan tidak berbobot pada Gambar 2.3
Gambar 2.2 Graf berarah dan berbobot
3
53
6
2
6
10
1
8
C
E
A
F
B
D
7
4
Gambar 2.3 Graf tidak berarah dan tidak berbobot
C
E
A
F
B
D
Universitas Sumatera Utara
11
4. Graf berarah dan tidak berbobot
Graf yang setiap sisinya mempunyai arah tetapi tidak mempunyai bobot apapun.
Perhatikan contoh graf berarah dan tidak berbobot pada Gambar 2.4
2.1.3 Representasi Graf
Terdapat beberapa cara mempresentasikan graf, tiga diantaranya yang sering
digunakan adalah matriks ketetanggaan, matriks bersisian dan senarai ketetanggaan.
1. Matriks Ketetanggan (adjacency matrix)
Misalkan G = (V,E) adalah graf dengan n simpul, 1n . Matriks ketetanggaan G
adalah matriks yang berukuran nn . Bila matriks tersebut dinamakan ][ ijaA ,
maka 1ija jika simpul i dan j bertetangga atau terhubung, sebaliknya 0ija
jika simpul i dan j tidak bertetangga atau tidak terhubung. Matriks bertetanggaan
hanya berisi 0 dan 1, selain dengan angka 0 dan 1, elemen matriks dapat juga
dinyatakan dengan nilai false (menyatakan 0) dan true (menyatakan 1).
Gambar 2.4 Graf berarah dan tidak berbobot
C
E
A
F
B
D
Universitas Sumatera Utara
12
Matriks ketetanggaan nol-satu tidak dapat digunakan untuk mempresentasikan
graf yang mempunyai sisi ganda (graf ganda). Untuk graf semu, gelang pada
simpul dinyatakan dengan nilai 1 pada matriks tetanggaannya. Tabel matriks
ketetanggaan untuk graf ABCDEF dapat dilihat pada Tabel 2.1
A B C D E F
A 0 1 1 1 0 0
B 0 0 0 1 1 0
C 0 1 0 0 0 1
D 0 0 0 0 1 1
E 0 0 1 0 0 0
F 0 0 0 0 1 0
Jumlah elemen matriks ketetanggaan untuk graf dengan n simpul atau titik adalah
2n . Jika setiap elemen membutuhkan ruang memori sebesar N, maka ruang
memori yang diperlukan seluruhnya adalah 2nN .
Pada graf tidak berarah :
a. Ruang memori yang diperlukan adalah 2
2 nn
b. Derajat simpulnya adalah
n
jiji avd
1
)(
Pada graf berarah :
a. Jumlah nilai pada baris i
n
jijout ad
1
b. Jumlah nilai pada kolom j
n
iijin ad
1
2. Matriks Bersisian (incidency matrix)
Tabel 2.1 Matriks Tetanggaan Graf ABCDEF
Universitas Sumatera Utara
13
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
yang berukuran mn . Baris menunjukkan label simpul, sedangkan kolom
menunjukkan label sisi. Bila matriks tersebut dinamakan ][ ijaA , maka 1ija
jika simpul i bersisian dengan j, sebaliknya 0ija jika simpul i tidak bersisian
dengan simpul j.
Matriks bersisian dapat digunakan untuk mempresentasikan graf yang
mengandung sisi ganda atau sisi gelang. Derajat setiap simpul i dapat dihitung
dengan menghitung jumlah seluruh elemen pada baris i (kecuali pada graf yang
mengandung gelang atau looping). Jumlah elemen matriks bersisian adalah mn .
Jika setiap elemen membutuhkan ruang memori sebesar N, maka ruang memori
yang diperlukan seluruhnya adalah mnN . Perhatikan Gambar 2.5
menunjukkan graf berarah yang terdiri dari 6 simpul dan 10 sisi serta Tabel 2.2
yang menunjukkan matriks bersisian untuk graf ABCDEF.
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10
A 1 0 0 1 0 0 0 0 0 0
B 0 0 1 0 0 0 0 0 0 0
C 0 1 0 0 1 0 0 0 0 0
Gambar 2.5 Graf berarah ABCDEF
e9
e8
e7
e10
e6
e5
e4e3
e2
e1
0
C
B
F
DE
A
Universitas Sumatera Utara
14
D 0 0 0 0 0 0 0 1 0 0
E 0 0 0 0 0 0 0 0 1 1
F 0 0 0 0 0 1 1 0 0 0
3. Senarai Ketetanggaan (adjacency list)
Jika dilihat dari segi implementasinya terhadap komputer matriks tetanggaan
memiliki kebutuhan ruang memori yang boros. Hal ini dikarenakan matriksnya
memiliki banyak elemen nol sedangkan didalam komputer elemen nol tidak perlu
disimpan. Untuk mengatasi hal tersebut maka senarai ketetanggaan yang lebih
baik. Senarai ketetanggaan mengurutkan simpul-simpul yang bertetangga dengan
setiap simpul di dalam graf. Sebagai contoh perhatikan senarai ketetanggaan
gambar 1.1 pada bab 1.
2.2 Permasalahan Optimasi
Secara umum pencarian jalur terpendek dapat dibagi menjadi dua metode, yaitu
metode konvensional dan metode heuristik. Metode konvensional diterapkan dengan
menggunakan perhitungan matematika murni, sedangkan metode heuristik diterapkan
dengan menggunakan perhitungan kecerdasan buatan.
1. Metode Konvensional
Metode konvensional adalah metode yang diterapkan menggunakan
perhitungan matematika murni. Ada beberapa metode konvensional yang
sering digunakan untuk menyelesaikan masalah optimasi, diantaranya:
algoritma Djikstra, algoritma Floyd-Warshall, dan algoritma Bellman-Ford.
2. Metode Heuristik
Metode heuristik adalah salah satu dari bidang kecerdasan buatan yang
digunakan untuk menyelesaikan masalah optimasi. Terdapat beberapa
algoritma dari metode heuristik yang sering digunakan dalam permasalahan
Tabel 2.2 Matriks bersisian graf ABCDEF
Universitas Sumatera Utara
15
optimasi, diantaranya adalah algoritma genetika, algoritma pencarian tabu,
jaringan saraf tiruan, algoritma semut dan lain-lain.
2.2.1 Permasalahan Lintasan Terpendek (Shortest Path Problem)
Menurut Munir, 2009 persoalan lintasan terpendek di dalam graf merupakan salah
satu persoalan optimasi. Graf yang digunakan dalam pencarian lintasan terpendek
adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu
nilai atau bobot. Bobot pada sisi graf dapat dinyatakan sebagai jarak antar kota, waktu
pengiriman pesan dan lain-lain.
Dengan kata lain lintasan terpendek merupakan suatu jaringan atau kerangka jalur
petunjuk perjalanan dari suatu simpul atau titik ke simpul lainnya atau yang menjadi
tujuan perjalanan dengan beberapa pilihan jalur yang mungkin untuk di jalani.
Gambar 2.6 menunjukkan graf berarah ABCDEF dan tidak berberbobot.
Dapat dilihat pada Gambar 2.6 untuk malakukan suatu perjalanan dari simpul awal A
ke simpul tujuan F, maka terdapat beberapa pilihan jalur yang mungkin untuk di
tempuh, yaitu :
Jalur ke-1 : A B C F
Jalur ke-2 : A B E F
Jalur ke-3 : A C F
Jalur ke-4 : A D E F
E
DA
FC
B
Gambar 2.6 graf berarah ABCDEF
Universitas Sumatera Utara
16
Jalur ke-5 : A D E F
Dari uraian jalur diatas dapat ditentukan jalur atau lintasan terpendek dengan mencari
jarak suatu jalur antara simpul-simpulnya kemudian membandingkan dengan jarak
pada jalur yang lain dan menentukan total jarak yang terpendek atau yang paling kecil.
2.3 Algoritma Tabu Search (TS)
Tabu Search merupakan salah satu algoritma yang berada dalam ruang lingkup
metode heuristik. Algoritma ini menggunakan short-term memory untuk menjaga agar
proses pencarian tidak terjebak pada nilai optimum lokal. Algoritma ini menggunakan
tabu list untuk menyimpan sekumpulan solusi yang baru saja dievaluasi. Selama
proses optimasi, pada setiap iterasi, solusi yang akan dievaluasi akan dicocokkan
terlebih dahulu dengan isi tabu list untuk melihat apakah solusi tersebut sudah ada
pada tabu list.
Apabila solusi tersebut sudah ada pada tabu list, maka solusi tersebut tidak
akan dievaluasi lagi pada iterasi berikutnya. Dan jika sudah tidak ada lagi solusi yang
tidak akan menjadi anggota tabu list, maka nilai terbaik yang baru saja diperoleh
merupakan solusi yang sebenarnya.
Beberapa elemen utama pada Tabu Search adalah sebagai berikut :
1. Representasi solusi : setiap solusi yang mungkin pada suatu permasalahan
optimasi harus direpresentasikan.
2. Fungsi cost : setiap fungsi cost akan memetakan setiap solusi yang mungkin ke
nilai cost-nya
3. Neightbourhood (tetangga) : suatu fungsi yang memetakan setiap solusi yang
mungkin ke solusi-solusi yang lainnnya.
4. Tabu list : suatu list atau daftar yang berisi solusi gerakan terakhir.
5. Jumlah elemen yang harus ada pada suatu solusi.
Algoritma Tabu Search secara garis besar dapat ditulis sebagai berikut :
Universitas Sumatera Utara
17
Langkah 0 : Tetapkan :X = Matriks input berukuran (n x m).MaxItr = Maksimum Iterasi.
Langkah 1 : S = bangkitkan solusi secara random.Langkah 2 : GlobalMin = FCost(S).Langkah 3 : Best = S.Langkah 4 : TabuList = [ ].Langkah 5 : Kerjakan dari k = 1 sampai MaxItr:Langkah 6 : BestSoFar = Cost.Langkah 7 : BestMove = S.Langkah 8 : Kerjakan dari i = 1 sampai MaxItr:Langkah 9 : Kerjakan dari j = i sampai n:Langkah 10: L = Tukar(S[i],S[j]).Langkah 11: Cost = FCost(L).Langkah 12: Jika(L TabuList)atau(Cos<GlobalMin),kerjakan :Langkah 13: Jika (Cost < BestSoFar), kerjakan :Langkah 14: BestSoFar = Cost.Langkah 15: BestMove = L.Langkah 16: S = BestMove.Langkah 17: Tambahkan S ke Tabu List.Langkah 18: Jika BestSoFar < GlobalMin, kerjakan :Langkah 19: GlobalMin = BestSoFar.Langkah 20: Best = BestMove.
Solusi Akhir adalah Best, dengan cost sebesar GlobalMin.
Contoh penyelesaian kasus Travelling Sales Problem menggunakan algoritma TS :
Misalkan pada kasus ini jalur yang ditetapkan dimulai dari kota ke-5 dan berakhir di
kota ke-2. Menggunakan TS dengan maksimum 6 iterasi. Perhatikan Gambar 2.7 graf
tidak berarah dan tidak berbobot 123456 dan Tabel 2.3 Matriks jarak antar titik.
6
5
2
4
3
1
Gambar 2.7 graf tidak berarah 123456
Universitas Sumatera Utara
18
1 2 3 4 5 6
1 0 20 21 25 30 36
2 20 0 25 21 36 30
3 21 25 0 10 11 18
4 25 21 10 0 18 11
5 30 36 11 18 0 20
6 36 30 18 11 20 0
Jalur awal :
5 1 3 4 6 2 Panjang jalur = 102
Iterasi ke-1 :
Tabu List :
5 1 3 4 6 2 Panjang jalur = 102
Tetangga (Jalur alternatif berikutnya) :
Jalur ke-1 : 5 3 1 4 6 2 Panjang jalur = 98
BestSoFar = 98
Jalur ke-2 : 5 4 3 1 6 2 Panjang jalur = 115
Jalur ke-3 : 5 6 3 4 1 2 Panjang jalur = 93
BestSoFar = 93
Jalur ke-4 : 5 1 4 3 6 2 Panjang jalur = 113
Jalur ke-5 : 5 1 6 4 3 2 Panjang jalur = 112
Jalur ke-6 : 5 1 3 6 4 2 Panjang jalur = 101
BestSoFar = 93, yaitu pada jalur ke-3 diterima sebagai GlobalMin
GlobalMin = 93
Iterasi ke-2 :
Tabu List :
5 1 3 4 6 2 Panjang jalur = 102
5 6 3 4 1 2 Panjang jalur = 93
Tabel 2.3 Matriks jarak pada graf tidak berarah 123456
Universitas Sumatera Utara
19
Tetangga (Jalur alternatif berikutnya) :
Jalur ke-1 : 5 3 6 4 1 2 Panjang jalur = 85
BestSoFar = 85
Jalur ke-2 : 5 4 3 6 1 2 Panjang jalur = 102
Jalur ke-3 : 5 1 3 4 6 2 Panjang jalur = 102
Jalur ke-4 : 5 6 4 3 1 2 Panjang jalur = 82
BestSoFar = 82
Jalur ke-5 : 5 6 1 4 3 2 Panjang jalur = 116
Jalur ke-6 : 5 6 3 1 4 2 Panjang jalur = 105
BestSoFar = 82, yaitu pada jalur ke-4 diterima sebagai GlobalMin
GlobalMin = 82
Iterasi ke-3 :
Tabu List :
5 1 3 4 6 2 Panjang jalur = 108
5 6 3 4 1 2 Panjang jalur = 93
5 6 4 3 1 2 Panjang jalur = 82
Tetangga (Jalur alternatif berikutnya) :
Jalur ke-1 : 5 4 6 3 1 2 Panjang jalur = 88
Jalur ke-2 : 5 3 4 6 1 2 Panjang jalur = 88
Jalur ke-3 : 5 1 4 3 6 2 Panjang jalur = 113
Jalur ke-4 : 5 6 3 4 1 2 Panjang jalur = 93
Jalur ke-5 : 5 6 1 3 4 2 Panjang jalur = 108
Jalur ke-6 : 5 6 4 1 3 2 Panjang jalur = 101
GlobalMin = 82
Seterusnya hingga 6 iterasi, dan pada iterasi ke-2 akan diperoleh suatu jalur
terpendek, yaitu :
Jalur ke-4 : 5 6 4 3 1 2 Panjang jalur = 82
Universitas Sumatera Utara
20
2.4 Kompleksitas Algoritma
Algoritma adalah urutan logis langkah-langkah penyelesaian masalah secara
sistematis. Sebuah algoritma tidak saja harus benar tetapi juga harus efisien (Munir,
2009). Efisiensi algoritma dinilai berdasarkan kecepatan waktu eksekusi dan
penggunaan struktur data yang menyebabkan banyaknya ruang memori komputer
yang terpakai.
2.4.1 Efficiency Algoritma
Algorima yang terbaik adalah bukan karena algoritma itu harus benar, akan tetapi juga
harus di pandang dari efisiensinya. Jadi algoritma yang terbaik adalah algoritma yang
efisien dalam penggunaan waktu eksekusi dan ruang memori komputer. Efisiensi
algoritma juga berguna dalam membandingkan algoritma. sebuah masalah dapat
mempunyai lebih dari satu jenis algoritma. Misalkan untuk masalah pengurutan data
dalam array, dapat digunakan berbagai macam algoritma seperti: bubble sort,
selection sort, merge sort dan lain-lain.
2.4.2 Kebutuhan Waktu dan Ruang
Kebutuhan waktu suatu algoritma biasanya dihitung dalam satuan detik, milidetik dan
lain sebagainya. Sedangkan untuk ruang memori yang digunakan dapat dihitung
dalam satuan byte atau kilobyte. Biasanya seorang pengguna algoritma mengukur
kebutuhan waktu sebuah algoritma dengan mengeksekusi langsung algoritma tersebut
pada sebuah komputer, lalu dihitung berapa lama durasi waktu yang dibutuhkan untuk
menyelesaikan sebuah persoalan yang berbeda-beda.
Keakuratan waktu eksekusi algoritma dapat diperoleh dengan tidak
menghitung kebutuhan waktu untuk menampilkan antarmuka program, operasi
input/output dan sebagainya. Sehingga akan dihitung bagian inti dari programnya saja.
Universitas Sumatera Utara
21
2.4.3 Kompleksitas Waktu
Setelah siap untuk menjalankan suatu program maka untuk mengukur kompleksitas
waktunya adalah dengan menghitung banyaknya operasi yang dilakukan oleh
algoritma, seperti: operasi penjumlahan, pengurangan, perkalian, pembagian dan lain
sebagainya. Namun yang paling idealnya adalah cukup menghitung berapa kali
operasi yang sama terjadi secara berulang dan mencatat waktu yang terjadi selama
eksekusi.
Universitas Sumatera Utara