maths.free › Combinatorics & Graph Theory › 13. Network Flows › Network Flows: exercises

Network Flows: exercises

Network Flows: exercises — from Keller & Trotter, Applied Combinatorics.

Practice (11)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Consider the network diagram in . For each directed edge, the first number is the capacity and the second value is intended to give a flow \(\phi\) in the network. However, the flow suggested is not valid.

    1. Identify the reason(s) \(\phi\) is not valid.

    2. Without changing any of the edge capacities, modify \(\phi\) into a valid flow \(\widehat{\phi}\). Try to use as few modifications as possible.

  2. Alice claims to have found a (valid) network flow of value \(20\) in the network shown in . Bob tells her that there's no way she's right, since no flow has value greater than \(18\). Who's right and why?

  3. Find an augmenting path \(P\) with at least one backward edge for the flow \(\phi\) in the network shown in . What is the value of \(\delta\) for \(P\)? Carry out an update of \(\phi\) using \(P\) to obtain a new flow \(\hat{\phi}\). What is the value of \(\hat{\phi}\)?

  4. Prove . You will need to verify that the flow conservation laws hold at each vertex along an augmenting path (other than \(S\) and \(T\)). There are four cases to consider depending on the forward/backward status of the two edges on the augmenting path that are incident with the vertex.

  5. Find the capacity of the cut \((L,U)\) with \[\begin{aligned}\end{aligned}\] in the network shown in .

  6. Find the capacity of the cut \((L,U)\) with \[\begin{aligned}\end{aligned}\] in the network shown in .

  7. For each of the augmenting paths \(P_1\), \(P_2\), \(P_3\), and \(P_4\) in , update the flow in . (Note that your solution to this exercise should consist of four network flows. Do not attempt to use the four paths in sequence to create one updated network flow.)

  8. Continue running the Ford-Fulkerson labeling algorithm on the network flow in until the algorithm halts without labeling the sink. Find the value of the maximum flow as well as a cut of minimum capacity.

  9. Use the Ford-Fulkerson labeling algorithm to find a maximum flow and a minimum cut in the network shown in by starting from the current flow shown there.

  10. shows a network. Starting from the zero flow, , the flow with \(\phi(e)=0\) for every directed edge \(e\) in the network, use the Ford-Fulkerson labeling algorithm to find a maximum flow and a minimum cut in this network.

  11. Consider a network in which the source \(S\) has precisely three neighbors: \(B\), \(E\), and \(F\). Suppose also that \(c(S,B)=30\), \(c(S,E)=20\), and \(c(S,F)=25\). You know that there is a flow \(\phi\) on the network but you do not know how much flow is on any edge. You do know, however, that when the Ford-Fulkerson labeling algorithm is run on the network with current flow \(\phi\), the first two vertices labeled are \(S\) with label \((*,+,\infty)\) and \(F\) with label \((S,+,15)\). Use this information to determine the value of the flow \(\phi\) and explain how you do so.

Symbols used here

\infty
infinity
Not a number: "grows without bound" in limits and intervals.
\varepsilon,\ \delta
epsilon, delta
Small positive tolerances in the definition of a limit.
\sup,\ \inf
supremum, infimum
Least upper bound, greatest lower bound.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

خودت امتحان کن

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

بیشتر در Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs