bab 2 teori dasar - digilib.itb.ac.id er yang berisi komponen-komponen entity set dan relationship...

22
6 BAB 2 TEORI DASAR Bab ini akan membahas mengenai Pemodelan basis data (dibahas pada subbab 2.1), pengenalan peta dijital beserta model data (dibahas pada subbab 2.2), teori dasar mengenai graf serta representasi graf (dibahas pada subbab 2.3), dan berbagai macam algoritma pencarian jalur jalan seperti algoritma Djikstra, A-star (A*), dan Shooting-star (shooting*) (dibahas pada subbab 2.4). 2.1 Pemodelan Basis Data Dalam SIG, dunia nyata harus disederhanakan karena pada dasarnya dunia nyata sendiri bersifat tidak teratur (irregular), kompleks, dan secara tetap mengalami perubahan yang tidak bisa diprediksi dengan mudah. Persepsi dunia nyata dalam SIG sangat bergantung pada pengamat (subjektif). Proses-proses yang terlibat dalam mentranslasikan hasil pengamatan dari dunia nyata ke dalam data yang dimengerti dan dibutuhkan oleh SIG dengan menggunakan model dunia nyata dan model data disebut dengan pemodelan data (data modelling) [Prahasta, 2001]. 2.1.1 Model Entity-Relationship (ER) Model Entity-Relationship merupakan model yang dipakai untuk mentransformasikan keadaan dunia nyata dengan menggunakan seperangkat konseptual sehingga menjadi sebuah diagram relasi antar entitas. Komponen utama pembentuk model ER adalah relasi dan entitas. Kedua komponen ini dideskripsikan dengan menggunakan atribut-atribut (properties). Model ER ini menggambarkan relasi atau hubungan antar entitas, dimana terdapat 2 jenis hubungan, yaitu : a. Obligatory : bila semua anggota dari suatu entitas harus berpartisipasi atau memiliki hubungan dengan entitas yang lain. b. Non-obligatory : bila tidak semua anggota dari suatu entitas harus berpartisipasi atau memiliki hubungan dengan entitas lain. Dalam menggambarkan model ER, terdapat beberapa komponen yang harus diperhatikan, yaitu :

Upload: nguyenxuyen

Post on 11-Jul-2018

217 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

6

BAB 2

TEORI DASAR

Bab ini akan membahas mengenai Pemodelan basis data (dibahas pada subbab

2.1), pengenalan peta dijital beserta model data (dibahas pada subbab 2.2), teori

dasar mengenai graf serta representasi graf (dibahas pada subbab 2.3), dan

berbagai macam algoritma pencarian jalur jalan seperti algoritma Djikstra, A-star

(A*), dan Shooting-star (shooting*) (dibahas pada subbab 2.4).

2.1 Pemodelan Basis Data

Dalam SIG, dunia nyata harus disederhanakan karena pada dasarnya dunia nyata

sendiri bersifat tidak teratur (irregular), kompleks, dan secara tetap mengalami

perubahan yang tidak bisa diprediksi dengan mudah. Persepsi dunia nyata dalam

SIG sangat bergantung pada pengamat (subjektif). Proses-proses yang terlibat

dalam mentranslasikan hasil pengamatan dari dunia nyata ke dalam data yang

dimengerti dan dibutuhkan oleh SIG dengan menggunakan model dunia nyata dan

model data disebut dengan pemodelan data (data modelling) [Prahasta, 2001].

2.1.1 Model Entity-Relationship (ER)

Model Entity-Relationship merupakan model yang dipakai untuk

mentransformasikan keadaan dunia nyata dengan menggunakan seperangkat

konseptual sehingga menjadi sebuah diagram relasi antar entitas. Komponen

utama pembentuk model ER adalah relasi dan entitas. Kedua komponen ini

dideskripsikan dengan menggunakan atribut-atribut (properties). Model ER ini

menggambarkan relasi atau hubungan antar entitas, dimana terdapat 2 jenis

hubungan, yaitu :

a. Obligatory : bila semua anggota dari suatu entitas harus berpartisipasi atau

memiliki hubungan dengan entitas yang lain.

b. Non-obligatory : bila tidak semua anggota dari suatu entitas harus

berpartisipasi atau memiliki hubungan dengan entitas lain.

Dalam menggambarkan model ER, terdapat beberapa komponen yang harus

diperhatikan, yaitu :

Page 2: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

7

1. Entitas

Entitas merupakan individu yang mewakili sesuatu yang nyata eksistensinya

dan dapat dibedakan dengan yang lainnya. Sekumpulan entitas yang sama atau

sejenis yang terdapat dalam lingkup yang sama akan membentuk entity set

