Flow Through Cuts in Networks

Author

Your Name

Published

January 30, 2025

Introduction

This lecture introduces the concept of flow through a cut in network flow theory. We will extend the notion of divergence from a single node to a set of nodes, defining the flow across a cut set. We will explore the properties of cut sets, particularly those that separate the source and sink nodes. A crucial theorem stating that the flow through any cut is equal to the value of the flow will be presented and proved. Furthermore, we will define the capacity of a cut and discuss its relationship to the flow through the cut, leading to the weak form of the Max-Flow Min-Cut Theorem. Finally, we will touch upon the minimum cut problem and its applications, highlighting the connection between minimum cuts and maximum flows.

Flow Through a Cut

Definition of Flow Across a Cut

Let $S$ be a set of vertices and $\flow$ be a flow in a network. We define the flow through $S$, denoted as $\divergence_{\flow}(S)$, as the net flow out of the set $S$. Formally, it is given by:

\[\divergence_{\flow}(S) = \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} - \sum_{\substack{(i,j) \in E \\ i \notin S, j \in S}} \flow_{ij}\]

where the first sum is over all edges $(i,j)$ leaving $S$ (i.e., starting in $S$ and ending outside $S$), and the second sum is over all edges $(i,j)$ entering $S$ (i.e., starting outside $S$ and ending in $S$).

In words, the flow through $S$ is the total flow out of $S$ minus the total flow into $S$.

This definition generalizes the concept of divergence at a single node. Recall that the divergence at a node $v$ was defined as the total outflow from $v$ minus the total inflow into $v$. Now, $\divergence_{\flow}(S)$ extends this to an entire set of nodes $S$, representing the net flow from $S$ to the rest of the network.

Cut Sets and Their Properties

Source and Sink Separation

In the context of network flows from a source node $\source$ to a sink node $\sink$, we are particularly interested in sets of vertices $S$ that contain the source $\source$ but not the sink $\sink$. Such sets are called cut sets or simply cuts.

A cut set (or cut) in a network with source $\source$ and sink $\sink$ is a set of vertices $S$ such that:

$\source \in S$
$\sink \notin S$

A cut set $S$ effectively partitions the vertices of the graph into two disjoint sets, $S$ and $V \setminus S$, where $V$ is the set of all vertices. The source is in $S$, and the sink is in $V \setminus S$.

In graph theory, the term "cut" is often used to refer to the set of edges that, when removed, disconnect the graph. In our context, a cut set $S$ induces a set of edges that "separate" the source from the sink.

Number of Possible Cuts

Consider a network with $n$ vertices. If we fix the source $\source$ and the sink $\sink$, and we want to count the number of possible cut sets $S$. Since $\source$ must be in $S$ and $\sink$ must be outside $S$, we are free to choose for each of the remaining $n-2$ vertices whether they belong to $S$ or not.

Therefore, there are $2^{n-2}$ possible cut sets that separate a given source $\source$ from a sink $\sink$ in a network with $n$ vertices.

Relationship to Divergence

As mentioned earlier, the definition of flow through a cut $\divergence_{\flow}(S)$ is an extension of the divergence at a single node. Specifically, if we consider a cut set $S$ that consists of only the source node $\source$, i.e., $S = \{\source\}$, then the flow through this cut is:

\[\divergence_{\flow}(\{\source\}) = \sum_{\substack{(\source,j) \in E \\ j \neq \source}} \flow_{\source j} - \sum_{\substack{(i,\source) \in E \\ i \neq \source}} \flow_{i \source}\]

This is exactly the definition of the value of the flow $\flowvalueX$, which represents the net flow out of the source node.

Flow Through a Specific Cut: The Source Node

The value of a flow $\flowvalueX$ is, by definition, the net flow out of the source node $\source$. As discussed above, this is a special case of the flow through a cut, where the cut set $S$ is just the set containing the source node itself, $S = \{\source\}$.

Thus, the value of the flow $\flowvalueX$ can be seen as the flow through the cut $S = \{\source\}$.

Examples of Flow Through Different Cuts

Consider a network with a flow. Let’s examine some examples to calculate the flow through different cut sets.

Consider a flow network (diagram of the network and flow values are assumed to be provided as in the transcription, but are not available here for reproduction). Let’s analyze four different cut sets $S$ and calculate the flow through each of them. Assume the network has nodes labeled 1 to 8, with node 1 as the source and node 8 as the sink.

