teori graph

14
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 e 1, e 2 ,e 3 , … 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

Upload: murdi-cayank-bibi-lung

Post on 04-Jul-2015

317 views

Category:

Documents


4 download

TRANSCRIPT

Page 1: Teori Graph

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

Page 2: Teori Graph

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

Page 3: Teori Graph

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

Page 4: Teori Graph

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

Page 5: Teori Graph

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

Page 6: Teori Graph

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

Page 7: Teori Graph

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

Page 8: Teori Graph

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

Page 9: Teori Graph

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

Page 10: Teori Graph

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

Page 11: Teori Graph

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

Page 12: Teori Graph

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

Page 13: Teori Graph

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

Page 14: Teori Graph

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