GRAPH THEORY

Graph theory

Setiap node bisa berhubungan dengan satu atau lebih node sebelumnya dan juga dengan satu atau lebih node sesudahnya

Contoh graph angkutan darat

Jakarta

Bandung

Semarang

Yogya

Surabaya

Multigraph

D

AC

B

e2

e1e3

e4

e5

e6

e7

e8

Contoh Multigraph

Sebuah multigraph hampir menyerupai graf, tetapi tidak dikatakan sebuah graf karena didalamnya mengandung lebih dari satu garis yang menghubungkan dua buah titik atau mengandung garis yang menhubungkan titik yang sama

Banyaknya edges yang melewati sebuah Vertex adalah besarnya derajat vertex didalam graf.Derajat dari vertex Badalah 4, biasa ditulis deg(B)=4.Untuk titik yang memiliki loop, maka ruas loop tersebut dihitung dua kali, jadi titik C memiliki derajat = 5.

Derajat (Degree) Vertex dan Derajat Graf

Derajat suatu Graf adalah jumlah dari seluruh derajat simpul (node/vertex)nya.Bila dihitung maka derajat suatu graf adalah dua kali banyak ruas.Pada gambar derajat graf tersebut = 16 (dua kali banyak ruas/garisnya)

e5

D

AC

B

e2

e1e3

e4

e6

e7

e8

Graf dengan titik terpencil atau terisolasi

BA

C

E

D

Contoh graf dengan titik E yang terisolasi

Graf Reguler

Graf yang pada setiap vertexnya memiliki derajat yang sama

Contoh graph reguler yang masing-masing vertexnya berderajat 4

Jakarta

Bandung

Semarang

Yogya

Surabaya

Ukuran (size) dari Graf

Banyaknya garis yang terdapat dalam graf merupakan ukuran dari sebuah graf.Pada gambar ukuran graf = 10, yaitu : [Jkt, Bdg], [Jkt, Smr], [Jkt, Ygy], [Jkt, Sby], [Bdg, Ygy], [Bdg, Sby], [Bdg, Smr], [Smr, Sby], Smr, Ygy], [Ygy, Sby]

Jakarta

Bandung

Semarang

Yogya

Surabaya

Graf Pohon

BA C

ED

Contoh graf Pohon

F

Sebuah graf terhubung (connected graph) tanpa adanya cycle

Graf Berbobot (Berlabel)

BA

4

ED

F

6

74

5

5 3

Graf yang diberikan bobot disetiap garisnya

Graf Planar

Graf yang bila digambarkan bisa dengan tidak adanya garis yang berpotongan

Graf Nonplanar

Graf kebalikan dari graf planar

Graf Berarah (Digraph)

Contoh graf Berarah

BA

CD

e1 e2

e3

e4 e5

e6

e7

Terminologi pada graf berarah :1. Garis e bermula dari titik U

dan berakhir dititik V2. Titik U disebuit dengan titik

sumber (source point), titik asal (origin point) atau titik inisial (initial point) dari garis e, dan titik V adalah titik tujuan (destination point), atau titik akhir (terminal point) dari garis e

3. Titik U adalah pendahulu (predecessor) dari titik V, dan titik V adalah penerus (successor) atau tetangga (neighbor) dari titik U

4. Titik U berdekatan atau berdampingan (adjacent) dengan titik V atau sebaliknya.

BA

C D

e1 e2

e3

e4 e5

e6

e7

Derajat keluar dari sebuah titik (outdegree) dilambangkan outdeg(U) adalah banyaknya garis yang berasal dari titik U.Derajat masuk dari sebuah titik (indegree) dilambangkan indeg(U) adalah banyaknya garis yang menuju ke titik U.Pada gambar titik B memiliki outdeg(B) = 2 dan indeg (B) = 2.

Contoh graf Berarah

Titik C disebut dengan titik sumber.Titik D disebut dengan titik benam.

1. adjacency matrix

Representasi Graf

Misalkan G = (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan G adalah matriks yang berukuran n x n . Bila matriks tersebut dinamakan A = [aij] ,maka aij=1 jika simpul i dan j bertetangga atau terhubung, sebaliknya aij= 0 jika simpul i dan j tidak bertetangga atau tidak terhubung.

1. adjacency matrix

Matriks Tetanggaan Graf ABCDEF

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 n xm . Baris menunjukkan label simpul, sedangkan kolommenunjukkan label sisi. Bila matriks tersebut dinamakan A = [aij], maka aij= 1 jika simpul i bersisian dengan j, sebaliknya aij= 0 jika simpul i tidak bersisian dengan simpul j.

2. Matriks Bersisian (incidency matrix)

Graf berarah ABCDEF

Matriks bersisian graf ABCDEF

Skema representasi linked mengandung dua buah daftar yaitu daftar titik (node list) dan daftar garis (egde list)

Representasi Linked

Graf Berarah

Titik Titik Tujuan

ABCDE

DA, DB, D, E

D

Tabel pemetaan

A

B C

D E

Skema representasi linked

A X

B

C

D X

E X X

X

X

Node List Egde List

Start

Representasi graf di memori

NODE

NEXT ADJ

1 8

2 D 7 0

3 1

4 B 9 6

5 A 4 3

6 3

7 E 0 12

8 10

9 C 2 8

10 0

DEST

LINK

1 7(E) 0

2 11

3 2(D) 0

4 2(D) 1

5 9

6 5(A) 10

7 0

8 4(B) 4

9 7

10 2(D) 0

11 5

12 2(D) 0

5

6

START

AVAIL

2

Soal : Pemetaan graf di memori sebagai berikut :

NODE

A B E D C

NEXT 7 4 0 6 8 0 2 3

ADJ 1 2 5 7 9

1 2 3 4 5 6 7 8

START = 1 , AVAILN = 5

DESK

2 6 4 6 7 4 4 6

LINK 10 3 6 0 0 0 0 4 0 0

1 2 3 4 5 6 7 8 9 10

AVAILE = 8

a. Gambarkanlah graf berarah tersebutb. Tulis jalur-jalur sederhana yang dimulai

dari A dan berakhir di Ec. Tentukan matrik adjency-nya