Assignment 3
Task 1
(a) The graph is
The problem is find the maximum number of edge-disjoint paths from s to t.
(b) The iterations is as follows:
The first iteration: remove s->a->b->t from the graph, since it’s the shortest path from s to t.
There’s no path from s to t any more. Stop iteration.
(c) In fact, there are two edge-disjoint paths in H,
s->a->f->g->t
s->d->e->b->t
Task 2
(a) If the graph in the edge direct problem is
It can be transformed to the following max flow decision problem:
Decide the max flow in has value at least or not; the output is either YES or NO.
and L = B + 1. Each edge in H has a capacity of 1.
To form H, we add an extra new vertex s to G, and add edges from s to each of the vertices in G. Then find the max flows from s to other vertices. If among all the max flows, the max flow value is equal or larger than L, output YES. Output NO otherwise.
(b) Proof
1) If the max flow from s to other vertices in H is at least L, for a flow from s in H with max flow value, direct all the edges in the flow. For other edges, direct them at random. Since the flow value is L, the destination node of the flow have in-degree of L including the edge from s. Remove vertex s, in the resulted directed graph, the sink vertex will have a in-degree of B = L-1. If other vertex has larger in-degree, the selected flow would not be the max flow among all the flows. Thus, the resulted directed graph is graph in which all the vertices has an in-degree at mos B =L-1
2) If a directed graph generated by directing edges in G= (V, E) has in-degree at most B, we can add a vertex s, and direct s to each of the vertices in the directed graph. Then max flow is L = B + 1. The max flow starts from s, to the vertex with the largest in-degree.
(c)
L
({},{(,)|})
HVsEsvvV
=Î
UU
(,)
GVE
=
H