Cut Set 1: $S = \{1\}$. Edges leaving $S$: $(1, 3), (1, 2)$. Assume flow values are $\flow_{13} = 8, \flow_{12} = 3$. Edges entering $S$: None. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{13} + \flow_{12}) - 0 = 8 + 3 = 11$.
Cut Set 2: $S = \{1, 3, 4, 5, 7\}$. Edges leaving $S$: $(1, 2), (4, 2), (4, 6), (5, 6), (5, 8), (7, 8)$. Assume flow values are $\flow_{12} = 3, \flow_{42} = 0, \flow_{46} = 4, \flow_{56} = 3, \flow_{58} = 2, \flow_{78} = 2$. Edges entering $S$: $(2, 3)$. Assume flow value is $\flow_{23} = 3$. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{12} + \flow_{42} + \flow_{46} + \flow_{56} + \flow_{58} + \flow_{78}) - \flow_{23} = (3 + 0 + 4 + 3 + 2 + 2) - 3 = 14 - 3 = 11$.
Cut Set 3: $S = \{1, 2, 3, 4\}$. Edges leaving $S$: $(3, 5), (4, 6)$. Assume flow values are $\flow_{35} = 8, \flow_{46} = 4$. Edges entering $S$: $(5, 4), (6, 2)$. Assume flow values are $\flow_{54} = 1, \flow_{62} = 0$. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{35} + \flow_{46}) - (\flow_{54} + \flow_{62}) = (8 + 4) - (1 + 0) = 12 - 1 = 11$.
Cut Set 4: $S = \{1, 4\}$. Edges leaving $S$: $(1, 3), (1, 2), (4, 2), (4, 6)$. Assume flow values are $\flow_{13} = 8, \flow_{12} = 3, \flow_{42} = 0, \flow_{46} = 4$. Edges entering $S$: $(3, 4), (5, 4)$. Assume flow values are $\flow_{34} = 3, \flow_{54} = 1$. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{13} + \flow_{12} + \flow_{42} + \flow_{46}) - (\flow_{34} + \flow_{54}) = (8 + 3 + 0 + 4) - (3 + 1) = 15 - 4 = 11$.

In all four examples, the flow through the cut is the same, which is 11. This illustrates a general theorem that we will discuss next.

Theorems and Properties of Cuts

Theorem: Flow Through Any Cut Equals the Value of the Flow

Let $\flow$ be an $\source-\sink$ flow in a network, and let $S$ be any $\source-\sink$ cut set. Then the flow through the cut $S$, $\divergence_{\flow}(S)$, is equal to the value of the flow $\flowvalueX$. \[\divergence_{\flow}(S) = \flowvalueX\]

Proof of the Theorem

Proof. Proof. By definition, the value of the flow $\flowvalueX$ is equal to the divergence at the source node $\source$, i.e., $\flowvalueX = \divergence_{\flow}(\{\source\})$. We can express this as the sum of divergences over all nodes $v$ in the set $S$:

\[\flowvalueX = \divergence_{\flow}(\{\source\}) = \sum_{v \in \{\source\}} \divergence_{\flow}(v)\]

Since for any node $v \neq \source, \sink$, the divergence is zero (flow conservation), and for any cut set $S$ that contains $\source$ but not $\sink$, we can extend the sum to all nodes in $S$:

\[\flowvalueX = \sum_{v \in \{\source\}} \divergence_{\flow}(v) = \sum_{v \in S} \divergence_{\flow}(v)\]

because for all $v \in S \setminus \{\source\}$, $\divergence_{\flow}(v) = 0$.

Now, let’s expand the definition of divergence for each node $v \in S$:

\[\sum_{v \in S} \divergence_{\flow}(v) = \sum_{v \in S} \left( \sum_{(v,j) \in E} \flow_{vj} - \sum_{(i,v) \in E} \flow_{iv} \right)\]

We can rewrite this sum by considering edges $(i,j)$. For each edge $(i,j)$, there are a few cases:

Case 1: Both $i \in S$ and $j \in S$. In this case, $\flow_{ij}$ is counted with a positive sign when considering divergence at node $i$, and with a negative sign when considering divergence at node $j$. When we sum over all $v \in S$, the contributions from such edges cancel out.
Case 2: $i \in S$ and $j \notin S$. In this case, $\flow_{ij}$ is counted with a positive sign when considering divergence at node $i$. It is not counted (or contributes zero) for any other node in $S$.
Case 3: $i \notin S$ and $j \in S$. In this case, $\flow_{ij}$ is counted with a negative sign when considering divergence at node $j$. It is not counted (or contributes zero) for any other node in $S$.
Case 4: Both $i \notin S$ and $j \notin S$. In this case, $\flow_{ij}$ is not counted when considering divergence at any node in $S$.

Therefore, when we sum $\sum_{v \in S} \divergence_{\flow}(v)$, we are left with the sum of flows out of $S$ minus the sum of flows into $S$:

\[\begin{aligned} \sum_{v \in S} \left( \sum_{(v,j) \in E} \flow_{vj} - \sum_{(i,v) \in E} \flow_{iv} \right) &= \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} - \sum_{\substack{(i,j) \in E \\ i \notin S, j \in S}} \flow_{ij} \\ &= \divergence_{\flow}(S) \end{aligned}\]

Thus, we have shown that $\flowvalueX = \sum_{v \in S} \divergence_{\flow}(v) = \divergence_{\flow}(S)$. Hence, the flow through any cut $S$ is equal to the value of the flow. ◻

Capacity of a Cut

Definition of Cut Capacity

Now, let’s define the capacity of a cut.