(sekumpulan entitas) [Prahasta, 2001].

2. Atribut

Setiap entitas pasti memiliki atribut-atribut yang akan mendeskripsikan

karakteristik-karakteristik dari entitas yang bersangkutan. Penentuan atau

pemilihan atribut-atribut yang relevan bagi suatu entitas merupakan hal

penting di dalam pembentukan model data. Penentuan atribut-atribut bagi

suatu entitas pada umumnya didasarkan pada fakta-fakta yang ada.

3. Relasi

Relasi menunjukkan adanya hubungan atau keterkaitan antara suatu entitas

dengan entitas lain yang berbeda. Jika relasinya banyak, maka kumpulan suatu

relasi yang ada diantara entitas yang terdapat pada entity set - entity set yang

berbeda akan membentuk relationship set (sekumpulan atau himpunan relasi).

4. Tingkat Relasi

Tingkat relasi menunjukkan adanya batas jumlah maksimum entitas dapat

berelasi dengan entitas yang terdapat pada entity set yang lain. Dari sejumlah

kemungkinan relasi antar entitas, tingkat relasi merujuk pada jumlah

maksimum relasi yang mungkin terjadi di antara entity set - entity set yang

bersangkutan. Berikut ini adalah kemungkinan-kemungkinan tingkat relasi

yang terdapat pada entity set, untuk setiap tingkat relasi akan dijelaskan oleh

diagram ER-nya masing-masing :

i. Tingkat relasi satu ke satu (one to one). Yaitu satu entitas dalam A

dihubungkan dengan maksimum satu entitas dalam sejumlah entitas

dalam B (gambar 2.1). Relasi satu ke satu dibedakan menjadi dua

macam yaitu obligatory (gambar 2.1 a ) dan non-obligatory (gambar

2.1 b).

Page 3: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

8

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entity set A Entity set B

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entity set A Entity set B

Entity set A Entity set B Entity set BEntity set B1 1 1 1

(a) (b)Obligatory Non-Obligatory

Gambar 2.1 Tingkat relasi satu ke satu

ii. Tingkat relasi satu ke banyak (one to many). Yaitu satu entitas dalam

A dihubungkan dengan sejumlah entitas dalam B. Satu entitas dalam B

dihubungkan dengan maksimum satu entitas dalam A (gambar 2.2).

Relasi satu ke banyak dibedakan menjadi dua macam yaitu obligatory

(gambar 2.2 a) dan non-obligatory (gambar 2.2 b).

Entitas 1

Entitas 2

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entity set A Entity set B

Entitas 1

Entitas 2

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entity set A Entity set B

Entity set A Entity set B Entity set BEntity set Bm 1 m 1

(a) (b)Obligatory Non-Obligatory

Gambar 2.2 Tingkat relasi satu ke banyak

iii. Tingkat relasi banyak ke satu (many to one). Yaitu satu entitas dalam

A dihubungkan dengan maksimum satu entitas dalam B. Satu entitas

dalam B dapat dihubungkan dengan sejumlah entitas dalam A (gambar

Page 4: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

9

2.3). Relasi banyak ke satu dibedakan menjadi dua macam yaitu

obligatory (gambar 2.3 a) dan non-obligatory (gambar 2.3 b).

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entitas 1

Entitas 2

Entity set A Entity set B

Entity set A Entity set B Entity set BEntity set B1 m 1 m

(a) (b)Obligatory Non-Obligatory

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entitas 1

Entitas 2

Entity set A Entity set B

Gambar 2.3 Tingkat relasi banyak ke satu

iv. Tingkat relasi banyak ke banyak (many to many). Satu entitas dalam A

dihubungkan dengan sejumlah entitas dalam B, dan satu entitas dalam

B dihubungkan dengan sejumlah entitas dalam A (Gambar 2.4). Relasi

banyak ke banyak dibedakan menjadi dua macam yaitu obligatory

(gambar 2.4 a) dan non-obligatory (gambar 2.4 b).

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entity set A Entity set B

Entity set A Entity set B Entity set BEntity set B1 m 1 m

(a) (b)Obligatory Non-Obligatory

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entitas 1

Entitas 2

Entitas 3

Entitas 4

Entity set A Entity set B

Gambar 2.4 Tingkat relasi banyak ke banyak

Page 5: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

10

2.1.2 Diagram Entity Relationship (ER)

Model ER yang berisi komponen-komponen entity set dan relationship set yang

masing-masing dilengkapi dengan atribut-atribut yang merepresentasikan seluruh

fakta dari sebagian dunia nyata dapat digambarkan secara sitematis dengan

