Bab 5: Rangkaian dalam teori Graf

5.1

Rangkaian

Perkaitan antara rangkaian dengan graf

	Penjelasan

	Graf digunakan untuk mewakilkan data yang terdiri daripada objek diskret dan menggambarkan kaitan antara objek tersebut secara grafik

	Dalam teori graf, graf ditafsirkan sebagai suatu siri bintik sama ada berkait atau tidak berkait antara satu sama lain melalui garis

	Bintik dikenali sebagai bucu dan garis yang mengaitkan dua bucu ialah tepi

	Graf juga sering digunakan untuk mewakilkan suatu rangkaian

	Rangkaian merupakan sebahagian daripada graf dengan keadaan bucu dan tepi mempunyai sifat tersendiri dan struktur data rangkaian mempunyai hubungan banyak kepada banyak

	Tatanda graf merupakan set pasangan tertib iaitu \(G= (V,E)\) dengan keadaan \(V\) ialah set bintik atau bucu, \(V={ v_1, v_2, v_3, ....v_n }\) \(E\) ialah set tepi atau garis yang menghubungkan sepasang bucu

	Darjah, \(d\) ialah bilangan tepi yang menghubungkan sepasang bucu. Bilangan darjah suatu graf ialah dua kali bilangan tepi iaitu \(\sum d(v)= 2E\)

Graf mudah

Graf mudah ialah graf yang tidak mengandungi gelung atau berbilang tepi
Bilangan darjah suatu graf ialah dua kali bilangan tepi

Berbilang tepi dan gelung pada graf

Berbilang tepi

Melibatkan dua bucu

Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal

Bilangan darjah setiap gelung ialah dua

Gelung

Melibatkan dua bucu

Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal.

Bilangan darjah setiap gelung ialah \(2\).

	Contoh

Perbezaan antara graf terarah dengan graf tak terarah

Graf terarah	Graf tak terarah
Sejenis graf yang mempunyai pasangan tertib bucu	Sejenis graf yang mempunyai pasangan tidak tertib bucu
Tepi mewakili arah bagi bucu	Tepi tidak mewakili arah bagi bucu
Anak panah mewakili tepi	Tidak mempunyai anak panah yang mewakili tepi

	Contoh

Perbezaan antara graf berpemberat dengan graf tak berpemberat

	Graf berpemberat	Graf tidak berpemberat
Jenis graf	Graf terarah dan graf tak terarah	Graf terarah dan graf tak terarah
Tepi	Diberi nilai atau pemberat	Tiada nilai atau pemberat dinyatakan
Contoh	Tepi mewakili: jarak di antara dua bandar masa yang diambil untuk pergerakan nilai arus litar elektrik kos	Tepi mengaitkan maklumat hierarki jawatan dalam carta organisasi peta alir peta pokok peta buih

Subgraf

	Definisi

	Subgraf merupakan sebahagian atau keseluruhan suatu graf yang dilukis semula tanpa mengubah kedudukan asal bucu dan tepi

	Suatu graf \(H\) dikatakan subgraf kepada graf \(G\) jika, bucu-bucu graf \(H\) ialah subset kepada bucu-bucu graf \(G\) iaitu \(V(H) \subset V(G)\) tepi-tepi graf \(H\) ialah subset kepada tepi-tepi graf \(G\) iaitu \(E(H) \subset E(G)\) pasangan bucu setiap tepi graf \(H\) aalah sama dengan tepi graf \(G\)

Pokok suatu graf ialah subgraf bagi graf tersebut dengan ciri-ciri berikut

Graf mudah iaitu tanpa gelung atau berbilang tepi

Semua bucu mesti berkait dan setiap pasangan bucu dikaitkan oleh satu tepi sahaja

Bilangan tepi \( =\)bilangan bucu \(-1\)

Bilangan bucu\(=n\)

Bilangan tepi \(= n-1\)

	Contoh subgraf

Bab 5: Rangkaian dalam teori Graf

5.1

Rangkaian

