4. Homework

The list x is the graph of an undirected graph:

x = [[3], [11, 6, 5], [4, 11, 5], [0], [2, 6, 6], [12, 19, 2, 1],
    [4, 17, 1, 4, 8], [14, 11], [6], [], [15, 11], [10, 2, 1, 16, 15, 7],
    [5], [], [7], [10, 11], [11], [6, 19], [], [5, 17]]

Use the computational techniques you have studied this week to answer the following questions. Submit your answers as a single .py file.

1. The adjacency list of an undirected graph has the property that for any two nodes i and j, if i is a neighbour of j then j is a neighbour of i. Show that x is the adjacency list of an undirected graph.

2. Find two nodes that are not connected by a path.

3. Determine the node pair(s) with the maximum path distance in the graph.

4. Determine all connected components in the graph (full marks if you use a technique which would work for any undirected graph regardless of size).

NB while it might be possible to answer these questions using pen and paper, you should determine your answers using Python code and the computational techniques studied in class. Full marks will be given for answers which use techniques which could work for an undirected graph of ANY size (not just x). You should include sufficient text (in the form of Python comments) to explain how your code determines the answer to each question.