menggunakan diagram ER. Simbol-simbol dan notasi yang digunakan dalam

penulisan diagram ER dapat dilihat pada tabel 2.1 berikut ini.

Tabel 2.1 Notasi atau simbol yang digunakan dalam diagram ER

Notasi / Simbol Keterangan

Merepresentasikan entity set.

Menggambarkan relationship set.

Menghubungkan antara entity set dengan relationship

set-nya.

2.2 Pengenalan Peta Dijital

Peta dijital adalah representasi fenomena geografik yang disimpan untuk

ditampilkan dan dianalisis oleh komputer dijital. Setiap objek pada peta dijital

disimpan sebagai sebuah atau sekumpulan koordinat. Sebagai contoh, objek

berupa lokasi sebuah titik akan disimpan sebagai sebuah koordinat, sedangkan

objek berupa wilayah akan disimpan sebagai sekumpulan koordinat. Peta dijital

dapat direpresentasikan dalam dua model: model raster dan model vektor. Pada

tugas akhir ini, akan dibahas mengenai model vektor.

Persegi panjang

(Obligatoy)

Belah

Ketupat

Persegi panjang

(Non-Obligatoy)

Page 6: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

11

2.2.1 Model Data Vektor

Model data vektor menampilkan, menempatkan, dan menyimpan data spasial

dengan menggunakan titik-titik, garis-garis atau kurva, poligon beserta atribut-

atributnya. Pada model data ini, poligon, garis atau kurva merupakan kumpulan

titik-titik terurut yang dihubungkan. Pada poligon, titik awal dan titik akhir

memiliki nilai koordinat yang sama, sehingga bentuknya menjadi tertutup

sempurna [Prahasta, 2001].

1. Entity titik

Titik adalah representasi grafis yang paling sederhana untuk suatu objek.

Representasi ini tidak memiliki dimensi tetapi dapat diidentifikasi di atas peta

dan dapat ditampilkan pada layar monitor dengan menggunakan simbol-

simbol. Sudut property suatu batas (poligon) juga merupakan titik.

2. Entity garis

Garis adalah bentuk linier yang akan menghubungkan paling sedikit dua titik

dan digunakan untuk merepresentasikan objek-objek satu dimensi. Batas-batas

poligon merupakan garis-garis, demikian pula dengan jaringan jalan, listrik,

pipa dan utilitas lain-lain.

3. Entity poligon

Poligon digunakan untuk merepresentasikan objek-objek dua dimensi. Suatu

danau, batas propinsi, batas kota adalah tipe entitas yang pada umumnya

direpresentasikan sebagai poligon. Suatu poligon paling sedikit dibatasi oleh

tiga garis yang saling terhung diantara ketiga titik tersebut. Di dalam basis

data, semua bentuk area (luasan) dua dimensi akan direpresentasiakn oleh

bentuk poligon.

2.2.1.1 Model Data Spaghetti

Pada model ini, lembar peta kertas ditranslasikan garis demi garis ke dalam list

koordinat (x,y) dalam format dijital. Sebuah titik dikodekan sebagai pasangan

koordinat (x,y) tunggal, sebuah garis dikodekan sebagai list atau string pasangan-

pasangan koordinat (x,y), sementara area atau luasan dikodekan sebagai poligon

dan direkam sebagai pasangan-pasangan koordinat tertutup yang mendefinisikan

Page 7: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

12

batas-batasnya. Garis-garis yang menjadi batas-batas bersama di antara poligon-

poligon yang bersebelahan di-trace dan direkam dua kali (sekali untuk poligon

pertama, dan sekali lagi untuk poligon yang terletak di sebelahnya).

Struktur model data ini sangat sederhana dan sangat mudah dimengerti. Model

data ini benar-benar merupakan ekspresi peta di dalam sistem koordinat kartesian.

File data koordinat-koordinat (x,y) merupakan struktur data yang sebenarnya

dalam sistem komputer. Dalam struktur model data ini, semua unsur-unsur

spasialnya (spatial features) tersimpan/terekam, namun hubungan spasial yang

ada diantara unsur-unsur tersebut tidak tersimpan. Sebagai contoh, informasi

mengenai unsur-unsur yang berada tepat di sebelah suatu poligon tidak disimpan.

Informasi ini dapat dibuat dengan cara melakukan proses pencarian ke semua

unsur-unsur spasial yang terdapat di dalam file data, dan kemudian melakukan

analisis atau hitungan untuk memutuskan apakah poligon yang bersangkutan

memiliki tetangga atau tidak.

Model vektor spaghetti ini sangat tidak efisien untuk kebanyakan tipe-tipe analisis