Given an $\source-\sink$ cut set $S$, the capacity of the cut $S$, denoted as $\capacitycut$, is the sum of the capacities of all edges going out of $S$. Formally, \[\capacitycut = \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \capacity_{ij}\] Note that we only consider the capacities of the edges going from $S$ to $V \setminus S$. Edges going into $S$ are not considered in the cut capacity.

Cut Capacity vs. Flow Through a Cut

It is important to distinguish between the flow through a cut and the capacity of a cut.

Flow through a cut $\divergence_{\flow}(S)$ is the net flow out of $S$, considering both outgoing and incoming flow.
Capacity of a cut $\capacitycut$ is the sum of capacities of only the outgoing edges from $S$.

Examples of Cut Capacity Calculation

Let’s revisit the examples from Section 2.5 and calculate the capacity for each cut set. We need to assume capacity values for the edges in the network (these were implicitly used in the transcription example, but are not explicitly given here. We will assume capacity values consistent with the transcription example).

Using the same cut sets as in Example 2.5, let’s calculate the capacity of each cut. Assume the capacities of the edges are as implicitly used in the transcription.

Cut Set 1: $S = \{1\}$. Edges leaving $S$: $(1, 3), (1, 2)$. Assume capacities are $\capacity_{13} = 10, \capacity_{12} = 20$. Capacity of $S$: $\capacity(S) = \capacity_{13} + \capacity_{12} = 10 + 20 = 30$.
Cut Set 2: $S = \{1, 3, 4, 5, 7\}$. Edges leaving $S$: $(1, 2), (4, 2), (4, 6), (5, 6), (5, 8), (7, 8)$. Assume capacities are $\capacity_{12} = 20, \capacity_{42} = 8, \capacity_{46} = 8, \capacity_{56} = 6, \capacity_{58} = 5, \capacity_{78} = 4$. Capacity of $S$: $\capacity(S) = \capacity_{12} + \capacity_{42} + \capacity_{46} + \capacity_{56} + \capacity_{58} + \capacity_{78} = 20 + 8 + 8 + 6 + 5 + 4 = 51$. (Corrected calculation from transcription).
Cut Set 3: $S = \{1, 2, 3, 4\}$. Edges leaving $S$: $(3, 5), (4, 6)$. Assume capacities are $\capacity_{35} = 12, \capacity_{46} = 8$. Capacity of $S$: $\capacity(S) = \capacity_{35} + \capacity_{46} = 12 + 8 = 20$.
Cut Set 4: $S = \{1, 4\}$. Edges leaving $S$: $(1, 3), (1, 2), (4, 2), (4, 6)$. Assume capacities are $\capacity_{13} = 10, \capacity_{12} = 20, \capacity_{42} = 16, \capacity_{46} = 0$. Capacity of $S$: $\capacity(S) = \capacity_{13} + \capacity_{12} + \capacity_{42} + \capacity_{46} = 10 + 20 + 16 + 0 = 46$.

We observe that the capacities of these cuts are different: 30, 51, 20, and 46.

Cut Capacity as an Upper Bound on Flow

For any $\source-\sink$ cut $S$ and any $\source-\sink$ flow $\flow$, the flow through the cut is bounded by the capacity of the cut.

For any $\source-\sink$ cut $S$ and any $\source-\sink$ flow $\flow$, the flow through the cut $S$ is less than or equal to the capacity of the cut $S$: \[\divergence_{\flow}(S) \leq \capacitycut\]

Proof. Proof. By definition, the flow through the cut is:

\[\divergence_{\flow}(S) = \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} - \sum_{\substack{(i,j) \in E \\ i \notin S, j \in S}} \flow_{ij}\]

Since flow values are non-negative, $\flow_{ij} \geq 0$, we have:

\[\divergence_{\flow}(S) \leq \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij}\]

Also, for any edge $(i,j)$, the flow is limited by the capacity, $\flow_{ij} \leq \capacity_{ij}$. Therefore, for edges going out of $S$:

\[\sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} \leq \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \capacity_{ij} = \capacitycut\]

Combining these inequalities, we get $\divergence_{\flow}(S) \leq \capacitycut$. ◻

Max-Flow Min-Cut Theorem (Weak Form)

Maximum Flow is Bounded by Minimum Cut Capacity

Since the flow through any cut is equal to the value of the flow, and the flow through any cut is less than or equal to the capacity of that cut, it follows that the value of any $\source-\sink$ flow is bounded by the capacity of any $\source-\sink$ cut.

Let $f_{max}$ be the maximum value of an $\source-\sink$ flow, and let $c_{min}$ be the minimum capacity among all $\source-\sink$ cuts.

The maximum value of an $\source-\sink$ flow is less than or equal to the minimum capacity of an $\source-\sink$ cut. \[f_{max} \leq c_{min}\]

Proof. Proof. Let $\flow$ be any $\source-\sink$ flow and $S$ be any $\source-\sink$ cut. We know that $\flowvalueX = \divergence_{\flow}(S) \leq \capacitycut$. Since this holds for any flow $\flow$ and any cut $S$, it must also hold for the maximum flow and the minimum cut capacity. Therefore,

