(Solved): Consider the following floor-plan of a house: The owner, Ingvar, has forgotten to build any interio ...

Consider the following floor-plan of a house: The owner, Ingvar, has forgotten to build any interior doors. He would like to spend as little as possible, and so wants to install the minimum number of doors that will make his house completely accessible. He would also like visitors to his house to be able to visit each room in turn, starting from the hall, with a minimum amount of backtracking. Use the graph theory you have learnt in this module to solve Ingvar's problem. In your answer, you should: (a) Convert the floor plan into a graph, with one node

for each of the six rooms, and an edge between two rooms if they share a wall. (b) _ State which graph-theoretic concept will provide a solution to the problem of installing a minimum number of doors that will make the house completely accessible. (c) State an algorithm studied in the unit which will provide a solution which satisfies Ingvar's constraints. (d) Carry out this algorithm on the graph, and illustrate your answer on a copy of the original floor-plan. (USING DEPTH-FIRST search with table please)