Nota Rangkaian Teori Graf SPM Tingkatan 4 | Euler KSSM — JomSkor
Nota ringkas Rangkaian dalam Teori Graf SPM Tingkatan 4 — bucu, tepi, darjah bucu, jejak Euler, litar Euler, pokok rentang minimum. Contoh soalan & tips SPM.
1. Asas Teori Graf
- Graf — terdiri daripada set bucu (V) dan set tepi (E)
- Bucu (vertex/node) — titik-titik dalam graf
- Tepi (edge) — garis yang menghubungkan dua bucu
- Darjah bucu — bilangan tepi yang bertemu pada bucu tersebut
- Gelung (loop) — tepi yang bermula dan berakhir pada bucu yang sama (sumbang darjah 2)
- Graf terkait — setiap pasang bucu dihubungkan oleh laluan
2. Teorem Jabat Tangan
Hasil tambah semua darjah bucu = 2 × bilangan tepi
Akibat: Bilangan bucu berdarjah ganjil dalam sebarang graf sentiasa genap.
Contoh 1
Graf dengan bucu A(darjah 3), B(darjah 2), C(darjah 3), D(darjah 2). Cari bilangan tepi.
- Jumlah darjah = 3 + 2 + 3 + 2 = 10
- Bilangan tepi = 10 ÷ 2 = 5 tepi
3. Jenis-Jenis Graf Khas
| Jenis Graf | Ciri |
|---|---|
| Graf lengkap (Kₙ) | Setiap pasang bucu dihubungkan; bilangan tepi = n(n−1)/2 |
| Graf dwi-bahagi | Bucu dibahagi dua kumpulan; tepi hanya antara kumpulan berlainan |
| Graf berarah | Tepi mempunyai arah (anak panah) |
| Rangkaian berbobot | Setiap tepi ada nilai (berat/kos/jarak) |
4. Jejak Euler dan Litar Euler
| Konsep | Takrifan | Syarat |
|---|---|---|
| Jejak Euler | Laluan yang melalui setiap tepi tepat sekali | Tepat 2 bucu berdarjah ganjil |
| Litar Euler | Jejak Euler yang bermula dan berakhir di bucu yang sama | Semua bucu berdarjah genap |
| Tiada jejak Euler | Tidak mungkin melintasi semua tepi tepat sekali | Lebih dari 2 bucu berdarjah ganjil |
Contoh 2 — Tentukan kewujudan jejak Euler
Graf dengan darjah bucu: A=3, B=2, C=3, D=2, E=2. Adakah jejak Euler wujud?
- Bucu berdarjah ganjil: A(3) dan C(3) → tepat 2 bucu ganjil
- Ya, jejak Euler wujud — bermula di A, berakhir di C (atau sebaliknya)
5. Pokok Rentang (Spanning Tree)
Pokok rentang ialah subgraf yang menghubungkan semua bucu tanpa membentuk kitaran, dengan bilangan tepi minimum.
- Untuk graf dengan n bucu: pokok rentang mempunyai tepat n − 1 tepi
- Pokok rentang minimum — pokok rentang dengan jumlah berat tepi paling kecil
Algoritma Prim (Pokok Rentang Minimum)
- Pilih mana-mana bucu sebagai permulaan
- Tambah tepi berat terendah yang menghubungkan bucu dalam pokok ke bucu luar (tanpa membentuk kitaran)
- Ulangi sehingga semua bucu terhubung
Contoh 3
Graf dengan tepi: AB=4, AC=2, BC=5, BD=3, CD=6. Cari pokok rentang minimum.
- Pilih tepi terkecil: AC = 2
- Tepi seterusnya (tidak bentuk kitaran): AB = 4
- Tepi seterusnya: BD = 3
- Semua 4 bucu terhubung dengan 3 tepi
- Jumlah berat minimum = 2 + 3 + 4 = 9
6. Petua Peperiksaan SPM
Tip 1: Hitung darjah setiap bucu dengan teliti — kira bilangan tepi yang BERTEMU pada setiap bucu (bukan bilangan tepi keseluruhannya). Gelung dikira 2.
Tip 2: Soalan jejak Euler — hitung dulu bilangan bucu berdarjah ganjil. Tepat 0 = litar Euler; tepat 2 = jejak Euler; lebih dari 2 = tiada jejak Euler.
Tip 3: Untuk pokok rentang minimum, semak semula bahawa: (i) semua bucu terhubung, (ii) tiada kitaran, (iii) bilangan tepi = n − 1.
Soalan lazim
Apakah syarat untuk wujudnya jejak Euler?
Jejak Euler wujud jika graf mempunyai tepat DUA bucu berdarjah ganjil (mula dari satu bucu ganjil, tamat di bucu ganjil yang lain). Jika tiada bucu berdarjah ganjil, ia adalah litar Euler (bermula dan berakhir di titik yang sama).
Apakah perbezaan antara graf dan rangkaian?
Graf ialah struktur matematik dengan bucu dan tepi. Rangkaian (network) ialah graf berbobot — setiap tepi mempunyai nilai (seperti jarak atau kos). Dalam SPM, rangkaian digunakan untuk cari laluan terpendek atau pokok rentang minimum.
Bagaimana cara cari bilangan tepi dari darjah bucu?
Hasil tambah semua darjah bucu = 2 × bilangan tepi. Ini kerana setiap tepi menyumbang darjah 1 kepada dua bucu yang dihubungkannya.