6.18
gradute based, proof.
Observe that: A minimum flow will require some lowerbound, or else this is trivial because zero flow will always be an optimal solution.
We need to convert the problem to an max flow, with/without the lower bound. 2 Applications of the maxflow probably means that we need a lower bound yes.
6.43.
graduate base, proof, see page 195 for theorem 6.11
Figure 6.22 Examples for Exercises 6.12 and 6.13.
Undergraduate based:
Using the shortest augmenting path algorithm, solve the maximum flow problem give in Figure 6.22(b). Describe the augmenting paths at each iteration as well as any advances and/or retreats and the distance labels at each iteration. Verify you have the maximum flow by exhibiting an appropriate cut.
In brief, run the Dinic's algorithm for this graph.
Establishing a Feasible Flow
Feasibility search for the max flow problem with lower bound constraint.
Didn't mention what happen to the \(s, t\) vertices for the mass balance constraints.
6.34
Undergraduate based. (a) F, (b) F. (c) F, (d) F, (e) T, (f) F.
\(x_{i, j}= 0 \dot\vee x_{j, i} = 0\)
6.20
Undergraduate, modeling based:
Make sure to prove the transformation works after describing it by proving a correspondence between flows of the multiple source/sink problem and the single source/sink problem.
We refer totwo directed paths from node s to node t as arc disjoint if they do not have any arcin common.
arc disjont s-t path.
6.7 FLOWS WITH LOWER BOUNDS
A small generalization of the maximum flow problem where lower capacity constraints are introduced for all the arcs.
6.13.
undergraduate, hw description:
Find the longest path in the residual network by inspection. (Note: finding the longest path in a network is NP-complete unless the network is acyclic.)
Labeling Algorithm Page 184
Theorem 6.12.
Theorem 6.11 (Circulation Feasibility Conditions)
This is a NECESSARY CONDITIONS for feasibility of the circulation problem.
Theorem 6.10 (Generalized Max-Flow Min-Cut Theorem).
Assumption 6.4.
\((i, j)\in A\iff (j, i)\in A\). We allow for arcs with zero capacity. For all single direction arc, the opposite direction arc on the graph is having a capacity of zero.
I think this is essentially a residual graph on the zero flow, which is trivially feasible. Residual graph on the network is covered in the later part of the chapter (pg177).
Theorem 6.6.
complexity of the max flow labeling algorithm.
Theorem 6.7.
Min cut capacity and the cardinality of maximum number of arc disjoint path from source to destination.
Property 6.2.
augmenting flow is upper bounded by the residual capacity across all \(s-t\) cut.
Assumption 6.5
No parallel arcs.
Assumption 6.3
Doesn't contain a direction path with infinite capacity from source to node. (Makes sure that the problem is not unbounded)
Assumption 6.2
All capacities are nonnegative integers.
Assumption 6.1
The Network is Directed
Theorem 6.3 (Max-Flow Min-Cut Theorem).
Theorem 6.4 (Augmenting Path Theorem).
Aug Path theorem
6.12.
Undergraduarte, algorithm based.
Theorem 6.5 (Integrality Theorem).
Network flow integers theorem.
Theorem 6.8
Application 6.1
Property 6.1.
The capacity of the cut of any flow is less than or equal to the capacity of any cut in the network, in the context of maximum flow problem.