Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
INT202 Complexity of Algorithms
Tutorial 5
1. Use Prim’s algorithm starting at node A to compute the Minimum Spanning Tree (MST) of
the following graph. Write down the edges of the MST in the order in which Prim’s algorithm
adds them to the MST.
2. Prim and Kruskal Executions
1) Execute Prim’s algorithm on the following graph starting at vertex A. If there are any ties,
the vertex with the lower letter comes first. List the edges in the order in which they are
added to the tree.
2) Execute Kruskal’s algorithm on the following graph starting at vertex A. Assume that equal
weight edges are ordered lexicographically by the labels of their vertices assuming that the
lower labeled vertex always comes first when specifying an edge, e.g. (C, E) is before (C, F)
which in turn is before (D, G). List the edges in the order in which they are added to the
developing forest.
3. Consider the flow network N and the flow f shown in the following figure:
The figure shows an augmenting path π drawn in thick edges.
1) What are the forward edges of augmenting path π in this figure? What are the backward
edges?
2) How many augmenting paths are there with respect to flow f in this figure? For each such
a path, list the sequence of vertices of the path and the residual capacity of the path.
4. Execute the Ford-Fulkerson maximum flow algorithm on the following network:
For each step of the algorithm, write in a table the augmenting path by listing its vertices, its
residual capacity and the resulting flow on the network.
5. Consider the following flow network and feasible flow f.
(1) What is the value of the flow f?
(2) Perform one iteration of the Ford-Fulkerson algorithm, starting from the flow f. Give the
sequence of vertices on the augmenting path.
(3) What is the value of the maximum flow?
(4) List the vertices on the s side of the minimum cut.
(5) What is the capacity of the minimum cut?