Matematik notesnota, bab 5

Rangkaian dalam Teori Graf

Notes made with reference toNota dibuat dengan rujukan kepada TextbookBuku teks Matematik Tingkatan 4 (KSSM), pageshalaman 128-153

What this chapter coversMatlamat bab ini

Saya boleh mengenal dan menerangkan rangkaian sebagai graf, termasuk bucu, tepi, darjah, graf mudah, gelung dan berbilang tepi (5.1.1)
Saya boleh membandingkan beza antara graf terarah dengan graf tak terarah (5.1.2)
Saya boleh membandingkan beza antara graf berpemberat dengan graf tak berpemberat (5.1.2)
Saya boleh mengenal dan melukis subgraf dan pokok, termasuk pokok dengan jumlah pemberat minimum (5.1.3)
Saya boleh mewakilkan maklumat dalam bentuk rangkaian (5.1.4)
Saya boleh menyelesaikan masalah yang melibatkan rangkaian (5.1.5)

5.1Rangkaian

Rangkaian sebagai graf (5.1.1)

Graf ialah suatu siri bintik yang disambungkan dengan garis. Bintik dikenali sebagai bucu dan garis yang mengaitkan dua bucu ialah tepi. Rangkaian ialah sebahagian daripada graf dengan keadaan bucu dan tepi mempunyai sifat tersendiri, misalnya hubungan banyak kepada banyak.

Rangkaian	Bucu	Tepi
Pengangkutan darat	Kawasan, pekan, bandar atau sesuatu bangunan yang dikaitkan	Jalan raya, lebuh raya atau landasan kereta api
Sosial	Individu, kumpulan atau organisasi	Jenis hubungan seperti kawan, rakan sekerja atau keluarga

Graf ditulis dalam bentuk set pasangan tertib G = (V, E). V ialah set bucu, V = {v₁, v₂, ... v_n}. E ialah set tepi, E = {(a₁, b₁), (a₂, b₂), ...}, dengan a dan b ialah pasangan bucu. Dalam graf tak terarah, tepi (1, 2) sama dengan tepi (2, 1).

Darjah, d(v), bagi suatu bucu ialah bilangan tepi yang mengaitkannya dengan bucu lain. Jumlah darjah suatu graf ialah dua kali bilangan tepi: Σd(v) = 2E, v ∈ V.

Graf mudah ialah graf yang tidak mengandungi gelung atau berbilang tepi. Gelung melibatkan satu bucu sahaja: tepi berbentuk lengkung yang berbalik kepada bucu asal. Berbilang tepi melibatkan dua bucu yang dikaitkan melalui lebih daripada satu tepi.

Graf mudah dengan enam bucu bernombor 1 hingga 6 dan tujuh tepi — Contoh 1 (buku teks m.s. 131). V = {1, 2, 3, 4, 5, 6}, n(V) = 6. E = {(1, 2), (1, 5), (2, 3), (2, 4), (3, 4), (4, 5), (5, 6)}, n(E) = 7.

Darjah: d(1) = 2, d(2) = 3, d(3) = 2, d(4) = 3, d(5) = 3, d(6) = 1. Jumlah = 14 = 2 × 7.

Contoh 2 (m.s. 131 dan 132): bucu, tepi dan darjah

(a) Bucu = 7, tepi = 7. Darjah = 2 × tepi = 2 × 7 = 14.
(b) Bucu = 7, tepi = 9. Darjah = 2 × tepi = 2 × 9 = 18.

Graf dengan enam bucu P hingga U, gelung pada S dan dua tepi antara P dengan U — Contoh 3 (m.s. 132). Gelung (S, S); berbilang tepi (P, U) dua kali. n(E) = 10, jadi jumlah darjah = 20. d(S) = 4 kerana gelung menyumbang 2.

Bilangan darjah bagi setiap gelung ialah dua, iaitu pusingan mengikut arah jam dan pusingan lawan arah jam. Pasangan bucu gelung berbentuk (a, a); pasangan bucu berbilang tepi berbentuk (a, b) yang ditulis lebih daripada sekali.

