MATH2000 Network Optimisation Test 1

Semester 2, 2022

Question 1.

(a) Construct an example of a graph G so that G is simple and has vertices of only degrees 1,2,3,4 and 5. (4 marks)

(b) Use induction to prove that any connected simple graph with n vertices has at least n-1 edges. (6 marks)

Question 2.

1. Draw the graph defined by the following node-arc incident matrix. (5 marks)

2. Draw the graph defined by the following linked list data structure. (5 marks)

Question 3. Consider the following graph:

1. Using vertex 1 as the root, perform. the depth-first search of the above graph. When there are choices available within the algorithm, choose the vertex with the smallest labels first. List the order of vertices visited and give the resultant tree. (You do not have to write explicit steps/actions from the algorithm.) (5 marks)

2. Apply the breadth-first search algorithm to the above graph, using vertex 1 as the root. When there are choices available within the algorithm, choose the vertex with the smallest label first. List the order of vertices visited and give the resultant vertex labels, but other than this you don't have to write explicit steps/actions from the algorithm. (5 marks)

Question 4.

1. Apply the Sequential Colouring algorithm to the following graph. Give the list Li for each vertex i, as well as its colour.  (5 marks)

2. Apply the Sequential Edge Colouring algorithm to the following graph. Give the list Li for each edge i, as well as its colour. (5 marks)

Question 5. Find the chromatic polynomial of the following graph.           (10 marks)

Question 6. Consider the following directed street network

where the numbers on the edges represents their respective capacities.

1. Use Ford-Fulkerson Algorithm to find the maximum flow possible from node 1 to node 5.   (8 marks)

2. Find a minimum cut of the network.            (2 marks)

X = {1,2,3}, Xbar = {4,5}