spasial yang diperlukan dalam SIG. hal ini disebabkan karena hampir semua tipe

analisis spasial di dalam SIG berikut hubungan spasialnya harus diturunkan

dengan menggunakan proses komputasi. Model spaghetti ini sangat efisien untuk

reproduksi peta-peta secara dijital karena informasi-informasi yang tidak

berhubungan dengan masalah proses plotting dan reproduksi, misalkan hubungan

spasial dan topologi, tidak ikut tersimpan.

2.2.1.2 Model Data Vektor Dengan Topologi

Topologi adalah konsep atau metode matematis yang digunakan didalam

mendefinisikan hubungan spasial di antara unsur-unsurnya. Hubungan topologi

merupakan properties inherent yang dimiliki oleh setiap objek atau entitas

geometri, atau spasial.

Page 8: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

13

Topologi merupakan salah satu dari sejumlah hubungan terpenting didalam basis

data spasial. Struktur datanya menentukan bagaimana dan dimana titik-titik dan

garis-garis berhubungan satu dengan yang lainnya pada suatu node. Selain itu,

urutan koneksi atau keterhubungan juga menentukan bentuk dari suatu arc

(merupakan sekumpulan titik / pasangan koordinat yang dimalai dari suatu titik

yang didefinisikan sebagai node awal dan diakhiri pada suatu titik yang

didefinisikan sebagai node akhir). Informasi mengenai hubungan topologi ini

biasanya disimpan dalam beberapa tabel pada struktur basis data spasial.

Berikut ini adalah contoh hubungan unsur-unsur spasial di dalam basis data

[Prahasta, 2001] :

1. Menyimpan semua node yang merupakan titik-titik (endpoints) dan

perpotongan-perpotongan garis-garis (arcs) dan batas-batas (boundaries atau

polygons) terlihat pada gambar 2.5.

Gambar 2.5 Koordinat dan Posisi-posisi Nodes

2. Berdasarkan node tersebut, kemudian didefinisikan arcs dengan menggunakan

informasi-informasi : endpoints (node), direction (arah yang dimuali dari from

node ke dengan tujuan to node), orientasi vektor yang direpresentasikan oleh

direction-nya terlihat pada gambar 2.6.

Node X Y

1. 25 82

2. 30 78

3. 21 76

4. 26 79

5. 27 75

Node 2

Node 5

Node 4

Node 1Node 3

Page 9: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

14

Gambar 2.6 Arcs dan nodes

Arcs ini tersusun dari garis-garis lurus yang dibentuk oleh vertex yang

memungkinkan untuk melakukan perubahan-perubahan arah (derection)

sehingga bentuk arcs menyerupai kurva yang halus (smooth). Selain itu,

dengan orientasi arcs, pembuatan rute-rute dari suatu node ke node yang

ditentukan atau dari suatu tempat ke tempat lain yang ditentukan menjadi

memungkinkan.

3. Poligon-poligon didefinisikan dengan menggunakan arcs: sebuah poligon

didefinisikan dengan melakukan tracing batas-batasnya seara h dengan

perputaran jarum jam (clockwise), komponen-komponen arcs beserta

orientasinya direkam, tanda negatif diberikan kepada arcs yang

mendefinisikan batas-batas internal, dan untuk setiap arc, poligon-poligon

yang terletak di sebelah kiri dan kanan arah orientasinya, juga direkam.

Terlihat pada gambar 2.7

Gambar 2.7 Topologi poligon

Arc From Node To Node

A. 1 2

B. 3 2

C. 3 1

D. 1 4

E. 3 4

F. 5 5

G. 4 2

Poly Jumlah arc Arc list

A. 3 A,D,G

B. 3 C,D,E

C. 1 F

D. 4 B,E,G,F

Arc A

Arc DArc

G

Arc F

Arc

E

Arc C

Arc

B

1

3

4

2

5

Arc A

Arc DArc

G

Arc F

Arc

E

Arc C

Arc

B

A

BD

C1

3

4

2

5

Page 10: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

15

4. jika sebuah arc merupakan salah satu sisi (pinggiran) study area, arc tersebut

dibatasi oleh universe atau outer world (dunia luar). Dengan contiguity

(keterhubungan dengan unsur-unsur geometri yang bersebelahan) ini, SIG dapat

menjawab pertanyaan-pertanyaan mengenai konektivitas dan lokasi seperti:

poligon-poligon mana yang berdampingan atau bersebelahan (adjoin) dengan

poligon A, rute terpendek mana yang menghubungkan dari node 3 ke node 2,

poligon mana yang dilalui secara langsung dari poligon B di sepanjang arc D.

Terlihat pada gambar 2.8

