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}
版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。