11
sebuah rusuk dari v ke w. Pada gambar 2.4 dapat dilihat graf terarah atau directed graph
di mana V = {A,B,C,D,E} dan e = {e1, e2, e3, e
4
,
e
5
}.
B
e3
E
e1
A
e2
e
4
e
6
e
5
D
C
e
7
Gambar 2.4 Graf terarah
Pada
gambar 2.4
diatas rusuk
terarah ditunjukkan dengan anak panah. Rusuk
e1
menghubungkan
pasangan
verteks-verteks
terurut
(A,B)
dan
rusuk
e3
menghubungkan
verteks-verteks terurut (E,B).
Rusuk
e1
dinyatakan dalam (A,B)
dan
rusuk
e3
dinyatakan
dalam (E,B).
Pada
suatu
graf
jika
setiap
rusuknya
memiliki
suatu
bobot
atau
nilai
di
mana
bobot
itu
merupakan
suatu
nilai
yang
bisa
berupa
biaya
atau
jarak
atau
lainnya,
graf
semacam itu dikatakan graf berbobot (weighted graph).
2.2.2
Teori Lintasan dan Siklus
Misalkan
v
0
dan
v
n
adalah
verteks-verteks
dalam
sebuah
graf.
Sebuah
lintasan
dari
v
0
ke v
n
dengan
panjang
n
adalah
sebuah
barisan
berselang-seling dari
n+1
verteks
dan n rusuk yang berawal dengan verteks v
0
dan berakhir dengan verteks v
n
,
(v
0
,e1 ,v1 ,e2 ,v2, ... ,v
n-1
,e
n
,v
n
),
dengan rusuk ei insiden pada verteks v
i-1
dan vi untuk i = 1,2,...,n.
 |