RO_(36)_Reti_di_flusso.mp4

Author

Your Name

Published

January 30, 2025

Introduction

This lecture introduces flow networks, a fundamental concept for modeling the transportation of commodities from producers to consumers. We will define flow networks, discuss arc capacities and costs, and explore real-world examples. We will formally define flow, feasibility, and flow divergence in nodes. We will also discuss source and sink nodes, flow conservation, and circulations. Finally, we will touch upon optimization problems in flow networks, such as the maximum flow problem, the minimum cost flow problem, and the flow decomposition theorem.

Flow Networks and Fundamental Concepts

Definition of a Flow Network

A flow network models the movement of a commodity from producers to consumers through a network, represented as a directed graph.

A flow network is a triple $G = (V, A, K, C)$, where:

$G = (V, A)$ is a directed graph, with $V$ being the set of nodes and $A$ being the set of arcs.
$K: A \to \mathbb{R}_{\geq 0}$ is a capacity function that assigns a non-negative real number $K_{ij}$ to each arc $(i, j) \in A$, representing the maximum amount of commodity that can flow through the arc.
$C: A \to \mathbb{R}$ is a cost function that assigns a real number $C_{ij}$ to each arc $(i, j) \in A$, representing the cost per unit of commodity flowing through the arc.

Arc Capacity and Cost

Arc Capacity ($K_{ij}$): Represents the maximum amount of commodity that can pass through an arc $(i, j)$. It can be thought of as the bandwidth or the physical limitation of the arc.
Arc Cost ($C_{ij}$): Represents the cost incurred for each unit of commodity that flows through an arc $(i, j)$. This could be a toll, operational cost, or any other expense associated with using the arc.

Real-World Examples of Flow Networks

Road Networks with Bridges: If arcs represent roads and nodes represent intersections, the capacity of an arc representing a bridge could be the maximum weight it can support.
Transportation Lines: Arcs can represent train or bus lines between locations (nodes). The capacity could be the maximum number of passengers per unit of time.
Pipelines: If arcs represent pipes carrying fluids, the capacity is the maximum volume of fluid that can flow per unit of time, determined by the pipe’s diameter.

Definition of Flow and Feasibility

A flow in a network $G = (V, A, K, C)$ is a vector $X \in \mathbb{R}^{|A|}$, where each component $X_{ij}$ represents the amount of commodity flowing through arc $(i, j) \in A$.

A flow $X$ is feasible if it satisfies the capacity constraints for every arc $(i, j) \in A$: \[0 \leq X_{ij} \leq K_{ij} \quad \forall (i, j) \in A\] This means the flow through each arc is non-negative and does not exceed the arc’s capacity.

Saturated and Empty Arcs

Saturated Arc: An arc $(i, j)$ is saturated with respect to a flow $X$ if $X_{ij} = K_{ij}$. This means the arc is carrying the maximum possible flow.
Empty Arc: An arc $(i, j)$ is empty or unloaded with respect to a flow $X$ if $X_{ij} = 0$. This means no commodity is flowing through the arc.

Flow Divergence

Definition of Flow Divergence at a Node

For a given flow $X$ in a network $G=(V,A,K,C)$ and a node $v \in V$, the flow divergence at node $v$, denoted as $\text{div}(v)$, is defined as the total outflow minus the total inflow at that node: \[\text{div}(v) = \sum_{(v, j) \in A} X_{vj} - \sum_{(i, v) \in A} X_{iv}\] Where $\delta^+(v) = \{(v, j) \in A\}$ is the set of outgoing arcs from $v$, and $\delta^-(v) = \{(i, v) \in A\}$ is the set of incoming arcs to $v$. We can write this as: \[\text{div}(v) = X(\delta^+(v)) - X(\delta^-(v))\]

Source and Sink Nodes

Based on the divergence at each node, we can classify nodes:

Source Node: A node $s$ with $\text{div}(s) > 0$. This indicates that more flow is leaving the node than entering it, suggesting it is a source of commodity.
Sink Node: A node $t$ with $\text{div}(t) < 0$. This indicates that more flow is entering the node than leaving it, suggesting it is a destination or sink of commodity.
Transshipment Node: A node $v$ with $\text{div}(v) = 0$. This indicates that the inflow and outflow are balanced, meaning the node is merely a point of transit.

Theorem on the Sum of Divergences

For any feasible flow $X$ in a flow network $G=(V,A,K,C)$, the sum of divergences over all nodes is zero: \[\sum_{v \in V} \text{div}(v) = 0\] Furthermore, let $S = \{v \in V \mid \text{div}(v) > 0\}$ be the set of source nodes and $T = \{v \in V \mid \text{div}(v) < 0\}$ be the set of sink nodes. Then, \[\sum_{v \in S} \text{div}(v) = - \sum_{v \in T} \text{div}(v)\]

