Page 97 - Trends in Science and Technology fo Sustainable Living

58 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)

tersebut bukan graf sederhana karena memuat loop yaitu e atau
7
sisi ganda yaitu e dan e . Adapun graf berikut adalah contoh graf
3 6
sederhana.

Gambar 4. Graf Sederhana G

Misalkan titik u dan v di G. Suatu barisan titik di G, yang
berawal di u dan berakhir di v sehingga titik-titik yang berurutan
tersebut bertetangga di G disebut jalan u-v. Jalan W di G dinyatakan
dengan W = ( u = vv 2 , ,v k 1 + = v ) dengan vv 1 + ∈ E ()G untuk
,
1
ii
i ∈   1,k   . Titik tak berurutan di w tidak harus berbeda. Suatu jalan di G
yang sisinya tidak berulang disebut jejak di G. Suatu jalan di G yang
titiknya tak berulang disebut lintasan. Sebagai contoh, perhatikan
graf G di Gambar 4. Jalan v -v adalah W = v ,v ,v ,v ,v ) ,
1 2 1 ( 1 4 5 4 2
jejak v -v adalah W = vv ,v ,v ,v ) , dan lintasan v -v adalah
,
1 2 2 ( 1 2 4 3 2 1 2
W = vv ,v ,v
,
3 ( 1 4 3 2 ) .
Graf lintasan berorde n, yang dinotasikan dengan P , adalah
n
graf yang titik-titiknya dapat diberi label vv 2 , ,v sehingga
,
1
n
( E P ) = v v ,v v , ,v v ) . Dalam hal ini, v dan v disebut titik
n ( 1 2 23 n− 1 n 1 n
ujung lintasan P maka lintasan tersebut dinamakan lintasan
n
v -v . Adapun panjang lintasan P didefinisikan sebagai banyaknya
1 n n
sisi dalam lintasan tersebut. Karena itu, untuk setiap P , banyaknya
n
sisi adalah ( ) = n − 1. Gambar 5 berikut ini adalah ilustrasi
mP
n
lintasan P .
n