Question 11 Write your answers in the boxes provided. For this question, working is not required and will not be marked. The diagram at right shows the capacities and directions of all links in a transport network with sources, target t and intermediate nodes a, b, c, d. Working on a separate piece of paper, not to be submitted, use the max flow labelling algorithm to find the maximum flow through the network. Use the version of the algorithm described in lectures, with strict adherence to the level and alphabetical order rules. Then complete the following two statements. (a) The first label applied to the target is [This is the label that is applied to t during the determination of the first incremental flow.] (b) The final label applied to the target is [This is the label that is applied to t during the determination of the last incremental flow before the algorithm terminates.) 7 5 2 5 30 The diagram at right shows the capacities and directions of all links in another transport network with source s, target t and intermediate nodes a, b, c, d. Again working on a separate piece of paper, not to be submitted, use the max flow labelling algorithm to find the maximum flow through the network. Once again use the version of the algorithm described in lectures, with strict adherence to the level and alphabetical order rules. Then complete the following four statements. 4 6 8>t (c) The total number of distinct paths from s to t in this digraph is (This is the number of different potential incremental flows.] (d) The number of these that are actually used as incremental flows is (e) The number of different labels that get applied to vertex b over the entire duration of the application of the algorithm is (f) The max flow value for this transport network is Question 11 Write your answers in the boxes provided. For this question, working is not required and will not be marked. The diagram at right shows the capacities and directions of all links in a transport network with sources, target t and intermediate nodes a, b, c, d. Working on a separate piece of paper, not to be submitted, use the max flow labelling algorithm to find the maximum flow through the network. Use the version of the algorithm described in lectures, with strict adherence to the level and alphabetical order rules. Then complete the following two statements. (a) The first label applied to the target is [This is the label that is applied to t during the determination of the first incremental flow.] (b) The final label applied to the target is [This is the label that is applied to t during the determination of the last incremental flow before the algorithm terminates.) 7 5 2 5 30 The diagram at right shows the capacities and directions of all links in another transport network with source s, target t and intermediate nodes a, b, c, d. Again working on a separate piece of paper, not to be submitted, use the max flow labelling algorithm to find the maximum flow through the network. Once again use the version of the algorithm described in lectures, with strict adherence to the level and alphabetical order rules. Then complete the following four statements. 4 6 8>t (c) The total number of distinct paths from s to t in this digraph is (This is the number of different potential incremental flows.] (d) The number of these that are actually used as incremental flows is (e) The number of different labels that get applied to vertex b over the entire duration of the application of the algorithm is (f) The max flow value for this transport network is