Proof. Proof. Consider the sum of divergences over all nodes: \[\sum_{v \in V} \text{div}(v) = \sum_{v \in V} \left( \sum_{(v, j) \in A} X_{vj} - \sum_{(i, v) \in A} X_{iv} \right)\] We can rewrite this sum by considering each arc $(i, j) \in A$. For each arc $(i, j)$, $X_{ij}$ is counted positively in the divergence of node $i$ and negatively in the divergence of node $j$. Thus, when we sum over all nodes, the contribution of each flow $X_{ij}$ cancels out: \[\sum_{v \in V} \text{div}(v) = \sum_{(i, j) \in A} X_{ij} - \sum_{(i, j) \in A} X_{ij} = 0\] To show the second part, we partition the set of nodes $V$ into three disjoint sets: $S$, $T$, and $N = \{v \in V \mid \text{div}(v) = 0\}$. Then, \[\sum_{v \in V} \text{div}(v) = \sum_{v \in S} \text{div}(v) + \sum_{v \in N} \text{div}(v) + \sum_{v \in T} \text{div}(v) = 0\] Since $\text{div}(v) = 0$ for all $v \in N$, we have $\sum_{v \in N} \text{div}(v) = 0$. Therefore, \[\sum_{v \in S} \text{div}(v) + \sum_{v \in T} \text{div}(v) = 0\] \[\sum_{v \in S} \text{div}(v) = - \sum_{v \in T} \text{div}(v)\] This shows that the total excess outflow from source nodes is equal to the total excess inflow into sink nodes. ◻

Flow Conservation

A flow $X$ is conserved at node $v \in V$ if the flow divergence at $v$ is zero, i.e., $\text{div}(v) = 0$. This means that the total inflow into node $v$ is equal to the total outflow from node $v$.

Circulations: Flows with Zero Divergence

A flow $X$ in a network $G$ is called a circulation if it is conserved at every node $v \in V$, i.e., $\text{div}(v) = 0$ for all $v \in V$. In a circulation, the commodity flows around the network without any net source or sink.

Consider a network and a flow assignment (red numbers) with capacities (numbers in square brackets) as described in the transcription. Verify that for each node, the inflow equals the outflow, confirming it’s a circulation. (Diagram from transcription would be helpful here if possible to recreate in TikZ).

Source-Sink Flows (s-t Flows)

Definition of an s-t Flow

Given a flow network $G=(V, A, K, C)$ with a designated source node $s \in V$ and a sink node $t \in V$, an s-t flow (or flow from $s$ to $t$) is a feasible flow $X$ such that flow conservation holds at every node $v \in V \setminus \{s, t\}$. That is, $\text{div}(v) = 0$ for all $v \in V \setminus \{s, t\}$.

Value of an s-t Flow

The value of an s-t flow $X$, denoted by $\phi(X)$, is the flow divergence at the source node $s$: \[\phi(X) = \text{div}(s) = \sum_{(s, j) \in A} X_{sj} - \sum_{(i, s) \in A} X_{is}\] By the Theorem on the Sum of Divergences, the value of an s-t flow is also equal to the negative of the divergence at the sink node $t$: \[\phi(X) = - \text{div}(t) = \sum_{(i, t) \in A} X_{it} - \sum_{(t, j) \in A} X_{tj}\] Thus, the value represents the net flow out of the source $s$ and into the sink $t$.

Example of an s-t Flow

Consider a network with source node $s=1$ and sink node $t=8$. A flow assignment is given in the transcription. Verify that flow conservation holds for all nodes except node 1 and node 8. Calculate the value of this s-t flow as the divergence at node 1. (Diagram from transcription would be helpful here if possible to recreate in TikZ).

Optimization Problems in Flow Networks

The Maximum Flow Problem

Given a flow network $G=(V, A, K, C)$ with source $s$ and sink $t$, the maximum flow problem is to find a feasible s-t flow $X$ that maximizes the value $\phi(X)$.

The goal is to send as much commodity as possible from the source to the sink without violating capacity constraints.

The Minimum Cost Flow Problem

Given a flow network $G=(V, A, K, C)$, a source $s$, a sink $t$, and a required flow value $B$, the minimum cost flow problem is to find a feasible s-t flow $X$ with value $\phi(X) = B$ that minimizes the total cost: \[\text{Cost}(X) = \sum_{(i, j) \in A} C_{ij} X_{ij}\]

The objective is to achieve a specific flow value from source to sink at the minimum possible cost.

Polynomial Time Solvability

