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.
