Network Flow and Ford-Fulkerson Algorithm

Network Flow

• A flow network is a directed graph G = (V, E) featuring a source node s ∈ V, a sink node t ∈ V, and a capacity c(u, v) ≥ 0 for each edge (u, v) ∈ E.
• A flow is a function f: V × V → ℝ that satisfies the capacity constraint, skew symmetry, and flow conservation.
  • The capacity constraint is expressed such that for all u, v ∈ V, f(u, v) ≤ c(u, v)
  • Skew symmetry implies that for all u, v ∈ V, f(u, v) = -f(v, u)
  • Flow conservation is such that for all u ∈ V \ {s, t}, ∑v ∈ V f(u, v) = 0
• The value of a flow f is given by |f| = ∑v ∈ V f(s, v)
• The maximum-flow problem aims to find a flow of maximum value in a given flow network G.

Ford-Fulkerson Algorithm

• This algorithm is used to solve the maximum-flow problem in a network
• It initializes the flow f(u, v) = 0 for all u, v ∈ V.
• The algorithm iterates as long as there exists an augmenting path p in G.
  • It finds a path p from s to t in Gf, where Gf is the "residual network".
  • It calculates cf(u, v) = c(u, v) - f(u, v)
  • It sets cf(p) = min{cf(u, v) : (u, v) is in p}
  • For each edge (u, v) in p: f(u, v) = f(u, v) + cf(p) and f(v, u) = f(v, u) - cf(p)
• Returns f.

Definitions for Ford-Fulkerson

• Residual capacity of an edge (u, v) is calculated as cf(u, v) = c(u, v) - f(u, v).
  • It represents the additional flow that can be pushed from u to v.
• The residual network of G induced by f is Gf = (V, Ef), where Ef = {(u, v) ∈ V × V : cf(u, v) > 0}.
  • These edges can admit more flow.
• An augmenting path is a simple path from s to t in Gf.

Max-Flow Min-Cut Theorem

• A cut (S, T) of a flow network G = (V, E) is a partition of V into S and T = V \ S such that s ∈ S and t ∈ T.
• The capacity of a cut (S, T) is defined as c(S, T) = ∑u ∈ S ∑v ∈ T c(u, v).
• The flow across a cut (S, T) is defined as f(S, T) = ∑u ∈ S ∑v ∈ T f(u, v).
• Max-Flow Min-Cut Theorem: For a flow f in a flow network G = (V, E), the following conditions are equivalent:
  • f is a maximum flow in G.
  • The residual network Gf contains no augmenting paths.
  • |f| = c(S, T) for some cut (S, T) of G.

Eigenvalues and Eigenvectors Definitions

• For an n × n matrix A, a scalar λ is considered an eigenvalue if there exists a non-zero vector v such that Av = λv.
• If λ is an eigenvalue of A, then v is an eigenvector of A corresponding to λ.
• For an n × n matrix A, a scalar λ is an eigenvalue if and only if det(A - λI) = 0.

Finding Eigenvalues and Eigenvectors

• For an n × n matrix A:
  • Solve the characteristic equation det(A - λI) = 0 for λ.
  • For each eigenvalue λ, solve the homogeneous system (A - λI)v = 0 for the eigenvectors v.

Example 1: Find Eigenvalues and Eigenvectors

• Solve for matrix A = [1 3; 4 2]
• The eigenvalues of A are λ1 = 5 and λ2 = -2.
• The eigenvector corresponding to λ1 = 5 is v1 = [3; 4].
• The eigenvector corresponding to λ2 = -2 is v2 = [1; -1].

Example 2: Find Eigenvalues and Eigenvectors

• Solve for matrix A = [2 -1; 5 -2]
• The eigenvalues are λ = ±i.
• For λ1 = i, the corresponding eigenvector is v1 = [1; 2 - i].
• For λ2 = -i, the corresponding eigenvector is v2 = [1; 2 + i].

Example 3: Find Eigenvalues and Eigenvectors

• Solve for A = [1 2 1; 0 1 0; 0 1 3]
• The eigenvalues are λ1 = 1 and λ2 = 3.
• The eigenvector corresponding to λ1 = 1 is v1 = [1; 0; 0].
• The eigenvector corresponding to λ2 = 3 is v2 = [1; 0; 2].

Theorem 1 Relating to Eigenvalues

• For an n × n matrix A, the following are equivalent:
  • λ is an eigenvalue of A.
  • (A - λI)v = 0 has nontrivial solutions.
  • The linear system (A - λI)v = 0 has infinitely many solutions.
  • A - λI is singular.
  • det(A - λI) = 0.

Theorem 2 Relating to Eigenvalues

• If A is a triangular matrix, its eigenvalues are the entries on the main diagonal.

Geometric Vectors (Chapter 1, Linear Algebra and Analytic Geometry I)

