3. a. The maximum-flow problem may have more than one optimal solution.
In fact, there may be infinitely many of them if we allow (as the definition
does) non-integer edge flows. For example, for any 0≤≤1,theflow
depicted in the diagram below is a maximum flow of value 1. Exactly two
b. The answer for the number of distinct minimum cuts is analogous
to that for maximum flows: there can be more than one of them in the
same network (though, of course, their number must always be finite be-
cause the number of all edge subsets is finite to begin with). For example,
the network
2
21
capacities. For example, the network
4. a. Add two vertices to the network given to serve as the source and sink
of the new network, respectively. Connect the new source to each of the
original sources and each of the original sinks to the new sink with edges
b. Replace each intermediate vertex with an upper bound on a flow
amount that can flow through it with two vertices 0and 00 connected by
an edge of capacity as shown below:
5. The problem can be solved by calling TreeFlow (()∞)where
Algorithm TreeFlow (())
//Finds a maximum flow for tree ()rooted at
//whose value doesn’t exceed (available at the root),
22
6. a. Adding the −2equalities expressing the flow conservation require-
ments yields
b. Summing up the flow-value definition =P
1and the flow-conservation
requirement P
=P
for every ∈(1)we obtain
Moving the summation from the left-hand side to the right-hand side and
splitting the sum into the sum over the vertices in and the sum over
the vertices in ¯
, we obtain:
23
Note that equation (10.9) expresses this general property for two special
cuts: 1(1¯
1)induced by 1={1}and 2(2¯
2)induced by 2=
−{}.
7. a. maximize =12 +14
b. The optimal solution is 12 =2
14 =1
23 =1
25 =1
36 =2
43 =1
56 =1
8. n/a
9. n/a
10. Solve the maximum flow problem for the following network:
24
Exercises 10.3
1. For each matching shown below in bold, find an augmentation or explain
why no augmentation exists.
2. Apply the maximum-matching algorithm to the following bipartite graph:
3. a. What is the largest and what is the smallest possible cardinality of a
matching in a bipartite graph =h iwith vertices in each vertex
set and and at least edges?
b. What is the largest and what is the smallest number of distinct solu-
4. a. Hall’s Marriage Theorem asserts that a bipartite graph =
h ihas a matching that matches all vertices of the set if and
only if for each subset ⊆ |()|≥||where R(S)isthesetofall
25
b. You have to devise an algorithm that returns “yes” if there is a matching
in a bipartite graph =h ithat matches all vertices in and
returns “no” otherwise. Would you base your algorithm on checking the
condition of Hall’s Marriage Theorem?
7. Consider the following greedy algorithm for finding a maximum matching
in a bipartite graph =h i: Sort all the vertices in nondecreasing
order of their degrees. Scan this sorted list to add to the current matching
(initially empty) the edge from the list’s free vertex to an adjacent free
vertex of the lowest degree. If the list’s vertex is matched or if there are
no adjacent free vertices for it, the vertex is simply skipped. Does this
algorithm always produce a maximum matching in a bipartite graph?
8. Design a linear-time algorithm for finding a maximum matching in a tree.
Hints to Exercises 10.3
1. You may but do not have to use the algorithm described in the section.
4. a. You do not have to check the inequality for each subset of if you
can point out a subset for which the inequality does not hold. Otherwise,
fill in a table for all the subsets of the indicated set with columns for
()and |()|≥||.
b. Think time efficiency.
5. Reduce the problem to finding a maximum matching in a bipartite graph.
7. Since this greedy algorithm is arguably simpler than the augmenting path
algorithm given in the section, should we expect a positive or negative
answer? Of course, this point cannot be substituted for a more specific
argument or a counterexample.
27
Solutions to Exercises 10.3
1. a. The matching given in the exercise is reproduced below:
1 2 3 4
Its possible augmentations are:
1 2 3 4
1 2 3 4
b. No augmentation of the matching given in part b (reproduced below)
is possible.
1 2 3 4
28
2. Here is a trace of the maximum-matching algorithm applied to the bipar-
tite graph in question:
1 2 3
456
3
V
U
1 2 3
456
1
Queue: 1 2 3 Queue: 1
↑23
Augment from 5
1 2 3
456
3
3
1 2 3
456
2
5
Queue: 2 Queue: 2
↑5
↑1
↑
3. a. The largest cardinalilty of a matching is when all the vertices of a
graph are matched (perfect matching). For example, if ={1
2 },
b. Consider the bipartite graph in which each of the vertices
in is connected to each of the vertices in To obtain a p erfect
4. a. (i) For ={1234}the inequality obviously fails for =since
|()|=||=3while ||=4
Hence, according to Hall’s Marriage Theorem, there is no matching that
matches all the vertices of the set {1234}
(ii) For subsets of ={567}we have the following table:
()|()|≥||
{5} {1,2,3} 3≥1
{6} {1} 1≥1
30
5. It is convenient to model the situation by a bipartite graph =h i
where represents the committees, represents the committee members,
and ( )∈if and only if belongs to committee :
A
B C D E
6. Add one source vertex and connect it to each of the vertices in the set
by directed edges leaving .Addonesinkvertexand connect each of the
7. The greedy algorithm does not always find a maximum matching. As a
counterexample, consider the bipartite graph shown below:
1 2 3
31