DATA STRUCTURE AND ALGORITHM DESIGN Question

b. Graph Coloring is a process of assigning colors to the vertices of a graph such that no two adjacent vertices of it are assigned the same color. Recently IIUM Student Affairs and Community Engagement Division opened up Mahallat toilet painting competition, only 6 Mahallat are participating in the first round scheduled for 21st December 2020 to 5th January 2021. The constraint is that, No two adjacent Mahallat will be choosing same color for the painting competition. Use FigureQ4b to answer the following question: i. Apply Backtracking strategy to indicate the chromatic number of each Mahallah (2 marks) ii. What is the minimum Color to be used? (2 marks) iii. Assuming Mahallah Hamzah and Faruq could not make it to the next round (taken out of the graph) and we are left with Mahallah Ali, Bilal Asiah and Zubair. You as a student of Algorithm Design and Analysis are to help Student Affairs Division to construct a State Space Tree to generate all possible combinations of the graph, given only 3 colours (Red Grey Black}. (6 marks) Zubair Bilal Ali Faruq Asiah Hamzah Figure Q4b