Rangkaian dalam Teori Graf
Cara Mencari laluan terpendek dalam rangkaian
Gunakan ini untuk mencari laluan berpemberat terendah antara dua titik pada rangkaian.
Sebelum anda mula
- Boleh membaca rangkaian berpemberat: bucu (titik) yang disambung oleh tepi dengan nombor.
- Boleh menambah beberapa nombor dengan tepat.
- Faham bahawa laluan ialah urutan tepi yang bersambung dari mula ke akhir.
Bila menggunakannya
Gunakan ini untuk mencari laluan berpemberat terendah antara dua titik pada rangkaian.
Langkah-langkah
- Labelkan setiap tepi dengan pemberatnya (jarak, masa atau kos).
- Senaraikan laluan munasabah antara bucu mula dan akhir.
- Jumlahkan pemberat sepanjang setiap laluan.
- Bandingkan jumlah dan pilih yang terkecil.
- Tunjukkan jumlah bagi setiap laluan supaya perbandingan jelas.
Contoh berjawab
Suatu rangkaian menyambung pekan A, B, C dan D. Jalan dan jaraknya ialah A–B = 5 km, A–C = 3 km, B–C = 1 km, B–D = 4 km dan C–D = 6 km.
Cari laluan terpendek dari A ke D.
- Labelkan setiap tepi dengan pemberatnya: A–B = 5 km, A–C = 3 km, B–C = 1 km, B–D = 4 km, C–D = 6 km.
- Senaraikan laluan yang munasabah dari A ke D: A–B–D, A–C–D, A–C–B–D dan A–B–C–D.
- Jumlahkan pemberat sepanjang setiap laluan: A–B–D = 5 + 4 = 9 km; A–C–D = 3 + 6 = 9 km; A–C–B–D = 3 + 1 + 4 = 8 km; A–B–C–D = 5 + 1 + 6 = 12 km.
- Bandingkan jumlah 9, 9, 8 dan 12 km, dan pilih yang terkecil, iaitu 8 km.
- Tunjukkan jumlah supaya perbandingan jelas: laluan A–C–B–D pada 8 km lebih pendek daripada setiap laluan lain.
Contoh kedua, dengan selekoh
Rangkaian ini mempunyai lima pekan dan pemberatnya ialah kos perjalanan dalam ringgit, jadi ada lebih banyak laluan untuk dijumlahkan, dan laluan melalui pekan paling sedikit bukanlah yang termurah. Suatu rangkaian menyambung pekan P, Q, R, S dan T.
Kos perjalanan ialah P–Q = RM8, P–R = RM5, Q–S = RM4, R–S = RM3, Q–T = RM9, S–T = RM6 dan R–T = RM15. Cari laluan termurah dari P ke T.
- Labelkan setiap tepi dengan kosnya: P–Q = RM8, P–R = RM5, Q–S = RM4, R–S = RM3, Q–T = RM9, S–T = RM6, R–T = RM15.
- Senaraikan laluan yang munasabah dari P ke T: P–Q–T, P–Q–S–T, P–R–T, P–R–S–T dan P–R–S–Q–T.
- Jumlahkan kos sepanjang setiap laluan: P–Q–T = 8 + 9 = RM17; P–Q–S–T = 8 + 4 + 6 = RM18; P–R–T = 5 + 15 = RM20; P–R–S–T = 5 + 3 + 6 = RM14; P–R–S–Q–T = 5 + 3 + 4 + 9 = RM21.
- Bandingkan jumlah RM17, RM18, RM20, RM14 dan RM21, dan pilih yang terkecil, iaitu RM14.
- Tunjukkan jumlah supaya perbandingan jelas: P–R–S–T pada RM14 termurah, walaupun P–R–T menggunakan jalan yang lebih sedikit.
Halaman rumus
Berlatih dengan soalan KBAT
Soalan lazim
Adakah saya perlu senaraikan setiap laluan yang mungkin?
Senaraikan setiap laluan yang munasabah dari mula ke akhir. Anda boleh tinggalkan laluan yang jelas berpusing balik atau mengambil lencongan jauh yang ketara, tetapi masukkan mana-mana laluan yang mungkin pendek.
Terlepas satu laluan itu berisiko, kerana yang terpendek kadangkala laluan yang anda tidak sangka perlu disemak.
Adakah laluan melalui pekan paling sedikit sentiasa yang terpendek?
Tidak. Laluan dengan tepi yang lebih sedikit masih boleh mempunyai pemberat yang lebih besar dan menjadi lebih panjang secara keseluruhan.
Laluan yang melalui lebih banyak pekan tetapi menyusuri tepi yang pendek dan murah mungkin berjumlah kurang. Sebab itu anda mesti menjumlahkan pemberat setiap laluan dan membandingkan jumlahnya, bukan sekadar mengira bilangan hentian.
Apa patut saya buat jika dua laluan mempunyai jumlah yang sama?
Maka kedua-dua laluan itu terpendek dan mana-mana satu ialah jawapan yang betul. Adalah amalan baik untuk menyatakan bahawa keduanya seri dan memberi jumlah yang sama, contohnya 'A–C–D dan A–B–D kedua-duanya 9 km'.
Menunjukkan setiap jumlah dalam kerja anda menjelaskan mengapa lebih daripada satu laluan boleh menang.