Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH2000

Network Optimisation

Discipline of Mathematics and Statistics

Question 1     (10 marks): (a)     Draw the graph described by the following link list data structure                  (5 marks)   1    2    3    4    5    6    7     8     9    10   11   12   13   14   15   16   17   18   19

2 2 - 4 1 4 3 5 1 5 3 4 4 - - 2 - 5 1 12 6 - 8 7 0 10 0 11 0 4 18 19 - - 13 - 0 0

Link List

1 5 2 9 16 0 0 0

Pointers

3 15 17 14

(b)     Derive the graph edge list.   

(3 marks)

(c)     Suppose the edge joining vertex v1  and v4  is deleted. Indicate how the link list data structure changes?                                                                                         (2 marks)

Question 2      (10 marks):

Starting from vertex v5 , apply DFS and BFS procedures to the following graph. When there are multiple options, choose the smallest label first. Compare the order in which the graph is explored in both procedures.

Question 3     (6 marks): Consider graph G1 drawn below:
Graph Gn consists of n copies of G1 joined side by side:
...
(a)     Determine P(G!, 入).	(2 marks)
(b)     Derive the formulation for P(Gn, 入) in terms of P(Gn#!, 入).                              (4 marks)

Question 4      (12 marks):

(a)     Determine, using the Sequential Colouring Algorithm, the number of colours needed to

colour the following graph. You need to show sufficient working to demonstrate the use

of the algorithm.                                                                                                   (4 marks)

(b)     Comment on the quality of your solution in (a).                                              (2 marks)

(c)     Calculate the chromatic polynomial of the graph.                                           (6 marks)

Question 5     (5 marks):

Consider the commodity network N drawn below. Nodes S1 and S2 are source nodes, each supplying 40 units of the commodity. Nodes T1 and T2 are sink nodes requiring 50 and 25 units of the commodity, respectively. All other nodes are intermediate nodes. The numbers on the arcs represent the arc capacity. The problem is to determine whether or not it is possible to meet the demand with the available supplies.

 

 

 

 

 

Can the supplies meet the demands? Justify your answer using the partitioning of the vertices shown in the graph.    (Note that you do NOT need to find the maximum flow in the network).

Question 6     (7 marks):

Imagine there is a bank of numeric codes, all with same length. Two codes are successive if they differ by one number. We are interested to find the link between two specific codes. Below is an example of linking two codes 39875 and 59276 in 4 steps:

39875 - 39876 - 49876 - 49276 - 59276

 

(a)     How do you present the bank of codes as a graph? Explain what nodes and edges

represent.                                                                                                        (3 marks)

 

(b)    The problem of interest is to link two given codes in the least number of steps. Which

network algorithm would you implement to link two given codes? Explain.    (4 marks)

 

Question 7     (16 marks):

 

You need to justify your answer to the following True/False questions.

(a)     Every tree is a 2-colorable.

 

(b)    The polynomial 入(入 - 1)2  (入 - 2)3 can be a chromatic polynomial of a graph.

 

(c)     The edge-chromatic number of a complete graph on 2n+1 nodes is 2n.

 

(d)    We can apply Breadth First Search to determine if a graph is bipartite.

 

(e)     Edge list is the best data structure for Depth First Search algorithm.

(f)     We can construct a 3-regular graph with 5 nodes.

(g)     Minimum spanning tree in a graph is always unique.

(h)     Every Kn,n graph is connected.

Question 8     (7 marks):

Consider the commodity network N drawn below. Nodes S1 and S2 are source nodes, each supplying 50 units of the commodity. Nodes T1 and T2 are sink nodes requiring 55 and 35 units of the commodity, respectively. All other nodes are intermediate nodes. The numbers on the arcs represent the arc capacity. The problem is to determine whether or not it is possible to meet the demand with the available supplies.

 

10

10

5

40

 

35

(a)  Give the modified network that transforms the problem into a single source single sink

(2 marks)

 

 

10

10

5

40

 

35

 

 

(b)  State the conditions of the modified network under which N has a feasible flow.

(2 mark)

(c)   Implement only one iteration of the Ford-Fulkerson algorithm given the initial flow of zero. (3 marks)

Question 9     (10 marks):

(a)     Prove that any subgraph of a bipartite graph is bipartite.                               (5 marks)

 

(b)     Is K8 2-factorable? Justify your answer.                                                          (3 marks)

(c)     If a graph is simply a cycle on n vertices, how many edges does it have? Justify your answer.                                                                                                           (2 marks)