1

GRAPH-THEORY

Dr. Ilyas Fakhir

 Course Outline
2

Introduction to Graph Theory, Basic definitions, computer representations and

properties of Graph, Data structure for representing Graphs, Fundamental theorem of
Graph Theory, Isomorphic and Special Graphs, Properties of Trees and Forests, Binary
tree, Balanced binary tree, Directed and Undirected rooted tree, Minimum Spanning
Tree algorithms and implementation, Path and Distance in graphs, Shortest path
algorithms and implementation, Cycle and distance in weighted graph and digraphs,
Distance algorithms and implementation, Eulerian graphs and Hamiltonians graphs
with applications, Flow networks, Max-flow Min-cut Theorem, Ford-Fulkerson
Algorithm, Graph coloring, Edge coloring, Planar graphs, Four color theorem,
Deadlock of computer system, Matching Algorithms, Dominance & Ramsey theory.
Recommended Books:
1. Fournier (2011), Graph Theory & Applications (1st Ed), Published by Wiley-ISTE.
2. Chartrand (1995), Applied Algorithmic Graph Theory (1st Ed), Published by McGraw
Hill College.
3. Jonathan (2004), Handbook of Graph Theory (Series Edition), Published by CRC
Press.
4. J. A. Bondy (1982), Graph Theory with Applications (8th Ed), Published Elsevier
USA.
 Konigsberg Bridge Problem
3

A Rules
1.

B D 2.

C
 Your solution
4

Did it every time .1

Did it at least once .2

Can’t seem to do it .3
4 6.1 Introduction to Graphs
 Konigsberg Bridge th
(8 bridge)
5

5 6.1 Introduction to Graphs

 Your solution
6

Did it every time .1

Did it at least once .2

Can’t seem to do it .3 6 6.1 Introduction to Graphs

 Konigsberg Bridge (9th bridge)
7

6.1 Introduction to Graphs

 Your solution
8

Did it every time .1

Did it at least once .2

Can’t seem to do it .3 8 6.1 Introduction to Graphs

 3 Cases for Konigsberg
9

1. 7 Bridges (Non-traversable) .1 Picture

2. 8 Bridges (Euler Path) Picture

3. 9 Bridges (Euler circuit)

Picture
 Euler’s View
10

Map Graph

A
B
C

10 6.1 Introduction to Graphs

 You try one
A Graph

River
Island
Island
B C

11 6.1 Introduction to Graphs

 Motivation
12

 What is the common link between the following

problems: traffic network design and cancer
research?
 Arranging marriages and scheduling flights?
 Finding cure for mental illness, computer chip
design, architectural floor planning, fighting terror
online?
 Fighting epidemics, e-commerce, designing voting
schemes, job assignment, designing electrical
networks, deciding on facility location,
communication networks etc.
 What is Graph Theory?
13

Definition: The mathematical theory of the properties

and applications of graphs.

Used to understand and solve

many of mathematical and path
problems.
 Fields of Study
14

The cells of a GSM Mathematical

mobile phone network problem

Other examples:

Electrical eng.•
Biochemistry•
Music Computer science•
Physics•
 Applications in computer Science (1)
15

Since computer science is not a concrete/centralized

subject, we can introduce graph theory in many areas.

But where

Let’s see some

examples…
 Applications in computer Science (2)
16

Networks: Graph theory can be used in computer

networks, for security purpose or to schematize network
topologies, for example.
 Applications in computer Science (3)
17

Webpage: can be represented by a directed

graph. The vertices are the web pages available at
the website and a directed edge from page A to
page B exists if and only if A contains a link to B.

Facebook is based in
graph theory
 Applications in computer Science (4)
18

Workflow: It’s sequence of processes through which a

piece of work passes from initiation to completion. Can be
also represented as directed graph.
 Applications in computer Science (5)
19

Neural Networks: A series of algorithms that

attempt to identify underlying relationships in a set
of data by using a process that mimics the way
the human brain operates.
 Applications in computer Science (6)
20

Google Maps:
 Graph Operations (1)
21

Basic Operations
Graph Operations (2)

Shortest Path: is the problem of finding a path

