Flow Networks - Georgia Tech - Computability, Complexity, Theory: Algorithms

1. Formula
   Observation

   The board writes $G = (V, E)$ under the heading Flow Network.

2. Audio
   Observation

   The lecturer says a flow network consists of, among other things, a directed graph G.

G

The directed graph component of a flow network.

A pair (V, E) of vertex set and edge set.

1. Formula
   Observation

   $G = (V, E)$ appears on the board.

2. Audio
   Observation

   The lecture refers to vertices in the graph and to pairs of vertices.

V

The vertex set of the directed graph G.

A finite set of vertices.

1. Formula
   Observation

   $G = (V, E)$ and (u,v) $\in E \Rightarrow (v,u) \notin E$ are written on the board.

2. Audio
   Observation

   The lecturer says antiparallel edges are disallowed.

E

The edge set of the directed graph G.

A set of ordered pairs of vertices.

1. Formula
   Observation

   The board uses (u,v) $\in E$ and $C(u,v)$.

2. Audio
   Observation

   The lecturer speaks about every pair of vertices and about flow between two vertices.

(u,v)

An ordered pair of vertices, used to denote a directed edge or a capacity/flow value between u and v.

u, $v \in V$.

1. Formula
   Observation

   The board writes "source" s and $\forall v \in V$, (v,s),(t,v) $\notin E$.

2. Diagram
   Observation

   The leftmost node is labeled s.

3. Audio
   Observation

   The lecturer says a source, typically labeled s, is where whatever is flowing through the network starts from.

s

The source vertex of the flow network.

A distinguished vertex in V.

1. Formula
   Observation

   The board writes "sink" t and $\forall v \in V$, (v,s),(t,v) $\notin E$.

2. Diagram
   Observation

   The rightmost node is labeled t.

3. Audio
   Observation

   The lecturer says a sink, typically labeled t, is where the flow ends up.

t

The sink vertex of the flow network.

A distinguished vertex in V.

1. Formula
   Observation

   The board writes C : $V \times V \to \mathbb{N} \cup$ \{0\} and $C(u,v)=0$ if (u,v) $\notin E$.

2. Audio
   Observation

   The lecturer says associated with every pair of vertices is a capacity.

C

The capacity function assigning a nonnegative integer capacity to each ordered pair of vertices.

C : $V \times V \to \mathbb{N} \cup$ \{0\}.

1. Formula
   Observation

   The board writes Flow f : $V \times V \to$ [0,$\infty$).

2. Audio
   Observation

   The lecturer says the flow itself is a function from pairs of vertices to the nonnegative reals.

f

The flow function on ordered pairs of vertices.

f : $V \times V \to$ [0,$\infty$).

1. Formula
   Observation

   The board writes f^{in}(u) = $\sum_{v \in V} f(v,u)$.

2. Audio
   Observation

   The lecturer defines f in to be the flow into a vertex.

f^{in}(u)

Total incoming flow at vertex u.

Defined for $u \in V$ by summing over all $v \in V$.

1. Formula
   Observation

   The board writes f^{out}(u) = $\sum_{v \in V} f(u,v)$.

2. Audio
   Observation

   The lecturer defines f out to be the flow out.

f^{out}(u)

Total outgoing flow at vertex u.

Defined for $u \in V$ by summing over all $v \in V$.

1. Formula
   Observation

   The board writes Flow Value |f| = f^{out}(s) = f^{in}(t).

2. Audio
   Observation

   The lecturer says the overall value of the flow is defined as the flow going out of the source or equivalently the flow going into the sink.

|f|

The value of the flow.

A nonnegative real number determined by the flow function f.

1. Formula
   Observation

   The board shows $G = (V, E)$; (u,v) $\in E \Rightarrow (v,u) \notin E$.

2. Audio
   Observation

   The lecturer says a flow network consists of, among other things, a directed graph G, and that antiparallel edges are disallowed to simplify equations.

The video introduces a flow network by first specifying its underlying structure: a directed graph $G=(V,E)$, together with the restriction that if (u,v) is an edge then (v,u) is not. The lecturer explicitly says this restriction is imposed to simplify later equations and is not a serious limitation.

1. The graph is directed.

2. Antiparallel edges are disallowed.

3. This restriction is stated as a simplifying assumption.

1. Formula
   Observation

   The board writes "source" s, "sink" t, "internal" and $\forall v \in V$, (v,s),(t,v) $\notin E$.

2. Diagram
   Observation

   The leftmost node is labeled s and the rightmost node is labeled t.

3. Audio
   Observation

   The lecturer distinguishes a source s, a sink t, and calls all other vertices internal; he also assumes no incoming edges into s or outgoing edges from t.

A flow network has two distinguished vertices: a source s and a sink t. All remaining vertices are called internal. The video further imposes boundary conditions so that no edge enters s and no edge leaves t.

