Page 138 - Buku Teks Digital Mate KSSM T5

Bab 5 Rangkaian dalam Teori Graf

Apakah beza antara graf berpemberat dengan graf tak berpemberat?

Graf berpemberat Graf tak berpemberat
Jenis
graf Graf terarah dan graf tak terarah. Graf terarah dan graf tak terarah.
Tepi Diberi nilai atau pemberat. Tiada nilai atau pemberat yang dinyatakan.

Tepi mewakili: Tepi mengaitkan maklumat:
• jarak di antara dua bandar. • hierarki jawatan dalam carta organisasi.
Contoh • masa yang diambil untuk suatu gerakan. • peta alir.
• nilai arus suatu litar elektrik. • peta pokok.
• kos dan sebagainya. • peta buih.

Contoh 7

Lukis graf terarah mengikut maklumat yang diberikan. ZON INFORMASI
(a) V = {P, Q, R, S, T, U} (b) Mempunyai satu gelung pada bucu Bagi contoh 7(a) bucu
E = {(P, Q), (P, R), Q dan RS ialah berbilang tepi dengan U wujud dalam set V
(R, Q), (S, R), keadaan tetapi tidak dalam set
E. Hal ini bermakna
(S, Q), (S, T)} d (P) = 1, d out (P) = 1 bucu U tidak berkaitan 5
in
d (Q) = 3, d out (Q) = 2 dengan bucu-bucu lain BAB
in
dan dikenali sebagai
d (R) = 0, d out (R) = 3 bucu terpencil.
in
d (S) = 3, d out (S) = 1
in
Penyelesaian:
(a) Pasangan bucu Arah
( P, Q) P ke Q } Dua tepi dari bucu P P R
( P, R) P ke R >
( R, Q) R ke Q Satu tepi dari bucu R > > >
( S, R) S ke R }
( S, Q) S ke Q Tiga tepi dari bucu S Q > S >
( S, T) S ke T U T
Bucu T hanya berkaitan dengan bucu S
(b) Jumlah bucu = 4 RS – berbilang tepi, Lengkapkan graf mengikut
Gelung pada bucu Q. bilangan tepi yang masuk
dan keluar pada setiap bucu.
P Q P Q P > Q

> > >

S R S R S > > R Saiz sebenar

137