|
|
| |
| 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 |
| |
|
|
| |
- Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal
|
| |
- Bilangan darjah setiap gelung ialah dua
|
| |
| Gelung |
| |
|
|
| |
- 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
|
|
|
- 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\)
|
| |
|
|
| |
|
|
| |
| |
Contoh subgraf |
|
| |
|
|
| |
  |
|
| |
|
|
|
| |
| |
| |
| |
| |