Contoh 5 (m.s. 133): membaca graf daripada V dan E

V = {P, Q, R, S}, E = {(P, P), (P, Q), (P, S), (Q, S), (Q, S), (Q, R), (S, R), (R, R)}.
(P, P) dan (R, R) ialah gelung; (Q, S) muncul dua kali, jadi ia berbilang tepi. n(E) = 8, maka jumlah darjah = 16.
Semak: d(P) = 2 + 1 + 1 = 4, d(Q) = 1 + 2 + 1 = 4, d(S) = 1 + 2 + 1 = 4, d(R) = 1 + 1 + 2 = 4. Jumlah = 16.

Contoh 6 (m.s. 133): bolehkah graf dilukis?

(a) 3, 2, 2, 1, 3: jumlah = 11 (ganjil), maka graf tidak boleh dilukis.
(b) 2, 1, 1, 3, 3, 2: jumlah = 12 (genap), maka graf boleh dilukis.

Mengira gelung sebagai 1 apabila mencari darjah. Gelung keluar dari bucu dan kembali ke bucu itu juga, jadi ia menyumbang 2. Jumlah darjah mesti genap.

Suatu graf mempunyai 9 tepi. Apakah jumlah darjahnya? Bolehkah graf dilukis dengan darjah bucu 4, 3, 3, 2, 2?

Tunjuk jawapanSembunyi jawapan

Jumlah darjah = 2 × 9 = 18.
4 + 3 + 3 + 2 + 2 = 14, iaitu genap, maka graf boleh dilukis (7 tepi).

Graf terarah dan tak terarah, berpemberat dan tak berpemberat (5.1.2)

Graf terarah ialah graf dengan tepi yang mengaitkan dua bucu ditanda dengan arah kaitan. Bagi tepi AB, bucu A ialah bucu awal dan bucu B ialah bucu akhir. Graf tak terarah ialah graf yang dilukis tanpa penandaan arah pada tepi.

	Graf tak terarah	Graf terarah
Penulisan pasangan bucu	Kedudukan bebas: (A, B) atau (B, A) mewakili tepi AB.	Mengikut arah: (A, B) dan (B, A) mewakili tepi yang berlainan.
Darjah	d(v) = bilangan tepi pada v	d(v) = d_in(v) + d_out(v)

Graf tak terarah dengan bucu A, B, C dan D — Tak terarah: d(A) = 2, d(B) = 2, d(C) = 3, d(D) = 1. Σd(V) = 8.

Graf terarah dengan tepi BA, CA, BC dan DC — Terarah: d_in(A) = 2, d_out(A) = 0, maka d(A) = 2. Σd(V) = 8 juga.

d_in(A) ialah bilangan darjah bagi tepi yang masuk ke bucu A. d_out(A) ialah bilangan darjah bagi tepi yang keluar dari bucu A. Gelung dikira satu masuk dan satu keluar.

Bucu yang wujud dalam set V tetapi tidak dalam set E tidak berkaitan dengan bucu lain dan dikenali sebagai bucu terpencil (Contoh 7, m.s. 137).

Contoh 7(a) (m.s. 137): melukis graf terarah daripada E

E = {(P, Q), (P, R), (R, Q), (S, R), (S, Q), (S, T)}: P ke Q dan P ke R (dua tepi keluar dari P); R ke Q; S ke R, S ke Q dan S ke T (tiga tepi keluar dari S). Bucu T hanya berkaitan dengan bucu S. Bucu U ialah bucu terpencil.

	Graf berpemberat	Graf tak berpemberat
Jenis graf	Terarah dan tak terarah	Terarah dan tak terarah
Tepi	Diberi nilai atau pemberat	Tiada nilai atau pemberat yang dinyatakan
Contoh	Jarak di antara dua bandar, masa yang diambil untuk suatu gerakan, nilai arus suatu litar elektrik, kos	Hierarki jawatan dalam carta organisasi, peta alir, peta pokok, peta buih