• A geometric vector is an oriented line segment.
• The vector from point A to point B is denoted as $\overrightarrow{AB}$, where A is the origin, and B is the endpoint.
• The length of the segment is the norm, denoted as $|\overrightarrow{AB}|$.
• The direction of $\overrightarrow{AB}$ is that of the line (AB), and the sense is from A to B.
• Two vectors are equal if they share the same norm, direction, and sense.
• A vector with a norm of 1 is a unit or normalized vector.
• The vector whose origin and endpoint coincide is the zero vector, $\vec{0}$, with a norm of zero and no direction or sense.
• The opposite of a vector $\overrightarrow{AB}$ is $\overrightarrow{BA}$, denoted as $-\overrightarrow{AB}$.

Vector Operations

• The sum of two vectors $\vec{u}$ and $\vec{v}$ is found by placing the origin of $\vec{v}$ at the endpoint of $\vec{u}$.
  • $\vec{u} + \vec{v}$ connects the origin of $\vec{u}$ to the endpoint of $\vec{v}$.
• (Parallelogram Rule): If $\vec{u}$ and $\vec{v}$ share an origin, $\vec{u} + \vec{v}$ is the diagonal of the parallelogram formed by $\vec{u}$ and $\vec{v}$.

Vector Addition Properties

• Commutativity: $\vec{u} + \vec{v} = \vec{v} + \vec{u}$
• Associativity: $(\vec{u} + \vec{v}) + \vec{w} = \vec{u} + (\vec{v} + \vec{w})$
• Identity Element: $\vec{u} + \vec{0} = \vec{u}$
• Inverse Element: $\vec{u} + (-\vec{u}) = \vec{0}$

Scalar Multiplication

• Multiplying a vector $\vec{u}$ by a scalar $\lambda \in \mathbb{R}$ results in a vector $\lambda\vec{u}$ with the same direction as $\vec{u}$.
  • The norm is $|\lambda||\vec{u}|$, and the sense is the same as $\vec{u}$ if $\lambda > 0$, or opposite if $\lambda < 0$.
  • If $\lambda = 0$ or $\vec{u} = \vec{0}$, then $\lambda\vec{u} = \vec{0}$.

Scalar Multiplication Properties

• Associativity: $\lambda(\mu\vec{u}) = (\lambda\mu)\vec{u}$
• Distributivity over scalar addition: $(\lambda + \mu)\vec{u} = \lambda\vec{u} + \mu\vec{u}$
• Distributivity over vector addition: $\lambda(\vec{u} + \vec{v}) = \lambda\vec{u} + \lambda\vec{v}$
• Identity element: $1\vec{u} = \vec{u}$

Linear Combination of Vectors

• A linear combination of vectors $\vec{u}_1, \vec{u}_2,..., \vec{u}_n$ is a vector like this: $\lambda_1\vec{u}_1 + \lambda_2\vec{u}_2 +... + \lambda_n\vec{u}_n$, where $\lambda_1, \lambda_2,..., \lambda_n \in \mathbb{R}$.

Analytical Vector Representation

• In a Cartesian plane $(O, \vec{i}, \vec{j})$, every vector $\vec{u}$ can be uniquely expressed as $\vec{u} = u_1\vec{i} + u_2\vec{j}$, where $u_1$ and $u_2$ are components of $\vec{u}$ in the base $(\vec{i}, \vec{j})$.
  • $\vec{u} = (u_1, u_2)$
• In a Cartesian space $(O, \vec{i}, \vec{j}, \vec{k})$, every vector $\vec{u}$ can be uniquely expressed as $\vec{u} = u_1\vec{i} + u_2\vec{j} + u_3\vec{k}$, where $u_1$, $u_2$, and $u_3$ are components of $\vec{u}$ in the base $(\vec{i}, \vec{j}, \vec{k})$.
  • $\vec{u} = (u_1, u_2, u_3)$

Vector Component Operations

• Given vectors $\vec{u} = (u_1, u_2, u_3)$, $\vec{v} = (v_1, v_2, v_3)$, and scalar $\lambda \in \mathbb{R}$:
  • $\vec{u} + \vec{v} = (u_1 + v_1, u_2 + v_2, u_3 + v_3)$
  • $\lambda\vec{u} = (\lambda u_1, \lambda u_2, \lambda u_3)$
  • $\vec{0} = (0, 0, 0)$
  • $-\vec{u} = (-u_1, -u_2, -u_3)$

Vector Norm

• The norm of $\vec{u} = (u_1, u_2, u_3)$ is $|\vec{u}| = \sqrt{u_1^2 + u_2^2 + u_3^2}$.
  • In the plane, $|\vec{u}| = \sqrt{u_1^2 + u_2^2}$.

Distance Between Two Points

• The distance between points $A(x_1, y_1, z_1)$ and $B(x_2, y_2, z_2)$ is $d(A, B) = |\overrightarrow{AB}| = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2 + (z_2 - z_1)^2}$.
  • In the plane, $d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.