Pulang Malaysia 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 diwamakan 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 wama yang paling minima dan memastikan bahawa dua negeri yang bersebelahan diwamakan dengan wama berbeza. Masalah pewamaan graf ini adalah masalah klasik di dalam bidang Teori Graf. Anda hanya dikehendaki untuk memikirkan 13 negeri dan tidak perlu untuk menimbangkan pewamaan 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 Nke 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. Draw a graph denoted as G with each of the 13 states represented as a vertex and its boundaries as edges. For simplicity you can represent each state with a number or an alphabet. How many vertices and edges does the graph have? State both elements of set V and E. Is there a path in West Malaysia, where starting from one state, a person can travel and cross all borders only once (But you can visit the same state multiple times)? Similarly is there a path where starting from one state, a person can travel and cross all borders only once and end up in the starting state? Both of these paths have special names, state them with their definitions. If your answer is yes, show the paths in G2. If your answer is No, then can you find subgraphs of G:(V,E) defined as H = (W, 5), where WSV and FSE that has such paths? Show only one of your answers. This question is similar (but different) to the previous one. Is there a path in West Malaysia, where starting from one state, a person can visit all of the states only once? Similarly is there a path where starting from one state, except for the starting state, a person can visit all states only once and return to the starting state? Both of these paths have a special name, state them and their definitions. If your answer is Yes, show the paths. Finally, let's colour the map of Malaysia represented by graph G. 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 x(G). (Here x 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 x(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 G here). Indicate also the number for each colour that you have used on G. Why can't we colour the graph using colours less than x(G)? Does the algorithm guarantees of finding optimal X(G)