Gambar 2.8 Contiguity

2.3 Teori Graf

Graf adalah struktur diskrit yang terdiri dari simpul (vertex) dan sisi (edge), atau

dengan kata lain, graf adalah pasangan himpunan (V,E) di mana V adalah

himpunan tidak kosong dari vertex dan E adalah himpunan sisi yang

menghubungkan sepasang simpul dalam graf tersebut. Graf dapat ditulis dengan

notasi G=(V,E). Pada gambar 2.9 menggambarkan suatu graf dengan 6 node dan 7

edge [Rinaldi Munir 2003].

Arc Left Poly Right Poly

A. Universe A

B. D Universe

C. Universe B

D. A B

E. B D

F. D C

G. A D

Arc A

Arc DArc

G

Arc F

Arc

E

Arc C

Arc

B

A

BD

C1

3

4

2

5

Page 11: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

16

Gambar 2.9 Graf dengan 6 node dan 7 edge

2.3.1 Jenis Graf

Graf digunakan untuk merepresentasikan objek diskrit dan hubungan antara objek.

Representasi visual graf adalah dengan menyatakan objek sebagai noktah, bulatan,

atau titik. Sedangkan hubungan antara objek dinyatakan dengan garis.Berdasarkan

vertex (simpul) dan edge (sisi), graf terbagi menjadi tiga bagian antara lain

[Rinaldi Munir 2003]:

1. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf

digolongkan menjadi dua jenis:

a. Graf sederhana (simple graph)

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan

graf sederhana. G1 pada Gambar 2.2 adalah contoh graf sederhana.

b. Graf tak-sederhana (unsimple-graph)

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-

sederhana (unsimple graph). G2 dan G3 pada Gambar 2.2 adalah

contoh graf tak-sederhana.

2. Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat

digolongkan menjadi dua jenis:

a. Graf berhingga (limited graph)

Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

b. Graf tak-berhingga (unlimited graph)

Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut

graf tak-berhingga.

3. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas

dua jenis:

Page 12: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

17

a. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-

berarah. Tiga buah graf pada Gambar 2.10 adalah graf tak-berarah.

b. Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf

berarah. Dua buah graf pada Gambar 2.11 adalah graf berarah.

G1 G2 G3

Gambar 2.10 Graf berdasarkan ada tidaknya sisi gelang atau sisi ganda, (a). Graf

Sederhana, (b). Graf ganda, (c). Graf semu

(a) (b)

G4 G5

Gambar 2.11 (a) graf berarah, (b) graf-ganda berarah

Dalam penggambaran graf dalam bidang datar, graf dibagi menjadi dua yaitu:

1. Graf Planar (Planar Graph)

Yaitu graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang

tidak saling memotong (bersilangan). Tiga buah graf pada gambar 2.12

termasuk graf planar.

1 1

2 3

4

2 3

4

Page 13: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

18

2. Graf Bidang (Plane Graph)

Yaitu Graf planar yang digambarkan dengan sisi-sisi yang tidak saling

berpotongan. Graf (b) dan (c) pada gambar 2.12 termasuk graf bidang.

(a) (b) (c)

Gambar 2.12 Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang

2.3.2 Representasi Graf

Untuk pemrosesan graf dengan program komputer, graf harus direpresentasikan

ke dalam memori. Terdapat beberapa representasi untuk graf, antara lain matriks

ketetanggaan, matriks bersisian, dan senarai ketetanggaan [Rinaldi Munir 2003].

1. Matriks Ketetanggaan (adjacency matrix)

Untuk mempermudah perhitungan pada program komputer, graf dapat

direpresentasikan dengan menggunakan matriks. Salah satunya adalah

matriks ketetanggaan. Misalkan G = (V, E) adalah sebuah graf sederhana

dimana |V| = n, n > 1. Misalkan simpul dari G adalah v1, v2, … vn. Maka,

matriks ketetanggaan A dari G adalah n x n matriks dimana:

A = [aij],

1, jika simpul i dan j bertetangga

0, jika simpul i dan j tidak bertetangga

Matrks ketetanggaan nol-satu tidak dapat digunakan untuk merepresentasikan

graf yang mempunyai sisi ganda. Untuk mengatasinya, maka elemen a[ij]

pada matiks ketetanggaan sama dengan jumlah yang berasosiasi dengan

(vi,vj), matriks ketetanggaannya bukan lagi matriks nol-satu. Untuk graf semu,

gelang pada simpul vi dinyatakan dengan nilai satu pada posisi (i,j) di matriks

ketetanggaannya.

Page 14: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

19

Keuntungan representasi dengan matriks adalah elemen matriksnya dapat