Both the maximum flow problem and the minimum cost flow problem are solvable in polynomial time, meaning there exist efficient algorithms to find optimal solutions.

The Flow Decomposition Theorem

Elementary Cycles and Circular Flows

An elementary cycle $C$ in a directed graph is a sequence of nodes $v_1, v_2, \ldots, v_k, v_1$ where $v_1, v_2, \ldots, v_k$ are distinct nodes and $(v_i, v_{i+1}) \in A$ for $i=1, \ldots, k-1$ and $(v_k, v_1) \in A$.

Given an elementary cycle $C$ and a value $\tau > 0$, a circular flow $X^C_\tau$ along $C$ with value $\tau$ is defined as: \[X^C_\tau(i, j) = \begin{cases} \tau & \text{if } (i, j) \in C \\ 0 & \text{otherwise} \end{cases}\] A circular flow is a circulation.

Statement of the Flow Decomposition Theorem

Let $X$ be a circulation in a flow network $G=(V, A, K, C)$. Then, $X$ can be decomposed into a sum of elementary circular flows. Specifically, there exist elementary cycles $C_1, C_2, \ldots, C_q$ and positive values $\tau_1, \tau_2, \ldots, \tau_q$ such that: \[X = \sum_{i=1}^{q} X^{C_i}_{\tau_i}\]

Proof of the Theorem

Proof. Proof. We prove this by induction on the number of cycles in the subgraph induced by arcs with positive flow. Let $A^+(X) = \{(i, j) \in A \mid X_{ij} > 0\}$. Let $R(X)$ be the number of cycles in the subgraph $G(A^+(X)) = (V, A^+(X))$.

Base Case: If $R(X) = 0$, then $G(A^+(X))$ is acyclic. Since $X$ is a circulation, for every node $v$ with an incoming arc in $A^+(X)$, there must be an outgoing arc in $A^+(X)$ and vice-versa (unless the degree is zero). In an acyclic graph, this is impossible unless $A^+(X)$ is empty, meaning $X$ is a zero flow, which can be considered a sum of zero circular flows. If $R(X) = 1$, then $G(A^+(X))$ consists of a single elementary cycle $C$. Then $X$ must be a circular flow along $C$ with some value $\tau = \min_{(i,j) \in C} X_{ij}$.

Inductive Step: Assume the theorem holds for all circulations $X'$ with $R(X') < R(X)$. Let $X$ be a circulation with $R(X) > 0$. Since $G(A^+(X))$ has cycles, choose an elementary cycle $C$ in $G(A^+(X))$. Let $\tau = \min_{(i,j) \in C} X_{ij} > 0$. Define a circular flow $X^C_\tau$ along $C$ with value $\tau$. Consider $X' = X - X^C_\tau$.

$X'$ is still a circulation because subtracting a circulation from a circulation results in a circulation. For each arc $(i, j) \in C$, $X'_{ij} = X_{ij} - \tau \geq 0$. For at least one arc $(u, v) \in C$, $X'_{uv} = X_{uv} - \tau = 0$, because $\tau$ was chosen as the minimum flow on $C$. Thus, $A^+(X') \subsetneq A^+(X)$, which implies $R(X') < R(X)$.

By the induction hypothesis, $X'$ can be decomposed into a sum of elementary circular flows: $X' = \sum_{i=1}^{r} X^{C'_i}_{\tau'_i}$. Therefore, $X = X' + X^C_\tau = \sum_{i=1}^{r} X^{C'_i}_{\tau'_i} + X^C_\tau$. This decomposes $X$ into a sum of elementary circular flows. ◻

Corollary: Decomposition into Paths and Cycles

Let $X$ be an s-t flow with value $\phi(X) > 0$. Then $X$ can be decomposed into the sum of flows along elementary paths from $s$ to $t$ and flows along elementary cycles. Specifically, there exist elementary paths $P_1, \ldots, P_p$ from $s$ to $t$, elementary cycles $C_1, \ldots, C_q$, and positive values $y_1, \ldots, y_p$ and $\tau_1, \ldots, \tau_q$ such that: \[X = \sum_{i=1}^{p} X^{P_i}_{y_i} + \sum_{j=1}^{q} X^{C_j}_{\tau_j}\] where $X^{P_i}_{y_i}$ is the flow of value $y_i$ along path $P_i$.

Proof. Proof. To transform an s-t flow into a circulation, add a return arc $(t, s)$ to the network with infinite capacity and zero cost. Define the flow on this arc as $X_{ts} = \phi(X)$. Now, in the augmented network, the flow is conserved at all nodes, including $s$ and $t$, thus it is a circulation. By the Flow Decomposition Theorem for Circulations, this circulation can be decomposed into elementary circular flows.

Some of these cycles may contain the arc $(t, s)$. If a cycle $C$ contains $(t, s)$, then removing the arc $(t, s)$ from $C$ results in a path $P$ from $s$ to $t$. The circular flow along $C$ corresponds to a path flow along $P$ plus flow on arc $(t,s)$. Cycles that do not contain $(t, s)$ remain cycles in the original network. Summing up the path flows and the cycle flows gives the decomposition of the original s-t flow. ◻

Example of Flow Decomposition

Refer to the example of s-t flow in the transcription. Decompose the given s-t flow into path flows and cycle flows as described in the transcription. (Diagram and decomposition example from transcription would be helpful here if possible to recreate in TikZ and list paths and cycles).

Transformations and Simplifications

Modeling Undirected Arcs

An undirected arc between nodes $i$ and $j$ with capacity $K_{ij}$ and cost $C_{ij}$ can be modeled by replacing it with two directed arcs: $(i, j)$ and $(j, i)$, both with capacity $K_{ij}$ and cost $C_{ij}$.

Modeling Node Capacities

A node $v$ with capacity $K_v$ can be modeled by splitting node $v$ into two nodes $v'$ and $v''$ and adding a directed arc $(v', v'')$ with capacity $K_v$ and zero cost. All incoming arcs to $v$ are redirected to $v'$, and all outgoing arcs from $v$ are redirected from $v''$.

Eliminating Parallel Arcs

If there are multiple parallel arcs from node $i$ to node $j$, they can be replaced by a single arc from $i$ to $j$. The capacity of the new arc is the sum of the capacities of the parallel arcs, and the cost can be defined based on the problem requirements (e.g., minimum cost selection or average cost). For simplification, if costs are identical, sum capacities and keep one arc with that cost. If costs are different, more complex transformations might be needed depending on the problem (e.g., for min-cost flow, keep the arc with minimum cost for each unit of capacity). For the purpose of simplification mentioned in transcription, splitting might be used to avoid parallel arcs in theoretical discussions.

To eliminate parallel arcs in a simplified manner (as suggested by the transcription’s approach to anti-parallel arcs), for each set of parallel arcs between nodes $i$ and $j$, we can replace all but one with a path of two arcs by introducing a new intermediate node. For example, replace a parallel arc $(i,j)_2$ with a path $i \to v_{ij} \to j$. Assign the original capacity and cost to $(i, v_{ij})$ and the same capacity but zero cost to $(v_{ij}, j)$.

Eliminating Anti-Parallel Arcs

Anti-parallel arcs, i.e., arcs $(i, j)$ and $(j, i)$, can be eliminated by splitting one of them. For example, to eliminate $(j, i)$, replace it with a path $j \to v_{ji} \to i$. Assign the original capacity and cost of $(j, i)$ to $(j, v_{ji})$ and the same capacity but zero cost to $(v_{ji}, i)$.

Transforming Multiple Sources/Sinks to Single Source/Sink

If there are multiple source nodes $S_1, S_2, \ldots, S_r$ and multiple sink nodes $T_1, T_2, \ldots, T_q$, introduce a supersource node $S$ and a supersink node $T$. Add arcs from $S$ to each $S_i$ with infinite capacity and zero cost. Add arcs from each $T_j$ to $T$ with infinite capacity and zero cost. Now, the problem can be transformed into a single-source single-sink problem from $S$ to $T$.

Standard Assumptions on Source and Sink

It is often assumed that no arcs enter the source node $s$ and no arcs leave the sink node $t$. If there are such arcs, they can be removed without affecting the maximum s-t flow or minimum cost s-t flow, as flow conservation at intermediate nodes ensures that flow originates from $s$ and terminates at $t$.

Conclusion

In this lecture, we have laid the groundwork for understanding flow networks, defining key concepts such as flow, capacity, cost, and divergence. We explored the fundamental theorem on the sum of divergences and the important concept of flow conservation. We also introduced s-t flows and their values, and discussed two crucial optimization problems: maximum flow and minimum cost flow. Finally, we examined the flow decomposition theorem, which provides a valuable structural insight into flows, and discussed transformations to handle more general network configurations.

In future lectures, we will delve deeper into algorithms for solving the maximum flow and minimum cost flow problems, and explore their applications in various domains. We will also investigate the implications of the flow decomposition theorem in algorithm design and network analysis.

