Soalan 4 / Question 4 Anda menguruskan sebuah syarikat percetakan dan telah menerima pesanan untuk mencetak brosur yang mengandungi peta Malaysia. Pelanggan telah meminta agar peta tersebut dicetak seperti gambar di atas di mana negeri-negeri dan wilayah persekutuan diwarnakan dengan 5 warna berbeza. Disebabkan pandemik yang melanda, anda ingin mengurangkan kos pencetakan sebanyak mungkin dan anda tahu ia boleh dilakukan dengan mengurangkan bilangan warna yang digunakan. Tugas anda adalah untuk mewarnakan peta tersebut dengan menggunakan bilangan warna yang paling minima dan memastikan bahawa dua negeri yang bersebelahan diwarnakan dengan warna berbeza. Masalah pewarnaan graf ini adalah masalah klasik di dalam bidang Teori Graf. Anda hanya dikehendaki untuk memikirkan 13 negeri dan tidak perlu untuk menimbangkan pewarnaan Wilayah Persekutuan Putrajaya, Labuan dan Kuala Lumpur. Soalan ini memerlukan pembacaan lanjutan tentang tajuk-tajuk yang tidak dirangkumi dalam pembentangan kuliah (pewarnaan graf, graf mendatar, nombor kromatik dan algoritma tamak). Bagi soalan (b) dan (c), anda dikehendaki untuk hanya menimbangkan peta/graf Malaysia Barat sahaja. You are running a printing company and have received an order to print brochures that contain the map of Malaysia. The customer has initially asked for you to print the map like the figure above where states and federal territories have been coloured using 5 different colours. Because of the pandemic, you would like to reduce the cost of printing as much as you can and you know that can be done by reducing the number of colours used. Your job is to colour the map with as few colours as possible in such a way that two adjacent states are of different colours. This graph colouring problem is a classical problem in the field of Graph Theory. You are only asked to consider the 13 states and ignore the colouring of Putrajaya, Labuan and Kuala Lumpur federal territories. This question requires extra readings on topics not covered in the lecture slides (graph colouring, planar graphs, chromatic number, greedy algorithm). For question (b) and (c), you are required to consider the map/graph of West Malaysia only

Akhir sekali, mari mewarna peta Malaysia yang diwakili oleh graf G1. Tetapi kita perlu terdahulu memperkenalkan definisi nombor kromatik dan Teorem Empat Nombor. Nombor kromatik suatu graf G, k adalah bilangan warna yang paling sedikit yang diperlukan untuk mewarnakan graf ini. Nombor kromatik graf G ditandakan dengan (G). (Di sini adalah abjad Yunani chi.) Teorem Empat Nombor menyatakan bahawa nombor kromatik graf mendatar adalah tidak lebih daripada empat. Menggunakan Algoritma Pewarnaan Tamak, cari (G1). Nyatakan algoritma tersebut (menggunakan perkataan, bukannya bahasa pengaturcaraan seperti Python dan C++) dan nyatakan aturan warna yang anda pilih untuk mewarnakan bucu pada G1 (Anda perlu melukis kembali G1 di sini). Nyatakan juga nombor pada setiap warna yang anda telah gunakan pada G1. Mengapakah kita tidak boleh mewarnakan graf tersebut menggunakan bilangan warna yang kurang daripada (G1)? Adakah algoritma tersebut menjamin bahawa nilai optima (G1) akan sentiasa dijumpai? Finally, lets colour the map of Malaysia represented by graph G1. But first we need to introduce the definitions for the chromatic number and Four Number Theorem. The chromatic number, k of a graph G is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by (G). (Here is the Greek letter chi.) The Four Colour Theorem states that the chromatic number of a planar graph is no greater than four. Using the Greedy Colouring Algorithm find (G1). State the algorithm (In words, not in programming languages such as Python or C++) and indicate the order of which you coloured the vertices on (You need to redraw G1 here). Indicate also the number for each colour that you have used on G1. Why cant we colour the graph using colours less than (G1)? Does the algorithm guarantees of finding optimal (G1) ? (