Rangkaian dalam Teori Graf · Tingkatan 4
Rangkaian dalam Teori Graf: Contoh Berjawab (Lebih Mudah)
Membaca rangkaian dengan menamakan bucu dan tepinya, mengira darjah setiap bucu, dan menggunakan peraturan bahawa jumlah darjah ialah dua kali bilangan tepi. Sesuai untuk murid yang baru mengenali istilah teori graf.
Contoh berjawab 1
Sebuah graf mempunyai bucu A, B, C, D dan E. Tepinya ialah AB, AC, AD, BC dan CE.
Nyatakan bilangan bucu dan tepi, tuliskan darjah setiap bucu, dan sahkan bahawa jumlah darjah sama dengan dua kali bilangan tepi.
- Bilang bucu: A, B, C, D, E, jadi terdapat 5 bucu.
- Bilang tepi yang disenaraikan: AB, AC, AD, BC, CE, jadi terdapat 5 tepi.
- Darjah A = tepi yang bertemu di A = AB, AC, AD → 3.
- Darjah B = AB, BC → 2; darjah C = AC, BC, CE → 3.
- Darjah D = AD → 1; darjah E = CE → 1.
- Jumlah darjah = 3 + 2 + 3 + 1 + 1 = 10, dan 2 × 5 tepi = 10, kedua-duanya sepadan.
Contoh berjawab 2
Sebuah graf berarah mempunyai bucu P, Q, R dan S dengan tepi berarah P→Q, P→R, Q→R, R→S dan S→P. Cari darjah keluar dan darjah masuk bagi setiap bucu, dan nyatakan jumlah tepi berarah.
- Darjah keluar mengira anak panah yang meninggalkan bucu; darjah masuk mengira anak panah yang memasuki bucu.
- P: keluar ke Q dan R → darjah keluar 2; anak panah masuk dari S → darjah masuk 1.
- Q: keluar ke R → darjah keluar 1; anak panah masuk dari P → darjah masuk 1.
- R: keluar ke S → darjah keluar 1; anak panah masuk dari P dan Q → darjah masuk 2.
- S: keluar ke P → darjah keluar 1; anak panah masuk dari R → darjah masuk 1.
- Jumlah tepi berarah = jumlah darjah keluar = 2 + 1 + 1 + 1 = 5.
Contoh berjawab 3
Sebuah rangkaian tersambung bagi 9 komputer disambung sebagai pokok, tanpa sebarang gelung kabel. Berapa banyak kabel digunakan?
Terangkan penaakulan anda.
- Pokok ialah graf tersambung yang tidak mengandungi kitar.
- Bagi mana-mana pokok, bilangan tepi = bilangan bucu − 1.
- Di sini bucu ialah 9 komputer itu, jadi v = 9.
- Bilangan kabel = v − 1 = 9 − 1 = 8.
Contoh berjawab 4
Sebuah graf mempunyai lima bucu dengan darjah 3, 3, 2, 2 dan 2. Cari bilangan tepi dalam graf itu.
- Hasil tambah semua darjah sama dengan dua kali bilangan tepi: Σ darjah = 2E.
- Tambah darjah: 3 + 3 + 2 + 2 + 2 = 12.
- Jadi 2E = 12, memberi E = 12 ÷ 2 = 6.
Contoh berjawab 5
Sebuah graf mempunyai 5 bucu, dan setiap bucu disambung kepada setiap bucu lain tepat sekali (graf lengkap). Cari bilangan tepi.
- Dalam graf lengkap setiap bucu bersambung dengan (n − 1) bucu lain, jadi setiap satu berdarjah n − 1 = 4.
- Bilangan tepi = n(n − 1) ÷ 2.
- Gantikan n = 5: 5 × 4 ÷ 2 = 20 ÷ 2 = 10.
Contoh berjawab 6
Dalam satu rangkaian jalan, pekan P disambung terus ke pekan Q, R, S dan T. Pekan Q juga disambung terus ke pekan R.
Tuliskan darjah bagi P dan darjah bagi Q.
- Darjah bucu ialah bilangan tepi yang bertemu padanya.
- P disambung ke Q, R, S dan T, itu 4 tepi, jadi darjah P = 4.
- Q disambung ke P dan R, itu 2 tepi, jadi darjah Q = 2.
Contoh berjawab 7
Satu rangkaian mempunyai satu hab pusat H yang disambung terus kepada empat titik W, X, Y dan Z, tanpa sebarang sambungan lain. Nyatakan darjah H dan darjah setiap satu W, X, Y dan Z.
- H disambung kepada W, X, Y dan Z, maka darjah H = 4
- Setiap satu W, X, Y, Z hanya disambung kepada H, maka darjah setiap satu ialah 1
Contoh berjawab 8
Satu graf mempunyai 7 tepi. Cari hasil tambah darjah semua bucunya.
- Hasil tambah darjah = 2 × bilangan tepi
- Hasil tambah darjah = 2 × 7
- Hasil tambah darjah = 14
Sumber:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
Soalan lazim
Apakah kemahiran yang diuji dalam soalan mudah rangkaian (teori graf)?
Pada tahap mudah, soalan menguji sama ada anda boleh membaca gambar rajah rangkaian dengan betul, mengira bilangan bucu, sisi, dan darjah sesuatu bucu, atau melengkapkan gambar rajah ringkas daripada penerangan. Pengiraan yang terlibat sedikit; ketepatan datang daripada mengira dengan teliti dan memahami bahawa darjah bucu ialah bilangan sisi yang bersambung dengannya.
Bagaimana saya boleh mengelakkan kesilapan mengira ceroboh dalam gambar rajah rangkaian mudah?
Labelkan setiap bucu dengan huruf dan tandakan setiap sisi semasa anda mengiranya, bukan sekadar mengimbas gambar rajah dengan mata. Untuk darjah, kesan setiap sisi yang menyentuh bucu satu demi satu, gelung pada satu bucu dikira dua kali terhadap darjahnya, satu perincian yang sering terlepas pandang oleh pelajar pada percubaan pertama.
Mengapakah melukis gambar rajah rangkaian dengan kemas penting walaupun pada tahap mudah?
Gambar rajah yang sesak atau bertindih memudahkan anda tersalah kira sisi atau meletakkan bucu di tempat salah, dan pemeriksa juga perlu melihat gambar rajah anda dengan jelas untuk memberi markah. Renggangkan bucu, gunakan garis lurus jika boleh, dan labelkan setiap bucu, gambar rajah yang kemas melindungi markah yang boleh hilang secara senyap akibat kerja tergesa-gesa.