Rangkaian dalam Teori Graf — Nota JomSkor
Bab ini memperkenalkan Teori Graf sebagai cabang matematik diskret. Graf terdiri daripada bucu (vertex) dan tepi (edge). Pelajar belajar mentakrif dan mengelas graf (ringkas, gelung, berbilang tepi, terarah), mengira darjah bucu, mengenal subgraf, pokok (tree), dan mencari laluan terpendek dalam graf berwajaran.
Matematik · Tingkatan 4
Bab ini memperkenalkan Teori Graf sebagai cabang matematik diskret. Graf terdiri daripada bucu (vertex) dan tepi (edge). Pelajar belajar mentakrif dan mengelas graf (ringkas, gelung, berbilang tepi, terarah), mengira darjah bucu, mengenal subgraf, pokok (tree), dan mencari laluan terpendek dalam graf berwajaran.
Graf G = (V, E)
Graf terdiri daripada set bucu V (vertex/nod) dan set tepi E (edge/sisi). Tepi menghubungkan dua bucu.
Darjah Bucu deg(v)
Bilangan tepi yang bertemu di bucu v. Bucu terpencil mempunyai darjah 0. Gelung (loop) mengira darjah 2 untuk bucu yang sama.
Teorem Jabat Tangan
Jumlah semua darjah bucu = 2 × bilangan tepi: Σdeg(v) = 2|E|. Akibatnya: bilangan bucu berdarjah ganjil adalah genap.
Jenis Graf
Graf ringkas: tiada gelung, tiada tepi berganda. Graf berganda (multigraf): ada tepi berganda antara dua bucu. Graf terarah (digraf): tepi mempunyai arah (anak panah).
Graf Berwajaran
Setiap tepi diberi nilai (wajaran/berat), seperti jarak atau kos. Digunakan dalam masalah laluan terpendek.
Subgraf
Graf H adalah subgraf bagi G jika semua bucu dan tepi H terdapat dalam G. Ia adalah subset graf asal.
Pokok (Tree)
Graf terhubung tanpa kitaran (cycle). Pokok dengan n bucu mempunyai tepat n−1 tepi. Pokok merentang (spanning tree) melibatkan semua bucu graf asal.
Laluan Terpendek
Laluan dengan jumlah wajaran tepi yang minimum antara dua bucu. Boleh diselesaikan dengan kaedah inspeksi atau Algoritma Dijkstra.
Contoh soalan
Graf G mempunyai bucu {A,B,C,D,E} dan tepi {AB, AC, BC, BD, CD, DE}. (i) Cari darjah setiap bucu. (ii) Sahkan Teorem Jabat Tangan. (iii) Tentukan sama ada G adalah pokok.
- (i) deg(A)=2, deg(B)=3, deg(C)=3, deg(D)=3, deg(E)=1 (ii) Σdeg = 2+3+3+3+1 = 12; bilangan tepi = 6; 2×6 = 12 ✓ (iii) Bilangan bucu = 5, bilangan tepi = 6. Pokok memerlukan 5−1=4 tepi. G mempunyai 6 tepi, jadi G BUKAN pokok (ada kitaran).
- Terlupa gelung mengira darjah 2 bukan 1 — Setiap gelung pada bucu v menyumbang 2 kepada deg(v)
- Keliru antara laluan (path), jejak (trail), dan kitaran (cycle) — Laluan: bucu tidak berulang. Jejak: tepi tidak berulang. Kitaran: laluan tertutup yang bucu mula dan akhirnya sama, tanpa ulangan bucu lain sepanjang laluan. Jejak tertutup tanpa ulangan tepi boleh mengulangi bucu perantaraan, maka tidak semestinya satu kitaran.
- Mengatakan pokok ada n tepi untuk n bucu — Pokok dengan n bucu mempunyai tepat n−1 tepi, bukan n tepi
- Tidak semak ketersambungan ketika menentukan pokok — Pokok mestilah terhubung (connected) DAN tanpa kitaran. Graf tanpa kitaran tetapi tidak terhubung dipanggil hutan (forest).
- Salah kira laluan terpendek — hanya tengok bilangan tepi, bukan jumlah wajaran — Laluan terpendek dalam graf berwajaran = jumlah wajaran terkecil, bukan bilangan tepi terkecil
- Senaraikan semua bucu dan kira darjah setiap satu sebelum menjawab soalan — ini mengelakkan kesilapan pengiraan
- Gunakan Teorem Jabat Tangan untuk semak kebenaran jawapan: Σdeg mesti genap
- Untuk laluan terpendek, senaraikan semua laluan yang mungkin dan kira jumlah wajaran masing-masing
- Pokok merentang — cari subset tepi yang menghubungkan semua bucu dengan tepi minimum (n−1 tepi)
- Soalan SPM kerap tanya: (a) darjah bucu, (b) teorem jabat tangan, (c) sama ada pokok atau bukan — latih ketiganya
- Bucu (v)
- Vertex / Node
- Tepi (e)
- Edge
- Darjah Bucu (deg(v))
- Degree of Vertex
- Gelung
- Loop
- Graf Terarah
- Directed Graph / Digraph
- Graf Berwajaran
- Weighted Graph
- Subgraf
- Subgraph
- Pokok
- Tree
- Pokok Merentang
- Spanning Tree
- Laluan Terpendek
- Shortest Path
- Kitaran
- Cycle