BM
Tempah Kelas Percubaan

Rangkaian dalam Teori Graf · Tingkatan 4

Rangkaian dalam Teori Graf: Contoh Berjawab (KBAT)

Masalah perancangan sebenar yang menyembunyikan idea graf dalam ceritanya: memasang kabel pada jumlah kos terendah, menukar laluan penghantaran apabila sebatang jalan ditutup, dan menguji sama ada satu set sambungan yang dicadangkan boleh wujud. Murid memilih teknik sendiri.

Ditulis oleh pasukan editorial spmmath.com.my.

Contoh berjawab 1

Sebuah majlis perbandaran akan memasang kabel gentian optik supaya lima kawasan perumahan P, Q, R, S dan T semuanya tersambung, secara terus atau melalui satu sama lain, pada jumlah kos terendah. Kos kabel (dalam RM'000) antara kawasan ialah P–Q = 8, P–R = 5, Q–R = 6, Q–S = 9, R–S = 7, R–T = 6, S–T = 4 dan P–T = 12.

Tentukan kabel mana perlu dipasang dan cari jumlah kos terendah.

  1. Untuk menyambung 5 kawasan tanpa gelung terbuang, bina pokok merentang: ia memerlukan 5 − 1 = 4 kabel dan tiada kitar.
  2. Susun kabel dari termurah: S–T = 4, P–R = 5, Q–R = 6, R–T = 6, R–S = 7, P–Q = 8, Q–S = 9, P–T = 12.
  3. Ambil S–T (4), kemudian P–R (5), belum ada kitar.
  4. Ambil Q–R (6): menyambung Q ke kumpulan P, R. Ambil R–T (6): menyambung kumpulan P-Q-R ke kumpulan S-T, jadi kesemua lima kini tersambung.
  5. Berhenti pada 4 kabel; yang termurah seterusnya, R–S = 7, akan menutup kitar, jadi langkau.
  6. Jumlah kos terendah = 4 + 5 + 6 + 6 = 21 (RM'000).

Contoh berjawab 2

Seorang kurier bertolak dari hab H dan mesti sampai kepada pelanggan F. Jarak jalan (km) ialah H–A = 4, H–B = 9, A–B = 3, A–C = 8, B–C = 2, B–F = 10 dan C–F = 3.

(a) Cari laluan terpendek dari H ke F. (b) Pada hari itu, jalan A–B ditutup untuk pembaikan.

Cari laluan terpendek baharu dan berapa lebih panjangnya.

  1. (a) Jumlahkan jarak pada setiap laluan munasabah: H–A–C–F = 4 + 8 + 3 = 15 km.
  2. H–B–C–F = 9 + 2 + 3 = 14 km; H–A–B–C–F = 4 + 3 + 2 + 3 = 12 km; H–A–B–F = 4 + 3 + 10 = 17 km.
  3. Jumlah terkecil ialah 12 km, jadi laluan terpendek ialah H–A–B–C–F.
  4. (b) Dengan A–B ditutup, buang setiap laluan yang menggunakan jalan A–B.
  5. Antara laluan yang tinggal, H–B–C–F = 14 km dan H–A–C–F = 15 km, jadi laluan terpendek baharu ialah H–B–C–F = 14 km.
  6. Ia 14 − 12 = 2 km lebih panjang daripada laluan asal.

Contoh berjawab 3

Sebuah sekolah merancang laluan berbumbung antara 7 blok. Satu draf menyatakan bilangan laluan yang bertemu di setiap blok sepatutnya 4, 4, 3, 3, 2, 2 dan 1.

(a) Dengan menggunakan darjah, terangkan mengapa draf ini tidak boleh dibina. (b) Perancang menukar blok berdarjah 1 kepada berdarjah 2.

Tunjukkan bahawa pelan baharu boleh berfungsi dan cari jumlah laluan.

  1. Anggap setiap blok sebagai bucu dan setiap laluan sebagai tepi, jadi nombor yang diberi ialah darjah.
  2. Bilangan bucu berdarjah ganjil mesti genap, kerana semua darjah berjumlah 2 × (bilangan tepi).
  3. (a) Darjah ganjil dalam draf ialah 3, 3 dan 1, tiga blok berdarjah ganjil, satu bilangan ganjil, jadi rangkaian sedemikian tidak wujud.
  4. Sebagai semakan, jumlah 4 + 4 + 3 + 3 + 2 + 2 + 1 = 19 ialah ganjil, tetapi 2 × tepi mesti genap, ia gagal lagi.
  5. (b) Menukar 1 kepada 2 memberi darjah 4, 4, 3, 3, 2, 2, 2, kini hanya dua blok berdarjah ganjil, yang dibenarkan.
  6. Jumlah = 4 + 4 + 3 + 3 + 2 + 2 + 2 = 20, jadi bilangan laluan = 20 ÷ 2 = 10.

Contoh berjawab 4

Sebuah resort perlu memasang paip air untuk menyambung 5 chalet A, B, C, D dan E. Kos paip antara dua chalet, dalam ribu ringgit, ialah: A–B 8, A–C 5, A–E 6, B–C 9, B–D 11, C–D 15, C–E 10, D–E 7.

(a) Cari kos minimum untuk menyambung kesemua 5 chalet tanpa gelung terbuang, dan senaraikan paip yang digunakan. (b) Satu pelan lebih ringkas menyambung chalet dalam satu gelang A–B–C–D–E–A.

Berapa lebih murahkah pelan minimum berbanding pelan gelang ini?

  1. Sambungan tanpa gelung ialah pokok merentang; untuk 5 chalet ia memerlukan 5 − 1 = 4 paip.
  2. Pilih paip termurah yang tidak membentuk gelung (terkecil dahulu): A–C 5, kemudian A–E 6, kemudian D–E 7, kemudian A–B 8.
  3. Keempat-empat paip ini menyambung kesemua 5 chalet, jadi kos minimum = 5 + 6 + 7 + 8 = 26 (ribu) = RM26 000.
  4. Pelan gelang A–B–C–D–E–A = 8 + 9 + 15 + 7 + 6 = 45 (ribu) = RM45 000.
  5. Penjimatan = 45 000 − 26 000 = RM19 000.

Contoh berjawab 5

Seorang jurujual memandu dari pekan P ke pekan T. Setiap jalan mempunyai jarak dan tol.

Kos petrol ialah RM0.50 sekilometer. Jalan-jalan itu: P–Q (40 km, tol RM6), Q–T (30 km, tol RM4), P–R (50 km, tiada tol), R–T (35 km, tol RM3), Q–R (10 km, tol RM1).

Cari laluan dari P ke T dengan jumlah kos perjalanan terendah (petrol campur tol), dan nyatakan kos itu.

  1. Kos setiap jalan = jarak × RM0.50 + tol.
  2. P–Q = 40 × 0.50 + 6 = 26; Q–T = 30 × 0.50 + 4 = 19; P–R = 50 × 0.50 + 0 = 25; R–T = 35 × 0.50 + 3 = 20.50; Q–R = 10 × 0.50 + 1 = 6.
  3. P–Q–T = 26 + 19 = 45.00.
  4. P–R–T = 25 + 20.50 = 45.50; P–R–Q–T = 25 + 6 + 19 = 50.00.
  5. Jumlah kos terendah ialah RM45.00 melalui P–Q–T.

Contoh berjawab 6

Sebuah sekolah ingin membina laluan berbumbung supaya 7 blok membentuk satu rangkaian bersambung tanpa gelung (sebuah pokok). (a) Cari bilangan minimum laluan yang diperlukan.

(b) Satu pelan draf memberi bilangan laluan pada setiap blok: A 3, B 1, C 2, D 2, E 1, F 2, G 1. Tunjukkan bahawa ini sepadan dengan sebuah pokok dengan bilangan laluan dari bahagian (a).

(c) Pengetua kemudian menambah satu laluan lagi dari blok A ke blok E. Terangkan mengapa rangkaian itu tidak lagi boleh menjadi pokok.

  1. (a) Pokok dengan n bucu mempunyai n − 1 tepi, jadi 7 blok memerlukan 7 − 1 = 6 laluan.
  2. (b) Hasil tambah darjah = 3 + 1 + 2 + 2 + 1 + 2 + 1 = 12, dan tepi = 12 ÷ 2 = 6, yang sepadan dengan 6 laluan sebuah pokok.
  3. (c) Menambah satu laluan menaikkan bilangan tepi kepada 6 + 1 = 7.
  4. Graf bersambung dengan 7 bucu dan 7 tepi mempunyai lebih banyak tepi daripada pokok (yang memerlukan tepat 6), jadi ia mesti mengandungi gelung dan tidak boleh menjadi pokok.

Contoh berjawab 7

Sebuah majlis perbandaran mencadangkan jambatan pejalan kaki baharu yang menghubungkan 6 buah taman, dengan bilangan jambatan yang bertemu di setiap taman diberi sebagai 3, 3, 3, 2, 2 dan 1. (a) Dengan menggunakan hasil tambah darjah, tentukan sama ada pelan ini mungkin dilaksanakan.

(b) Jika mungkin, cari jumlah bilangan jambatan yang diperlukan.

  1. Hasil tambah darjah = 3 + 3 + 3 + 2 + 2 + 1 = 14
  2. 14 ialah nombor genap, maka hasil tambah ini memenuhi syarat bahawa hasil tambah darjah bagi mana-mana graf mestilah genap, pelan ini boleh dilaksanakan
  3. Bilangan jambatan = hasil tambah darjah ÷ 2
  4. Bilangan jambatan = 14 ÷ 2 = 7

Contoh berjawab 8

Sebuah dron penghantaran terbang dari sebuah gudang W ke kondominium seorang pelanggan C melalui menara geganti, kerana ia tidak boleh terbang terus melalui zon larangan terbang. Jarak penerbangan yang mungkin, dalam km, ialah W–P = 3, W–Q = 5, P–Q = 2, P–R = 6, Q–R = 3, Q–C = 8 dan R–C = 4.

(a) Cari laluan penerbangan terpendek dari W ke C dan jumlah jaraknya. (b) Bateri dron membenarkan jarak penerbangan maksimum 11 km sebelum ia perlu kembali ke pangkalan.

Tentukan sama ada dron boleh menyelesaikan penghantaran melalui laluan ini tanpa mengecas semula.

  1. Senaraikan laluan yang mungkin dan jumlah jaraknya:
  2. W–Q–C = 5 + 8 = 13
  3. W–P–R–C = 3 + 6 + 4 = 13
  4. W–P–Q–R–C = 3 + 2 + 3 + 4 = 12
  5. W–Q–R–C = 5 + 3 + 4 = 12
  6. Jarak terpendek ialah 12 km, contohnya melalui W–Q–R–C
  7. Oleh sebab 12 km > 11 km, dron tidak dapat menyelesaikan penghantaran melalui laluan ini tanpa mengecas semula

Sumber:DSKP KSSM Mathematics Form 4 and 5 (Versi English)

Tempah Kelas PercubaanPercubaan berbayar 1 jam · Balasan hari yang sama · dari RM50/jam

Soalan lazim

Apakah yang membezakan soalan KBAT rangkaian teori graf daripada soalan latihan biasa?

Soalan KBAT meletakkan rangkaian dalam situasi sebenar, merancang laluan penghantaran, sambungan kabel, atau pemadanan acara, dan meminta anda mewajarkan pilihan, seperti bilangan minimum sisi yang diperlukan untuk menyambungkan semua bucu. Anda perlu berfikir daripada definisi asas (pokok, darjah, graf bersambung) dan bukan menggunakan formula hafalan, serta menjelaskan jawapan anda dalam ayat.

Bagaimana saya mewajarkan jawapan dalam ayat untuk soalan rangkaian KBAT?

Nyatakan definisi yang anda gunakan (contohnya, "pokok yang menyambung n bucu memerlukan tepat n − 1 sisi"), kemudian gunakannya pada nombor dalam soalan dan nyatakan kesimpulan anda dengan jelas. Wajaran satu atau dua ayat yang mengaitkan peraturan dengan situasi yang diberi memperoleh lebih markah berbanding hanya nombor akhir sahaja.

Apakah perangkap biasa apabila soalan rangkaian KBAT bertanya sambungan "minimum" yang diperlukan?

Pelajar sering melukis rangkaian yang bersambung tetapi bukan minimum, masih mengandungi satu sisi tambahan yang boleh dibuang tanpa memutuskan mana-mana bucu. Sebelum memuktamadkan jawapan, semak sama ada membuang mana-mana satu sisi daripada gambar rajah anda akan memutuskan sambungan; jika tidak, anda masih ada sisi untuk dipotong.

Tempah Kelas Percubaan

Tempah Kelas Percubaan
Percubaan berbayar 1 jam · Balasan hari yang samadari RM50/jam
Tempah Kelas Percubaan