Graph Algorithms

André Raspaud

LaBRI
Université Bordeaux I
France
raspaud@[Link]
Table of contents

Chapter 1: Asymptotic notations

Chapter 2: Graph: Definitions

Chapter 2: Traversal of graphs

Chapter 4: Minimum Spanning tree

Chapter 5: Shortest path

Chapter 6: Maximum flow problem

Chapter 1: Asymptotic notations

Chapter 2: Graph: Definitions

Chapter 2: Traversal of graphs

Chapter 4: Minimum Spanning tree

Chapter 5: Shortest path

Chapter 6: Maximum flow problem

Chapter 1: O, Θ, Ω

We consider the sets:

N, R, R+ , R∗ . All the functions will be of the type :
f : N → R∗ .

1. O
Let f : N → R∗ .

O(f (n)) = {t : N → R∗ | (∃c ∈ R+ )(∃n0 ∈ N)[∀n ≥ n0 ][t(n) ≤ cf (n)]}

In other words, O(f (n)) is the set of functions t(n) bounded by a

real number multiplied by f (n) for all n enough big (n ≥ n0 ).
Hence t(n) ∈ O(f (n)), we write t(n) = O(f (n)).
O(1)
We must consider the function 1 : N → R∗ such that 1(n) = 1 for
evrey n ∈ N
t(n) = O(1) ⇒ ∃c ∈ R+ , ∃n0 ∈ N such that for every n ≥ n0
t(n) ≤ c1(n). It means that for n ≥ n0 t(n) ≤ 1(n), t(n) ≤ c
t(n) = O(1) means that t is bounded by a constant.

O(n3 )
t(n) = 3n3 + 2n2
t(n) ≤ 3n3 , n0 = 1.
t(n) = 0(n3 ).

