CSDS 455: Applied Graph Theory

Homework 16

Our subject next week is flows. We will spend much of the time looking at k-flows, but for this weekend, I

want to read about (or recall) network flows where we have a source and a sink on a graph.

Problem 1: Prove that you can reduce the maximum bipartite matching problem to the network flow

problem. (Given a bipartite graph, turn it into a flow problem such that the value of the flow equals the

maximum matching of the bipartite graph.)

Problem 2: Prove that you can reduce Menger’s Theorem to the network flow problem. (Given a graph,

turn it into a flow problem so that the flow size gives the number of vertex disjoint paths of the graph.)

Problem 3: Suppose we have a network (directed graph) D with edge weights (capacities) and with source

node s and sink node t. Let S ⊂ V (D) and T ⊂ V (D) be subsets of nodes such that s ∈ S, T but t /∈ S, T.

(S, S) is a cut of the network, and cap(S, S) is the sum of weights of edges with their tail in S and head in

S. Prove that cap(S ∪ T, S ∪ T) + cap(S ∩ T, S ∩ T) ≤ cap(S, S) + cap(T, T).