\[\max_{\flow} \{\flowvalueX\} \leq \min_{S} \{\capacitycut\}\]

which is $f_{max} \leq c_{min}$. ◻

Maximum Flow and Minimum Cut Problems

Definitions

Maximum Flow

The maximum flow problem is to find an $\source-\sink$ flow $\flow$ such that the value of the flow $\flowvalueX$ is maximized.

Minimum Cut

The minimum cut problem is to find an $\source-\sink$ cut $S$ such that the capacity of the cut $\capacitycut$ is minimized.

The Minimum Cut Problem

The minimum cut problem is concerned with finding a partition of the vertices that separates the source from the sink with the minimum total capacity of edges going from the source side to the sink side.

Minimum Cut in Undirected Graphs

The concept of minimum cut can also be defined for undirected graphs. In an undirected graph with capacities on edges and two specified vertices $\source$ and $\sink$, a cut is a partition of vertices into two sets $S$ and $V \setminus S$ such that $\source \in S$ and $\sink \in V \setminus S$. The capacity of the cut is the sum of capacities of all edges that have one endpoint in $S$ and the other in $V \setminus S$. The minimum cut problem is to find a cut with the minimum capacity.

Reduction of Undirected to Directed Graphs

The minimum cut problem in an undirected graph can be reduced to the minimum cut problem in a directed graph. For each undirected edge between vertices $u$ and $v$ with capacity $c$, we can replace it with two directed edges: $(u, v)$ and $(v, u)$, both with capacity $c$. Then, we can solve the minimum cut problem in the resulting directed graph.

Relationship Between Minimum Cut and Maximum Flow

Intuitive Understanding

Intuitively, a minimum cut represents a bottleneck in the network. It is a set of edges that, if "removed" (in terms of capacity), would most restrict the flow from source to sink. The Max-Flow Min-Cut Theorem (in its strong form, which will be discussed later) states that the maximum flow is exactly equal to the capacity of the minimum cut. This means that the bottleneck capacity defined by the minimum cut precisely limits the maximum flow that can be pushed through the network.

Algorithmic Connection

Algorithms for finding the maximum flow, such as the Ford-Fulkerson algorithm, can also be used to find a minimum cut. In fact, the process of finding a maximum flow often naturally leads to the identification of a minimum cut. When a maximum flow is achieved, there will be a "bottleneck" cut that is saturated, and this cut turns out to be a minimum cut.

Applications of Minimum Cuts

Minimum cut problems have various applications in different fields.

Network Disconnection

One significant application is in network disconnection problems. For example, in telecommunications or transportation networks, we might want to find the minimum cost to disrupt the connection between two points. The capacities of edges can represent the "strength" of connections, and finding a minimum cut helps identify the weakest links that, when severed, will disconnect the network most effectively at the least cost. This has applications in scenarios like isolating enemy troops by disrupting supply lines, as mentioned in the transcription.

Finding the Global Minimum Cut

The discussion in the transcription touches upon finding a global minimum cut, which is not necessarily between a specific source and sink, but rather the minimum cut that partitions the graph into any two disconnected components.

Reducing Complexity by Fixing the Source Node

To find a global minimum cut in a network, one might initially think of trying all pairs of vertices as source and sink and finding the minimum cut for each pair. However, as mentioned in the lecture, we can optimize this. We can fix a source node, say node 1, and then for each other node $v \neq 1$, find the minimum cut that separates node 1 from $v$. The minimum among all these cuts will be the global minimum cut in the network. This reduces the number of minimum cut computations needed. Instead of considering $O(n^2)$ pairs of (source, sink), we only need to consider $O(n)$ pairs by fixing one node as a "source" and varying the "sink" across all other nodes.

Conclusion

In this lecture, we defined the concept of flow through a cut and the capacity of a cut. We established that the flow through any $\source-\sink$ cut is equal to the value of the flow, and that the capacity of a cut provides an upper bound on the flow through it. We introduced the weak form of the Max-Flow Min-Cut Theorem, stating that the maximum flow is bounded by the minimum cut capacity. We also briefly discussed the minimum cut problem and its applications, and hinted at the strong connection between maximum flow and minimum cut, which will be explored further. Key takeaways include understanding how cuts represent bottlenecks in flow networks and how their capacities limit the maximum achievable flow. Further questions to consider might include: How can we algorithmically find the maximum flow and minimum cut? And what is the strong form of the Max-Flow Min-Cut Theorem and its implications?