--- title: "RO_(36)_Reti_di_flusso.mp4" 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 flow networks, a fundamental concept for modeling the transportation of commodities from producers to consumers. We will define flow networks, discuss arc capacities and costs, and explore real-world examples. We will formally define flow, feasibility, and flow divergence in nodes. We will also discuss source and sink nodes, flow conservation, and circulations. Finally, we will touch upon optimization problems in flow networks, such as the maximum flow problem, the minimum cost flow problem, and the flow decomposition theorem. # Flow Networks and Fundamental Concepts ## Definition of a Flow Network A flow network models the movement of a commodity from producers to consumers through a network, represented as a directed graph. ::: tcolorbox A flow network is a triple $G = (V, A, K, C)$, where: - $G = (V, A)$ is a directed graph, with $V$ being the set of nodes and $A$ being the set of arcs. - $K: A \to \mathbb{R}_{\geq 0}$ is a capacity function that assigns a non-negative real number $K_{ij}$ to each arc $(i, j) \in A$, representing the maximum amount of commodity that can flow through the arc. - $C: A \to \mathbb{R}$ is a cost function that assigns a real number $C_{ij}$ to each arc $(i, j) \in A$, representing the cost per unit of commodity flowing through the arc. ::: ## Arc Capacity and Cost - **Arc Capacity ($K_{ij}$)**: Represents the maximum amount of commodity that can pass through an arc $(i, j)$. It can be thought of as the bandwidth or the physical limitation of the arc. - **Arc Cost ($C_{ij}$)**: Represents the cost incurred for each unit of commodity that flows through an arc $(i, j)$. This could be a toll, operational cost, or any other expense associated with using the arc. ## Real-World Examples of Flow Networks - **Road Networks with Bridges**: If arcs represent roads and nodes represent intersections, the capacity of an arc representing a bridge could be the maximum weight it can support. - **Transportation Lines**: Arcs can represent train or bus lines between locations (nodes). The capacity could be the maximum number of passengers per unit of time. - **Pipelines**: If arcs represent pipes carrying fluids, the capacity is the maximum volume of fluid that can flow per unit of time, determined by the pipe's diameter. ## Definition of Flow and Feasibility ::: tcolorbox A flow in a network $G = (V, A, K, C)$ is a vector $X \in \mathbb{R}^{|A|}$, where each component $X_{ij}$ represents the amount of commodity flowing through arc $(i, j) \in A$. ::: ::: tcolorbox A flow $X$ is feasible if it satisfies the capacity constraints for every arc $(i, j) \in A$: $$0 \leq X_{ij} \leq K_{ij} \quad \forall (i, j) \in A$$ This means the flow through each arc is non-negative and does not exceed the arc's capacity. ::: ## Saturated and Empty Arcs - **Saturated Arc**: An arc $(i, j)$ is saturated with respect to a flow $X$ if $X_{ij} = K_{ij}$. This means the arc is carrying the maximum possible flow. - **Empty Arc**: An arc $(i, j)$ is empty or unloaded with respect to a flow $X$ if $X_{ij} = 0$. This means no commodity is flowing through the arc. # Flow Divergence ## Definition of Flow Divergence at a Node ::: tcolorbox For a given flow $X$ in a network $G=(V,A,K,C)$ and a node $v \in V$, the flow divergence at node $v$, denoted as $\text{div}(v)$, is defined as the total outflow minus the total inflow at that node: $$\text{div}(v) = \sum_{(v, j) \in A} X_{vj} - \sum_{(i, v) \in A} X_{iv}$$ Where $\delta^+(v) = \{(v, j) \in A\}$ is the set of outgoing arcs from $v$, and $\delta^-(v) = \{(i, v) \in A\}$ is the set of incoming arcs to $v$. We can write this as: $$\text{div}(v) = X(\delta^+(v)) - X(\delta^-(v))$$ ::: ## Source and Sink Nodes Based on the divergence at each node, we can classify nodes: - **Source Node**: A node $s$ with $\text{div}(s) > 0$. This indicates that more flow is leaving the node than entering it, suggesting it is a source of commodity. - **Sink Node**: A node $t$ with $\text{div}(t) < 0$. This indicates that more flow is entering the node than leaving it, suggesting it is a destination or sink of commodity. - **Transshipment Node**: A node $v$ with $\text{div}(v) = 0$. This indicates that the inflow and outflow are balanced, meaning the node is merely a point of transit. ## Theorem on the Sum of Divergences ::: tcolorbox For any feasible flow $X$ in a flow network $G=(V,A,K,C)$, the sum of divergences over all nodes is zero: $$\sum_{v \in V} \text{div}(v) = 0$$ Furthermore, let $S = \{v \in V \mid \text{div}(v) > 0\}$ be the set of source nodes and $T = \{v \in V \mid \text{div}(v) < 0\}$ be the set of sink nodes. Then, $$\sum_{v \in S} \text{div}(v) = - \sum_{v \in T} \text{div}(v)$$ ::: ::: proof *Proof.* Consider the sum of divergences over all nodes: $$\sum_{v \in V} \text{div}(v) = \sum_{v \in V} \left( \sum_{(v, j) \in A} X_{vj} - \sum_{(i, v) \in A} X_{iv} \right)$$ We can rewrite this sum by considering each arc $(i, j) \in A$. For each arc $(i, j)$, $X_{ij}$ is counted positively in the divergence of node $i$ and negatively in the divergence of node $j$. Thus, when we sum over all nodes, the contribution of each flow $X_{ij}$ cancels out: $$\sum_{v \in V} \text{div}(v) = \sum_{(i, j) \in A} X_{ij} - \sum_{(i, j) \in A} X_{ij} = 0$$ To show the second part, we partition the set of nodes $V$ into three disjoint sets: $S$, $T$, and $N = \{v \in V \mid \text{div}(v) = 0\}$. Then, $$\sum_{v \in V} \text{div}(v) = \sum_{v \in S} \text{div}(v) + \sum_{v \in N} \text{div}(v) + \sum_{v \in T} \text{div}(v) = 0$$ Since $\text{div}(v) = 0$ for all $v \in N$, we have $\sum_{v \in N} \text{div}(v) = 0$. Therefore, $$\sum_{v \in S} \text{div}(v) + \sum_{v \in T} \text{div}(v) = 0$$ $$\sum_{v \in S} \text{div}(v) = - \sum_{v \in T} \text{div}(v)$$ This shows that the total excess outflow from source nodes is equal to the total excess inflow into sink nodes. ◻ ::: ## Flow Conservation ::: tcolorbox A flow $X$ is conserved at node $v \in V$ if the flow divergence at $v$ is zero, i.e., $\text{div}(v) = 0$. This means that the total inflow into node $v$ is equal to the total outflow from node $v$. ::: ## Circulations: Flows with Zero Divergence ::: tcolorbox A flow $X$ in a network $G$ is called a circulation if it is conserved at every node $v \in V$, i.e., $\text{div}(v) = 0$ for all $v \in V$. In a circulation, the commodity flows around the network without any net source or sink. ::: ::: tcolorbox Consider a network and a flow assignment (red numbers) with capacities (numbers in square brackets) as described in the transcription. Verify that for each node, the inflow equals the outflow, confirming it's a circulation. (Diagram from transcription would be helpful here if possible to recreate in TikZ). ::: # Source-Sink Flows (s-t Flows) ## Definition of an s-t Flow ::: tcolorbox Given a flow network $G=(V, A, K, C)$ with a designated source node $s \in V$ and a sink node $t \in V$, an s-t flow (or flow from $s$ to $t$) is a feasible flow $X$ such that flow conservation holds at every node $v \in V \setminus \{s, t\}$. That is, $\text{div}(v) = 0$ for all $v \in V \setminus \{s, t\}$. ::: ## Value of an s-t Flow ::: tcolorbox The value of an s-t flow $X$, denoted by $\phi(X)$, is the flow divergence at the source node $s$: $$\phi(X) = \text{div}(s) = \sum_{(s, j) \in A} X_{sj} - \sum_{(i, s) \in A} X_{is}$$ By the Theorem on the Sum of Divergences, the value of an s-t flow is also equal to the negative of the divergence at the sink node $t$: $$\phi(X) = - \text{div}(t) = \sum_{(i, t) \in A} X_{it} - \sum_{(t, j) \in A} X_{tj}$$ Thus, the value represents the net flow out of the source $s$ and into the sink $t$. ::: ## Example of an s-t Flow ::: tcolorbox Consider a network with source node $s=1$ and sink node $t=8$. A flow assignment is given in the transcription. Verify that flow conservation holds for all nodes except node 1 and node 8. Calculate the value of this s-t flow as the divergence at node 1. (Diagram from transcription would be helpful here if possible to recreate in TikZ). ::: # Optimization Problems in Flow Networks ## The Maximum Flow Problem ::: tcolorbox Given a flow network $G=(V, A, K, C)$ with source $s$ and sink $t$, the maximum flow problem is to find a feasible s-t flow $X$ that maximizes the value $\phi(X)$. ::: The goal is to send as much commodity as possible from the source to the sink without violating capacity constraints. ## The Minimum Cost Flow Problem ::: tcolorbox Given a flow network $G=(V, A, K, C)$, a source $s$, a sink $t$, and a required flow value $B$, the minimum cost flow problem is to find a feasible s-t flow $X$ with value $\phi(X) = B$ that minimizes the total cost: $$\text{Cost}(X) = \sum_{(i, j) \in A} C_{ij} X_{ij}$$ ::: The objective is to achieve a specific flow value from source to sink at the minimum possible cost. ## Polynomial Time Solvability Both the maximum flow problem and the minimum cost flow problem are solvable in polynomial time, meaning there exist efficient algorithms to find optimal solutions. # The Flow Decomposition Theorem ## Elementary Cycles and Circular Flows ::: tcolorbox An elementary cycle $C$ in a directed graph is a sequence of nodes $v_1, v_2, \ldots, v_k, v_1$ where $v_1, v_2, \ldots, v_k$ are distinct nodes and $(v_i, v_{i+1}) \in A$ for $i=1, \ldots, k-1$ and $(v_k, v_1) \in A$. ::: ::: tcolorbox Given an elementary cycle $C$ and a value $\tau > 0$, a circular flow $X^C_\tau$ along $C$ with value $\tau$ is defined as: $$X^C_\tau(i, j) = \begin{cases} \tau & \text{if } (i, j) \in C \\ 0 & \text{otherwise} \end{cases}$$ A circular flow is a circulation. ::: ## Statement of the Flow Decomposition Theorem ::: tcolorbox Let $X$ be a circulation in a flow network $G=(V, A, K, C)$. Then, $X$ can be decomposed into a sum of elementary circular flows. Specifically, there exist elementary cycles $C_1, C_2, \ldots, C_q$ and positive values $\tau_1, \tau_2, \ldots, \tau_q$ such that: $$X = \sum_{i=1}^{q} X^{C_i}_{\tau_i}$$ ::: ## Proof of the Theorem ::: proof *Proof.* We prove this by induction on the number of cycles in the subgraph induced by arcs with positive flow. Let $A^+(X) = \{(i, j) \in A \mid X_{ij} > 0\}$. Let $R(X)$ be the number of cycles in the subgraph $G(A^+(X)) = (V, A^+(X))$. **Base Case**: If $R(X) = 0$, then $G(A^+(X))$ is acyclic. Since $X$ is a circulation, for every node $v$ with an incoming arc in $A^+(X)$, there must be an outgoing arc in $A^+(X)$ and vice-versa (unless the degree is zero). In an acyclic graph, this is impossible unless $A^+(X)$ is empty, meaning $X$ is a zero flow, which can be considered a sum of zero circular flows. If $R(X) = 1$, then $G(A^+(X))$ consists of a single elementary cycle $C$. Then $X$ must be a circular flow along $C$ with some value $\tau = \min_{(i,j) \in C} X_{ij}$. **Inductive Step**: Assume the theorem holds for all circulations $X'$ with $R(X') < R(X)$. Let $X$ be a circulation with $R(X) > 0$. Since $G(A^+(X))$ has cycles, choose an elementary cycle $C$ in $G(A^+(X))$. Let $\tau = \min_{(i,j) \in C} X_{ij} > 0$. Define a circular flow $X^C_\tau$ along $C$ with value $\tau$. Consider $X' = X - X^C_\tau$. $X'$ is still a circulation because subtracting a circulation from a circulation results in a circulation. For each arc $(i, j) \in C$, $X'_{ij} = X_{ij} - \tau \geq 0$. For at least one arc $(u, v) \in C$, $X'_{uv} = X_{uv} - \tau = 0$, because $\tau$ was chosen as the minimum flow on $C$. Thus, $A^+(X') \subsetneq A^+(X)$, which implies $R(X') < R(X)$. By the induction hypothesis, $X'$ can be decomposed into a sum of elementary circular flows: $X' = \sum_{i=1}^{r} X^{C'_i}_{\tau'_i}$. Therefore, $X = X' + X^C_\tau = \sum_{i=1}^{r} X^{C'_i}_{\tau'_i} + X^C_\tau$. This decomposes $X$ into a sum of elementary circular flows. ◻ ::: ## Corollary: Decomposition into Paths and Cycles ::: tcolorbox Let $X$ be an s-t flow with value $\phi(X) > 0$. Then $X$ can be decomposed into the sum of flows along elementary paths from $s$ to $t$ and flows along elementary cycles. Specifically, there exist elementary paths $P_1, \ldots, P_p$ from $s$ to $t$, elementary cycles $C_1, \ldots, C_q$, and positive values $y_1, \ldots, y_p$ and $\tau_1, \ldots, \tau_q$ such that: $$X = \sum_{i=1}^{p} X^{P_i}_{y_i} + \sum_{j=1}^{q} X^{C_j}_{\tau_j}$$ where $X^{P_i}_{y_i}$ is the flow of value $y_i$ along path $P_i$. ::: ::: proof *Proof.* To transform an s-t flow into a circulation, add a return arc $(t, s)$ to the network with infinite capacity and zero cost. Define the flow on this arc as $X_{ts} = \phi(X)$. Now, in the augmented network, the flow is conserved at all nodes, including $s$ and $t$, thus it is a circulation. By the Flow Decomposition Theorem for Circulations, this circulation can be decomposed into elementary circular flows. Some of these cycles may contain the arc $(t, s)$. If a cycle $C$ contains $(t, s)$, then removing the arc $(t, s)$ from $C$ results in a path $P$ from $s$ to $t$. The circular flow along $C$ corresponds to a path flow along $P$ plus flow on arc $(t,s)$. Cycles that do not contain $(t, s)$ remain cycles in the original network. Summing up the path flows and the cycle flows gives the decomposition of the original s-t flow. ◻ ::: ## Example of Flow Decomposition ::: tcolorbox Refer to the example of s-t flow in the transcription. Decompose the given s-t flow into path flows and cycle flows as described in the transcription. (Diagram and decomposition example from transcription would be helpful here if possible to recreate in TikZ and list paths and cycles). ::: # Transformations and Simplifications ## Modeling Undirected Arcs An undirected arc between nodes $i$ and $j$ with capacity $K_{ij}$ and cost $C_{ij}$ can be modeled by replacing it with two directed arcs: $(i, j)$ and $(j, i)$, both with capacity $K_{ij}$ and cost $C_{ij}$. ## Modeling Node Capacities A node $v$ with capacity $K_v$ can be modeled by splitting node $v$ into two nodes $v'$ and $v''$ and adding a directed arc $(v', v'')$ with capacity $K_v$ and zero cost. All incoming arcs to $v$ are redirected to $v'$, and all outgoing arcs from $v$ are redirected from $v''$. ## Eliminating Parallel Arcs If there are multiple parallel arcs from node $i$ to node $j$, they can be replaced by a single arc from $i$ to $j$. The capacity of the new arc is the sum of the capacities of the parallel arcs, and the cost can be defined based on the problem requirements (e.g., minimum cost selection or average cost). For simplification, if costs are identical, sum capacities and keep one arc with that cost. If costs are different, more complex transformations might be needed depending on the problem (e.g., for min-cost flow, keep the arc with minimum cost for each unit of capacity). For the purpose of simplification mentioned in transcription, splitting might be used to avoid parallel arcs in theoretical discussions. To eliminate parallel arcs in a simplified manner (as suggested by the transcription's approach to anti-parallel arcs), for each set of parallel arcs between nodes $i$ and $j$, we can replace all but one with a path of two arcs by introducing a new intermediate node. For example, replace a parallel arc $(i,j)_2$ with a path $i \to v_{ij} \to j$. Assign the original capacity and cost to $(i, v_{ij})$ and the same capacity but zero cost to $(v_{ij}, j)$. ## Eliminating Anti-Parallel Arcs Anti-parallel arcs, i.e., arcs $(i, j)$ and $(j, i)$, can be eliminated by splitting one of them. For example, to eliminate $(j, i)$, replace it with a path $j \to v_{ji} \to i$. Assign the original capacity and cost of $(j, i)$ to $(j, v_{ji})$ and the same capacity but zero cost to $(v_{ji}, i)$. ## Transforming Multiple Sources/Sinks to Single Source/Sink If there are multiple source nodes $S_1, S_2, \ldots, S_r$ and multiple sink nodes $T_1, T_2, \ldots, T_q$, introduce a supersource node $S$ and a supersink node $T$. Add arcs from $S$ to each $S_i$ with infinite capacity and zero cost. Add arcs from each $T_j$ to $T$ with infinite capacity and zero cost. Now, the problem can be transformed into a single-source single-sink problem from $S$ to $T$. ## Standard Assumptions on Source and Sink It is often assumed that no arcs enter the source node $s$ and no arcs leave the sink node $t$. If there are such arcs, they can be removed without affecting the maximum s-t flow or minimum cost s-t flow, as flow conservation at intermediate nodes ensures that flow originates from $s$ and terminates at $t$. # Conclusion In this lecture, we have laid the groundwork for understanding flow networks, defining key concepts such as flow, capacity, cost, and divergence. We explored the fundamental theorem on the sum of divergences and the important concept of flow conservation. We also introduced s-t flows and their values, and discussed two crucial optimization problems: maximum flow and minimum cost flow. Finally, we examined the flow decomposition theorem, which provides a valuable structural insight into flows, and discussed transformations to handle more general network configurations. In future lectures, we will delve deeper into algorithms for solving the maximum flow and minimum cost flow problems, and explore their applications in various domains. We will also investigate the implications of the flow decomposition theorem in algorithm design and network analysis.