ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo
Pert 14
Setiap node bisa berhubungan dengan satu atau lebih
node sebelumnya dan juga dengan satu atau lebih
node sesudahnya
Surabaya

Semarang
Jakarta

Yogya
Bandung

Contoh graph angkutan darat
D
e8

e6
C

e7

A
e2

e4
e3

e1

B
Contoh Multigraph

e5

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.
D
e8

e6
C

e7

A
e2

e4
e3

e1
B

e5

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)
A

B

E

D

C
Contoh graf dengan titik E yang terisolasi
Graf Reguler
Graf yang pada setiap vertexnya memiliki derajat yang
sama
Surabaya

Semarang
Jakarta

Yogya
Bandung

Contoh graph reguler yang masing-masing vertexnya
berderajat 4
Surabaya

Semarang
Jakarta

Yogya
Bandung
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]
Graf Pohon
Sebuah graf terhubung (connected graph) tanpa
adanya cycle
A

B

E

D
Contoh graf Pohon

C

F
Graf Berbobot (Berlabel)
F

5
A

4

D

Graf yang diberikan
bobot disetiap garisnya

3
5

7

6

B

4

E
Graf Planar
Graf yang bila digambarkan bisa dengan tidak adanya garis yang
berpotongan
Graf Nonplanar
Graf kebalikan dari graf planar
e7

e3

B

A

e1

D

e2

e4

e6
Contoh graf Berarah

e5

C

Terminologi pada graf berarah :
1. Garis e bermula dari titik U
dan berakhir dititik V
2. 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.
e7

e3

B

A
e1

e2

C

e4
e6

e5

D

Contoh graf Berarah

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

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.
1. adjacency matrix
Misalkan G = (V,E) adalah graf dengan n simpul, n ≥ 1.
Matriks ketetanggaan G adalah matriks yang berukuran
nxn.
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.
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 kolom
menunjukkan 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.
Matriks bersisian graf ABCDEF
Skema representasi linked mengandung dua
buah daftar yaitu daftar titik (node list) dan
daftar garis (egde list)
B

C

A

D

Graf Berarah

E

Titik

Titik Tujuan

A
B
C
D
E

D
A, D
B, D, E
D

Tabel pemetaan
Node List

Egde List
X

A
Start

B

X

C

X

D
E

X
X

X
NODE
START

1
2

5

NEXT

ADJ

8
D

3

7

DEST
1

0

1

0
11

3

2(D)

0

2(D)

1

B

9

6

4

5

A

4

3

5

6

6

7(E)

2

4

AVAIL

LINK

7

3
E

8

9
10

0

6
12

10

C

2
0

5(A)

7
8

8

9
0
4(B)

9
10

4
7

2(D)

11
12

10

0
5

2(D)

0

2
NODE

A

B

NEXT

7

4

ADJ

1

2

1

E

2

0

D
0

5
3

4

5

9

6

8

2

7

6

C

7

3
8

START = 1 , AVAILN = 5

DESK

2

6

4

LINK

10 3

6

1

3

2

AVAILE = 8

6

7

4

0

0

0

0

4

5

6

7

4

6

4

0

0

8

9

10
a.
b.
c.

Gambarkanlah graf berarah tersebut
Tulis jalur-jalur sederhana yang dimulai dari
A dan berakhir di E
Tentukan matrik adjency-nya

More Related Content

Pert 14