Week 10 Flow

Question 1

Directed graph

Answer 1

A directed graph (or quiver) is a quadruple (V, E, h, t)
consisting of a pair of sets V (vertices) and E (edges or arrows) and two maps h, t : E →V declaring the vertex at
the head and tail of each arrow respectively.

Question 2

Flow network

Answer 2

A flow network is a directed graph G = (V, E, h, t) together
with a function c : E →R+ indicating the capacity of each
edge.

Question 3

Feasible flow

Answer 3

A feasible flow (or simply a flow) is a function f : E →R≥0
assigning a non-negative value to each edge satisfying:
1) 0 ≤f (e) ≤c(e) for every edge e ∈E (flow cannot exceed capacity);
2) for all vertices except the source s and sink t, the
outflow at each vertex is equal to the inflow (no leakages).

Question 4

Maximum flow

Answer 4

A maximum flow (or maximal flow) is a feasible flow whose
value is maximal, that is, f is a maximal flow if v(f ) ≥v(f ′)
for all feasible flows f′.