BM
Tempah Kelas Percubaan

Rangkaian dalam Teori Graf · Tingkatan 4

Rangkaian dalam Teori Graf: Contoh Berjawab (Sederhana)

Menggunakan asas untuk menyelesaikan masalah: membaca jarak daripada rangkaian berpemberat untuk membandingkan laluan, mengira jabat tangan dengan graf lengkap, dan menggunakan peraturan tepi pokok untuk menentukan tepi mana perlu dibuang. Untuk murid yang bersedia menggabungkan dua atau tiga langkah.

Ditulis oleh pasukan editorial spmmath.com.my.

Contoh berjawab 1

Rajah menunjukkan jalan raya antara lima pekan, dengan jarak dalam km: A–B = 4, A–C = 3, B–C = 1, B–D = 6, C–D = 2, C–E = 9 dan D–E = 3. Cari laluan terpendek dari pekan A ke pekan E dan nyatakan panjangnya.

  1. Senaraikan laluan yang munasabah dari A ke E dan jumlahkan jarak pada setiap satu.
  2. A–C–E = 3 + 9 = 12 km.
  3. A–C–D–E = 3 + 2 + 3 = 8 km.
  4. A–B–C–D–E = 4 + 1 + 2 + 3 = 10 km.
  5. A–B–D–E = 4 + 6 + 3 = 13 km.
  6. Jumlah terkecil ialah 8 km, melalui A–C–D–E.

Contoh berjawab 2

Enam sahabat di satu majlis reunion masing-masing berjabat tangan tepat sekali dengan setiap orang lain. Dengan memodelkan setiap orang sebagai bucu dan setiap jabat tangan sebagai tepi, cari darjah setiap bucu dan jumlah jabat tangan.

  1. Setiap orang berjabat tangan dengan 5 orang lain, jadi setiap bucu mempunyai darjah 5.
  2. Ini membentuk graf lengkap pada 6 bucu.
  3. Jumlah darjah = 6 × 5 = 30.
  4. Bilangan tepi = jumlah darjah ÷ 2 = 30 ÷ 2 = 15.

Contoh berjawab 3

Sebuah rangkaian tersambung mempunyai 10 bucu dan 15 tepi. Terangkan mengapa ia tidak boleh menjadi pokok, dan cari bilangan tepi terkecil yang mesti dibuang supaya yang tinggal ialah pokok merentang yang masih menyambungkan kesemua 10 bucu.

  1. Pokok pada 10 bucu akan mempunyai tepat v − 1 = 10 − 1 = 9 tepi.
  2. Rangkaian ini mempunyai 15 tepi, lebih daripada 9, jadi ia mesti mengandungi kitar dan bukan pokok.
  3. Pokok merentang bagi 10 bucu memerlukan 9 tepi dan mesti kekal tersambung.
  4. Tepi untuk dibuang = 15 − 9 = 6, dengan mengambil satu tepi daripada setiap kitar tanpa memutuskan rangkaian.

Contoh berjawab 4

Sebuah graf mempunyai 7 bucu dan 15 tepi. Enam daripada bucu itu masing-masing berdarjah 4.

Cari darjah bucu ketujuh.

  1. Hasil tambah semua darjah = 2 × bilangan tepi = 2 × 15 = 30.
  2. Enam bucu yang diketahui menyumbang 6 × 4 = 24.
  3. Darjah bucu ketujuh = 30 − 24 = 6.

Contoh berjawab 5

Rangkaian berpemberat menunjukkan jarak berjalan kaki, dalam meter, antara asrama H dan perpustakaan L melalui simpang A, B dan C: H–A = 120, H–B = 100, A–C = 90, B–C = 150, C–L = 80, B–L = 260. Cari jarak terpendek dari H ke L dan nyatakan laluannya.

  1. Senaraikan laluan yang mungkin dari H ke L dan tambah jaraknya.
  2. H–A–C–L = 120 + 90 + 80 = 290.
  3. H–B–C–L = 100 + 150 + 80 = 330.
  4. H–B–L = 100 + 260 = 360.
  5. Jumlah terkecil ialah 290, melalui H–A–C–L.

