Langkau ke kandungan
Matematik · Tingkatan 4 (SPM) · 5.0 RANGKAIAN DALAM TEORI GRAF

5.1 Rangkaian

Anda akan mengenal rangkaian sebagai graf, membanding jenis graf, mengenal subgraf dan pokok, mewakilkan maklumat dalam rangkaian serta menyelesaikan masalah.

  • KSSM
  • 5 SP
  • 16 latihan
  • Percuma
Belajar & latih secara interaktifSemua unit Matematik Tingkatan 4

SP 5.1.1Mengenal dan menerangkan rangkaian sebagai graf.

Huraian SPApa yang perlu dikuasai

Untuk guru: kata tugas Mengenal

Murid mengenal rangkaian sebagai graf dan menerangkan istilah graf, rangkaian, bucu, tepi, darjah, graf mudah, gelung dan tepi berbilang dalam situasi sebenar.

  1. IsiGraf dan rangkaian
    Huraian

    Graf ialah siri bintik (bucu) yang berkait atau tidak melalui garis (tepi); rangkaian ialah graf dengan sekurang-kurangnya sepasang bucu berkait.

    Contoh

    Bandar sebagai bucu dan jalan raya sebagai tepi membentuk rangkaian jalan raya.

  2. IsiDarjah, gelung, graf mudah
    Huraian

    Darjah = bilangan tepi pada bucu (gelung dikira 2); ∑darjah = 2 × bilangan tepi; graf mudah tiada gelung dan tiada tepi berbilang.

    Contoh

    Graf 4 bucu dan 5 tepi: ∑darjah = 10.

IstilahIstilah rangkaian

Graf
Suatu siri bintik (bucu) sama ada berkait atau tidak antara satu sama lain melalui garis (tepi)
Rangkaian
Graf yang mempunyai sekurang-kurangnya sepasang bintik berkait
Bucu
Titik dalam graf
Tepi
Garis yang menghubungkan dua bucu
Darjah bucu
Bilangan tepi yang bertemu pada bucu itu; gelung dikira 2
Gelung
Tepi yang bermula dan berakhir pada bucu yang sama
Graf mudah
Graf tak terarah tanpa gelung dan tanpa tepi berbilang
Tepi berbilang
Dua atau lebih tepi yang menghubungkan pasangan bucu yang sama
SP 5.1.1

NotaRumus darjah

Hasil tambah darjah semua bucu dalam suatu graf = 2 × bilangan tepi, iaitu ∑d(v) = 2E. Contoh: graf dengan 5 tepi mempunyai hasil tambah darjah 10. Rangkaian ialah graf yang mewakili hubungan, seperti jalan raya antara bandar atau hubungan rakan.

SP 5.1.1

SP 5.1.2Membanding beza (i) Graf terarah dengan graf tak terarah.
  1. Membanding beza (ii) Graf berpemberat dengan graf tak berpemberat.

Huraian SPApa yang perlu dikuasai

Untuk guru: kata tugas Membanding

Murid membanding beza (i) graf terarah dengan tak terarah dan (ii) graf berpemberat dengan tak berpemberat, termasuk kelebihan dan kekurangan rangkaian pengangkutan berbanding peta serta masalah kos optimum (masa, jarak, perbelanjaan).

  1. Isi(i) Terarah dan tak terarah
    Huraian

    Graf terarah mempunyai anak panah (hubungan sehala); tak terarah hubungan dua hala.

    Contoh

    Pengikut media sosial sehala: terarah; rakan sekelas: tak terarah.

  2. Isi(ii) Berpemberat dan tak berpemberat
    Huraian

    Graf berpemberat ada nilai pada tepi (jarak, masa, kos) dan sesuai mencari kos optimum; tak berpemberat hanya menunjukkan hubungan.

    Contoh

    Rangkaian LRT dengan tambang pada setiap tepi ialah graf berpemberat.

  3. IsiRangkaian pengangkutan dan peta
    Huraian

    Rangkaian ringkas dan mudah dibaca untuk laluan, tetapi tidak menunjukkan kedudukan dan jarak sebenar seperti peta.

    Contoh

    Peta LRT memudahkan pertukaran laluan tetapi jarak antara stesen tidak berskala.

Peta buih bergandaGraf terarah dan graf tak terarah

Graf terarahTepi mempunyai arah (anak panah)Ditulis sebagai pasangan tertib (A, B)Contoh: aliran trafik sehala
PersamaanTerdiri daripada bucu dan tepi
Graf tak terarahTepi tiada arahHubungan dua halaContoh: rangkaian rakan Facebook
SP 5.1.2

Peta buih bergandaGraf berpemberat dan graf tak berpemberat

Graf berpemberatSetiap tepi diberi nilai (jarak, masa, kos)Digunakan untuk mencari laluan terpendek atau termurah
PersamaanTerdiri daripada bucu dan tepi
Graf tak berpemberatTepi tiada nilaiHanya menunjukkan hubungan
SP 5.1.2

