2. 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
4. 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)
6. 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
7. 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]
8. Graf Pohon
Sebuah graf terhubung (connected graph) tanpa
adanya cycle
A
B
E
D
Contoh graf Pohon
C
F
12. 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.
13. 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.
14. 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.
16. 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.
18. 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