Page 101 - Trends in Science and Technology fo Sustainable Living

62 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)

Penghapusan lemah sisi e adalah menghapus suatu sisi
e dari himpunan sisi E(G). Penghapusan lemah sisi e dari graf G
dinotasikan dengan G = G-e lemah. Sebagai contoh, jika dilakukan
1
penghapusan lemah sisi e dari graf G pada Gambar 7, maka
2
diperoleh graf G berikut ini.
1

Gambar 10. Graf G = G-e Lemah
1 2
Misalkan graf G = (V,E). Suatu graf G' = (V',E') dikatakan
subgraf dari graf G, dinotasikan dengan G′ ⊆ G , jika V′ ⊆ V dan
E′ ⊆ E . Graf G' dikatakan subgraf merentang dari G jika G′ ⊆ G
dan V′ = V (Diestel, 2017). Dengan kata lain, subgraf merentang
diperoleh dari penghapusan lemah suatu sisi di graf G. Sebagai
contoh, graf G pada Gambar 9 dan pada Gambar 10 masing-
1
masing berturut-turut adalah subgraf dan subgraf merentang dari
graf pada Gambar 7.
Misalkan G = (V,E) dan G' = (V',E') adalah dua graf. Gabungan
(union) graf G dan G', yang dinotasikan dengan G ∪ G′ , adalah graf
yang mempunyai himpunan titik V ∪ V′ dan himpunan sisi E ∪ E′ .
Graf roda merupakan kelas graf yang dikonstruksi dari lingkaran.
Untuk n ≥ 3 , graf roda W didefinisikan sebagai C ∪ K , yaitu graf
n n 1
yang dikonstruksi dari satu titik yang dihubungkan ke setiap titik
lingkaran C . Jadi W = K . Adapun graf kipas adalah kelas graf yang
n 3 4
dikonstruksi dari lintasan. Untuk n ≥ 3 , graf kipas F didefinisikan
n
sebagai P ∪ K , yaitu graf yang dikonstruksi dari satu titik yang
n 1
dihubungkan ke setiap titik lintasan P . Gambar 11 berikut merupakan
n
contoh graf roda dan kipas.