diakses langsung melalui indeks. Selain itu, kita dapat mengetahui secara

langsung apakah simpul i dan simpul j bertetangga. Contoh matriks

ketetanggaan ada pada gambar 2.13

4321

4

3

2

1

0110

1011

1101

0110

Gambar 2.13 Contoh Matriks Ketetanggaan

2. Matriks Bersisian (incidency matrix)

A = [aij],

1, jika simpul i bersisian dengan sisi j

0, jika simpul i tidak bersisian dengan sisi j

Matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalkan G=(V,

E) adalah graf dengan n simpul dan m buah sisi, maka matriks kebersisian A

dari graf G adalah matriks yang berukuran m x n. Baris menunjukkan label

simpul, sementara kolom menunjukkan label sisinya. Gambar 2.14

menunjukkan representasi graf dalam bentuk matriks bersisian.

e1 e2 e3 e4 e5

4

3

2

1

10000

11100

00111

01011

Gambar 2.14

Contoh

Matriks

Besisian

1 2

3

4

e1

e2e3e4

e5

1

32

4

Page 15: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

20

3. Senarai Ketetanggaan (adjacency list)

Kelemahan matriks ketetanggaan adalah bila graf memiliki jumlah sisi relatif

sedikit, karena matriksnya bersifat jarang, yaitu banyak mengadung elemen

nol, sedangkan elemen yang bukan nol sedikit. Ditinjau dari segi

implementasi, kebutuhan ruang memory untuk matriks jarang, boros, karena

komputer menyimpan banyak elemen nol yang tidak perlu. Untuk mengatasi

masalah ini, senarai ketetanggaan digunakan. Senarai ketetanggaan

mengenumerasi simpul-simpul yang bertetangga dengan setiap simpul di

dalam graf. Contoh dari senarai ketetanggaan dapat dilihat dari Gambar 2.15.

Gambar 2.15 Contoh Senarai Ketetanggaan

2.4 Algoritma Pencarian Lintasan Terpendek

Penelusuran jalur pada SIG secara konseptual memiliki prinsip dasar yang sama,

yaitu menerapkan teori Graf kedalam jaringan jalan. Sebuah struktur graf dapat

dikembangkan dengan memberi bobot pada setiap edge. Graf berbobot dapat

digunakan untuk melambangkan banyak konsep berbeda. Jika suatu graf

melambangkan jaringan jalan, maka bobotnya dapat berarti panjang jalan maupun

batas kecepatan pada batas tertentu. Ekstensi lain pada graf adalah dengan

membuat edgenya bearah, atau secara teknis disebut graf berarah atau digraph

(directed graf). Graf berbobot inilah yang digunakan untuk mencari lintasan

terpendek. Terdapat dua metoda pencarian dalam graf yaitu :

Depth First Search (DFS): pada setiap pencabangan, penelusuran verteks-

verteks yang belum dikunjungi dilakukan selengkapnya pada pencabangan

pertama, kemudian selengkapnya pada pencabangan kedua, dan seterusnya

secara rekursif.

Simpul Simpul

Tetangga

1 2, 3

2 1, 3, 4

3 1, 2, 4

4 2, 3

1

32

4

Page 16: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

21

Breadth First Search (BFS): pada setiap pencabangan penelusuran verteks-

verteks yang belum dikunjungi dilakukan pada verteks-verteks adjacent,

kemudian berturut-turut selengkapnya pada masing-masing pencabangan dari

setiap verteks adjacent tersebut secara rekursif.

Pencarian lintasan terpendek (Shortest Path) yaitu pencarian lintasan yang

memiliki bobot minimum. Untuk memecahkan permasalahan lintasan terpendek,

ada beberapa algoritma yang sering digunakan antara lain :

2.4.1 Algoritma Dijkstra

Algoritma ini diberi nama sesuai nama penemunya, Edsger Wybe Dijkstra.

Algoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah.

Algoritma ini pada setiap langkah akan memilih sisi yang berbobot minimum dan

memasukkannya ke dalam himpunan solusi. Algoritma Djikstra menggunakan

strategi Greedy dalam mencari lintasan terpendek. Strategi Greedy adalah strategi

yang memecahkan masalah langkah demi langkah, pada setiap langkah

mengambil pilihan yang terbaik yang dapat diperoleh dengan berharap bahwa

pemilihan solusi optimum lokal pada setiap langkah akan mencapai solusi

optimum global. Dengan demikian algoritma Dijkstra adalah sebagai berikut :

“Pada setiap langkah, ambil sisi yang berbobot minimum yang menghubungkan

sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih.

Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan

terpendek diantara semua lintasannya ke simpul-simpul yang berlum terpilih”.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed

graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua

vertices dalam graph G. Algoritma Dijkstra dimulai dari sebuah simpul asal dan

dalam setiap iterasinya menambahkan sebuah verteks lain ke lintasan terpendek

pohon merentang. Verteks ini merupakan titik terdekat ke akar namun masih di

luar bagian pohon. Dalam algoritma Dijkstra, yang dicari adalah sisi yang

menghubungkan ke suatu verteks di (Vi-Vn) sehingga jarak dari verteks asal Vs

ke verteks tersebut adalah minimal.

Page 17: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

22

Algoritma Dijkstra akan membuat label untuk menunjukkan simpul-simpul.

Label-label ini melambangkan jarak dari simpul asal ke suatu simpul lain. Dalam

graf, terdapat dua macam label, sementara dan permanen. Label sementara

diberikan untuk simpul-simpul yang belum dicapai. Nilai yang diberikan untuk

label sementara ini dapat beragam. Label permanen diberikan untuk simpul-

simpul yang sudah dicapai dan jarak ke simpul asal diketahui. Nilai yang

diberikan untuk label ini ialah jarak dari suatu simpul ke simpul asal. Suatu

simpul pasti memiliki label permanen atau label sementara, tetapi tidak keduanya

terlihat pada gambar 2.16.

A

7

B

0

(a) (b)

Gambar 2.16 : (a). Simpul A berlabel sementara dengan jarak 0, (b). Simpul B

berlabel permanen dengan jarak 7

Algoritma dimulai dengan menginisialisasi simpul awal di dalam graf (misalkan

simpul A) dengan label permanen bernilai 0 dan simpul-simpul sisanya dengan

label sementara bernilai 0 terlihat pada gambar 2.17.

0

A

B C

D

5 7

86

0

0

0

Label permanen

dengan nilai 0

Label sementara

dengan nilai 0

Gambar 2.17 Inisialisasi awal

Page 18: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

23

Algoritma ini kemudian memilih nilai sisi yang menghubungkan simpul dengan

label permanen (dalam hal ini simpul A) ke sebuah simpul lain yang berlabel

sementara (misalkan simpul B). Kemudian label simpul B berubah dari label

sementara menjadi label permanen. Nilai simpul B merupakan penjumlahan nilai

sisi AB dan nilai simpul A terlihat pada gambar 2.18.

A

B C

D

5 7

86

0

0

0

Label berubah

menjadi permanen

dengan nilai 0+5 = 5

5

Gambar 2.18 Nilai simpul B menjadi permanen

Langkah selanjutnya ialah menemukan nilai sisi berikutnya yang menghubungkan

simpul awal (simpul A) ke simpul berikutnya (simpul C). Kemudian label simpul

C berubah menjadi label permanen, Nilai simpul C merupakan penjumlahan nilai

sisi AC dan nilai simpul A terlihat pada gambar 2.19.

A

B C

D

5 7

86

0

0

Label berubah

menjadi permanen

dengan nilai 0+7 = 7

5

7

Gambar 2.19 Nilai simpul C berubah

Page 19: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

24

Proses ini berulang hingga semua label simpul menjadi permanen kemudian

mencari nilai yang paling kecil. Proses ini menggunakan metode Depth First

Search (DFS), yang melakukan penelusuran simpul pada setiap pencabangan,

penelusuran simpul-simpul yang belum dikunjungi dilakukan selengkapnya pada

pencabangan pertama, kemudian selengkapnya pada pencabangan kedua, dan

seterusnya secara rekursif terlihat pada gambar 2.20.

A

B C

D

5 7

86

0

Label berubah

menjadi permanen

dengan nilai 5+6 = 11

5

7

11

Gambar 2.20 Semua Nilai Simpul Menjadi Permanen

2.4.2 Algoritma A*

Algoritma A* adalah suatu algoritma pencarian untuk graf. Ciri dari algoritma ini

adalah dengan adanya fungsi heuristik (h(x)) yang mempertimbangkan jarak

untuk menentukan urutan di mana pencarian mengunjungi simpul dalam graf.

Jalur x yang diberi notasi f(x) merupakan penjumlahan dari dua fungsi yaitu

fungsi penghitungan biaya suatu jalur (g(x)) dan fungsi perkiraan heuristik yang

memperkirakan jarak dari simpul saat ini ke simpul tujuan (h(x)). Pada algoritma

A* pencarian dilakukan secara inkremen pada semua rute yang mengarah ke

simpul mulai sampai berhasil ditemukan jalur tujuan yang terdekat. Untuk itu,

algoritma ini pertama memulai dengan memeriksa rute yang „keliatannya‟ paling

