Tiga semakan mengelaskan sesebuah rangkaian: adakah terdapat anak panah, adakah terdapat nombor pada tepi, dan adakah terdapat gelung atau tepi berulang. Setiap semakan berasingan, jadi satu graf boleh menjadi lebih daripada satu jenis.
Pelajaran ini menyambung mewakilkan rangkaian sebenar sebagai graf dalam bab rangkaian SPM Matematik.
Apa tiga semakan itu?
| Ciri | Semakan | Nama |
|---|---|---|
| Anak panah pada tepi | Adakah tepi mempunyai arah? | Terarah |
| Nombor pada tepi | Adakah setiap tepi membawa nilai? | Berwajaran |
| Gelung atau tepi berulang | Adakah ada tepi dari bucu kepada dirinya, atau dua tepi antara pasangan yang sama? | Bukan ringkas |
Graf yang tiada gelung dan tiada tepi berulang lulus ujian ringkas. Graf boleh lulus ujian itu sambil menjadi terarah atau berwajaran.
Contoh penyelesaian: tiga keadaan
Keadaan 1. Lima pekan dihubungkan oleh jalan raya, dan setiap jalan boleh dipandu dua arah. Tiada jalan yang berpusing kembali, dan tiada pasangan yang mempunyai dua jalan. Graf itu ringkas dan tidak terarah.
Keadaan 2. Pekan yang sama, tetapi jalan ditulis 9 km, 14 km, 7 km dan 11 km. Graf itu berwajaran, dan masih ringkas.
Keadaan 3. Sistem giliran di dewan makan sekolah mempunyai anak panah sehala dari kaunter ke meja, dan dua anak panah berasingan dari kaunter ke Meja 3 bagi dua laluan berbeza. Graf itu terarah, dan ia bukan ringkas kerana satu pasangan mempunyai dua tepi.
Kesilapan yang menyebabkan markah hilang
Kesilapan biasa ialah membaca nombor pada tepi sebagai darjah bucu, atau sebaliknya. Wajaran ditulis di sebelah tepi. Darjah dikira pada bucu.
| Wajaran | Darjah | |
|---|---|---|
| Milik | Tepi | Bucu |
| Di mana ia ditemui | Ditulis pada graf | Dikira daripada graf |
| Contoh | 9 km pada jalan AB | 3 jalan bertemu di A |
Jika soalan meminta “darjah A”, kira tepi di A. Jangan tambah wajaran.
Semak sendiri
Sebuah rangkaian mempunyai bucu X, Y dan Z. Tepinya: X ke Y dengan wajaran 6, Y ke Z dengan wajaran 4, dan satu gelung pada X. Semua tepi dua arah. Kelaskan rangkaian itu.
Jawapan
Anak panah: tiada, maka graf itu tidak terarah.
Nombor: X ke Y dan Y ke Z membawa wajaran, maka graf itu berwajaran. Gelung tiada wajaran yang diberi, jadi pelabelan itu belum lengkap.
Gelung: terdapat satu gelung pada X, maka graf itu bukan ringkas.
Apa yang dipelajari seterusnya
Wajaran menjadikan pencarian laluan mungkin. Teruskan dengan mencari laluan cekap dalam rangkaian berwajaran kecil. Bandingkan lukisan dengan makmal bukti graf dan perbandingan adil (Bahasa Inggeris), dan catat kesilapan dalam log kesilapan dan semakan ralat kertas.
Dalam tuisyen Matematik dalam talian satu lawan satu, seorang guru boleh menguji pengelasan anda pada rangkaian baharu.