Rangkaian dalam Teori Graf · Tingkatan 4
Rangkaian dalam Teori Graf: Soalan Latihan
Soalan latihan gaya SPM asli untuk Rangkaian dalam Teori Graf, setiap satu dengan penyelesaian penuh, aneka pilihan Kertas 1 dan berstruktur Kertas 2.
Soalan latihan asli untuk Rangkaian dalam Teori Graf, dalam gaya Matematik Kertas 1 (Objektif) dan Matematik Kertas 2 (Subjektif). Setiap jawapan diselesaikan supaya anda boleh menyemak kaedah anda.
Aneka pilihan (gaya Kertas 1)
Soalan 1
Suatu graf mempunyai 8 tepi. Berapakah jumlah darjah bagi semua bucunya?
- A. 8
- B. 16
- C. 32
- D. 64
Soalan 2
Suatu graf mempunyai bucu berdarjah 3, 3, 2, 2 dan 2. Berapakah bilangan tepi graf itu?
- A. 5
- B. 6
- C. 7
- D. 12
Soalan 3
Dalam mana-mana graf, bilangan bucu berdarjah ganjil mestilah genap. Antara berikut, yang manakah tidak boleh menjadi bilangan bucu berdarjah ganjil dalam suatu graf?
- A. 0
- B. 2
- C. 3
- D. 4
Soalan 4
Suatu rangkaian terarah mempunyai 10 tepi terarah. Berapakah jumlah darjah masuk bagi semua bucunya?
- A. 5
- B. 10
- C. 20
- D. 100
Soalan 5
Suatu gelung pada sesuatu bucu menyumbang berapakah kepada darjah bucu itu?
- A. 0
- B. 1
- C. 2
- D. 3
Soalan 6
Suatu rangkaian berpemberat menghubungkan bandar P, Q, R dan S dengan panjang jalan berikut: P–Q = 5 km, P–R = 3 km, R–Q = 1 km, Q–S = 4 km, R–S = 6 km. Berapakah panjang laluan terpendek dari P ke S?
- A. 7 km
- B. 8 km
- C. 9 km
- D. 12 km
Soalan 7
Dalam suatu graf lengkap dengan 5 bucu, setiap bucu disambung kepada setiap bucu lain dengan tepat satu tepi. Berapakah bilangan tepinya?
- A. 5
- B. 10
- C. 20
- D. 25
Soalan 8
Pokok ialah graf terhubung yang tidak mempunyai kitar. Suatu pokok dengan 7 bucu mempunyai berapakah tepi?
- A. 5
- B. 6
- C. 7
- D. 8
Soalan 9
Apakah nama yang diberikan kepada bucu yang berdarjah 0 dalam suatu graf?
- A. Gelung
- B. Bucu terpencil
- C. Bucu lengkap
- D. Bucu berpemberat
Soalan 10
Istilah manakah menggambarkan suatu graf yang setiap tepinya diberi nilai berangka seperti jarak, masa atau kos?
- A. Graf mudah
- B. Graf berpemberat
- C. Graf terarah
- D. Graf lengkap
Berstruktur (gaya Kertas 2)
Soalan 1 (5 markah)
Suatu graf rangkaian G mempunyai enam bucu A, B, C, D, E dan F dengan darjah A = 4, B = 3, C = 3, D = 2, E = 2 dan F = 2. (a) Cari jumlah darjah bagi semua bucu.
(b) Seterusnya, cari bilangan tepi G. (c) Nyatakan, dengan alasan, sama ada graf sedemikian boleh dilukis.
- (a) Jumlah darjah = 4 + 3 + 3 + 2 + 2 + 2 = 16.
- (b) Bilangan tepi = jumlah darjah ÷ 2 = 16 ÷ 2 = 8.
- (c) Hanya dua bucu (B dan C) berdarjah ganjil; oleh sebab bilangan bucu berdarjah ganjil (2) genap, graf itu boleh dilukis.
Soalan 2 (4 markah)
Suatu rangkaian berpemberat menunjukkan jalan antara lima bandar P, Q, R, S dan T, dengan jarak dalam km: P–Q = 8, P–R = 5, Q–R = 3, Q–S = 6, R–T = 7, S–T = 4. (a) Senaraikan semua laluan yang mungkin dari P ke T dan jumlah panjangnya.
(b) Seterusnya, tentukan laluan terpendek dari P ke T dan nyatakan panjangnya.
- Laluan P–R–T: 5 + 7 = 12 km.
- Laluan P–Q–R–T: 8 + 3 + 7 = 18 km.
- Laluan P–Q–S–T: 8 + 6 + 4 = 18 km.
- Laluan P–R–Q–S–T: 5 + 3 + 6 + 4 = 18 km.
- Membandingkan semua laluan, jumlah panjang terkecil ialah 12 km.
Soalan 3 (6 markah)
Suatu rangkaian terarah memodelkan jalan sehala antara empat simpang A, B, C dan D. Tepi terarahnya ialah A→B, A→C, B→C, C→D, D→A dan D→B.
(a) Tuliskan darjah keluar bagi setiap simpang. (b) Tuliskan darjah masuk bagi setiap simpang.
(c) Tunjukkan bahawa jumlah darjah keluar sama dengan jumlah darjah masuk, dan nyatakan apa yang diwakili oleh jumlah ini.
- (a) Darjah keluar: A → B dan A → C memberi A = 2; B → C memberi B = 1; C → D memberi C = 1; D → A dan D → B memberi D = 2.
- (b) Darjah masuk: D → A memberi A = 1; A → B dan D → B memberi B = 2; A → C dan B → C memberi C = 2; C → D memberi D = 1.
- (c) Jumlah darjah keluar = 2 + 1 + 1 + 2 = 6; jumlah darjah masuk = 1 + 2 + 2 + 1 = 6; kedua-duanya sama dengan bilangan tepi terarah, iaitu 6.
Soalan 4 (5 markah)
Dalam suatu kejohanan catur, 7 orang pemain masing-masing bermain tepat satu perlawanan menentang setiap pemain lain. Ini dimodelkan oleh suatu graf yang bucunya ialah pemain dan setiap tepi ialah satu perlawanan yang dimainkan.
(a) Nyatakan darjah bagi setiap bucu dan berikan alasan. (b) Cari jumlah darjah bagi semua bucu.
(c) Seterusnya, cari jumlah bilangan perlawanan yang dimainkan.
- (a) Setiap pemain bermain menentang 6 pemain lain, jadi setiap bucu berdarjah 6.
- (b) Jumlah darjah = 7 × 6 = 42.
- (c) Bilangan tepi = jumlah darjah ÷ 2 = 42 ÷ 2 = 21, jadi 21 perlawanan dimainkan. (Semak: n(n−1)/2 = 7 × 6 ÷ 2 = 21.)
Sumber:SPM: Format Pentaksiran mulai 2021, Matematik (1449)
Soalan lazim
Apakah perbezaan antara soalan Kertas 1 dan Kertas 2 dalam set rangkaian dalam teori graf ini?
Soalan Kertas 1 berbentuk aneka pilihan, menguji pembacaan pantas bucu, sisi dan darjah daripada gambar rajah rangkaian kecil, serta mengecam rangkaian berarah berbanding tidak berarah atau berpemberat berbanding tidak berpemberat. Soalan Kertas 2 pula memerlukan anda melukis rangkaian daripada maklumat yang diberi, mengenal pasti subgraf atau pokok, dan menjumlahkan pemberat sepanjang laluan dengan kerja lengkap ditunjukkan.
Mengapa saya perlu mencuba setiap soalan rangkaian sebelum menyemak penyelesaian berpandu?
Membaca gambar rajah rangkaian dengan betul, mengira darjah, mengikut arah tepi, menjumlahkan setiap pemberat sepanjang laluan, memerlukan latihan di bawah tekanan masa. Mencuba soalan sendiri dahulu menunjukkan sama ada anda boleh membina dan membaca rangkaian itu secara bebas, bukan sekadar mengikut logik yang sudah kelihatan jelas dalam gambar rajah siap.
Apakah kesilapan biasa pelajar dalam soalan rangkaian dalam teori graf?
Pelajar sering tersilap kira darjah sesuatu bucu apabila tepi dilukis terlalu rapat, mengabaikan arah tepi berarah, atau terlupa menambah setiap pemberat sepanjang laluan yang dilalui. Set latihan ini dibina untuk mendedahkan kesilapan itu sebelum peperiksaan sebenar.