Contoh berjawab 6

Sebuah pokok mempunyai 8 bucu. Satu bucu berdarjah 3 dan empat bucu masing-masing berdarjah 2.

Bucu yang tinggal ialah daun (darjah 1). Cari bilangan daun.

  1. Pokok dengan 8 bucu mempunyai 8 − 1 = 7 tepi, jadi hasil tambah darjah = 2 × 7 = 14.
  2. Bucu yang diketahui menyumbang 3 + (4 × 2) = 3 + 8 = 11.
  3. Daun bersama-sama menyumbang 14 − 11 = 3 kepada hasil tambah darjah.
  4. Setiap daun berdarjah 1, jadi bilangan daun = 3 ÷ 1 = 3.

Contoh berjawab 7

Satu rangkaian komputer menyambungkan pelayan X kepada klien C melalui nod Y, Z dan penghala R. Masa penghantaran, dalam ms, ialah X–Y = 5, X–R = 9, Y–R = 3, Y–Z = 8, R–Z = 2, R–C = 10 dan Z–C = 4.

Cari jumlah masa penghantaran terpendek dari X ke C dan nyatakan lalurannya.

  1. Senaraikan laluan yang mungkin dan jumlah masanya:
  2. X–Y–R–C = 5 + 3 + 10 = 18
  3. X–Y–Z–C = 5 + 8 + 4 = 17
  4. X–Y–R–Z–C = 5 + 3 + 2 + 4 = 14
  5. X–R–Z–C = 9 + 2 + 4 = 15
  6. Jumlah paling kecil ialah 14, melalui X–Y–R–Z–C

Contoh berjawab 8

Satu graf terhubung mempunyai 9 bucu. Enam bucu masing-masing berdarjah 3, dua bucu masing-masing berdarjah 4, dan bucu yang selebihnya berdarjah 2.

Cari jumlah bilangan tepi dalam graf itu.

  1. Hasil tambah darjah = 6(3) + 2(4) + 1(2)
  2. Hasil tambah darjah = 18 + 8 + 2 = 28
  3. Bilangan tepi = hasil tambah darjah ÷ 2
  4. Bilangan tepi = 28 ÷ 2 = 14

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

Bagaimana saya patut mendekati soalan tahap sederhana teori graf tentang pokok dan subgraf?

Soalan sederhana biasanya meminta anda mengenal pasti atau melukis pokok (graf bersambung tanpa gelung) atau subgraf dalam rangkaian yang lebih besar, kadangkala dengan pemberat sisi. Bekerja secara sistematik: senaraikan semua bucu dan sisi dahulu, kemudian semak gambar rajah anda tiada gelung tertutup untuk pokok, dan setiap sisi yang dikekalkan turut wujud dalam rangkaian asal untuk subgraf.

Apakah perangkap biasa apabila mengendalikan sisi berpemberat dalam soalan-soalan ini?

Pelajar kadangkala menjumlahkan semua pemberat sisi dalam keseluruhan rangkaian, bukannya hanya sisi yang tergolong dalam pokok atau subgraf yang diminta. Sebelum menjumlahkan, bulatkan dengan tepat sisi mana yang dikehendaki soalan, jumlah jarak, laluan penyambung minimum, atau laluan tertentu, kerana memasukkan satu sisi tambahan sahaja mengubah keseluruhan jawapan.

Berapa banyak kerja kira perlu ditunjukkan untuk soalan teori graf tahap sederhana?

Tunjukkan gambar rajah akhir dilabel dengan jelas, ditambah sebarang jumlah (seperti jumlah pemberat) ditulis pada baris berasingan, bukan tersembunyi dalam lukisan. Jika anda mencuba lebih daripada satu pokok atau laluan yang mungkin, pastikan hanya percubaan akhir yang betul kelihatan bersih dan jelas, pemeriksa memberi markah kepada jawapan berlabel, bukan lakaran kasar yang berselerak.

Tempah Kelas Percubaan

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