Homework
Prove that 3n 6= O(2n )
Prove that O(f (n) + g (n)) = O(max(f (n), g (n)).
2. Ω
Let f : N → R∗ .

Ω(f (n)) = {t : N → R∗ | (∃c ∈ R+ )(∃n0 ∈ N)[∀n ≥ n0 ][t(n) ≥ cf (n)]}

t(n) ∈ Ω(g (n)) is written also t(n) = Ω(g (n))

Proposition

f (n) ∈ O(g (n)) ⇐⇒ g (n) ∈ Ω(f (n))

3. Θ
Θ(f (n) = O(f (n) ∩ Ω(f (n))

Definition
Let f : N → R∗ .
∗ +
Θ(f (n)) = {t : N → R | (∃c, d ∈ R )(∃n0 ∈ N)[∀n ≥ n0 ][cf (n) ≤ t(n) ≤ df (n)]}

Proposition

f (n) ∈ Θ(g (n)) ⇐⇒ g (n) ∈ Θ(f (n))

Chapter 2- Graphs-Definitions
1- Directed Graphs

Definition
G = (X , U), X the set of vertices, U the set of arcs.
T : U → X , a 7→ the terminal extremity
I : U → X , a 7→ the initial extremity

If a ∈ U we write also a = xy
~ where x and y are the extemities of
a.
Definition
~ ∈ U then we say that x is the predecessor of y and y is the
If xy
successor of x.
 2. Representation of a graph
Adjacency Matrix

Let G = (X , U) be a directed graph. We assume that |X | = n,

|U| = m and X = {1, 2, . . . , n}

Definition (Adjacency Matrix)

It is a square matrix n × n A[G ], where (aij ) are the coefficients:

A[G ] = (aij )1≤i ≤n,1≤j≤n

aij is the number of arcs with initial vertex equal to i and final
vertex equal to j.
 1
a
2 a6
a4 a5 3 a1 4

a3

2
Figure: Graph 2

 
0 1 1 0
 1 0 0 0 
A[G ] = 
 0

1 0 1 
0 0 0 1
Incidence Matrix

It is a n × m matrix B[G ] = (bi ,j )1≤i ≤n,1≤j≤m

U = {a1 , a2 , . . . , an }.


 1 if i is the initial vertex of aj
bij = −1 if i is the final vertex of aj
0 otherwise

Incidence Matrix

1
a
2 a6
a4 a5 3 a1 4

a3

2
Figure: Graph 2
 
0 1 0 1 −1 0
 0 0 −1 −1 1 0 
B[G ] = 
 1 −1 1

0 0 0 
−1 0 0 0 0 0
Memory space

The needed memory space is in O(n2 ) for the matrix A[G ], and in
O(n × m) for the matrix B[G ]
2-Undirected Graphs
Definition
G = (X , E ) S
X is the vertex set. E is the edge set. E ⊂ P2 (X ) X (P2 (X ) is
the set of pair of elements of X ). Parallel edges are allowed.

In the following example we have:

X = {1, 2, 3, 4, 5, 6} et E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }
4

e2 e3
2 3 5
1 e1 e4
e6

e7 e5

Figure: Graph 3
A graph G is said simple if it contains no loop neither multiple
edges (parallel edges).
Remarks
Like for the directed graphs, we define A[G ] = (aij )1≤i ≤n,1≤j≤n ,
the adjacency matrix and B[G ] = (bij )1≤i ≤n,1≤j≤m , the incidence
matrix.
1. For the adjacency matrix, aij is the number of edges linking i
et j.
2. For the incidence matrix, bij is the number of times that i is
incident to aj . In this representation the loops are present
because the value of bij is equal to 2.
Adjacency, Neighborood

Definition
◮ Two vertices, x and y , of a directed graph G = (X , E ) (or of
an undirected graph G = (X , U)) are adjacents if xy ∈ E (
−
→ or −
xy → ∈ U)
yx
◮ Two edges are adjacent if they share an extremity.

Definition
1. A vertex x is incident to an edge e if e = xy (e = −
→)
xy
2. The neighboorood of a vertex x ist: Γ(x) = {y ∈ X /xy ∈ E }
3. The degree of a vertex x is d(x) = |Γ(x)|. It is the number of
egdes incident to x, the loops are counted twice.
Definition
If G = (X , U) is a directed graph. Let x ∈ X .
1.
Γ+ (x) = {y ∈ X /−
→ ∈ U}
xy
2.
Γ− (x) = {y ∈ X /−
→ ∈ U}
yx
3. d + (x) = |Γ+ (x)| (outdegree of x)
4. d − (x) = |Γ− (x)| (indegree of x)
Proposition
Let G = (X , E ) be a simple unoriented graph (without loop and
multiple edges)
◮ m ≤ 12 n(n − 1), m is the number of edges and n is the
number of vertices.
P
x∈X d(x) = 2m
◮

◮ The number of vertices having a odd degree is even.

(Homework)

Proposition
Let G = (X ,P
U) be a directed graph, then
d + (x) = d − (x) = m (m is the number of arcs)
P
Data structures

Static structures
1. Adjacency Matrix
2. Incidence Matrix

Dynamic structures
List of successors: A list of lists, in which the first list is a list of
indices corresponding to each node in the graph. Each of these
refer to another list that stores the label of each adjacent node to
this one.
Data structures

1 2 3

4
2 2 3

3 3 4 5

1 5 4 5

Figure: List of successors

Chapter 3- Graph Traversals

Definition
Let G = (V , E ) be a graph.
1. A walk is a sequence of vertices µ = (x1 , x2 , · · · , xk ) such
that: xi xi +1 ∈ E , for i ∈ {1, · · · , k − 1}
2. A walk is closed if x1 = xk .
3. A path is a walk without repetition of edges.
4. A cycle is a closed path.
5. An elementary path (cycle) is a path (a cycle) without
repetition of vertices (for the cycle except for one vertex).
 b d

a f

c e

Figure: Walk, Path, Cycle

Closed walk: (a, b, c, e, b, d, b, a)

A path: (a, b, d, e, b, c)
A cycle: (b, d, e, c, b)
An elementary path : (a, c, e, f )
Properties and remarks

1. From any walk we can extract an elementary path.

2. For the directed graphs, we call path or dipath (resp. circuit)
a path (resp. cycle) with all the edges having the same
direction.
3. Let G be a gaph (digraph) and x, y belonging to V , the
distance between x and y is the number of edges of a shortest
path linking x and y .
Breadth-first search
BFS(G,s)
1 for each u ∈ V \ s
2 do color[u] ← WHITE
3 d[u] ← ∞
4 Π[u] ← NIL
5 color[s] ← GRAY
6 d[s] ← 0
7 Π[s] ← NIL
8 F←∅
9 ENQUEUE(F,s)
10 while F 6= ∅
11 do u ← DEQUEUE(F)
12 for each v ∈ Adj[u]
13 do if color[v ]=WHITE
14 then color[v ] ← GRAY
15 d[v ] ← d[u] +1
16 Π[v ] ← u
17 ENQUEUE(F,v )
18 color[u] ← BLACK
Remark-Complexity

◮ • At the beginning all the vertices are white. If a vertex is

dicovered then it becomes gray. A vertex with all the adjacent
vertices are visited becomes black. We construct a spanning
tree of shortest paths.
◮ • |V | = n and |E | = m
1. line 1 to 4: O(n)
2. line 12 : O(n) P
3. line 11, loop while, it is done at most x∈V d(x) = 2m: O(m)
Total complexity O(m + n)
Analysis (I)

We denote by δ(x, y ), the distance between two vertices x and y

of G
Lemma
Let G be a graph and s an arbitrary vertex of G . Then for any
edge e = xy , we have:

δ(s, y ) ≤ δ(s, x) + 1

Lemma
Let G be a graph and assume that BFS is run on G from a vertex
s. Then upon termination, for each vertex v ∈ V , the value d[v ]
computed by BFS satisfies: d[v ]≥ δ(s, v )
Analysis (II)

Lemma
Suppose that during the execution of BFS on a graph G = (V , E ),
the queue F contains the vertices < v1 , v2 , · · · , vr >, where v1 is
the head of F and vr is the tail of F . Then:
1. d[vr ] ≤ d[v1 ]+1.
2. d[vi ] ≤ d[vi +1 ] for i ∈ {1, · · · , r − 1}

Corollary
Assume that the vertices vi and vj are enqueued during the
execution of BFS, and that vi is enqueued before vj . Then d[vi ] ≤
d[vj ]] at the ime vj is enqueued.
Analysis (III)

Theorem
Let G = (V , E ) a directed or undirected graph, and assume that
BFS is run on G from a given source s ∈ V . Then during its
execution, BFS discovers every vertex v that is reachable from the
source s, and upon termination, d[v ]= δ(s, v ) for all v ∈ V .
Moreover, for any vertex v 6= s, one of the shortest paths from s to
v is a shortest path from s to Π[v ] followed by the edge Π[v ]v.
Depth-First search

The first timestamp d(v ) records when v is discovered (and

grayed).
The second timestamp f (v ) records when search finishes after
examining v ’s adjacency list (and blackens v )
◮ At the beginning all the vertices are WHITE.
◮ Any vertex u is WHITE before d(u).
◮ Any vertex u is GRAY after d(u) and before f (u).
◮ Any vertex u is black after f (u)
Depth-First search

DFS(G)
1 for each vertex u ∈ V
2 do color[u] ← WHITE
3 Π[u] ← NIL
4 time ← 0
5 for each vertex u ∈ V
6 do if color[u]=WHITE
7 then DFS-Visit(u)
DFS-Visit(u)
1 color[u] ← GRAY /* u is discovered */
2 d[u] ← time ← time + 1
3 for each v ∈ Adj[u]
4 do if color[v ]=WHITE
5 then Π[v ] ← u
6 DFS-Visit(v )
7 Color[u] ← BLACK
8 f(u) ← time ← time + 1
Complexity:

O(n + m)
Theorem
In an DFS of a (directed or undirected) graph G = (V , E ), for any
two vertices u and v , exacly one of the following conditions holds:
T
◮ [d(u), f (u)] [d(v ), f (v )] = ∅

◮ [d(u), f (u)] ⊂ [d(v ), f (v )] and u is a descendant of v in DFS.

◮ [d(v ), f (v )] ⊂ [d(u), f (u)] and v is a descendant of u in DFS.

Corollary
A vertex v is a proper descendant of vertex u in the DFS-forest for
a (directed or undirected) graph G ⇐⇒
d(u) < d(v ) < f (v ) < f (u)
Topological sort

Definition
Let G = (V , E ) be a directed graph. A topological sort is an
injective mapping f : V −→ N (it is a linear ordering of the
vertices) such that for any x and any y , if −
→ ∈ U then
xy
f (x) < f (y ).

Theorem
A directed graph G = (V , E ) has a topological sort ⇐⇒ it does
not contain any circuit.

A directed graph without circuit is called a DAG (directed acyclic

graph).
Topological sort algorithm

Topological-Sort(G)

1 call DFS(G) to compute finishing times f (v ) for each vertex v

2 as each vertex is finished, insert it onto the front of a linked list

3 return the linked list.

Complexity: θ(n + m)
Analysis

Lemma
A directed graph is acyclic ⇐⇒ if a DFS of G yields no back edges.

Theorem
Topological-Sort(G) produces a topological sort of a directed
acyclic graph G .
Strongly connected components

Let G = (V , E ) be a directed graph.

Definition
−
→ −
→
x C y ,We define C a binary relation in the set of vertices. For any
couple ofvertices (x, y ) we will write:
−
→  x=yor :
xCy ⇔ it exists a dipath from x to y and
it exists a dipath from y to x


−
→
C is a equivalence relation.
 −
→ −
→
An equivalent class ẋ under C , ẋ = {y /x C y } is called a strongly
connected component of G .
A graph G = (V , E ) is said strongly connected if it contains only
one strongly connected component.
Strongly connected component algorithm

Strongly-connected-component(G)

1 call DFS(G) to compute finishing times f (u) for each vertex u

2 compute G −1

3 call DFS(G −1 ), consider the vertices in order of decreasing f (u)

(as computed in line 1)

4 output the vertices of each tree in the DFS forest formed in line
3 as a separated strongly connected component.

Complexity: θ(n + m)
Analysis

Lemma
Two vertices x and y belong to the same strongly connected
component of G ⇐⇒ they belong to the same tree in the DFS
forest of G −1 .

Theorem
Strongly-connected-component(G) correctly computes the
strongly components of a directed grph G .
Chapter 4- Minimum spanning trees

We deal with undirected graph.

Definition
◮ let G = (V , E ) be a graph, a partial subgraph of G is a
graph G ′ = (V , F ) with F ⊂ E
◮ a tree is an acyclic conneted graph
◮ a spanning tree of G = (V , E ) is a partial subgraph of G that
is a tree.
Theorem

Theorem
The following conditions are equivalent:
1. T is a tree
2. T is a connected graph and m = n − 1 (m number of edges, n
number of vertices)
3. T is an acyclic graph and m = n − 1
4. T is a connected graph and every edge of T is a bridge
5. T is an acyclic graph and if we link any two non adjacent
vertices of T then we create a cycle (a unique cycce)
6. For any two vertices a et b, it exists a unique path linking a
and b.
Fundamental cycle

Definition
Let G = (V , E ) be graph and T = (V , F ) a spanning, the
fundamental cycle associated to e ∈ E \ F is the unique cycle
CT (e) of T ∪ e

12 13

8
11 5 3

15 2 14
10 9

1
Minimum spanning tree - Problem

Definition
Let G = (V , E ) be a graph p : E → R be a weight funcion. Let
T = (V ,P
F ) be a spanning tree of G then:
p(T ) = e∈F p(e)

Problem
Let G be a graph with a weighted function, find a minimum
(weighted spanning) tree for G .
Kruskal Algorithm (1956)

MST-Kruskal(G,p)
/* the edges are sorted into the nondecreasing order
by weight */
/* p(e1) ≤ p(e2 ) ≤ · · · ≤ p(em ) */

1 S ←∅

2 k←0

3 n and |S| < n − 1

while k < m

4 do if (V , S ∪ ek+1 ) is acyclic.

5 then S ← S ∪ ek+1

6 k ← k +1
Analysis-Complexity
We prove by contradition that:
Theorem
Any spaning tree T ∗ = {e1 , , e2 , · · · , en−1 } obtained by Kruskal
algorithm is optimal.

For the acyclic test, we give a numbering to the vertices from 1 to

n and we take an edge iff the number of the extremities of the
edge are distinct. Then all the vertices having the same number as
one of the extremity is renumbered with the samllest nuber of the
extremities.
Complexity:
1. to sort the edges: m log m
2. to compare the extremities of the edges θ(m)
3. to renumber the vertices O(n2 )
The complexity is: O(n2 + m log m)
Prim Algorithm (1956)

MST-Prim (G,p,r)

1 S←∅

2 A ← r /*A is the set of marked vertices*/

3 while |S| < n − 1

4 do u ← xy s.t. x ∈ A, y ∈
/ A and p(xy ) is minimum.

5 S ←S ∪u

6 A← S ∪y
Analysis

We prove by induction on the number of steps that:

Theorem
If S is the set of selected edges then it exists a minimum spanning
tree containg S
Prim Algorithm with priority queue

MST-Prim-Q(G,p,r)
1 for each u ∈ V
2 do key[u] ← ∞
3 Π[u] ← NIL
4 Key[r ] ← 0
5 Q←V
6 while Q 6= ∅
7 do u ← Extract-Min(Q)
8 for each v ∈ Adj[u]
9 do if v ∈ Q and p(uv ) < Key[v ]
10 then Π[v ] ← u
11 Key[v ] ← p(uv )
Complexity

◮ Build the heap O(n)

◮ Extract minimum log n, we do it n times
◮ line 8 to 11 O(m) × O(log n)
◮ Total: O(n log n + m log n), it is O(m log n)
Chapter 5- Shortest Paths
1- Definitions
Let G = (V , E ) be a directed graph.
Let w : E → R be a weight function. For u ∈ E w (u) is the weight
of u
Definition
◮ A path is a alternated sequence of vertices and edges
x1 , u1 , x2 , u2 , . . . , uk , xk+1 such that ui = −
x− −−→
k xk+1 .
P
◮ If P is a path, the weight of P is w (P) = u∈P w (u)
◮ An elementary path does not go through the same vertex
twice.
◮ A root of G is a vertex s of G such that for each x ∈ V \ {s}
it exists a path from s to x.
◮ A circuit is a closed path.
1- Definitions

Definition
◮ A circuit X
C is said an absorbing circuit if :
w (C ) = p(u) < 0
u∈C
◮ An arborescence with root r in a directed graph G = (V , E )
is a sub-graph such that the underlying undirected graph is a
tree and it exists a path from s to any vertex of the
arborescence.
◮ A shortest path linking two vertices x and y is a path linking
x to y with a smallest weight.
Theorem
Let G = (V , E ) be a directed weighted graph. Let s ∈ V , then for
any x ∈ V \ {s} it exists a path linking s to x iff:
1. s is a root of G
2. G does not contain an absorbing circuit.
Single-source shortest path
1: The weights are nonnegative: Dijkstra Algorithm

Remark. There is no absorbing circuit

Idea. We start from the vertes s. we build a set of edges by taking
successively edges with initial vertex in D (the set of discovered
vertices) and the final extremity not in D.
Dijkstra Algorithm

Dijkstra(G,s)
1 D ← s; A(s) ← ǫ; x1 ← s; d(s) ← 0; k ← 1
2 for each (x ∈ V and x 6= s)
3 do d(x) ← ∞
4 while (k < n and d(xk ) < ∞)
5 do for each u ∈ E s.t. I (u) = xk and T (u) ∈
/D
6 x ← T (u)
7 if d(x) > d(xk ) + w (u)
8 then d(x) ← d(xk ) + w (u)
9 A(x) ← u
10 Choose x ∈/ D s.t. d(x) = min{d(y ), y ∈
/ D}
11 k ←k +1
12 xk ← x
13 D ← D ∪ {xk }
Complexity

◮ line 2-3 O(n)

◮ line 5-9 O(n)
◮ line 10 to find the minimum O(n2 )
◮ total: O(n2 )
2- Graphs without circuit. DAG.
Bellman Algorithm

Bellman(G,s)
1 D ← s; A(s) ← ǫ; x ← s; d(s) ← 0
2 for each (x ∈ V and x 6= s)
3 do d(x) ← ∞
4 while it exists x ∈/ D with all its predecessors in D
5 do d(x) ← minu/T (u)=x,I (u)∈D {d(I (u)) + w (u)}
7 let ũ s.t. d(x) = minu/T (u)=x,I (u)∈D {d(I (u)) + w (u)}
8 A(x) ← ũ
9 D ← D ∪ {x}

Complexity : O(n2 )
 G = (V , E , w )
de num(1)=s

Bellman-with-topological-sort(G,s)
1 A(s) ← ǫ
2 d(s) ← 0
3 for each x ∈ V , x 6= s
4 do d(x) ← +∞
5 for j ← 2 to n
6 do y ← de num(j)
7 d(y ) ← minu/xy ~ =u [d(x) + w (u)]
8 let ũ such that d(y ) = d(x) + w (ũ)
9 A(y ) ← ũ

Complexity : O(n2 )
All-pairs shortest paths
1-Floyd Algorithm

We assume that the graph G = (V , E ) has a weight function ω.

V = {1, 2, . . . , n} and G does not contain absorbing circuit. We
proceed step by step. We consider the paths linking i and j such
that all intermediate vertices are in {1, · · · , k} at the step k. we
denote by:
◮ dk (i , j) the weight of a shortest path using only intermediates
vertices belonging to {1, · · · , k}
◮ predk (i , j) the predecessor of j in such a path.
We use the n × n matrix A such that :
( − → −
→
ω( ij ) si ij ∈ E
aij = −
→
+∞ si ij 6∈ E

At each step k aij = dk (i , j)

And the n × n matrix P :

 
x11 · · · x1n
P =  ... . . . ... 
 

xnn · · · xnn

where Pij = predk (i , j) At the beginning Pij = i

Floyd(G,w)

1 for i ← 1 to n
2 do for j ← 1 to n
3 A[i , j] ← ω(i , j)
4 P[i , j] ← i
5 do for k ← 1 to n
6 do for i ← 1 to n
7 do for j ← 1 to n
8 do if A[i , k] + A[k, j] < A[i , j]
9 then A[i , j] ← A[i , k] + A[k, j]
10 P[i , j] ← P[k, j]

Complexity : O(n3 )
Existence of paths between all pairs of vertices
1-Matrix

Let G = (V , E ) be a directed graph with V = {1, 2, . . . , n}.

We want to know if it exists a path from i to j for each couple
(i , j) of vertices of G .
Definition
Let G = (V , E ) be a directed graph. We define the boolean
matrix:

A = (aij )
1≤i ≤n
1≤j ≤n

ai ,j = 1 ⇔ ~ij ∈ E
Proposition
Let p ≥ 2 be a integer, we define
(p)
A(p) = (aij )
1≤i ≤n
1≤j≤n
A(p) = A(p−1) .A
(p)
We have : aij = 1 ⇔ it exists a path from i to j with a length
equal to p
2- Transitive closure- Warshall Algorithm

Definition
Let G = (V , E ) be a directed graph. The transitive closure of G is
the graph G ∗ = (V , E ∗ ) such that:
~ij ∈ E ∗ ⇔ it exists a path linking i to j in G

We will use the boolean matrix:

A = (aij )
1≤i ≤n
1≤j ≤n
for i = j ai ,j = 1

ai ,j = 1 ⇔ ~ij ∈ E
Warshall Algorithm

Warshall(G)

1 for i ← 1 to n
2 do for j ← 1 to n
3 do A[i , j] ← c(i , j)
4 do for k ← 1 to n
5 do for i ← 1 to n
6 do for j ← 1 to n
7 do A[i , j] ← (A[i , j] ∨ (A[i , k] ∧ A[k, j]))

Complexity : O(n3 )
Chapter 6- Maximum Flow
1- Definitions

Definition (Network)
Let G = (V , E ) be a directed graph.
◮ c : E → R+ . For each e ∈ E , c(e) is a nonnegative capacity.
◮ s and p two vertices of G , s is the source, p the sink of the
network.
◮ a special edge ur = ps is the back edge, c(ur ) = +∞
Flow

Definition
A flow is a real-valued function f : E → R+ such that:
X X
∀x ∈ V : f (u) = f (u)
u/T (u)=x u/I (u)=x
Maximum flow problem

Let G = (V , E , ur , c) be a network (c(ur ) = +∞).

Maximum flow problem
Find a real-valued function f : E → R+ such that:
◮ f is a flow
◮ ∀u ∈ E : 0 ≤ f (u) ≤ c(u)
◮ f (ur ) is maximum under the previous two conditions
Linear programming formulation

Let A be the incidence matrix of the graph G .

Maximum Flow Problem

 Af = 0
(FM ) 0≤f ≤c
f (ur ) = z(Max)

Ford-Fulkerson Algorithm

Let f be a flow, we say that the flow is feasible if

∀u ∈ E : 0 ≤ f (u) ≤ c(u).
We begin with a feasible flow . Let P be a path linking s to p with
its edges in E \ {ur }. We denote by P + the set of edges of P
oriented in the direction s to p and P − the set of edges of P
oriented in the reverse direction. By starting from s we search a
path P linking s and p containing no saturated edges. An edge is
saturated in the two following cases:
◮ u ∈ P + and f (u) = c(u)
◮ u ∈ P − and f (u) = 0
A such path P with no saturated edges is called an augmenting
path.
We define:
◮ δ1 = minu∈P + {c(u) − f (u)}
◮ δ2 = minu∈P − {f (u)}
◮ δ = min{δ1 , δ2 }
We define a new real-valued function f ′ such that:
◮ f ′ (u) = f (u) if u ∈
/ P ∪ {ur }
◮ f ′ (u) = f (u) + δ if u ∈ P +
◮ f ′ (u) = f (u) − δ if u ∈ P −
◮ f ′ (ur ) = f (ur ) + δ

Conclusion
f ′ is a feasible flow and f ′ (ur ) > f (ur )
Marking

f is a feasible flow of G .
We start from s. We mark the vertices of G .
s is marked. δ(s) = 0
◮ if x is marked and it exits u = xy~ with y not marked and
f (u) < c(u) then
◮ δ(y ) = min{δ(x), c(u) − f (u)}
◮ A(x) = u, y is marked.
◮ ~ with y not marked and
if x is marked and it exits u = yx
f (u) > 0 then
◮ δ(y ) = min{δ(x), f (u)}
◮ A(x) = u, y is marked.
Ford-Fulkerson Algorithm

G = (V , E , ur , c)

Marking Algorithm(G , f ) /* f is a feasible flow */

1 δ ← δ(s) ← c(ur ) − f (ur )
2 Y ← {s}
3 while p ∈/ Y and δ > 0
4 do if it exists u = xy ~ , x ∈ Y, y ∈/ Y et f (u) < c(u)
5 then Y ← Y ∪ {y }
6 A(y ) ← u
7 δ(y ) ← min{δ(x), c(u) − f (u)}
8 else
9 ~ x ∈ Y, y ∈
if it exists u = yx, / Y et f (u) > 0
10 then Y ← Y ∪ {y }
11 A(y ) ← u
12 δ(y ) ← min{δ(x), f (u)}
13 else δ ← 0
14 if p ∈ Y then δ ← δ(p)
Ford-Fulkerson Algorithm

G = (V , E , ur , c)

Changing flow(G , f , δ)
1 x ←p
2 f (ur ) ← f (ur ) + δ
3 while x 6= s
4 do u ← A(x)
5 if x = T (u) then f (u) ← f (u) + δ
6 x ← I (u)
7 else
8 f (u) ← f (u) − δ
6 x ← T (u)
Ford-Fulkerson Algorithm

G=(X,U,c)

Maximum flow Algorithm(G )

1 for each u ∈ U do f (u) ← 0
2 Iterate { Marking
3 stop δ = 0
4 Changing flow
5 }
Max Flow - Min Cut

~
Let G = (V , E , c, ur ) and ur = ps.
Definition
We say that C ⊂ E is a separating cut for s and p, if we can find
Y ⊂ V such that s ∈ Y and p ∈ / Y and

C = {u ∈ E : I (u) ∈ Y , T (u) ∈
/ Y}

Definition
The capacity of a cut C separating s and p is:
X
c(C) = c(u)
u∈C
Max Flow - Min Cut

Theorem
For any feasible flow f of G = (V , E , c) (c(ur ) = +∞) and for
any cut C separating s and p we have:

f (ur ) ≤ c(C)

Theorem
For any cocyle Ω(Y ):
f is a flow of G = (V , E ) ⇐⇒
X X
For any cocyle Ω(Y ) : f (u) = f (u)
u∈Ω(Y )+ u∈Ω(Y )−
Max Flow - Min Cut

Corollary
If the Marking Algorithm terminates without reaching p then the
obtained flow by Ford-Fulkerson Algorithm is an optimal solution
for the Maximum Flow problem in G = (V , E , c, ur ).

Theorem (Max Flow - Min cut)

The maximum value for a feasible flow of G = (V , E , c) (f (ur )) is
equal to the minimum capacity of a cut separating s and p.
Maximum matching in a bipartite graph

Definition
An undirected graph G = (V , E ) is bipartite if V = Y ∪ Z with
Y ∩ Z = ∅ and Y , Z are independant sets.

Theorem
A graph G is bipartite ⇐⇒ G does not contain cycles of odd
length.

Definition
A matching is a subset K of E such the edges belonging to K are
independant.

Definition
A maximum matching is a matching that saturates the maximum
number of vertices.
Definition
A transversal of a graph G = (V , E ) is a set of vertices T ⊂ V
such that V \ T is a stable set, i.e. any edge of G has at least one
extremity in T .

Observation
Let K be a matching and T be a transversal of G then |K | ≤ |T |.

Observation
If |K | = |T | then K is a maximum matching and T is a minimum
transversal.
Problem
Find a maximum matching in a bipartite graph.
Maximum matching in a bipartite graph

Let G = (V , E ) be a bipartite graph. E = Y ∪ Z with Y ∩ Z = ∅

and Y , Z are stable sets of vertices.
We define a network R = (V ′ , E ′ , c):
◮ V ′ = Y ∪ Z ∪ {s, p}, E ~ = {~y z : xy ∈ E }
◮ E′ = E ~ ∪ {~s y : y ∈ Y } ∪ {~z p : z ∈ Z }
◮ c : E → R+ ∪ {+∞}
′

◮ ∀u = yz : y ∈ Y , z ∈ Z , c(u) = c(ur ) = +∞
◮ ∀u = sy : y ∈ Y or u = zp : z ∈ Z , c(u) = 1.
Maximum matching in a bipartite graph

Let f be a maximum flow:

◮ f (ur ) = C(Ω+ (Y )), Ω+ (Y ) is a minimum cut.
◮ For any edge u ∈ E ′ , f (u) = 1 or f (u) = 0.
◮ Any two edges u = ~y z and u ′ = ~y ′ z ′ such that
f (u) = f (u ′ ) = 1 are not adjacent.
◮ K = {~u ∈ E : f (~u ) = 1} is a matching.
P
◮ f (ur ) = u∈E f (u) = |K | is the cardinality of the matching.
Maximum matching in a bipartite graph

Let S such that Ω+ (S) is the minimum cut obtained by the

algorithm. s ∈ S, p ∈
/S
◮ Ω+ (S) has finite capacity, then it does not contain any edge
u = ~y z. It implies that if u = ~y z then y ∈ S̄ either z ∈ S.
◮ T = (S̄ ∩ Y ) ∪ (S ∩ Z ) is a transversal of G .
◮ the edges of Ω+ (S) are
◮ ~s y : y ∈ S̄ ∩ Y
◮ ~z p : z ∈ S ∩ Z
◮ All this |T | edges have a capacity equal to 1, then c(C) = |T |
◮ c(C) = |T | = f (ur ) and f (ur ) = |K |, then |T | = |K |.
◮ K is a maximum matching of G .
Maximum matching in a bipartite graph

Theorem
In a bipartite graph, the cardinality of a minimum transversal is
equal to the cardinality of a maximum matching.
Menger Theorem

Theorem
Let s and p be two vertices of a directed graph G . The maximum
number Psp of edge disjoint paths linking s and p is equal to the
minimum cardinality Ns,p of a set of edges separating p from s