1. s is the source.

2. t is the sink.

3. All other vertices are internal.

4. No incoming edges into s.

5. No outgoing edges from t.

1. Flow network as a directed graph without antiparallel edges

1. Formula
   Observation

   The board writes C : $V \times V \to \mathbb{N} \cup$ \{0\} and $C(u,v)=0$ if (u,v) $\notin E$.

2. Diagram
   Observation

   Red numbers appear on the edges of the drawn graph.

3. Audio
   Observation

   The lecturer says every pair of vertices has a capacity indicating how much flow can be sent directly between them, that capacities are nonnegative integers, and that if there is no edge then the capacity is zero.

Each ordered pair of vertices is assigned a capacity $C(u,v)$. In this presentation capacities are nonnegative integers, and pairs that are not edges have capacity 0. The diagram illustrates this by placing red numeric labels on the directed edges.

1. Capacities are nonnegative integers.

2. If (u,v) is not an edge, then $C(u,v)=0$.

3. Capacity measures how much flow can be sent directly between two vertices.

1. Flow network as a directed graph without antiparallel edges

1. Formula
   Observation

   The board writes Flow f : $V \times V \to$ [0,$\infty$) where 1) $f(u,v) \le C(u,v)$ and 2) $f(u,v)+f(v,u)=0$.

2. Audio
   Observation

   The lecturer says the flow is a function from pairs of vertices to the nonnegative reals, must be nonnegative, cannot exceed capacity, and at least one direction between any two vertices must be zero.

A flow is a function f on ordered pairs of vertices taking values in the nonnegative reals. The video states two immediate constraints: flow never exceeds capacity, and for any pair of vertices at least one of the two opposite directions has zero flow.

1. f is nonnegative.

2. $f(u,v)$ cannot exceed $C(u,v)$.

3. For each pair u,v, at least one of $f(u,v)$ and $f(v,u)$ is 0.

1. Capacity function on vertex pairs

1. Formula
   Observation

   The board writes f^{in}(u)=$\sum_{v \in V} f(v,u)$, f^{out}(u)=$\sum_{v \in V} f(u,v)$, and f^{in}(u)=f^{out}(u) for internal u.

2. Audio
   Observation

   The lecturer says flow must be conserved at every internal vertex, defines f in and f out, and explains intuitively that internal nodes cannot generate or absorb flow.

For every internal vertex u, total incoming flow equals total outgoing flow. The video defines these totals by sums over all vertices and states that only the source and sink may generate or absorb net flow.

1. The equality is required for internal vertices u.

2. Incoming and outgoing flow are defined by sums over all $v \in V$.

1. Source, sink, and internal vertices
2. Flow function and its pairwise constraints

1. Formula
   Observation

   The board writes Flow Value |f| = f^{out}(s) = f^{in}(t).

2. Audio
   Observation

   The lecturer says the overall value of the flow is the flow going out of the source or equivalently the flow going into the sink.

The value of a flow is defined as the amount leaving the source, equivalently the amount entering the sink. This uses the previously defined outgoing and incoming flow functions.

1. s is the source.

2. t is the sink.

3. The definition relies on the earlier definitions of f^{out} and f^{in}.

1. Conservation of flow at internal vertices

1. Audio
   Observation

   The lecturer says antiparallel edges are disallowed to simplify some of the equations and that this is not a serious limitation.

The restriction (u,v) $\in E \Rightarrow (v,u) \notin E$ is imposed to simplify later equations and is presented as not a serious limitation.

1. We are defining the class of flow networks used in this lecture.

For the flow networks considered in this segment.

1. Audio
   Observation

   The lecturer says capacities are assumed to be nonnegative integers, that this makes arguments easier, and that it is not a serious limitation because a later algorithm will overcome it.

Assuming capacities are nonnegative integers simplifies the arguments and is not a serious limitation because a later algorithm will overcome it.

1. Capacities are taken in $\mathbb{N} \cup$ \{0\} in this presentation.

For the algorithms discussed later in the course, according to the lecturer's statement.

1. Audio
   Observation

   The lecturer says intuitively this just means that internal nodes can't generate or absorb any of the stuff that's flowing; those are the jobs of the source and the sink.

Flow conservation at internal vertices means internal nodes cannot generate or absorb flow; only the source and sink play that role.

1. The conservation condition f^{in}(u)=f^{out}(u) holds for internal u.

For every internal vertex u.

1. Audio
   Observation

   The lecturer says, 'So for example, in this node here, I have four plus two coming in, and I have five plus one going out. These are both six, so we say that flow is conserved at this vertex.'

2. Diagram
   Observation

   The pen points to an internal vertex in the worked example graph while discussing incoming and outgoing amounts.

1. The exact identity of the referenced internal vertex is visually approximate, but the spoken arithmetic is clear.

