Rangkaian dalam Teori Graf · Tingkatan 4
Rangkaian dalam Teori Graf: Istilah Utama
Istilah Rangkaian dalam Teori Graf utama yang anda perlukan untuk Matematik SPM, ditakrifkan secara ringkas dalam tiga bahasa.
- Bucu Titik dalam rangkaian, disambung kepada yang lain oleh tepi.
- Tepi Garis yang menyambung dua bucu dalam rangkaian.
- Darjah bucu Bilangan tepi yang bertemu pada sesuatu bucu.
- Tepi berpemberat Tepi yang membawa nilai seperti jarak, masa atau kos.
- Darjah bucu Bilangan tepi yang bertemu di sesuatu bucu.
- Pokok Rangkaian bersambung tanpa kitaran.
- Subgraf Rangkaian yang dibentuk daripada sebahagian bucu dan tepi rangkaian yang lebih besar.
Pasangan istilah yang pelajar keliru
- Bucu vs Tepi, bucu ialah titik (sebuah bandar, satu simpang); tepi ialah garis yang menyambung dua bucu (sebatang jalan). Kira titik untuk bucu dan garis untuk tepi.
- Darjah vs Pemberat, darjah ialah bilangan tepi yang bertemu pada bucu; pemberat ialah nombor yang ditulis pada tepi, seperti jarak atau kos. Satu pada titik, satu lagi sepanjang garis.
- Tepi berarah vs tak berarah, tepi berarah ada anak panah dan boleh dilalui satu arah sahaja; tepi tak berarah tiada anak panah dan berfungsi dua hala.
- Darjah masuk vs Darjah keluar, dalam rangkaian berarah, darjah masuk mengira anak panah yang menghala masuk ke bucu, darjah keluar mengira anak panah yang keluar; jumlahnya ialah jumlah darjah.
- Pokok vs Subgraf, subgraf ialah mana-mana bahagian rangkaian; pokok ialah subgraf bersambung istimewa tanpa kitar dan tepat (bucu − 1) tepi.
- Gelung vs Tepi selari, gelung menyambung bucu kepada dirinya sendiri dan menambah 2 pada darjahnya; tepi selari ialah dua atau lebih tepi berasingan yang menyambung pasangan bucu yang sama.
Bagaimana istilah ini muncul dalam soalan SPM sebenar
- 'Cari darjah bucu X' bermaksud kira tepi yang bertemu X, dan ingat gelung dikira sebagai 2.
- 'Lukis satu rangkaian untuk mewakili maklumat dalam jadual' meminta anda menukar setiap hubungan yang disenaraikan menjadi tepi dan setiap item menjadi bucu.
- 'Nombor pada setiap tepi mewakili jarak / kos' menandakan rangkaian berpemberat, jumlah diperoleh dengan menambah pemberat tepi, bukan bucu.
- 'Lengkapkan rangkaian' mengharapkan anda menambah tepi, anak panah atau pemberat yang hilang supaya gambar rajah sepadan dengan perihalan.
- 'Nyatakan sama ada rangkaian itu pokok' bermaksud semak tiga perkara: ia bersambung, tiada kitar, dan mempunyai tepat (bucu − 1) tepi.
Sumber:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
Soalan lazim
Adakah 'darjah' sama dengan 'pemberat'?
Tidak, dan peperiksaan bergantung pada anda mengetahui ini. Darjah ialah kiraan nombor bulat bagi tepi yang bertemu pada bucu, sifat sesuatu titik.
Pemberat ialah nilai yang dibawa oleh tepi, seperti jarak dalam km, sifat sesuatu garis. Bucu mempunyai darjah; tepi mempunyai pemberat.
Adakah setiap rangkaian dalam bab ini ialah pokok?
Tidak. Kebanyakan rangkaian bukan pokok.
Pokok ialah kes istimewa: ia mesti bersambung, tiada kitar, dan mempunyai tepat satu tepi kurang daripada bilangan bucunya. Sebarang rangkaian dengan kitar, atau dengan lebih daripada (bucu − 1) tepi, bukan pokok walaupun setiap bucu bersambung.
Apabila soalan menyebut 'rangkaian', adakah ia bermaksud sama dengan 'graf'?
Ya. Dalam bab ini perkataan rangkaian dan graf bermaksud perkara yang sama, satu set bucu yang disambung oleh tepi.
'Rangkaian' ialah perkataan harian yang diutamakan sukatan, dan 'graf' ialah istilah matematik. Jangan kelirukan graf ini dengan graf sesuatu fungsi seperti y = x², yang merupakan idea yang berbeza sama sekali.