Perkaitan antara rangkaian dengan graf

	Penjelasan

	Graf digunakan untuk mewakilkan data yang terdiri daripada objek diskret dan menggambarkan kaitan antara objek tersebut secara grafik

	Dalam teori graf, graf ditafsirkan sebagai suatu siri bintik sama ada berkait atau tidak berkait antara satu sama lain melalui garis

	Bintik dikenali sebagai bucu dan garis yang mengaitkan dua bucu ialah tepi

	Graf juga sering digunakan untuk mewakilkan suatu rangkaian

	Rangkaian merupakan sebahagian daripada graf dengan keadaan bucu dan tepi mempunyai sifat tersendiri dan struktur data rangkaian mempunyai hubungan banyak kepada banyak

	Tatanda graf merupakan set pasangan tertib iaitu \(G= (V,E)\) dengan keadaan \(V\) ialah set bintik atau bucu, \(V={ v_1, v_2, v_3, ....v_n }\) \(E\) ialah set tepi atau garis yang menghubungkan sepasang bucu

	Darjah, \(d\) ialah bilangan tepi yang menghubungkan sepasang bucu. Bilangan darjah suatu graf ialah dua kali bilangan tepi iaitu \(\sum d(v)= 2E\)

Graf mudah

Graf mudah ialah graf yang tidak mengandungi gelung atau berbilang tepi
Bilangan darjah suatu graf ialah dua kali bilangan tepi

Berbilang tepi dan gelung pada graf

Berbilang tepi

Melibatkan dua bucu

Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal

Bilangan darjah setiap gelung ialah dua

Gelung

Melibatkan dua bucu

Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal.

Bilangan darjah setiap gelung ialah \(2\).

	Contoh

Perbezaan antara graf terarah dengan graf tak terarah

Graf terarah	Graf tak terarah
Sejenis graf yang mempunyai pasangan tertib bucu	Sejenis graf yang mempunyai pasangan tidak tertib bucu
Tepi mewakili arah bagi bucu	Tepi tidak mewakili arah bagi bucu
Anak panah mewakili tepi	Tidak mempunyai anak panah yang mewakili tepi

	Contoh

Perbezaan antara graf berpemberat dengan graf tak berpemberat

	Graf berpemberat	Graf tidak berpemberat
Jenis graf	Graf terarah dan graf tak terarah	Graf terarah dan graf tak terarah
Tepi	Diberi nilai atau pemberat	Tiada nilai atau pemberat dinyatakan
Contoh	Tepi mewakili: jarak di antara dua bandar masa yang diambil untuk pergerakan nilai arus litar elektrik kos	Tepi mengaitkan maklumat hierarki jawatan dalam carta organisasi peta alir peta pokok peta buih

Subgraf

	Definisi

	Subgraf merupakan sebahagian atau keseluruhan suatu graf yang dilukis semula tanpa mengubah kedudukan asal bucu dan tepi

	Suatu graf \(H\) dikatakan subgraf kepada graf \(G\) jika, bucu-bucu graf \(H\) ialah subset kepada bucu-bucu graf \(G\) iaitu \(V(H) \subset V(G)\) tepi-tepi graf \(H\) ialah subset kepada tepi-tepi graf \(G\) iaitu \(E(H) \subset E(G)\) pasangan bucu setiap tepi graf \(H\) aalah sama dengan tepi graf \(G\)

Pokok suatu graf ialah subgraf bagi graf tersebut dengan ciri-ciri berikut

Graf mudah iaitu tanpa gelung atau berbilang tepi

Semua bucu mesti berkait dan setiap pasangan bucu dikaitkan oleh satu tepi sahaja

Bilangan tepi \( =\)bilangan bucu \(-1\)

Bilangan bucu\(=n\)

Bilangan tepi \(= n-1\)

	Contoh subgraf

Bab 5: Rangkaian dalam teori Graf

Bab 5: Rangkaian dalam teori Graf

Bab : Rangkaian Dalam Teori Graf

Topik : Rangkaian

Nota yang berkaitan