1. Expression

   $$4+2$$
   Explanation

   The lecturer adds the two incoming flow amounts at the chosen internal vertex.

   Justification

   Directly stated in the audio.

   Shown in the video
2. Expression

   $$5+1$$
   Explanation

   The lecturer adds the two outgoing flow amounts at the same vertex.

   Justification

   Directly stated in the audio.

   Shown in the video
3. Expression

   $$6=6$$
   Explanation

   Both totals equal 6, so the vertex satisfies conservation.

   Justification

   Arithmetic comparison of the two sums.

   Shown in the video

At the cited internal vertex, incoming flow equals outgoing flow, so flow is conserved there.

1. Diagram
   Observation

   A six-vertex directed graph is shown with source s on the left and sink t on the right.

2. Formula
   Observation

   Red edge labels show capacities and blue labels show flows, including pairs such as $5/8$, $6/6$, $7/10$, $4/7$, $1/2$, $2/9$, $3/5$, $5/6$, and $2/2$.

3. Audio
   Observation

   The lecturer uses the graph to explain capacities, flows, and conservation at an internal vertex.

1. Some edge-to-label correspondences are visually approximate because the board is handwritten and the pen moves quickly.

Illustrate the definitions of capacity, flow, and conservation on a concrete directed graph with source s and sink t.

1. A directed graph with vertices including s and t.

2. Capacities written in red on edges.

3. Flows written in blue on edges.

4. One internal vertex is checked with incoming amounts 4 and 2 and outgoing amounts 5 and 1.

Show how the displayed numbers instantiate the definitions of C, f, and conservation.

1. Expression

   $$C(u,v) \text{ shown as red edge labels}$$
   Explanation

   The red numbers on the graph represent capacities of the corresponding directed edges.

   Justification

   Diagram plus the lecturer's definition of capacity.

   Shown in the video
2. Expression

   $$f(u,v) \text{ shown as blue edge labels}$$
   Explanation

   The blue numbers represent the actual flow assigned to each directed edge.

   Justification

   Diagram plus the lecturer's definition of flow.

   Shown in the video
3. Expression

   $$4+2 = 5+1 = 6$$
   Explanation

   At the cited internal vertex, total incoming flow equals total outgoing flow.

   Justification

   Explicit spoken numerical check.

   Shown in the video

The example graph instantiates a flow network by assigning integer capacities and nonnegative flows that satisfy the stated constraints, with conservation verified at the cited internal vertex.

The lecturer verifies conservation numerically at one internal vertex by comparing incoming and outgoing sums.

1. Diagram
   Observation

   The board title reads Flow Networks, with a small directed graph drawn on the right and the formula $G = (V, E)$; (u,v) $\in E \Rightarrow (v,u) \notin E$ on the left.

2. Animation
   Observation

   A hand with a stylus points around the formula and graph while the lecturer introduces the definition.

1. Title 'Flow Networks'

2. Formula for $G=(V,E)$

3. Small directed graph with six vertices

1. The stylus points to the formula and then to the graph.

1. The graph remains directed.

2. The antiparallel-edge restriction stays visible on the board.

The opening visual establishes that a flow network is built on a directed graph with no antiparallel edges.

1. Diagram
   Observation

   Green text appears: "source" s, "sink" t, "internal", and $\forall v \in V$, (v,s),(t,v) $\notin E$.

2. Animation
   Observation

   The leftmost and rightmost nodes of the graph are labeled s and t.

1. Graph vertices

2. Labels s and t

3. Green boundary-condition formula

1. The leftmost node receives label s.

2. The rightmost node receives label t.

3. Boundary-condition text is added below the initial definition.

1. The underlying directed graph structure remains the same.

2. The no-antiparallel-edge condition remains in force.

The visual step distinguishes the two special vertices and encodes the assumption that nothing enters s and nothing leaves t.

1. Diagram
   Observation

   Red numbers appear next to the directed edges of the graph.

2. Formula
   Observation

   The board adds C : $V \times V \to \mathbb{N} \cup$ \{0\} and $C(u,v)=0$ if (u,v) $\notin E$.

1. Exact mapping of every red number to a specific ordered pair is visually approximate.

1. Directed graph

2. Red numeric edge labels

3. Capacity formulas

1. Red capacity values are written onto the edges.

2. The capacity function definition is added on the left.

1. The graph topology and source/sink labels remain unchanged.

The red labels visualize the capacity function C on selected vertex pairs.

1. Diagram
   Observation

   Blue numbers are added beside the red ones, producing paired labels such as $5/8$, $6/6$, $7/10$, $4/7$, $1/2$, $2/9$, $3/5$, $5/6$, and $2/2$.

