Page 99 - Trends in Science and Technology fo Sustainable Living

60 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)

Gambar 7. Graf Terhubung G

Pandang lintasan u-v. Jarak titik u ke v di graf G,
dinotasikan dengan d(u,v), adalah panjang lintasan terpendek
yang menghubungkan kedua titik tersebut di G. Lintasan u-v
dengan panjang d(u,v) disebut geodesik u-v (Chartrand &
Zhang, 2020). Dalam Li dan Sun (2012), eccentricity titik v di graf
terhubung G adalah jarak antara titik v dan titik terjauh dari v di
G, yang dinotasikan dengan ecc( )v = max d ( , )v x . Diameter
x VG∈ ()
graf G adalah diam( )G = max ecc( )x . Radius graf G adalah
x VG∈ ()
rad( )G = min ecc( )x . Untuk setiap graf terhubung non-trivial,
x VG∈ ()
berlaku rad( )G ≤ diam( )G ≤ 2.rad( )G . Sebagai contoh, perhatikan
graf terhubung G pada Gambar 7. Jarak titik v ke v adalah
2 5
d (v ,v ) = 2 , sedangkan jarak titik v ke v adalah d (v ,v ) 1.=
2 5 2 4 2 4
Adapun lintasan P = ( 2 ,v 4 ,v 5 ) adalah geodesik v -v . Eccentricity
v
2
5
titik v adalah ecc(v 2 ) = 2 . Adapun diameter graf G adalah
2
diam( )G = 2 dan radius graf G adalah rad( ) 1G = .
Graf G disebut graf lengkap jika setiap dua titik berbeda
di graf tersebut bertetangga. Graf lengkap berorde n dinotasikan
dengan K . Karena itu, K merupakan graf berorde n dan berukuran
n n

n
 . Jika setiap titik pada graf G berderajat sama, maka G disebut

2

graf reguler. Jika setiap titik di G berderajat r, maka G disebut graf
reguler-r. Sebagai contoh, graf lingkaran C adalah graf reguler-2,
n
sedangkan graf lengkap K adalah graf reguler-(n-1). Graf reguler-3
n
disebut juga graf kubik, contohnya graf Petersen.