mungkin mengarah ke tujuan. Algoritma A* dimulai dengan menginisialisasi

simpul awal dalam graf (misalkan simpul A) terlihat pada gambar 2.21.

Page 20: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

25

A

B

1

C

2

D

3

1 2

Nilai sisi

E

4

F

5

G

6

H

7

6

1078 9

543

Nilai Heuristik

Gambar 2.21 Inisialisasi Awal

Algoritma ini kemudian akan memilih simpul yang kelihatannya yang paling

mungkin ke tujuan (dalam hal ini simpul H). Algoritma A* menggunakan Breadth

First Search (BFS) yang pada setiap pencabangan penelusuran simpul-simpul

yang belum dikunjungi dilakukan pada simpul-simpul adjacent, kemudian

berturut-turut selengkapnya pada masing-masing pencabangan dari setiap verteks

adjacent tersebut secara rekursif. Pemeriksaan nilai dilakukan dengan menghitung

nilain sisi (g(x)) dengan nilai heuristic (h(x)). Dari gambar didapat bahwa nilai

dari simpul A B adalah 2, dan simpul A C adalah 4. Terlihat pada gambar

2.22.

A

B

1

C

2

D

3

1 2

E

4

F

5

G

6

H

7

6

1078 9

543

Nilai sisi+nilai

Heuristik=1+1=2

Nilai sisi+nilai

Heuristik=2+2=4

2

0

4

Gambar 2.22 Pencarian Nilai dari Simpul A

Page 21: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

26

Proses selanjutnya adalah memilih nilai yang paling kecil (dalam hal ini adalah

dari A B). Proses ini dilakukan sampai menemukan simpul tujuan (dalam hal

ini simpul H) sehingga akan didapat nilai penelusuran yang terkecil. Terlihat pada

gambar 2.23.

A

B

1

C

2

D

3

1 2

E

4

F

5

G

6

H

7

6

1078 9

543

Nilai sisi+nilai

Heuristik=3+3=6

Nilai sisi+nilai

Heuristik=4+4=8

2

0

4

6 8

14

Nilai sisi+nilai

Heuristik=7+7=14

Gambar 2.23 Pencarian Nilai dari Simpul B

2.4.3 Algoritma Shooting*

Algoritma Shooting* adalah algoritma pencarian dalam graf. Algoritma ini

hampir sama dengan algoritma A*, yang membedakannya adalah dalam setiap

pencarian algoritma shooting* akan mencari sisi yang terdekat bukan simpul.

Algoritma Shooting * dimulai dengan menginisialisasi sisi awal dalam graf

(misalkan sisi A) terlihat pada gambar 2.24.

0

1 2

3

A

1B

2

Nilai sisi

4 5 6

7

F

6

J

10

G

7

H

8

I

9

E

5D

4

C

3

Nilai Heuristik

0

0

0

Gambar 2.24 Inisialisasi Awal

Page 22: BAB 2 TEORI DASAR - digilib.itb.ac.id ER yang berisi komponen-komponen entity set dan relationship set yang ... dapat direpresentasikan dalam dua model: ... Di dalam basis data, semua

27

Algoritma ini kemudian akan memilih sisi yang kelihatannya yang paling

mungkin ke tujuan (dalam hal ini sisi G). Algoritma Shooting* menggunakan

Breadth First Search (BFS. Pemeriksaan nilai dilakukan dengan menghitung nilai

sisi (g(x)) dengan nilai heuristic (h(x)). Dari gambar didapat bahwa nilai dari sisi

A C adalah 4, dan sisi A D adalah 5. Terlihat pada gambar 2.25.

0

1 2

3

A

1B

2

4 5 6

7

F

6

J

10

G

7

H

8

I

9

E

5D

4

C

3

0

Nilai sisi+nilai

Heuristik=1+3=6

0

4

5

Nilai sisi+nilai

Heuristik=1+4=5

Gambar 2.25 Pencarian Nilai dari Sisi A

Proses selanjutnya adalah memilih nilai yang paling kecil (dalam hal ini adalah

dari sisi A C). Proses ini dilakukan sampai menemukan sisi tujuan (dalam hal

ini sisi G) sehingga akan didapat nilai penelusuran yang terkecil. Terlihat pada

gambar 2.26.

0

1 2

3

A

1B

2

4 5 6

7

F

6

J

10

G

7

H

8

I

9

E

5D

4

C

3

0

Nilai sisi+nilai

Heuristik=4+8=12

0

10

12

Nilai sisi+nilai

Heuristik=3+7=10

Gambar 2.26 Pencarian Nilai dari Sisi C