Tingkatan 4 · Discrete Mathematics
Rangkaian dalam Teori Graf
Rangkaian menukar peta, laluan dan sambungan kepada titik dan garisan yang boleh anda ukur, bab yang sangat visual dan moden.
Apakah Rangkaian dalam Teori Graf?
Rangkaian (graf) ialah set titik, dipanggil bucu, disambung oleh garisan, dipanggil tepi. Bab ini mengajar anda membaca dan melukis rangkaian, mengira darjah, mencari hasil tambah pemberat pada tepi, dan menggunakannya untuk memodelkan situasi sebenar seperti laluan dan sambungan.
Standard kandungan (DSKP)
DSKP KSSM menetapkan standard kandungan ini untuk bab ini:
- 5.1 Rangkaian
Idea utama
Bucu, tepi dan darjah
Darjah sesuatu bucu ialah berapa banyak tepi bertemu padanya, soalan pantas paling lazim.
Rangkaian berarah dan berpemberat
Tepi boleh membawa arah (sehala) atau pemberat (jarak atau kos), baca jenis yang digunakan soalan.
Melukis rangkaian daripada penerangan
Menukar situasi berkata kepada graf yang jelas ialah kemahiran yang paling diberi ganjaran Kertas 2 di sini.
Bagaimana bab ini diuji
Jangkakan melukis atau melengkapkan rangkaian daripada jadual atau penerangan, mengira darjah, dan kadangkala menjumlahkan pemberat sepanjang laluan. Gambar rajah kemas penting, lakaran sempit menyebabkan tersalah kira.
Soalan Kertas 2 biasanya tersusun baik dan murah hati dengan markah kaedah jika graf anda jelas.
Cara mengulang bab ini
Kesilapan lazim untuk dielakkan
- Tersalah kira darjah apabila tepi dilukis terlalu rapat
- Mengabaikan arah tepi berarah
- Membiarkan gambar rajah rangkaian bersepah sehingga pemeriksa tidak dapat mengikutinya
Jumlah darjah sentiasa dua kali bilangan tepi
Setiap tepi menyentuh dua hujung, jadi setiap tepi menambah tepat 1 pada darjah setiap dua bucunya, 2 kesemuanya. Jumlahkan darjah semua bucu dan anda mesti mendapat dua kali bilangan tepi: Σ(darjah) = 2 × (bilangan tepi).
Ini memberi dua perkara sekaligus. Ia cara pantas mencari darjah yang hilang apabila bilangan tepi diketahui, dan ia semakan diri: jumlah semua darjah sentiasa genap, jadi jika darjah anda berjumlah nombor ganjil, anda tersilap kira di suatu tempat.
Satu gelung dikira 2 pada bucunya sendiri, dan di tempat beberapa tepi menyambung pasangan bucu yang sama, setiap satu dikira berasingan.
Pokok dan subgraf
Subgraf hanyalah sebahagian daripada rangkaian: kekalkan sebahagian bucu dan sebahagian tepi asal, tanpa menambah apa-apa yang baharu. Pokok ialah rangkaian bersambung istimewa tanpa kitar, anda tidak boleh bermula pada satu bucu, bergerak di sepanjang tepi tanpa mengulang mana-mana, dan kembali ke tempat mula.
Pokok mempunyai peraturan kemas yang berbaloi diketahui: pokok dengan n bucu mempunyai tepat n − 1 tepi. Jadi pokok yang menyambung 6 bandar menggunakan tepat 5 jalan.
Jika rangkaian dengan n bucu mempunyai n − 1 tepi dan berada dalam satu kepingan, ia ialah pokok; tambah satu tepi lagi dan anda mencipta satu kitar.
Membaca rangkaian terarah dan berpemberat
Dalam rangkaian terarah setiap tepi ialah anak panah sehala, jadi satu bucu mempunyai dua kiraan berasingan: darjah keluar (anak panah meninggalkannya) dan darjah masuk (anak panah memasukinya). Sesuatu laluan mesti mengikut anak panah dengan arah yang betul, anda tidak boleh bergerak menentang anak panah.
Dalam rangkaian berpemberat setiap tepi juga membawa nombor: jarak dalam km, kos dalam RM, atau masa dalam minit. Untuk mencari jumlah bagi sesuatu laluan, senaraikan tepi yang benar-benar anda guna mengikut urutan dan tambah hanya pemberatnya, bucu itu sendiri tiada nilai.
Membaca anak panah dan menambah hanya tepi pada laluan pilihan anda mengelakkan kebanyakan markah yang hilang dalam topik ini.
Contoh gaya peperiksaan berjawab
Contoh ini menggunakan hukum jumlah darjah untuk mencari darjah yang hilang, kemudian menjumlahkan pemberat di sepanjang laluan, dua kemahiran yang sering digandingkan dalam Kertas 2.
- (a) Jumlah semua darjah bersamaan dua kali bilangan tepi: Σ(darjah) = 2 × 9 = 18.
- Tambah lima darjah yang diketahui: 3 + 2 + 4 + 3 + 2 = 14.
- Darjah F = 18 − 14 = 4.
- (b) Laluan itu menggunakan tiga tepi dengan pemberat 5, 8 dan 6. Jumlah pemberat = 5 + 8 + 6 = 19.
Ulang kaji Rangkaian dalam Teori Graf
Rumus
Soalan lazim
Bagaimana bab ini diuji
Matematik SPM menguji bab ini merentasi Matematik Kertas 1 (Objektif) dan Matematik Kertas 2 (Subjektif), berdasarkan standard kandungan DSKP di atas. Kertas 2 memberi markah untuk kerja, jadi menunjukkan setiap langkah penting.
Kesilapan lazim untuk dielakkan
Tersalah kira darjah apabila tepi dilukis terlalu rapat; Mengabaikan arah tepi berarah; Membiarkan gambar rajah rangkaian bersepah sehingga pemeriksa tidak dapat mengikutinya.
Adakah sebarang rumus Rangkaian dalam Teori Graf diberi dalam peperiksaan?
Bab ini tiada rumus pada helaian rumus peperiksaan, kerja dijangka daripada ingatan dan kaedah.
Bagaimana saya kira darjah sesuatu bucu dengan betul?
Kira berapa hujung tepi bertemu pada bucu itu, bukan berapa bucu lain yang dicapainya. Setiap tepi biasa menambah 1.
Satu gelung, yang bermula dan berakhir pada bucu yang sama, menambah 2. Jika dua bucu disambung oleh lebih daripada satu tepi, kira setiap tepi itu berasingan.
Semakan pantas: semua darjah dicampur mesti nombor genap.
Apa yang menjadikan sesuatu rangkaian itu pokok?
Pokok ialah bersambung, setiap bucu boleh dicapai dari setiap bucu lain, dan tiada kitar, bermakna tiada cara untuk berpusing kembali ke bucu mula tanpa mengulang tepi. Ujian kemas ialah bilangan tepi: pokok dengan n bucu mempunyai tepat n − 1 tepi.
Jika lebih, mesti ada kitar; jika kurang, ia tidak bersambung sepenuhnya.
Apa maksud darjah masuk dan darjah keluar dalam rangkaian terarah?
Dalam rangkaian terarah setiap tepi ialah anak panah. Darjah keluar sesuatu bucu mengira anak panah yang menghala keluar daripadanya, dan darjah masuk mengira anak panah yang menghala masuk kepadanya.
Satu bucu boleh mempunyai nilai berbeza bagi kedua-duanya, tiga anak panah keluar dan satu masuk memberi darjah keluar 3 dan darjah masuk 1. Semasa menjejak laluan anda mesti sentiasa bergerak mengikut arah anak panah.
Sumber:DSKP KSSM Mathematics Form 4 and 5 (Versi English)· SPM: Format Pentaksiran mulai 2021, Matematik (1449)
Dapatkan bantuan dengan Rangkaian dalam Teori Graf
Satu-ke-satu, dalam Bahasa Inggeris, dengan kerja anda disemak baris demi baris.
Dapatkan bantuan dengan Rangkaian dalam Teori Graf