NOTA MATEMATIK TINGKATAN 4 BAB 5

NOTA MATEMATIK TINGKATAN 4 BAB 5

Nota Matematik Tingkatan 4 – Bab 5
Matematik Tingkatan 4 KSSM

BAB 5: RANGKAIAN DALAM TEORI GRAF

Mengkaji Hubungan dan Kaitan antara Objek

Σ d(v) = 2E

Elemen Sebuah Graf

Graf ditandakan sebagai G = (V, E). Suatu rangkaian merupakan graf yang mempunyai sekurang-kurangnya sepasang bintik yang dikaitkan dengan satu garis.

Bucu (Vertex)

Bintik yang mewakili objek (seperti bandar, stesen, atau orang).

V = Set Bucu
Contoh: V = {1, 2, 3}
n(V) = Bilangan Bucu

Tepi (Edge)

Garis yang mengaitkan (menyambungkan) dua bucu.

E = Set Tepi
Contoh: E = {(1,2), (2,3)}
n(E) = Bilangan Tepi

Darjah (Degree)

Bilangan tepi yang mengaitkan sesuatu bucu dengan bucu yang lain.

Rumus Jumlah Darjah:
Σ d(v) = 2E
Jumlah darjah = 2 × Bilangan Tepi

Sifat-Sifat Graf

Bentuk dan ciri graf bergantung kepada cara tepi menyambungkan bucu-bucu.

Graf Mudah

  • Tiada gelung.
  • Tiada berbilang tepi.
  • Setiap pasangan bucu disambung oleh maksimum satu garis.

Berbilang Tepi

Melibatkan dua bucu yang dikaitkan dengan lebih daripada satu tepi. Darjah bagi kedua-dua bucu bertambah.

Gelung (Loop)

Tepi yang berbentuk lengkung berbalik kepada bucu yang sama.

1 Gelung menyumbang = 2 Darjah
Kategori Rangkaian Lanjutan

Arah & Pemberat

Graf Terarah

Graf yang sisinya (tepi) mempunyai arah yang diwakili oleh anak panah. Laluan sah hanya mengikut arah panah.

A
B
  • Pasangan (A, B) ≠ (B, A).
  • Darjah Masuk, din(v) : Bilangan panah menuju bucu.
  • Darjah Keluar, dout(v) : Bilangan panah keluar bucu.

Graf Berpemberat

Graf yang setiap tepinya diletakkan suatu nilai atau pemberat. Sangat berguna untuk mengira kos terendah atau masa terpantas.

5 km
Nilai pemberat boleh mewakili:
Jarak (km) Masa (minit) Kos (RM)

Subgraf & Pokok

Pokok adalah salah satu aplikasi teori graf yang paling penting dalam sains komputer (hierarki data).

Subgraf

Subgraf ialah sebahagian atau keseluruhan daripada graf asal.

Ciri-ciri Subgraf:
  • Mesti dibentuk menggunakan bucu dan tepi yang SAH dari graf asal.
  • Kedudukan asal bucu dan tepi tidak boleh diubah.
  • Graf asal juga adalah subgraf kepada dirinya sendiri.

Pokok (Tree)

Pokok ialah suatu graf mudah yang semua bucunya berkait (tersambung), TETAPI tidak mempunyai kitaran (tiada laluan bergelung/tertutup).

Syarat Mutlak Pokok:
  • Graf Mesti Berkait.
  • Tiada Kitaran, Tiada Gelung, Tiada Berbilang Tepi.
Bilangan Tepi = Bilangan Bucu − 1
E = V − 1

Nota Padat Matematik KSSM

LUBUKSOALAN

Kuiz Matematik Tingkatan 4 – Rangkaian dalam Teori Graf
d(v)

Rangkaian Teori Graf

Matematik Tingkatan 4 (Bab 5)

Uji kefahaman anda tentang konsep Bucu, Tepi, Darjah, Subgraf dan Pokok. Adakah anda bersedia untuk menyambungkan semua titik pengetahuan ini?

  • 10 Persoalan Titik & Garisan (Sistem Rawak)
  • Pilihan Jawapan Rangkaian Dirombak
  • Huraian Fakta Teori Disediakan