# Maximum Flow and Minimum Cut: Step-by-Step Solution ## Problem Restatement Given a directed network (graph) with specified capacities on arcs, find: 1. **(a)** A linear program (LP) for the maximum flow from \(A\) to \(F\). 2. **(b)** Given an optimal flow solution, use complementary slackness to identify the minimum cut \((S, T)\) and its capacity. 3. **(c)** Formulate the min-cut problem as an integer program (IP). --- ## (a) LP Model for Maximum Flow from \(A\) to \(F\) **Let:** - \(x_{ij}\) = flow from node \(i\) to node \(j\) - \(c_{ij}\) = capacity of arc \((i, j)\) - \(V\) = set of all nodes in the network (includes \(A, B, C, D, E, F\)) - \(N(i)\) = set of neighbors of node \(i\) ### **Variables** - \(x_{ij} \geq \) for all arcs \((i, j)\) ### **Objective** Maximize the total flow out of source \(A\) (or into sink \(F\)), i.e., \[ \text{Maximize } \sum_{j} x_{Aj} \] ### **Constraints** 1. **Capacity:** For all arcs \((i, j)\): \[ \leq x_{ij} \leq c_{ij} \] 2. **Flow Conservation:** For all nodes \(k \in V\), except source \(A\) and sink \(F\): \[ \sum_{i} x_{ik} = \sum_{j} x_{kj} \] (Flow in = Flow out at each intermediate node.) --- ## (b) Min-Cut via Complementary Slackness Given optimal flows: - \(x_{AB}=11\) - \(x_{AC}=7\) - \(x_{BD}=6\) - \(x_{BE}=5\) - \(x_{CE}=7\) - \(x_{DF}=6\) - \(x_{EF}=12\) - All other \(x_{ij}=\) - **Max-flow value = 18** ### **Step 1: Identify Saturated Arcs (where \(x_{ij} = c_{ij}\))** Assume that the capacities are: - \((A,B)\): \(c_{AB}=11\) (\(x_{AB}=c_{AB}\)) - \((A,C)\): \(c_{AC}=7\) (\(x_{AC}=c_{AC}\)) - \((B,D)\): \(c_{BD}=6\) (\(x_{BD}=c_{BD}\)) - \((B,E)\): \(c_{BE}=5\) (\(x_{BE}=c_{BE}\)) - \((C,E)\): \(c_{CE}=7\) (\(x_{CE}=c_{CE}\)) - \((D,F)\): \(c_{DF}=6\) (\(x_{DF}=c_{DF}\)) - \((E,F)\): \(c_{EF}=12\) (\(x_{EF}=c_{EF}\)) All these arcs are saturated. ### **Step 2: Find the Minimum Cut \((S, T)\)** - Define \(S\) as the set of nodes reachable from \(A\) via **non-saturated forward arcs** (those with \(x_{ij} < c_{ij}\)), plus \(A\) itself. - But in this case, all outgoing arcs from \(A\) are saturated, so the only nodes in \(S\) are: - \(A\) - All nodes that can be reached from \(A\) along arcs where \(x_{ij} < c_{ij}\) But since both arcs from \(A\) are saturated, let's see if downstream nodes are reachable: - From \(A\) to \(B\): Saturated - From \(A\) to \(C\): Saturated So, **\(S = \{A\}\)**, and all other nodes are in \(T\). ### **Step 3: Capacity of the Minimum Cut** The capacity of the cut is the sum of capacities of arcs from \(S\) to \(T\): \[ \text{Capacity} = c_{AB} + c_{AC} = 11 + 7 = 18 \] --- ## (c) Integer Program for the Min-Cut **Variables:** - Let \(y_i = \begin{cases} 1 & \text{if node } i \in S \\ & \text{if node } i \in T \end{cases}\) - Let \(z_{ij} = \begin{cases} 1 & \text{if arc } (i,j) \text{ crosses from } S \text{ to } T \\ & \text{otherwise} \end{cases}\) ### **Objective:** Minimize total capacity of the cut: \[ \text{Minimize } \sum_{(i,j)} c_{ij} z_{ij} \] ### **Constraints:** 1. **Source and Sink assignments:** - \(y_A = 1\) (source in \(S\)) - \(y_F = \) (sink in \(T\)) 2. **Cut definition:** - For all arcs \((i,j)\): \[ z_{ij} \geq y_i - y_j \] (If \(i \in S\) and \(j \in T\), then \(y_i - y_j = 1\), so \(z_{ij} \geq 1\), else \(z_{ij} \geq \).) 3. **Binary restrictions:** - \(y_i \in \{,1\}\) for all \(i\) - \(z_{ij} \in \{,1\}\) for all \((i,j)\) --- ## **Summary** - **(a):** The LP for max flow maximizes the flow out of \(A\) subject to capacity and flow conservation. - **(b):** The min-cut \((S,T)\) is \(S = \{A\}\), \(T = \{B,C,D,E,F\}\), and its capacity is **18**. - **(c):** The min-cut problem is formulated as an integer program with binary variables indicating sides of the cut and whether arcs cross the cut. --- **Diagram not shown here, but you can visualize \(A\) as the only node in \(S\), all outgoing arcs saturated, forming the minimum cut.**

# Summary of Key Points ## (a) LP Model for Maximum Flow The linear programming model aims to maximize the flow from source node \(A\) to sink node \(F\) while ensuring that flow on each arc does not exceed its capacity and that flow conservation is maintained at intermediate nodes. The objective function is to maximize \(\sum_{j} x_{Aj}\) with constraints for capacities and flow conservation. ## (b) Min-Cut via Complementary Slackness Using the complementary slackness conditions, the minimum cut \((S, T)\) is identified as \(S = \{A\}\) and \(T = \{B, C, D, E, F\}\), with a capacity of **18**, which is the sum of capacities of saturated arcs from \(A\). This cut effectively separates the source from the sink based on the flow values provided. ## (c) Integer Program for the Min-Cut The integer program for the min-cut minimizes the total capacity of arcs crossing from set \(S\) to set \(T\) while maintaining binary constraints for node set memberships and arc crossings. The formulation includes constraints ensuring that the cut reflects the separation of source and sink nodes as required.