Page 100 - Trends in Science and Technology fo Sustainable Living

Trends in Science and Technology 61
for Sustainable Living

Suatu graf non-trivial disebut graf bipartit G jika himpunan
titik graf G dapat dipartisi menjadi dua subhimpunan U dan W
sehingga setiap sisi di G menghubungkan suatu titik di U dan suatu
titik di W. Apabila setiap titik di U bertetangga dengan setiap titik di
W maka disebut graf bipartit lengkap. Secara umum, untuk k ≥ 2,
+
k ∈  , dan nn , ,n bilangan asli, graf multipartit lengkap (atau
,
1 2 k
graf partit-k lengkap), yang dinotasikan dengan K n 1 ,n 2 , ,n k ),
(
adalah graf yang himpunan titiknya dapat dipartisi menjadi k
i
,
subhimpunan yaitu VV , ,V dengan V = n untuk 1 ≤≤ k
1 2 k i i
sedemikian hingga uv ∈ E K ) jika uV∈ dan v ∈ V ,
( n
1 ,n 2 , ,n k i j
, ij ∈   1,k   dan i ≠ j.

K K K = K K
2,3 1,5 1,1,1,1 4 2,2,2
Sumber: Chartrand & Zhang, 2020
Gambar 8. Graf Multipartit Lengkap G
Penghapusan kuat titik v adalah menghapus suatu titik v
dari himpunan titik V(G) dan menghapus semua sisi di E(G) yang
terkait dengan titik v tersebut. Penghapusan kuat titik v dari graf
G dinotasikan dengan G = Gv− . Sebagai contoh, jika dilakukan
1
penghapusan kuat titik v dari graf G pada Gambar 7, maka
2
diperoleh graf G berikut ini.
1

Gambar 9. Graf G = G-v
1 2