2. Formula
   Observation

   The board adds Flow f : $V \times V \to$ [0,$\infty$) with constraints 1) $f(u,v) \le C(u,v)$, 2) $f(u,v)+f(v,u)=0$, and later the conservation formulas.

1. Some paired labels are handwritten and their exact edge association is approximate.

1. Graph edges

2. Blue flow labels

3. Flow definition formulas

4. Conservation formulas

1. Blue flow values are written alongside red capacities.

2. The flow function definition and constraints are added.

3. The conservation equations are written below.

1. The capacity labels remain visible.

2. The source and sink labels remain fixed.

The paired red/blue labels illustrate a concrete assignment of capacities and flows satisfying the stated constraints.

1. Diagram
   Observation

   A boxed heading Flow Value appears at the lower right with |f| = f^{out}(s) = f^{in}(t).

2. Animation
   Observation

   The stylus points to the boxed formula as the lecturer defines the overall value of the flow.

1. Boxed heading 'Flow Value'

2. Formula |f| = f^{out}(s) = f^{in}(t)

1. A new boxed definition is added at the lower right.

1. The earlier graph and definitions remain on screen.

The closing visual summarizes the scalar quantity associated with the whole flow.

1. Audio
   Observation

   The lecturer says it doesn't make sense to have flow going from one vertex to another only to send it back again.

2. Formula
   Observation

   The board states $f(u,v)+f(v,u)=0$.

One might imagine sending positive flow in both directions between the same pair of vertices.

The video imposes $f(u,v)+f(v,u)=0$, so at least one direction must be zero; simultaneous positive flow in opposite directions is excluded.

1. Audio
   Observation

   The lecturer says internal nodes can't generate or absorb any of the stuff that's flowing; those are the jobs of the source and the sink.

A reader might think intermediate vertices can add or remove flow.

Conservation requires f^{in}(u)=f^{out}(u) at internal vertices, so only s and t account for net generation or absorption.

1. Formula
   Observation

   The source/sink notation is added directly beneath the initial graph definition.

2. Audio
   Observation

   The lecturer first defines the directed graph and then distinguishes special vertices s and t.

The definition of a flow network builds on the directed graph by adding distinguished source and sink vertices and boundary conditions on incident edges.

1. Formula
   Observation

   The conservation clause is written 'for internal u' after the source/sink/internal distinction.

2. Audio
   Observation

   The lecturer says flow must be conserved at every internal vertex and later contrasts internal nodes with source and sink.

Understanding conservation requires knowing which vertices are internal as opposed to the source and sink.

1. Formula
   Observation

   The flow constraint $f(u,v) \le C(u,v)$ directly references the capacity function.

2. Audio
   Observation

   The lecturer says flow can't exceed the capacity for any pair of vertices.

The flow definition depends on capacity because one of its constraints is an upper bound by $C(u,v)$.

1. Formula
   Observation

   The final boxed formula |f| = f^{out}(s) = f^{in}(t) uses the previously defined f^{out} and f^{in}.

2. Audio
   Observation

   The lecturer defines the overall value of the flow using source-outflow and sink-inflow.

The notion of flow value applies the incoming/outgoing flow machinery to the special vertices s and t.

1. Formula
   Observation

   Opening board shows $G = (V, E)$; (u,v) $\in E \Rightarrow (v,u) \notin E$.

2. Audio
   Observation

   The lecturer begins with the definition of a flow network.

1. Flow network as a directed graph without antiparallel edges

1. Audio
   Observation

   The lecturer says antiparallel edges are disallowed to simplify some of the equations.

1. Flow network as a directed graph without antiparallel edges
2. Disallowing antiparallel edges is a simplifying assumption

1. Formula
   Observation

   The board labels source s, sink t, internal, and writes the boundary condition.

2. Audio
   Observation

   The lecturer explains where flow starts and ends.

1. Source, sink, and internal vertices

1. Formula
   Observation

   The board writes $C(u,v)=0$ if (u,v) $\notin E$.

2. Audio
   Observation

   The lecturer says if there is no edge in the graph, then the capacity is defined to be zero.

1. Capacity function on vertex pairs

1. Formula
   Observation

   The board lists $f(u,v) \le C(u,v)$ and $f(u,v)+f(v,u)=0$.

2. Audio
   Observation

   The lecturer states the nonnegativity, capacity bound, and one-direction-zero requirements.

1. Flow function and its pairwise constraints

1. Audio
   Observation

   The lecturer gives the $4+2$ versus $5+1$ example and says internal nodes cannot generate or absorb flow.

1. Conservation of flow at internal vertices
2. Numerical verification of conservation at an internal vertex
3. Internal vertices do not create or destroy flow

1. Formula
   Observation

   The boxed formula reads |f| = f^{out}(s) = f^{in}(t).

2. Audio
   Observation

   The lecturer defines the overall value of the flow.

1. Value of a flow