between two vertices (or nodes) in a graph such
that the sum of the weights of its constituent
edges is minimized. E.g. Dijkstra’s algorithm
 What is a graph?
23

 A set of points and lines joining these points.

 Formally: G=(V,E), V-vertices V(G), E-edges E(G)
 The cardinality of V, is the number of vertices
denoted by n or nG and cardinality of E, is the
number of edged denoted by m or mG.
e6
v1
v4 V2 and v3 are adjacent.
v3 e2 is incident with v2
e1
e2 e3 and V3.
e5
v2
v5
e4
 Representation
24

 It is both usual and practical to draw a graph in a

plane in the following manner: the vertices are
represented by dots and the edges by simple
lines (which can be mathematically defined with
precision) connecting two endvertices.
 In previous example V = {v1, v2, v3, v4, v5} and
E = {e1, e2, e3, e4, e5, e6}.
 Vertex v4 is isolated vertex and edge e6 is
associated twice with the vertex v1 (loop)
 Terminology
25

 Two edges e and e’ or more may have the same

endvertices x and y; then these edges are said to
be parallel or there may be a multiple edge joining
x and y.
 A graph is simple if it has no loop or multiple edges,
i.e. each edge is identified by its pair of
endvertices, which are different, and denoted by
e = xy.
 A non-simple graph G is sometimes associated with
what is called the underlying simple graph.
 Isomorphism
26

 Isomorphism of graph G = (V, E) to a graph H = (W,

F) is two bijection: φ from V onto W and ψ from E to
F, so that for e ∈ E and x, y ∈ V, the edge ψ(e) has
for endvertices φ(x) and φ(y) in H if and only if the
e has x and y as endvertices in G.
 This means that these mappings preserve the
incidence relation of the edges and the vertices.
 Two isomorphic graphs are in fact identical in their
graph structure.
 Isomorphism
27

 They have exactly the same properties.

 They can only be distinguished by the sets of their
elements, vertices and edges, in more concrete terms,
by the names or labels given to these elements.
 Isomorphism
28

 Next, set f (1) = 1 and try to walk around

clockwise on the star.
2 2

1 1 3
3

5 4 5 4
 Presentations of graphs
29

 Drawing v3
e2
v4
e3

e5
 Incidence matrix v2
e4 v5

e1 e6
v1
e1 e2 e3 e4 e5 e6
v1 1 0 0 0 0 2
v2 1 1 0 1 0 0
v3 0 1 1 0 1 0
v4 0 0 0 0 0 0
v5 0 0 1 1 1 0
 Presentations of graphs
30

 Adjacency matrix
e2 v3
v1 v2 v3 v4 v5 v4
v1 2 1 0 0 0 e3

v2 1 0 1 0 1 e4 e5
v5
v2
v3 0 1 0 0 2
e1 e6
v1
v4 0 0 0 0 0

v5 0 1 2 0 0
 Directed Graphs
31

e2 v3
v4
 Adjacency matrix e3

v1 v2 v3 v4 v5 e4 e5
v5
v2
v1 1 0 0 0 0
e1 e6
v2 1 0 1 0 0 v1

v3 0 0 0 0 1

v4 0 0 0 0 0

v5 0 1 1 0 0
 Weighted Directed Graphs
32

2 v3
v4
 Adjacency matrix 2
5
v1 v2 v3 v4 v5 3 v5
v2
v1 3 0 0 0 0
1 3
v2 1 0 2 0 0 v1

v3 0 0 0 0 2

v4 0 0 0 0 0

v5 0 3 5 0 0
 Graphs as models
33

 Networks: transportation, roadmaps, computer,

electrical, etc.
 Graphs as models
34

 Personnel
assignment
problems. (assigning
people to jobs,
arranging
weddings, finding
appropriate
roommates, etc.)
 Social networks.
 Graphs as models
35

 Personnel assignment problems. (assigning people to

jobs, arranging weddings, finding appropriate
roommates, etc.)
 Social networks.
 VLSI chip design. (Planar graphs, visibility,…)
 Geometric polyhedra (Rigidity of structures,)
 Chemistry
 Biology
 Graphs as models (cont.)
