| Kaitan Antara Rangkaian dengan Graf |
|
- Graf digunakan untuk mewakilkan data yang terdiri daripada objek diskret dan menggambarkan kaitan antara objek tersebut secara grafik yang mudah difahami.
- Graf ditafsirkan sebagai suatu siri bintik sama ada berkait atau tidak antara satu sama lain melalui garis.
- Bintik dikenali sebagai bucu dan garis yang mengaitkan dua bucu ialah tepi.
- Graf sering digunakan untuk mewakilkan suatu rangkaian.
- Rangkaian merupakan sebahagian daripada graf dengan keadaan bucu dan tepi mempunyai sifat tersendiri.
- Struktur data rangkaian mempunyai hubungan banyak kepada banyak.
|
| Bilangan Darjah Suatu Graf |
\(\sum d(v)=2E;v \isin V\)
| \(G\) |
Graf (graph) |
| \(d\) |
Darjah (degree) |
| \(v\) |
Bucu (vertices) atau Bintik |
| \(V\) |
Set Bucu |
| \(e\) |
Tepi (edge) atau Garis atau Lengkung |
| \(E\) |
Set Pasangan Bucu |
| \(\sum\) |
Jumlah |
|
| Graf Mudah |
- Graf yang tidak mengandungi gelung atau berbilang tepi.
- Bilangan darjah ialah dua kali bilangan tepi.
|
|
Berdasarkan graf mudah, tentukan \(V\text{ dan }n(V)\), \(E\text{ dan }n(E)\) dan bilangan darjah.
| \(V\text{ dan }n(V)\) |
\(\text{Set bucu}=V=\{1,2,3,4,5,6\}\\\text{Bilangan bucu}=n(V)=6\color{red}\text{}\) |
| \(E\text{ dan }n(E)\) |
\(\text{Set pasangan baru}=E=\{(1,2),(1,5),(2,3),(2,4),(3,4),(4,5),(5,6)\}\\\text{Bilangan darjah}=n(E)=7\) |
| Bilangan Darjah |
\(\sum d(v)=2(E)\\\qquad\quad\;=2(7)\\\qquad\quad\;=14\)
|
|
| Berbilang Tepi dan Gelung Pada Graf |
| Berbilang Tepi |
Gelung |
- Melibatkan \(2\) bucu.
- Kaitan antara \(2\) bucu tersebut dinyatakan melalui lebih daripada \(1\) tepi.
- Bilangan darjah ialah \(2\) kali bilangan tepi.
|
- Melibatkan \(1\) bucu.
- Tepi berbentuk lengkung atau bulatan yang berbalik kepada bucu asal.
- Bilangan darjah setiap gelung ialah \(2\).
|
|
|
Bilangan darjah setiap gelung ialah \(2\), iaitu pusingan mengikut arah jam dan pusingan mengikut lawan arah jam. |
|
Rajah menunjukkan suatu graf yang mempunyai gelung dan berbilang tepi. Nyatakan \(V\text{ dan }n(V)\), \(E\text{ dan }n(E)\) dan bilangan darjah.
| \(V\text{ dan }n(V)\) |
\(V=\{P,Q,R,S,T,U\} \\n(V)=6\color{red}\text{}\) |
| \(E\text{ dan }n(E)\) |
\(E=\{(P,Q),(P,U),(P,U),(Q,R),(Q,U),(R,S),(R,T),(S,S),(S,T),(T,U)\} \\n(E)=10\color{red}\text{}\) |
| Bilangan Darjah |
\(\text{Bucu }P=3\\\text{Bucu }Q=3\\\text{Bucu }R=3\\\text{Bucu }S=4\\\text{Bucu }T=3\\\text{Bucu }U=4\)
Bilangan darjah ialah \(20\).
|
|
| Perbezaan Antara Graf Terarah dengan Graf Tak Terarah |
|
|
| Perbezaan Antara Graf Berpemberat dengan Graf Tak Berpemberat |
|
| Graf Berpemberat |
Graf Tak Berpemberat |
- Jenis graf:
- graf terarah
- graf tak terarah
- Tepi:
- diberi nilai atau pemberat
- Tepi mewakili:
- jarak di antara dua bandar
- masa yang diambil untuk suatu gerakan
- nilai arus suatu litar elektrik
- kos
|
- Jenis graf:
- graf terarah
- graf tak terarah
- Tepi:
- tiada nilai atau pemberat yang dinyatakan
- Tepi mengaitkan maklumat:
- hierarki jawatan dalam carta organisasi
- peta alir
- peta pokok
- peta buih
|
|
|
Rajah menunjukkan pilihan laluan sehala Aiman untuk menjalankan latihan larian. Bucu \(v_1\) ialah tempat permulaan dan bucu \(v_5\) ialah tempat terakhir sebelum dia balik ke rumah.
Tentukan
- jarak laluan sehala yang terpendek, dari \(v_1\) ke \(v_5\).
- jarak laluan sehala yang terpanjang, dari \(v_1\) ke \(v_5\).
- bucu-bucu yang perlu dilalui jika jarak larian sehala adalah di antara \(1.4\text{ km}\) hingga \(2.1\text{ km}\).
| |
Penyelesaian |
| Jarak laluan sehala yang terpendek, dari \(v_1\) ke \(v_5\) |
\(\quad v_1\rightarrow v_2 \rightarrow v_5\\=(600+500)\text{ m}\\=1\,100\text{ m}\\=1.1\text{ km}\) |
| Jarak laluan sehala yang terpanjang, dari \(v_1\) ke \(v_5\) |
\(\quad v_1\rightarrow v_2 \rightarrow v_3\rightarrow v_4 \rightarrow v_5\\=(600+900+500+500)\text{ m}\\=2\,500\text{ m}\\=2.5\text{ km}\) |
Bucu-bucu yang perlu dilalui jika jarak larian sehala adalah di antara  \(1.4\text{ km}\) dan\(2.1\text{ km}\) |
\(v_1,v_3,v_4,v_5 \text{ dan }v_1,v_2,v_4,v_5\) |
|
| Subgraph |
| Subgraf merupakan sebahagian atau keseluruhan suaru graf yang dilukis semula tanpa mengubah kedudukan asal bucu dan tepi. |
|
Tentukan sama ada rajah-rajah di bawah ialah subgraf bagi graf \(G\).
| |
Penyelesaian |
 |
