Question

Eight houses are lined up on a street, with four on each side of the road as shown: Each house wants to set up its own wi-fi network, but the wireless networks of neighbouring houses – that is, houses that are either next to each other (ignoring trees) or over the road from one another (directly opposite) – can interfere, and must therefore be on different channels. Houses that are sufficiently far away may use the same wi-fi channel. Your goal is to find the minimum number of different channels the neighbourhood requires. (a) Model this as a graph problem. Remember to: (i) Clearly define the vertices and edges of your graph. (4 marks) (ii) State the associated graph problem that you need to solve. (2 marks) (b) Give the solution to the graph problem corresponding to this scenario; and determine the minimum number of wi-fi channels required for the neighbourhood? (2 marks) (c) How do your answers to (a) and (b) change if a house's wireless network can also interfere with those of the houses to the left and right of the house over the road? (4 marks)

Answer 1

(a) The graph can be visualized as follows :

1 2 8 7 6 5

(i) Each house is represented by the vertex in the graph. Two vertex (houses) have an edge in between if there is WiFi interference. This happen when the two houses are either adjacent or they are just on the directly opposite sides of the road.

(ii) The problem reduces to the Graph Coloring Problem : we need to find the minimum number of colors required so that the graph can be vertex colored i.e.. any two vertices with a common edge should different colors. This minimum number of colors is also called as chromatic number. Then, number of different WiFi-channels required = Chromatic Number of the Graph.

(b) The solution to this problem is 2. So, we need exactly 2 different WiFi-channels so that everybody can have WiFi without interference. The solution is shown below :

1 2 8 7 6 5

Houses 2,4,6,8 can have WiFi on the one channel whereas Houses 1,3,5,7 can have WiFi on second channel. So, total WiFi channels required = 2.

(c) The edge conditions need to be updated as per the question. Each house remains a vertex and now edges are between adjacent houses and houses which are directly opposite to each other on the road and left and right of the opposite house. The updated Graph is shown below :

8 7 6 5

Again we need to color the vertices of the graph with minimum colors so no two vertices that share an edge should gave the same color. This can be done using 4 colors as shown below:

2 7 6 5

Hence, the number of WiFi-channels required is 4. Vertices with the same color can share the same channel. (1,3) will share first channel, (2,4) can share the second channel, (6,8) can share the third channel and (5,7) can share the fourth channel.