Graf terarah dan berpemberat dari v1 ke v5 dengan pemberat dalam meter — Contoh 8 (m.s. 138). Laluan sehala latihan larian Izarul, dalam meter. v₁ ialah tempat permulaan dan v₅ tempat terakhir.

Contoh 8 (m.s. 138): v₁ ke v₅

(a) Terpendek: v₁ → v₂ → v₅ = (600 + 500) m = 1 100 m = 1.1 km
(b) Terpanjang: v₁ → v₂ → v₃ → v₄ → v₅ = (600 + 900 + 500 + 500) m = 2 500 m = 2.5 km
(c) Jarak antara 1.4 km dengan 2.1 km: v₁ → v₃ → v₄ → v₅ (1 500 m) dan v₁ → v₂ → v₄ → v₅ (1 900 m).

Dalam graf terarah, laluan hanya boleh mengikut arah anak panah. Senaraikan semua laluan dahulu, kemudian tambah pemberat sepanjang setiap laluan.

Dalam suatu graf terarah, bucu T mempunyai tepi (T, S), (T, P), (T, T) dan (Q, T). Cari d_in(T), d_out(T) dan d(T).

Tunjuk jawapanSembunyi jawapan

d_out(T): (T, S), (T, P), (T, T) = 3
d_in(T): (T, T), (Q, T) = 2
d(T) = 3 + 2 = 5

Subgraf dan pokok (5.1.3)

Subgraf ialah sebahagian atau keseluruhan suatu graf yang dilukis semula. Graf H ialah subgraf kepada graf G jika (a) bucu-bucu H ialah subset kepada bucu-bucu G, V(H) ⊂ V(G); (b) tepi-tepi H ialah subset kepada tepi-tepi G, E(H) ⊂ E(G); (c) pasangan bucu setiap tepi H sama dengan tepi G.

Secara ringkasnya, suatu bucu dalam G ialah subgraf bagi G; suatu tepi dalam G bersama bucu yang dikaitkan ialah subgraf bagi G; setiap graf ialah subgraf kepada dirinya.

Contoh 9 (m.s. 139): adakah ia subgraf bagi G?

Graf G mempunyai tepi e₁ = PQ, e₂ = gelung pada Q, e₃ = QR, e₄ = SR, e₅ = PS.
Rajah 1 (tepi e₅ dengan bucu P, S): ya, kerana pasangan bucu e₅ adalah sama.
Rajah 2: tidak, kedudukan gelung e₂ bukan pada bucu Q.
Rajah 3: tidak, tepi yang mengaitkan P dan S bukan e₃.
Rajah 4: tidak, tepi gelung dan tepi yang mengaitkan bucu Q dan R adalah salah.

Pokok suatu graf ialah subgraf bagi graf tersebut dengan ciri-ciri: (a) graf mudah, iaitu tanpa gelung atau berbilang tepi; (b) semua bucu mesti berkait dan setiap pasangan bucu dikaitkan oleh satu tepi sahaja; (c) bilangan tepi = bilangan bucu − 1. Jika bilangan bucu = n, bilangan tepi = n − 1.

Pokok dengan lima bucu dan empat tepi — Pokok: 5 bucu, 4 tepi, semua bucu berkait.

Graf dengan lima bucu dan lima tepi yang mengandungi laluan tertutup B, C, D — Bukan pokok: 5 bucu, 5 tepi. Bucu B dan D boleh dikaitkan dengan dua cara.

Contoh 10 dan 11 (m.s. 140): mengenal dan melukis pokok

Graf dengan 6 bucu dan 7 tepi bukan pokok kerana setiap pasangan bucu boleh dikaitkan dengan pelbagai cara. Graf dengan 6 bucu dan 5 tepi yang berkait ialah pokok. Graf dengan 6 bucu dan 4 tepi bukan pokok kerana ada bucu yang tidak dikaitkan dengan bucu lain.
Melukis pokok: 6 bucu maka 5 tepi; 8 bucu maka 7 tepi; 4 tepi maka 5 bucu; 9 tepi maka 10 bucu.

