Course Instructor

ANUJ GHIMIRE
DISCLAIMER
 This document does not claim any originality and
cannot be used as a substitute for prescribed textbooks.
 The information presented here is merely a collection
from various sources as well as freely available material
from internet and textbooks.
 The ownership of the information lies with the
respective authors or institutions.
Chapter 4_Part_3

Graph Theory
Graph Coloring
 When a map is colored, two regions with a common
border are customarily assigned different colors.
 We want to use the smallest number of colors instead
of just assigning every region its own color.
 A coloring of a simple graph is the assignment of a
color to each vertex of the graph so that no two
adjacent vertices are assigned the same color.
 The chromatic number of a graph is the least number
of colors needed for a coloring of the graph.
 The Four Color Theorem
 Statement: The chromatic number of a planar graph is
no greater than four.

• Four colors are sufficient to color a map of the contiguous United States.
• Source of map: [Link]
Graph Coloring
What is the chromatic number of the graph shown
below?

b e

a g
d

c f
Graph Coloring
The chromatic number must be at least 3 since a, b, and c
must be assigned different colors.
So Let’s try 3 colors first. 3 colors work, so the chromatic
number of this graph is 3.

b e

a d g

c f
 Example
What is the chromatic number for each of the following
graphs?

White
White Yellow

Green Yellow
Yellow White

White Yellow Yellow White

Chromatic number: 2 Chromatic number: 3