--- title: "Flow Through Cuts in Networks" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture introduces the concept of flow through a cut in network flow theory. We will extend the notion of divergence from a single node to a set of nodes, defining the flow across a cut set. We will explore the properties of cut sets, particularly those that separate the source and sink nodes. A crucial theorem stating that the flow through any cut is equal to the value of the flow will be presented and proved. Furthermore, we will define the capacity of a cut and discuss its relationship to the flow through the cut, leading to the weak form of the Max-Flow Min-Cut Theorem. Finally, we will touch upon the minimum cut problem and its applications, highlighting the connection between minimum cuts and maximum flows. # Flow Through a Cut ## Definition of Flow Across a Cut Let $S$ be a set of vertices and $\flow$ be a flow in a network. We define the flow through $S$, denoted as $\divergence_{\flow}(S)$, as the net flow out of the set $S$. Formally, it is given by: ::: tcolorbox $$\divergence_{\flow}(S) = \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} - \sum_{\substack{(i,j) \in E \\ i \notin S, j \in S}} \flow_{ij}$$ ::: where the first sum is over all edges $(i,j)$ leaving $S$ (i.e., starting in $S$ and ending outside $S$), and the second sum is over all edges $(i,j)$ entering $S$ (i.e., starting outside $S$ and ending in $S$). In words, the flow through $S$ is the total flow out of $S$ minus the total flow into $S$. ::: tcolorbox This definition generalizes the concept of divergence at a single node. Recall that the divergence at a node $v$ was defined as the total outflow from $v$ minus the total inflow into $v$. Now, $\divergence_{\flow}(S)$ extends this to an entire set of nodes $S$, representing the net flow from $S$ to the rest of the network. ::: ## Cut Sets and Their Properties ### Source and Sink Separation In the context of network flows from a source node $\source$ to a sink node $\sink$, we are particularly interested in sets of vertices $S$ that contain the source $\source$ but not the sink $\sink$. Such sets are called **cut sets** or simply **cuts**. ::: tcolorbox A **cut set** (or **cut**) in a network with source $\source$ and sink $\sink$ is a set of vertices $S$ such that: - $\source \in S$ - $\sink \notin S$ A cut set $S$ effectively partitions the vertices of the graph into two disjoint sets, $S$ and $V \setminus S$, where $V$ is the set of all vertices. The source is in $S$, and the sink is in $V \setminus S$. ::: In graph theory, the term \"cut\" is often used to refer to the set of edges that, when removed, disconnect the graph. In our context, a cut set $S$ induces a set of edges that \"separate\" the source from the sink. ### Number of Possible Cuts Consider a network with $n$ vertices. If we fix the source $\source$ and the sink $\sink$, and we want to count the number of possible cut sets $S$. Since $\source$ must be in $S$ and $\sink$ must be outside $S$, we are free to choose for each of the remaining $n-2$ vertices whether they belong to $S$ or not. Therefore, there are $2^{n-2}$ possible cut sets that separate a given source $\source$ from a sink $\sink$ in a network with $n$ vertices. ## Relationship to Divergence As mentioned earlier, the definition of flow through a cut $\divergence_{\flow}(S)$ is an extension of the divergence at a single node. Specifically, if we consider a cut set $S$ that consists of only the source node $\source$, i.e., $S = \{\source\}$, then the flow through this cut is: ::: tcolorbox $$\divergence_{\flow}(\{\source\}) = \sum_{\substack{(\source,j) \in E \\ j \neq \source}} \flow_{\source j} - \sum_{\substack{(i,\source) \in E \\ i \neq \source}} \flow_{i \source}$$ ::: This is exactly the definition of the value of the flow $\flowvalueX$, which represents the net flow out of the source node. ## Flow Through a Specific Cut: The Source Node The value of a flow $\flowvalueX$ is, by definition, the net flow out of the source node $\source$. As discussed above, this is a special case of the flow through a cut, where the cut set $S$ is just the set containing the source node itself, $S = \{\source\}$. Thus, the value of the flow $\flowvalueX$ can be seen as the flow through the cut $S = \{\source\}$. ## Examples of Flow Through Different Cuts Consider a network with a flow. Let's examine some examples to calculate the flow through different cut sets. ::: tcolorbox Consider a flow network (diagram of the network and flow values are assumed to be provided as in the transcription, but are not available here for reproduction). Let's analyze four different cut sets $S$ and calculate the flow through each of them. Assume the network has nodes labeled 1 to 8, with node 1 as the source and node 8 as the sink. 1. **Cut Set 1:** $S = \{1\}$. Edges leaving $S$: $(1, 3), (1, 2)$. Assume flow values are $\flow_{13} = 8, \flow_{12} = 3$. Edges entering $S$: None. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{13} + \flow_{12}) - 0 = 8 + 3 = 11$. 2. **Cut Set 2:** $S = \{1, 3, 4, 5, 7\}$. Edges leaving $S$: $(1, 2), (4, 2), (4, 6), (5, 6), (5, 8), (7, 8)$. Assume flow values are $\flow_{12} = 3, \flow_{42} = 0, \flow_{46} = 4, \flow_{56} = 3, \flow_{58} = 2, \flow_{78} = 2$. Edges entering $S$: $(2, 3)$. Assume flow value is $\flow_{23} = 3$. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{12} + \flow_{42} + \flow_{46} + \flow_{56} + \flow_{58} + \flow_{78}) - \flow_{23} = (3 + 0 + 4 + 3 + 2 + 2) - 3 = 14 - 3 = 11$. 3. **Cut Set 3:** $S = \{1, 2, 3, 4\}$. Edges leaving $S$: $(3, 5), (4, 6)$. Assume flow values are $\flow_{35} = 8, \flow_{46} = 4$. Edges entering $S$: $(5, 4), (6, 2)$. Assume flow values are $\flow_{54} = 1, \flow_{62} = 0$. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{35} + \flow_{46}) - (\flow_{54} + \flow_{62}) = (8 + 4) - (1 + 0) = 12 - 1 = 11$. 4. **Cut Set 4:** $S = \{1, 4\}$. Edges leaving $S$: $(1, 3), (1, 2), (4, 2), (4, 6)$. Assume flow values are $\flow_{13} = 8, \flow_{12} = 3, \flow_{42} = 0, \flow_{46} = 4$. Edges entering $S$: $(3, 4), (5, 4)$. Assume flow values are $\flow_{34} = 3, \flow_{54} = 1$. Flow through $S$: $\divergence_{\flow}(S) = (\flow_{13} + \flow_{12} + \flow_{42} + \flow_{46}) - (\flow_{34} + \flow_{54}) = (8 + 3 + 0 + 4) - (3 + 1) = 15 - 4 = 11$. In all four examples, the flow through the cut is the same, which is 11. This illustrates a general theorem that we will discuss next. ::: # Theorems and Properties of Cuts ## Theorem: Flow Through Any Cut Equals the Value of the Flow ::: tcolorbox Let $\flow$ be an $\source-\sink$ flow in a network, and let $S$ be any $\source-\sink$ cut set. Then the flow through the cut $S$, $\divergence_{\flow}(S)$, is equal to the value of the flow $\flowvalueX$. $$\divergence_{\flow}(S) = \flowvalueX$$ ::: ### Proof of the Theorem ::::::: proof *Proof.* By definition, the value of the flow $\flowvalueX$ is equal to the divergence at the source node $\source$, i.e., $\flowvalueX = \divergence_{\flow}(\{\source\})$. We can express this as the sum of divergences over all nodes $v$ in the set $S$: ::: tcolorbox $$\flowvalueX = \divergence_{\flow}(\{\source\}) = \sum_{v \in \{\source\}} \divergence_{\flow}(v)$$ ::: Since for any node $v \neq \source, \sink$, the divergence is zero (flow conservation), and for any cut set $S$ that contains $\source$ but not $\sink$, we can extend the sum to all nodes in $S$: ::: tcolorbox $$\flowvalueX = \sum_{v \in \{\source\}} \divergence_{\flow}(v) = \sum_{v \in S} \divergence_{\flow}(v)$$ ::: because for all $v \in S \setminus \{\source\}$, $\divergence_{\flow}(v) = 0$. Now, let's expand the definition of divergence for each node $v \in S$: ::: tcolorbox $$\sum_{v \in S} \divergence_{\flow}(v) = \sum_{v \in S} \left( \sum_{(v,j) \in E} \flow_{vj} - \sum_{(i,v) \in E} \flow_{iv} \right)$$ ::: We can rewrite this sum by considering edges $(i,j)$. For each edge $(i,j)$, there are a few cases: - Case 1: Both $i \in S$ and $j \in S$. In this case, $\flow_{ij}$ is counted with a positive sign when considering divergence at node $i$, and with a negative sign when considering divergence at node $j$. When we sum over all $v \in S$, the contributions from such edges cancel out. - Case 2: $i \in S$ and $j \notin S$. In this case, $\flow_{ij}$ is counted with a positive sign when considering divergence at node $i$. It is not counted (or contributes zero) for any other node in $S$. - Case 3: $i \notin S$ and $j \in S$. In this case, $\flow_{ij}$ is counted with a negative sign when considering divergence at node $j$. It is not counted (or contributes zero) for any other node in $S$. - Case 4: Both $i \notin S$ and $j \notin S$. In this case, $\flow_{ij}$ is not counted when considering divergence at any node in $S$. Therefore, when we sum $\sum_{v \in S} \divergence_{\flow}(v)$, we are left with the sum of flows out of $S$ minus the sum of flows into $S$: ::: tcolorbox $$\begin{aligned} \sum_{v \in S} \left( \sum_{(v,j) \in E} \flow_{vj} - \sum_{(i,v) \in E} \flow_{iv} \right) &= \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} - \sum_{\substack{(i,j) \in E \\ i \notin S, j \in S}} \flow_{ij} \\ &= \divergence_{\flow}(S) \end{aligned}$$ ::: Thus, we have shown that $\flowvalueX = \sum_{v \in S} \divergence_{\flow}(v) = \divergence_{\flow}(S)$. Hence, the flow through any cut $S$ is equal to the value of the flow. ◻ ::::::: ## Capacity of a Cut ### Definition of Cut Capacity Now, let's define the capacity of a cut. ::: tcolorbox Given an $\source-\sink$ cut set $S$, the **capacity of the cut** $S$, denoted as $\capacitycut$, is the sum of the capacities of all edges going out of $S$. Formally, $$\capacitycut = \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \capacity_{ij}$$ Note that we only consider the capacities of the edges going from $S$ to $V \setminus S$. Edges going into $S$ are not considered in the cut capacity. ::: ### Cut Capacity vs. Flow Through a Cut It is important to distinguish between the flow through a cut and the capacity of a cut. - **Flow through a cut** $\divergence_{\flow}(S)$ is the net flow out of $S$, considering both outgoing and incoming flow. - **Capacity of a cut** $\capacitycut$ is the sum of capacities of only the outgoing edges from $S$. ## Examples of Cut Capacity Calculation Let's revisit the examples from Section 2.5 and calculate the capacity for each cut set. We need to assume capacity values for the edges in the network (these were implicitly used in the transcription example, but are not explicitly given here. We will assume capacity values consistent with the transcription example). ::: tcolorbox Using the same cut sets as in Example 2.5, let's calculate the capacity of each cut. Assume the capacities of the edges are as implicitly used in the transcription. 1. **Cut Set 1:** $S = \{1\}$. Edges leaving $S$: $(1, 3), (1, 2)$. Assume capacities are $\capacity_{13} = 10, \capacity_{12} = 20$. Capacity of $S$: $\capacity(S) = \capacity_{13} + \capacity_{12} = 10 + 20 = 30$. 2. **Cut Set 2:** $S = \{1, 3, 4, 5, 7\}$. Edges leaving $S$: $(1, 2), (4, 2), (4, 6), (5, 6), (5, 8), (7, 8)$. Assume capacities are $\capacity_{12} = 20, \capacity_{42} = 8, \capacity_{46} = 8, \capacity_{56} = 6, \capacity_{58} = 5, \capacity_{78} = 4$. Capacity of $S$: $\capacity(S) = \capacity_{12} + \capacity_{42} + \capacity_{46} + \capacity_{56} + \capacity_{58} + \capacity_{78} = 20 + 8 + 8 + 6 + 5 + 4 = 51$. (Corrected calculation from transcription). 3. **Cut Set 3:** $S = \{1, 2, 3, 4\}$. Edges leaving $S$: $(3, 5), (4, 6)$. Assume capacities are $\capacity_{35} = 12, \capacity_{46} = 8$. Capacity of $S$: $\capacity(S) = \capacity_{35} + \capacity_{46} = 12 + 8 = 20$. 4. **Cut Set 4:** $S = \{1, 4\}$. Edges leaving $S$: $(1, 3), (1, 2), (4, 2), (4, 6)$. Assume capacities are $\capacity_{13} = 10, \capacity_{12} = 20, \capacity_{42} = 16, \capacity_{46} = 0$. Capacity of $S$: $\capacity(S) = \capacity_{13} + \capacity_{12} + \capacity_{42} + \capacity_{46} = 10 + 20 + 16 + 0 = 46$. We observe that the capacities of these cuts are different: 30, 51, 20, and 46. ::: ## Cut Capacity as an Upper Bound on Flow For any $\source-\sink$ cut $S$ and any $\source-\sink$ flow $\flow$, the flow through the cut is bounded by the capacity of the cut. ::: tcolorbox For any $\source-\sink$ cut $S$ and any $\source-\sink$ flow $\flow$, the flow through the cut $S$ is less than or equal to the capacity of the cut $S$: $$\divergence_{\flow}(S) \leq \capacitycut$$ ::: :::::: proof *Proof.* By definition, the flow through the cut is: ::: tcolorbox $$\divergence_{\flow}(S) = \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} - \sum_{\substack{(i,j) \in E \\ i \notin S, j \in S}} \flow_{ij}$$ ::: Since flow values are non-negative, $\flow_{ij} \geq 0$, we have: ::: tcolorbox $$\divergence_{\flow}(S) \leq \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij}$$ ::: Also, for any edge $(i,j)$, the flow is limited by the capacity, $\flow_{ij} \leq \capacity_{ij}$. Therefore, for edges going out of $S$: ::: tcolorbox $$\sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \flow_{ij} \leq \sum_{\substack{(i,j) \in E \\ i \in S, j \notin S}} \capacity_{ij} = \capacitycut$$ ::: Combining these inequalities, we get $\divergence_{\flow}(S) \leq \capacitycut$. ◻ :::::: ## Max-Flow Min-Cut Theorem (Weak Form) ### Maximum Flow is Bounded by Minimum Cut Capacity Since the flow through any cut is equal to the value of the flow, and the flow through any cut is less than or equal to the capacity of that cut, it follows that the value of any $\source-\sink$ flow is bounded by the capacity of any $\source-\sink$ cut. Let $f_{max}$ be the maximum value of an $\source-\sink$ flow, and let $c_{min}$ be the minimum capacity among all $\source-\sink$ cuts. ::: tcolorbox The maximum value of an $\source-\sink$ flow is less than or equal to the minimum capacity of an $\source-\sink$ cut. $$f_{max} \leq c_{min}$$ ::: :::: proof *Proof.* Let $\flow$ be any $\source-\sink$ flow and $S$ be any $\source-\sink$ cut. We know that $\flowvalueX = \divergence_{\flow}(S) \leq \capacitycut$. Since this holds for any flow $\flow$ and any cut $S$, it must also hold for the maximum flow and the minimum cut capacity. Therefore, ::: tcolorbox $$\max_{\flow} \{\flowvalueX\} \leq \min_{S} \{\capacitycut\}$$ ::: which is $f_{max} \leq c_{min}$. ◻ :::: # Maximum Flow and Minimum Cut Problems ## Definitions ### Maximum Flow ::: tcolorbox The **maximum flow problem** is to find an $\source-\sink$ flow $\flow$ such that the value of the flow $\flowvalueX$ is maximized. ::: ### Minimum Cut ::: tcolorbox The **minimum cut problem** is to find an $\source-\sink$ cut $S$ such that the capacity of the cut $\capacitycut$ is minimized. ::: ## The Minimum Cut Problem The minimum cut problem is concerned with finding a partition of the vertices that separates the source from the sink with the minimum total capacity of edges going from the source side to the sink side. ### Minimum Cut in Undirected Graphs The concept of minimum cut can also be defined for undirected graphs. In an undirected graph with capacities on edges and two specified vertices $\source$ and $\sink$, a cut is a partition of vertices into two sets $S$ and $V \setminus S$ such that $\source \in S$ and $\sink \in V \setminus S$. The capacity of the cut is the sum of capacities of all edges that have one endpoint in $S$ and the other in $V \setminus S$. The minimum cut problem is to find a cut with the minimum capacity. ### Reduction of Undirected to Directed Graphs The minimum cut problem in an undirected graph can be reduced to the minimum cut problem in a directed graph. For each undirected edge between vertices $u$ and $v$ with capacity $c$, we can replace it with two directed edges: $(u, v)$ and $(v, u)$, both with capacity $c$. Then, we can solve the minimum cut problem in the resulting directed graph. ## Relationship Between Minimum Cut and Maximum Flow ### Intuitive Understanding Intuitively, a minimum cut represents a bottleneck in the network. It is a set of edges that, if \"removed\" (in terms of capacity), would most restrict the flow from source to sink. The Max-Flow Min-Cut Theorem (in its strong form, which will be discussed later) states that the maximum flow is exactly equal to the capacity of the minimum cut. This means that the bottleneck capacity defined by the minimum cut precisely limits the maximum flow that can be pushed through the network. ### Algorithmic Connection Algorithms for finding the maximum flow, such as the Ford-Fulkerson algorithm, can also be used to find a minimum cut. In fact, the process of finding a maximum flow often naturally leads to the identification of a minimum cut. When a maximum flow is achieved, there will be a \"bottleneck\" cut that is saturated, and this cut turns out to be a minimum cut. ## Applications of Minimum Cuts Minimum cut problems have various applications in different fields. ### Network Disconnection One significant application is in network disconnection problems. For example, in telecommunications or transportation networks, we might want to find the minimum cost to disrupt the connection between two points. The capacities of edges can represent the \"strength\" of connections, and finding a minimum cut helps identify the weakest links that, when severed, will disconnect the network most effectively at the least cost. This has applications in scenarios like isolating enemy troops by disrupting supply lines, as mentioned in the transcription. ## Finding the Global Minimum Cut The discussion in the transcription touches upon finding a global minimum cut, which is not necessarily between a specific source and sink, but rather the minimum cut that partitions the graph into any two disconnected components. ### Reducing Complexity by Fixing the Source Node To find a global minimum cut in a network, one might initially think of trying all pairs of vertices as source and sink and finding the minimum cut for each pair. However, as mentioned in the lecture, we can optimize this. We can fix a source node, say node 1, and then for each other node $v \neq 1$, find the minimum cut that separates node 1 from $v$. The minimum among all these cuts will be the global minimum cut in the network. This reduces the number of minimum cut computations needed. Instead of considering $O(n^2)$ pairs of (source, sink), we only need to consider $O(n)$ pairs by fixing one node as a \"source\" and varying the \"sink\" across all other nodes. # Conclusion In this lecture, we defined the concept of flow through a cut and the capacity of a cut. We established that the flow through any $\source-\sink$ cut is equal to the value of the flow, and that the capacity of a cut provides an upper bound on the flow through it. We introduced the weak form of the Max-Flow Min-Cut Theorem, stating that the maximum flow is bounded by the minimum cut capacity. We also briefly discussed the minimum cut problem and its applications, and hinted at the strong connection between maximum flow and minimum cut, which will be explored further. Key takeaways include understanding how cuts represent bottlenecks in flow networks and how their capacities limit the maximum achievable flow. Further questions to consider might include: How can we algorithmically find the maximum flow and minimum cut? And what is the strong form of the Max-Flow Min-Cut Theorem and its implications?