Menyangka setiap graf dengan n − 1 tepi ialah pokok. Graf itu juga mesti berkait. Graf dengan 6 bucu dan 4 tepi tidak berkait, jadi ia bukan pokok.

Membina pokok daripada graf (Contoh 12, m.s. 141): graf berkait dengan n bucu dan lebih daripada n − 1 tepi perlu dibuang tepinya, dengan semua bucu masih berkait, sehingga tinggal n − 1 tepi. Contohnya graf dengan 5 bucu dan 7 tepi memerlukan 3 tepi dibuang; graf dengan 6 bucu dan 8 tepi juga memerlukan 3 tepi dibuang.

Pokok digunakan untuk menentukan laluan terpendek dengan syarat semua bucu dilalui hanya sekali.

Graf berpemberat dengan bucu P, Q, R, S, T dan tujuh tepi — Contoh 13 (m.s. 141). 5 bucu dan 7 tepi, maka 3 tepi perlu dibuang.

Contoh 13 (m.s. 141): pokok dengan jumlah pemberat minimum

Langkah 1: Bucu = 5, tepi = 7, jadi 3 tepi dibuang. Keluarkan tepi dengan pemberat tertinggi (PQ = 25, QR = 20, PT = 19). Graf yang tinggal bukan pokok kerana bucu P tidak dikaitkan dengan bucu lain dan tiga tepi RS, ST dan RT hanya mengaitkan tiga bucu.
Langkah 2: Antara pemberat 19 dengan 25, pemberat 19 perlu dikekalkan kerana nilainya lebih rendah. Antara pemberat 12, 14 dengan 17, pemberat 17 perlu dikeluarkan.
Jumlah pemberat minimum pokok = 10 + 12 + 14 + 19 = 55.

Graf yang sama dengan tepi 25, 20 dan 17 dipudarkan dan tepi pokok 10, 12, 14 dan 19 diserlahkan — Tepi 25, 20 dan 17 dibuang. Pemberat pokok: 10 + 12 + 14 + 19 = 55, jumlah minimum.

Pokok mempunyai 12 bucu. Berapakah bilangan tepinya? Graf berkait mempunyai 6 bucu dan 8 tepi; berapakah tepi yang dibuang untuk menjadi pokok?

Tunjuk jawapanSembunyi jawapan

12 − 1 = 11 tepi.
Pokok memerlukan 6 − 1 = 5 tepi, maka 8 − 5 = 3 tepi dibuang.

Mewakilkan maklumat dalam bentuk rangkaian (5.1.4)

Rangkaian ialah satu bentuk graf yang unik dan digunakan untuk mewakilkan maklumat yang bertindih atau bersilang. Rangkaian boleh dilukis sebagai graf terarah dan berpemberat atau graf terarah dan tak berpemberat, atau graf tak terarah dan berpemberat atau graf tak terarah dan tak berpemberat.

Rangkaian pengangkutan: bucu mewakili nama stesen atau bandar dan tepi mewakili jenis keretapi atau jalan. Pemberat boleh mewakili jarak, masa perjalanan atau kos perjalanan (Sistem Kedudukan Global atau GPS menggunakan graf berpemberat).
Rangkaian sosial: digunakan untuk peluang pekerjaan, peluang perniagaan, bersosial, media sosial dan sebagainya. Murid perlu berhati-hati dan bersederhana agar tidak leka, terpedaya atau tertipu.

Contoh 14 (m.s. 143): tiga pilihan laluan ke Melaka

Laluan P berjarak 46.3 km, Q berjarak 50.2 km dan R berjarak 53.3 km. Laluan P ialah yang terpendek, tetapi mengambil jangka masa yang lebih panjang mungkin kerana ia melalui kawasan bandar yang sesak dan bilangan pengguna jalan raya yang lebih banyak. Jarak yang lebih pendek tidak semestinya masa yang lebih singkat.

Contoh 15 (m.s. 144): murid dan permainan

