Page 140 - Buku Teks Digital Mate KSSM T5

Bab 5 Rangkaian dalam Teori Graf

Bagaimanakah anda mengenal dan melukis subgraf dan pokok?

Apakah yang anda faham tentang subgraf? Standard
Pembelajaran
Subgraf merupakan sebahagian atau keseluruhan suatu graf yang Mengenal dan melukis
dilukis semula tanpa mengubah kedudukan asal bucu dan tepi. subgraf dan pokok.
Suatu graf H dikatakan subgraf kepada graf G jika,
(a) bucu-bucu graf H ialah subset kepada bucu-bucu graf G, iaitu V(H) ⊂ V(G).
(b) tepi-tepi graf H ialah subset kepada tepi-tepi graf G, iaitu E(H) ⊂ E(G).
(c) pasangan bucu setiap tepi graf H adalah sama dengan tepi graf G.
Secara ringkasnya,
• suatu bucu dalam graf G ialah subgraf bagi graf G. ZON INFORMASI
• suatu tepi dalam graf G bersama bucu-bucu yang dikaitkan ialah
subgraf bagi graf G. Simbol ⊆ juga boleh
• setiap graf ialah subgraf kepada dirinya. digunakan untuk subset.

Contoh 9

Tentukan sama ada Rajah 1, Rajah 2, Rajah 3 dan Rajah 4 ialah subgraf bagi graf G.
P e 1 Q e 2 P e 2 P e 1 Q P Q e 2 P e 1 Q e 3 5
BAB
e 5 e 3 e 5 e 5 e 3 e 5 e 2

S e 4 R S S S S e 4 R
Graf G Rajah 1 Rajah 2 Rajah 3 Rajah 4

Penyelesaian:
Rajah 1 – Ya kerana pasangan bucu untuk tepi e adalah sama.
5
{ e } ⊂ {e ,e ,e ,e ,e } dan {P, S} ⊂ {P,Q,R,S}
1 2 3 4 5
5

Rajah 2 – Tidak kerana kedudukan gelung e bukan pada bucu Q.
2
Rajah 3 – Tidak kerana tepi yang mengaitkan bucu P dan bucu S adalah bukan e .
3
Rajah 4 – Tidak kerana tepi gelung dan tepi yang mengaitkan bucu Q dan bucu R adalah salah.
Apakah yang anda faham tentang pokok? ZON INFORMASI
Pokok suatu graf ialah subgraf bagi graf tersebut dengan ciri-ciri Sebutan pokok
berikut: diperkenalkan oleh Arthur
(a) Graf mudah iaitu tanpa gelung atau berbilang tepi. Cayley, seorang ahli
Matematik Inggeris pada
(b) Semua bucu mesti berkait dan setiap pasangan bucu dikaitkan oleh tahun 1857.
satu tepi sahaja.
(c) Bilangan tepi = bilangan bucu – 1
Bilangan bucu = n ZON INFORMASI
Bilangan tepi = n – 1 Carta salasilah keluarga
Saiz sebenar
ialah contoh pokok.

139