36

 Ecosystems (food web…)

 Scheduling and timetabling problems
 Puzzles and games
 Many others
 Matching Problem
37

women men
w1 m1

w2 m2

w3 m3

w4 m4

w5 m5

Definition: A matching is a set of disjoint edges

in a graph. A matching is perfect if it meets every
vertex in the graph..
 Matching Problem
38

women men

w1 m1

w2 m2

w3 m3

w4 m4

w5 m5

Is this a maximum matching?

 Assignment Problem
39

workers machines

w1 1 m1
3
1
w2 2 m2
1.5
2
w3 2 m3
2 1
1.7 4
w4 m4
3
2
w5 m5

Find a minimum (maximum) cost

assignment of workers to machines
 Stable Marriage Problem
40

women men

w1 1 m1
1
1 Does there exist a
w2 2 m2 stable marriage?
1.5
2
w3 2 m3

1.7 4
w4 m4
3
2
w5 m5

W2 prefers m5 to her spouse and m5

prefers w2 to his spouse.
 Applications
41

 Assigning doctors to hospitals.

 Assigning people to jobs.
 Assigning students to dormitories.
 Assigning pairs of drivers to trucks.
 Etc.
 Timetabling problems
42

 m teachers, n classes.
T1 C1
 Teacher i is required to teach
class j for Pij periods. T2 C2
 In a given period a teacher can
be in at most 1 class, and a class C3
can have at most 1 teacher.
 Design a timetable with
minimum no. of periods.
Cn
 Tractable!
Tm
 Timetabling problems
43

 m teachers, n classes.
T1 C1
 Teacher i is required to teach
class j for Pij periods. T2 C2
 In a given period a teacher can
be in at most 1 class, and a class C3
can have at most 1 teacher.
 Design a timetable with
minimum no. of periods.
Cn
 Tractable!
 Properly color the edges of G Tm
with as few colors as possible.
 Edge coloring of graphs
44

 Definition: A proper k- edge coloring of a graph

G=(V,E) is a mapping
 c: E {1,2,…,k} such that adjacent edges
receive distinct colors.
 If the maximum degree is  then clearly k ≥ 
 Theorem (Vizing): Any graph has either a
-coloring or a (+1)-coloring.
 Designing a time-table is a proper edge coloring
of a graph.
 Theorem A bipartite graph has a -coloring
 Timetabling problems –
45
complications
 A limited number of classroom are available.
 If there are l lessons scheduled in a p-period
timetable, then how many rooms are needed?
 At least {l/p} rooms are needed.
 It is possible to arrange l lessons in p periods where
at most {l/p} rooms are occupied in any one period.
 More complications: teachers are not available for
every period, they need their tea breaks, etc. etc.
 Connector problem
46

 Design a railway network

connecting a number of cities,
with a minimum possible
construction cost.
 Or electrical network, cable
TV, gas, etc.
 Connector problem
47

 Design a railway network

connecting a number of cities,
with a minimum possible
construction cost.
 Or electrical network, cable
TV, gas, etc.
 Problem is Tractable
 A variation of it is intractable!
 Connector problem: Graph-theory
48

 Definition: A tree is a connected acyclic graph.

 Connected = between any 2 vertices there is a path.
Acyclic = contains no cycles.
 Spanning = contains all the vertices in the graph.
 Connector problem: Given a weighted graph G:
Find a minimum weight spanning tree of G.
 Travelling salesman problem
49

Lahore

Intractable!

Faisalabad Hyderabad

Karachi Islamabad

Peshawar

A salesperson begins in Karachi, has to visit all the

cities, and return to Karachi in a shortest possible
distance. (or time, or cost)
 Tractable and Intractable
50

 Tractable Problem: a problem that is solvable by a

polynomial-time algorithm. The upper bound is
polynomial.
 Intractable Problem: a problem that cannot be
solved by a polynomial-time algorithm. The lower
bound is exponential.
 Travelling salesman problem-Graph
51
Theory
 Given a graph (or a directed
graph), does there exist a
cycle in the graph that contains
each vertex once? (i.e. a
Hamilton cycle)?
 Given a complete weighted
graph, find a Hamilton cycle of
minimum weight.