SP 5.1.3Mengenal dan melukis subgraf dan pokok.

Huraian SPApa yang perlu dikuasai

Untuk guru: kata tugas Mengenal

Murid mengenal dan melukis subgraf (sebahagian bucu dan tepi graf asal) serta pokok (graf terhubung tanpa kitaran, tepi = bucu − 1).

  1. IsiSubgraf
    Huraian

    Pilih sebahagian bucu dan tepi; setiap tepi mesti menghubungkan bucu dalam subgraf.

    Contoh

    Daripada graf A, B, C, D, subgraf A-B-C dengan tepi AB dan BC.

  2. IsiPokok
    Huraian

    Terhubung, tiada kitaran, tiada gelung; bilangan tepi = bilangan bucu − 1.

    Contoh

    Pokok 6 bucu mempunyai 5 tepi.

Peta pokokSubgraf dan pokok

Graf G
Subgraf
  • Graf yang bucu dan tepinya ialah sebahagian daripada bucu dan tepi G
  • Setiap tepi subgraf mesti menghubungkan bucu dalam subgraf itu
Pokok
  • Graf terhubung tanpa kitaran
  • Tiada gelung dan tiada tepi berbilang
  • Bilangan tepi = bilangan bucu − 1
SP 5.1.3

SP 5.1.4Mewakilkan maklumat dalam bentuk rangkaian.

Huraian SPApa yang perlu dikuasai

Untuk guru: kata tugas Mewakilkan

Murid mewakilkan maklumat situasi (pengangkutan, sosial, aliran) dalam bentuk rangkaian dengan bucu, tepi, arah dan pemberat yang sesuai.

  1. IsiKenal pasti bucu dan tepi
    Huraian

    Objek menjadi bucu; hubungan menjadi tepi.

    Contoh

    Lima rakan dan siapa mengenali siapa.

  2. IsiTambah arah dan pemberat
    Huraian

    Gunakan anak panah bagi hubungan sehala dan nilai bagi jarak/masa/kos.

    Contoh

    Jadual bas: A ke B 20 minit, B ke C 15 minit.

Peta alirContoh: mewakilkan maklumat dan mencari laluan terpendek

  1. Maklumat: jalan P ke Q 5 km, Q ke R 4 km, P ke R 11 km, R ke S 3 km.
  2. Lukis bucu P, Q, R, S dan sambungkan dengan tepi berlabel jarak (graf berpemberat).
  3. Senaraikan laluan P ke S: P-Q-R-S = 5 + 4 + 3 = 12 km; P-R-S = 11 + 3 = 14 km.
  4. Laluan terpendek: P-Q-R-S, 12 km.
SP 5.1.4SP 5.1.5

SP 5.1.5Menyelesaikan masalah yang melibatkan rangkaian.

Huraian SPApa yang perlu dikuasai

Untuk guru: kata tugas Menyelesaikan

Murid menyelesaikan masalah rangkaian termasuk laluan dengan kos optimum (jarak terpendek, masa tersingkat, perbelanjaan terendah).

  1. IsiSenaraikan laluan
    Huraian

    Senaraikan semua laluan dari bucu mula ke bucu akhir dan jumlahkan pemberat.

    Contoh

    P-Q-R-S = 12 km, P-R-S = 14 km.

  2. IsiPilih kriteria
    Huraian

    Pilih laluan mengikut kriteria yang dikehendaki (jarak, masa atau kos).

    Contoh

    Laluan lebih panjang tetapi lebih cepat dipilih untuk penghantaran segera.

Ingat: mnemonik & kad imbas

Mnemonik

BTD
Bucu, Tepi, Darjah: tiga unsur asas yang dikenal pasti dalam setiap graf.

Kad imbas

∑ darjah
2 × bilangan tepi
Darjah gelung
Dikira 2
Graf terarah
Tepi mempunyai arah
Graf berpemberat
Tepi diberi nilai seperti jarak atau kos
Pokok
Graf terhubung tanpa kitaran; tepi = bucu − 1

Semak kefahaman

  1. Sebuah graf mempunyai 5 bucu dan 6 tepi. Hitung hasil tambah darjah semua bucu. (SP 5.1.1)

    Lihat jawapan

    ∑darjah = 2 × bilangan tepi = 2 × 6 = 12.

  2. Berikan satu contoh situasi yang sesuai diwakili oleh graf terarah. (SP 5.1.2)

    Lihat jawapan

    Contohnya rangkaian jalan sehala, kerana pergerakan hanya dalam satu arah.

  3. Hitung bilangan tepi bagi pokok yang mempunyai 10 bucu. (SP 5.1.3)

    Lihat jawapan

    Bilangan tepi = 10 − 1 = 9.

  4. Lima stesen A, B, C, D dan E bersambung secara berturutan dalam satu laluan. Nyatakan bilangan tepi rangkaian itu. (SP 5.1.4)

    Lihat jawapan

    Tepi AB, BC, CD dan DE, maka 4 tepi.

  5. Dengan jarak P-Q 7 km, Q-R 3 km dan R-S 9 km, hitung jarak laluan P-Q-R-S. (SP 5.1.5)

    Lihat jawapan

    7 + 3 + 9 = 19 km.