Ya, kerana pasangan bucu untuk tepi \(e_5\) adalah sama.
\(\{e_5\}\subset\{e_1,e_2,e_3,e_4,e_5\}\) dan \(\{P,S\}\subset\{P,Q,R,S\}\)
|
 |
Tidak, kerana kedudukan gelung \(e_2\) bukan pada bucu \(Q\). |
 |
Tidak, kerana tepi yang mengaitkan bucu \(P\) dan bucu \(S\) adalah bukan \(e_3\). |
 |
Tidak, kerana tepi gelung dan tepi yang mengaitkan bucu \(Q\) dan bucu \(R\) adalah salah. |
|
| Pokok |
|
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.
- \(\text{Bilangan tepi}=\text{Bilangan bucu}-1\\\text{Bilangan bucu}=n\\\text{Bilangan tepi}=n-1\)
|
 |
Pokok, kerana
- semua bucu berkait.
- setiap pasangan bucu dikaitkan oelh satu tepi sahaja.
- tidak ada gelung atau berbilang tepi.
- \(5\) bucu, \(4\) tepi.
|
 |
Bukan suatu pokok, kerana
- bucu \(B\) dan bucu \(E\) boleh dikaitkan dengan dua cara iaitu:
- \(B \rightarrow E\)
- \(B \rightarrow C \rightarrow D \rightarrow E\)
- \(5\) bucu, \(5\) tepi.
|
|
|
Rajah menunjukkan suatu graf tidak terarah dan berpemberat. Lukis satu pokok dengan jumlah nilai pemberat yang minimum.
Penyelesaian:
| Langkah \(1\) |
Langkah \(2\) |
- \(5\) bucu, \(7\) tepi.
- \(3\) tepi perlu dibuang.
- Keluarkan tepi dengan pemberat nilai tertinggi \((PQ, QR, PT)\).
Graf di atas bukan pokok kerana
- bucu \(P\) tidak dikaitkan dengan bucu lain.
- \(3\) tepi, \(RS,ST\) dan \(RT\) mengaitkan \(3\) bucu sahaja.
|
- Antara pemberat bernilai \(19\) dengan \(25\), pemberat bernilai \(19\) perlu dikekalkan kerana nilainya lebih rendah.
- Antara pemberat \(12\), \(14\) dengan \(17\), pemberat bernilai \(17\) perlu dikeluarkan.
Graf yang terhasil ialah pokok.
Jumlah pemberat minimum pokok
\(=10+12+14+19\\=55\)
|
|
|