Network Flow
 In graph theory, a flow network (also called transport
network, is a directed graph where each edge has a
capacity and each edge receives a flow.
 Here, capacity implies the maximum rate at when
something flows through the edge and the amount of
flow on an edge cannot exceed the capacity of the
edge.
 All vertices except the source denoted by S and sink
denoted by D are called intermediate vertices.
Network Flow
 A flow must satisfy the restriction that the amount of
flow into an intermediate vertex equals the amount of
flow out of it, unless it is a source S, which has only
outgoing flow, or sink D which has only incoming
flow.
 They are typically used to model problems involving
the transport of items between locations, using a
network of routes with limited capacity.
 Examples include modeling traffic on a network of
roads, fluid in a network of pipes, and electricity in a
network of circuit components
Network Flow
 Note: In most cases, there is single source and single
destination but sometimes there are multiple sources
and multiple destinations.
 In such case, we can create the equivalent transport
network by combining these multiple source into
single source with additional edge.
 Network Flow
A J G

B E H

C F I

In the above figure, there are two sources A and C and three destinations G, H, and I.
 Network Flow
Then, the equivalent network flow with single source S and single destination D is as
shown in figure.

A J G

S B E H D

C F I
Flows
 The resources that transport along any edge is known as
flow.
 Let us label edges with two components as (c(e), f(e))
where c(e) is the capacity of edge and f(e) is the
amount of flow through that edge.
 The two criteria are:
 The amount of flow can't exceed the capacity of that edge.
 For every node (except S & D), the amount of flow flowing
into vertex v (incoming flow) must be equal to the amount
of flow flowing out of vertex v which is also called flow
conservation.
Flows
(10,7)
A G

(15,13) (13,13)
(9,6) (5,1)
(10,5)

S B E D
(9,3) (9,2)

(8,6)
(15,9) (8,4)
(7,7)
C F
(10,3)

Incoming flow at B = 6 + 6 = 12
Outgoing flow at B = 5 + 3 + 4 = 12

Note: Total flow leaving at S = Total flow arriving at D

Flows
 Saturated Flow
 The flow along an edge is said to be saturated if the
capacity of an edge equals with the flow of that edge.
 That is whenever c(e)=f(e), then such flow is saturated flow.
Network Flow Problem
 Given a transport graph G = (V, E) where each edge e is
associated with its capacity c(e) > 0 and the two special
node: source node S and sink or destination node D.
 Then the network problem states that what is the
maximum total amount of flow possible to carry on
from Source node S to Destination node D.
 A flow F in a network (G, k) is called a maximal flow if
|F| >= |F'| for every flow F' in (G, k), where k is the
capacity of Network.
Computing Maximum Flow
 To compute the maximum flow in the given transport
network (G,k), following steps are applied:
 Identify the augmenting path
 Increase flow along that path
 Repeat the above steps till the maximum flow is obtained.
 An augmenting path P is simple path from S to D with
unsaturated edge.
 We build augmented path in two ways:
 Augmenting path with only forward unsaturated edge.
 Augmenting path with some backward edge.
Computing Maximum Flow
 In backward edged Augmenting Path (A.P), the
backward edge must have positive flow and of course,
the forward edge must be unsaturated.
 When an edge e.g. dc is taken in opposite direction
e.g. cd, is called backward edge.
 To increase the value of the flow two basic ways are
used:
 If an edge is not being used to capacity, try to send more
flow through it.
 If an edge is working against us by sending some flow back
toward the source, we could try to reduce the flow along
this edge and redirect in a more practical direction.
Example_1
 Find the maximum flow for the network given below:
(9,4)
A F

(15,11) (10,10)
(5,4)
(7,7) (4,2)

S (15,6) E D
B
(10,4)

(7,7) (4,0)
(15,10) (5,4)
(10,7)
C G
(7,3)
Solution,
To compute the maximum flow in the given network , we use following
steps:
 First we identify the augmenting path
 Second we increase flow along that augmenting path
 Repeat above steps until the maximum flow is obtained.
For augmenting path we first look for forward unsaturated edge.
Here different forward edges from S to G are:
SAFD
SABFD Among the given forward edges the
SABED only unsaturated augmenting path is
SABGD S C G D
SABEFD All other path has the A B, C B
and F D i.e. saturated flow
SCBED (capacity=flow).
SCBGD
SCBEGD
SCGD
To increase the flow along that augmenting path, we need to
compute the slack (the value that can be added to the flow of
augmented path).
We have S C G D as the augmenting path
Now Slack (S,C) = Capacity – Flow
= 15-10
=5
Again Slack (C,G) = Capacity – Flow
= 7-3
=4
Also Slack (G,D) = Capacity – Flow
= 10-7
=3
Among the slack (5, 4, 3) the minimum is 3. So, add 3 to all the flow
in the augmenting path
The network flow becomes as follows:

(9,4)
A F

(15,11) (10,10)
(5,4)
(7,7) (4,2)

S (15,6) E D
B
(10,4)

(7,7) (4,0)
(15,13) (5,4)
(10,10)
C G
(7,6)
Again,
We need to look for augmenting path, first check if there are any
forward unsaturated edge.
Here different forward edges from S to G are:
SAFD
SABFD
SABED Among the given forward edges the
there are no any unsaturated
SABGD augmenting path
SABEFD All path has the A B, C B, F D
and G  D i.e. saturated flow
SCBED (capacity=flow).
SCBGD
SCBEGD
SCGD
So,
We need to look for augmenting path with some backward edge.
Different augmenting path with backward edges from S to G are:
SAFBED
SAFED
SCGBED
Among the given backward edges the
SCGED
augmenting path SCGED
cannot be proceed as G E has the
flow value 0.

Now, we can proceed with any of the augmenting path with backward
edge.
We first continue with SAFBED
To increase the flow along that augmenting path, we need to
compute the slack (the value that can be added to the flow of
augmented path).
We have SAFBED as the augmenting path
Now, Slack (S, A) = Capacity – Flow = 15-11 = 4
Again, Slack (A,F) = Capacity – Flow = 9-4 = 5
Also, Slack (F,B) = 4
Here F B is the backward edge so the slack value is same as
the flow value i.e. 4
Similarly, Slack (B,E) = Capacity – Flow = 15-9 = 9
Finally, Slack (E,D) = Capacity – Flow = 10-4 = 6
Among the Slack (4, 5, 4, 9, 6) the minimum is 4. So, add 4 to all the
flow in the forward augmenting path and subtract 4 in the backward
edge.
The network flow becomes as follows:

(9,8)
A F

(15,15) (10,10)
(5,0)
(7,7) (4,2)

S (15,10) E D
B
(10,8)

(7,7) (4,0)
(15,13) (5,4)
(10,10)
C G
(7,6)
Again, we have augmenting path with backward edge as:
SAFED
SCGBED
Now we cannot choose SAFED because SA becomes
saturated flow as capacity=flow.
Now, we proceed with SCGBED
To increase the flow along that augmenting path, we need to
compute the slack (the value that can be added to the flow of
augmented path).
We have SCGBED as the augmenting path
Now, Slack (S, C) = Capacity – Flow = 15-13 = 2
Again, Slack (C,G) = Capacity – Flow = 7-6 = 1
Also, Slack (G,B) = 4
Here F B is the backward edge so the slack value is same as
the flow value i.e. 4
Similarly, Slack (B,E) = Capacity – Flow = 15-10 = 5
Finally, Slack (E,D) = Capacity – Flow = 10-8 = 2
Among the Slack (2, 1, 4, 5, 2) the minimum is 1. So, add 1 to all the
flow in the forward augmenting path and subtract 1 in the backward
edge.
The final network flow becomes as follows:

(9,8)
A F

(15,15) (10,10)
(5,0)
(7,7) (4,2)

S (15,11) E D
B
(10,9)

(7,7) (4,0)
(15,14) (5,3)
(10,10)
C G
(7,7)

So, the maximum flow of the network is 15+14=29.

S-D Cut
 A cut of transport network is a set of edge whose
removal will divide the network into two halves 𝑋 and
𝑋ത where:
 Source vertex S ∈ 𝑋
ത
 Sink vertex D ∈ 𝑋
 It is denoted by (𝑋, 𝑋ത )
ഥ ) is defined as sum of
 The capacity of S-D cut (𝑿, 𝑿
ത It is denoted by
all the capacities of edges from 𝑋 to 𝑋.
K(𝑿, 𝑿ഥ ).
Example_1
 Find all the S-D Cut in the following transport network
(4,4)
A C

(8,4) (7,4)

S D

(7,5)
(6,5)
B E
(5,5)
Solution,
 To compute the S-D cut in the given network, we will divide the
network into two halves 𝑋 and 𝑋ത where:
 Source vertex S ∈ 𝑋
 Sink vertex D ∈ 𝑋ത
Different possible S-D cuts are obtained by dividing the network into
two half as:
 First we divide the network where Source lies in one set and all
other nodes including Sink in the other set.
 We then divide the set with all possible combination where two
node including Source will be in first set and remaining node
including Sink in second set.
 We then divide the set with all possible combination where
three node including Source will be in first set and remaining
node including Sink in second set.
 We continue until all node except Sink in first set and Sink in
second set.
 There is path from S to A and S
to B so we make that pair and
Different possible S-D cuts are with capacity are: add the capacity of each pair
𝑋 𝑋ത (𝑋, 𝑋ത ) K(𝑋, 𝑋ത )
{S} {A,B,C,E,D} {(S,A),(S,B)} 8+7=15
{S,A} {B,C,E,D} {(S,B),(A,C)} 7+4=11
{S,B} {A,C,E,D} {(S,A),(B,E)} 8+5=13
{S,A,B} {C,E,D} {(A,C),(B,E)} 4+5=9
{S,A,C} {B,E,D} {(S,B),(C,D)} 7+7=14
{S,A,E} {B,C,D} {(S,B),(A,C),(E,D)} 7+4+6=17
{S,B,C} {A,E,D} {(S,A),(B,E),(C,D)} 8+5+7=20
{S,B,E} {A,C,D} {(S,A),(E,D)} 8+6=14
{S,A,B,C} {E,D} {(B,E),(C,D)} 5+7=12
{S,A,B,E} {C,D} {(A,C),(E,D)} 4+6=10
{S,A,B,C,E} {D} {(C,D),(E,D)} 7+6=13
From the above table the minimum capacity of S-D cut is 9
Example_2
 Find the maximum flow in the given transport
network using S-D cut method
5
U W

3 5

4 7
S 9 D

2 5

V X
6
Solution,
The maximum flow can also be computed using the S-D cut.
There is a Theorem as Max Flow Min Cut which states: In any flow
(transport) network, the value of any maximal flow is equal to
the capacity of a minimal cut.
So, we compute the S-D cut in the given network, which will be the
maximum flow in that network.
Different possible S-D cuts are obtained by dividing the network into
two half as:
 First we divide the network where Source lies in one set and all
other nodes including Sink in the other set.
 We then divide the set with all possible combination where two
node including Source will be in first set and remaining node
including Sink in second set.
 We then divide the set with all possible combination where
three node including Source will be in first set and remaining
node including Sink in second set.
 We continue until all node except Sink in first set and Sink in
second set.
Different possible S-D cuts are with capacity are:
𝑋 𝑋ത (𝑋, 𝑋ത ) K(𝑋, 𝑋ത )
{S} {U,V,W,X,D} {(S,U),(S,V)} 3+2=5
{S,U} {V,W,X,D} {(S,V),(U,W),(U,V)} 2+5+4=11
{S,V} {U,W,X,D} {(S,U),(V,W),(V,X)} 3+7+6=16
{S,W} {U,V,X,D} {(S,U),(S,V),(W,D)} 3+2+5=10
{S,X} {U,V,W,D} {(S,U),(S,V),(X,W),(X,D)} 3+2+9+5=19
{S,U,V} {W,X,D} {(U,W),(V,W),(V,X)} 5+7+6=18
{S,U,W} {V,X,D} {(S,V),(U,V),(W,D)} 2+4+5=11
{S,U,X} {V,W,D} {(S,V),(U,V),(U,W),(X,W),(X,D)} 2+4+5+9+5=25
{S,V,W} {U,X,D} {(S,U),(V,X),(W,D)} 3+6+5=14
 𝑋 𝑋ത (𝑋, 𝑋ത ) K(𝑋, 𝑋ത )
{S,X,V,} {U,W,D} {……..} ……
…… …… …… ……
…… …… …… ……
{S,U,V,X} {W,D} {(U,W),(V,W),(X,D)} 5+7+5=17
{S,U,V,W} {X,D} {(V,X),(W,D)} 6+5=11
…… …… …… ……
…… …… …… ……
{S,U,V,X,W} {D} {(X,D),(W,D)} 5+5=10

From the above table the minimum capacity of S-D cut is 5.

From Max Flow Min Cut Theorem In any flow (transport) network, the value
of any maximal flow is equal to the capacity of a minimal cut.
So the maximum flow in the transport network is 5
End of Chapter 4
Thank You !!!!