Bucu ialah jenis permainan dan tepi mewakili nama murid. Setiap murid meminati dua permainan, jadi setiap murid ialah satu tepi: Edmund (Badminton, Catur), Azwan (Bola sepak, Sepak takraw), Rajan (Catur, Bola sepak), Aina (Catur, Bola jaring), Maria (Badminton, Bola jaring), Jenny (Bola jaring, Bola tampar).
Semak: 6 tepi, maka jumlah darjah = 12. Darjah: Catur 3, Bola jaring 3, Badminton 2, Bola sepak 2, Sepak takraw 1, Bola tampar 1. Jumlah = 12.

Pilih maklumat yang tidak bersilang sebagai tepi.

Peta konsep Rangkaian dalam Teori Graf: graf mudah, graf mempunyai gelung dan berbilang tepi, darjah, graf terarah, graf tak terarah, subgraf, graf berpemberat, graf tak berpemberat dan pokok — Peta konsep Bab 5.

Menyelesaikan masalah yang melibatkan rangkaian (5.1.5)

Senaraikan semua pilihan laluan atau pilihan yang ada.
Tambah atau banding pemberat (kos, masa, jarak) bagi setiap pilihan.
Semak syarat dalam soalan (paling murah, paling cepat, melalui bucu tertentu).
Beri justifikasi, misalnya kos, masa, keselesaan dan keselamatan (Contoh 16, m.s. 146).

Contoh 16 (m.s. 146): Johor Bahru ke Kota Bharu

Bas: RM64 hingga RM75, 9 jam. Kereta api dengan kemudahan tempat tidur: kanak-kanak RM32 hingga RM38, dewasa RM49 hingga RM55, 17 jam. Kereta api tanpa kemudahan tempat tidur: kanak-kanak RM26, dewasa RM43. Kereta: RM120 untuk sebuah kereta, 9 jam.
Dua orang dewasa dan dua orang kanak-kanak (harga terendah): bas 4 × 64 = RM256; kereta api dengan tempat tidur 2 × 49 + 2 × 32 = RM162; kereta api tanpa tempat tidur 2 × 43 + 2 × 26 = RM138; kereta RM120. Kereta paling menjimatkan. (Buku teks mencetak RM43 dalam soalan tetapi RM44 dalam penyelesaian; kesimpulan sama.)
Bagi seorang dewasa tanpa kekangan masa, kereta api dengan kemudahan tempat tidur ialah pilihan terbaik kerana hanya beza kira-kira RM5 (RM6 jika RM43) berbanding kereta api tanpa tempat tidur dan lebih murah daripada memandu kereta. Bagi seorang dewasa dengan kekangan masa, bas lebih jimat dan penumpang boleh berehat; memandu jauh seorang diri bukan pilihan bijak dari aspek keselamatan.

Contoh 17 (m.s. 147): penerbangan domestik

Encik Joshua di Kuala Lumpur mahu ke Kota Kinabalu. Pilihan terbaik: penerbangan terus Kuala Lumpur ke Kota Kinabalu, atau Kuala Lumpur ke Labuan dan seterusnya ke Kota Kinabalu. Penerbangan terus menjimatkan masa dan kos; melalui Labuan mengambil masa lebih panjang dan mungkin kos lebih tinggi.

Praktis Kendiri 5.1e no. 1 (m.s. 147): Johor Bahru ke Miri

Hari Sabtu: terus Johor Bahru ke Miri RM259.30. Melalui Kuching: JB ke Kuching jam 0605 RM174.30, kemudian Kuching ke Miri jam 1145 RM64.00. Jumlah = 174.30 + 64.00 = RM238.30, paling murah.
Hari Jumaat (kerja tamat 12:30): JB ke Kuching jam 1930 RM124.30 dan Kuching ke Miri jam 2155 RM149.00 = RM273.30. Beza = 273.30 − 238.30 = RM35.00; masa bersama keluarga lebih lama.

Tiket bas RM42 seorang dewasa dan tiket kereta api RM28. Sebuah kereta RM90 untuk 4 orang. Manakah paling murah untuk 4 orang dewasa?

Tunjuk jawapanSembunyi jawapan

Bas 4 × 42 = RM168; kereta api 4 × 28 = RM112; kereta RM90. Kereta paling murah.