Page 98 - Trends in Science and Technology fo Sustainable Living

Trends in Science and Technology 59
for Sustainable Living

Gambar 5. Graf Lintasan P
n
Graf lingkaran berorde n, yang dinotasikan dengan C ,
n
adalah graf yang diperoleh dari lintasan P dengan menambahkan
n
satu sisi pada titik-titik ujung lintasan P yang menjadikan kedua titik
n
tersebut bertetangga. Panjang lingkaran C didefinisikan sebagai
n
banyaknya sisi dalam lingkaran tersebut. Karena itu, untuk setiap
C , banyaknya sisi adalah m(C ) = n. Misalkan G graf yang memuat
n n
lingkaran. Girth graf G adalah panjang lingkaran terkecil di G, yang
dinotasikan dengan g(G). Graf pohon berorde n, yang dinotasikan
dengan T , adalah graf yang tidak memuat lingkaran. Gambar 6
n
berikut ini merupakan ilustrasi lingkaran C .
n

Gambar 6. Graf Lingkaran C
n
Suatu graf G dinyatakan terhubung jika untuk setiap pasang
titik terdapat lintasan yang menghubungkannya. Jika graf G
tak-terhubung, maka G memuat dua atau lebih komponen yang
masing-masing merupakan graf terhubung. Sebagai contoh,
gambar berikut ini adalah graf terhubung, sedangkan graf
tak-terhubung ditunjukkan pada Gambar 4.