16 soalan latihan pelbagai aras, kad imbas dan Kad Tahniah ada dalam mod interaktif.

Tahap Penguasaan (TP)

TPTafsiran
TP1Mempamerkan pengetahuan asas tentang rangkaian.
TP2Mempamerkan kefahaman tentang rangkaian.
TP3Mengaplikasikan kefahaman tentang rangkaian untuk melaksanakan tugasan mudah.
TP4Mengaplikasikan pengetahuan dan kemahiran yang sesuai tentang rangkaian dalam konteks penyelesaian masalah rutin yang mudah.
TP5Mengaplikasikan pengetahuan dan kemahiran yang sesuai tentang rangkaian dalam konteks penyelesaian masalah rutin yang kompleks.
TP6Mengaplikasikan pengetahuan dan kemahiran yang sesuai tentang rangkaian dalam konteks penyelesaian masalah bukan rutin secara kreatif.
Untuk guru: cadangan aktiviti mencapai TP (6)
  1. TP1

    Mempamerkan pengetahuan asas tentang rangkaian.

    Aktiviti: Murid menyambung titik pada kertas dengan garis untuk membina rangkaian rakan sekelas yang dihubungkan, dan menyebut maksud bucu dan tepi, secara berpasangan.

    Evidens PBD: Rangkaian yang dilukis dan sebutan istilah.

    SP disasar: 5.1.1 · Latihan sepadan: aras Mengingat
  2. TP2

    Mempamerkan kefahaman tentang rangkaian.

    Aktiviti: Murid membezakan graf terarah dan tak terarah, graf berpemberat dan tak berpemberat daripada contoh peta laluan dan jalan raya dalam jadual.

    Evidens PBD: Jadual pengelasan yang betul.

    SP disasar: 5.1.2 · Latihan sepadan: aras Memahami
  3. TP3

    Mengaplikasikan kefahaman tentang rangkaian untuk melaksanakan tugasan mudah.

    Aktiviti: Murid melukis subgraf dan pokok daripada sebuah rangkaian dan menyatakan ciri pokok iaitu tiada gelung, dalam lembaran kerja.

    Evidens PBD: Lukisan subgraf dan pokok.

    SP disasar: 5.1.3 · Latihan sepadan: aras Mengaplikasi
  4. TP4

    Mengaplikasikan pengetahuan dan kemahiran yang sesuai tentang rangkaian dalam konteks penyelesaian masalah rutin yang mudah.

    Aktiviti: Murid mewakilkan maklumat pemetaan jarak antara lima tempat sebagai graf berpemberat dengan bucu dan tepi berlabel.

    Evidens PBD: Rangkaian yang dilukis dengan betul.

    SP disasar: 5.1.4 · Latihan sepadan: aras Menganalisis
  5. TP5

    Mengaplikasikan pengetahuan dan kemahiran yang sesuai tentang rangkaian dalam konteks penyelesaian masalah rutin yang kompleks.

    Aktiviti: Murid menyelesaikan masalah mencari laluan terpendek antara dua tempat daripada rangkaian berpemberat dan menjustifikasikan pilihan laluan.

    Evidens PBD: Penyelesaian dan justifikasi laluan.

    SP disasar: 5.1.5 · Latihan sepadan: aras Menilai dan Menghayati
  6. TP6

    Mengaplikasikan pengetahuan dan kemahiran yang sesuai tentang rangkaian dalam konteks penyelesaian masalah bukan rutin secara kreatif.

    Aktiviti: Murid mereka rangkaian jalan raya untuk taman permainan atau kampung hasil rekaan sendiri, menyelesaikan masalah laluan terpendek dan pokok pembinaan paling murah, dan membentangkan.

    Evidens PBD: Rangkaian dan penyelesaian hasil murid.

    SP disasar: 5.1.5 · Latihan sepadan: aras Mencipta

Cadangan sahaja; TP rasmi ditentukan guru melalui pertimbangan profesional (PBD). Buka unit dan latihan

Siapkan unit ini dalam mod interaktif untuk mendapat bintang, anggaran TP dan Kad Tahniah. Siapkan semua 19 unit Matematik Tingkatan 4 untuk Sijil Penghargaan SistemGuru.My.

Belajar & latih secara interaktifSemua unit Matematik Tingkatan 4

Unit lain dalam 5.0 RANGKAIAN DALAM TEORI GRAF

  1. 5.1 Rangkaian