Scribd
Upload
128 views30 pages

Nptel Week3 Module1 Graphintro

The document discusses graph coloring and other graph problems. It introduces graphs formally as consisting of a set of vertices and edges. The map coloring problem is presented as an example of graph coloring, where each state is a vertex and neighboring states are connected by edges. The goal is to assign colors to vertices such that no two connected vertices have the same color, using the fewest possible colors. It is noted that for maps, 4 colors are always sufficient. Other graph problems discussed include finding routes between vertices in a directed or undirected graph.

Uploaded by

Abhay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
128 views30 pages

Nptel Week3 Module1 Graphintro

The document discusses graph coloring and other graph problems. It introduces graphs formally as consisting of a set of vertices and edges. The map coloring problem is presented as an example of graph coloring, where each state is a vertex and neighboring states are connected by edges. The goal is to assign colors to vertices such that no two connected vertices have the same color, using the fewest possible colors. It is noted that for maps, 4 colors are always sufficient. Other graph problems discussed include finding routes between vertices in a directed or undirected graph.

Uploaded by

Abhay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 30

NPTEL MOOC,JAN-FEB 2015

Week 3, Module 1

DESIGN AND ANALYSIS



OF ALGORITHMS
Introduction to graphs

MADHAVAN MUKUND, CHENNAI MATHEMATICAL INSTITUTE


http://www.cmi.ac.in/~madhavan
Map
Colouring
Assign each
state or country
a colour

States that
share a border
should be
coloured
differently

How many
colours do we
need?
Map
Colouring
Mark each state
Map
Colouring
Mark each state

Connect states
that share a
border
Map
Colouring
Mark each state

Connect states
that share a
border

Assign colours
to dots so that
no two
connected dots
have the same
colour
Map
Colouring
Mark each state

Connect states
that share a
border

Assign colours
to dots so that
no two
connected dots
have the same
colour
Map
Colouring
Mark each state

Connect states
that share a
border

Assign colours
to dots so that
no two
connected dots
have the same
colour
Map
Colouring
Mark each state

Connect states
that share a
border

Assign colours
to dots so that
no two
connected dots
have the same
colour
Map
Colouring
Mark each state

Connect states
that share a
border

Assign colours
to dots so that
no two
connected dots
have the same
colour
Map
Colouring
Mark each state

Connect states
that share a
border

Assign colours
to dots so that
no two
connected dots
have the same
colour
Map
Colouring
Map
Colouring
In fact, the
actual map is
irrelevant!
Map
Colouring
In fact, the
actual map is
irrelevant!

All we need is
the underlying
pattern of dots
and connections
Map
Colouring
This kind of
diagram is
called a graph

Dots are nodes


or vertices

One vertex,
many vertices

Connections are
edges
Graph
Colouring
The problem we
have solved is called
graph colouring

We used 4 colours

In fact, 4 colours are


always enough for
such maps

This is a theorem
that is surprisingly
hard to prove!
Graph
Colouring
Observe that the
original map
used more than
4 colours
Graph
Colouring
Observe that the
original map
used more than
4 colours
Graph
Colouring
The graph
emphasizes the
essential features
of the problem

What is
connected to
what?
Graph
Colouring
The graph
emphasizes the
essential features
of the problem

What is
connected to
what?

We can distort
this figure and the
problem remains
the same
More graph
problems
More graph
problems
Airline routing
More graph
problems
Airline routing

Can I travel from


New Delhi to
Trivandrum
without
changing
airlines?
More graph
problems
Airline routing

Can I travel from


New Delhi to
Trivandrum
without
changing
airlines?

Again, all that is


important is the
underlying
graph
Graphs, formally
G = (V,E)

Set of vertices V

Set of edges E

E is a subset of pairs (v,v’): E ⊆ V × V

Undirected graph: (v,v’) and (v’,v) are the same edge

Directed graph:

(v,v’) is an edge from v to v’

Does not guarantee that (v’,v) is also an edge


Graph
Colouring
Undirected
graph
Graph
Colouring
Undirected
graph

Colouring C
assigns each
vertex v a colour
C(v)

Legal colouring:

if (v,v’) is in E,
then C(v) ≠ C(v’)
Finding a
route
Finding a
route
Directed graph
Finding a
route
Directed graph
v0
Find a sequence
of vertices v0, v1,
…, vk such that

v0 is New
Delhi
v1
v3
Each (vi,vi+1) is
an edge in E

v2 v4
vk is
Trivandrum
v5
Finding a
route
Also makes sense
v0
for undirected
graphs

Find a sequence
of vertices v0, v1,
…, vk such that

v1
v0 is New Delhi
v3

Each (vi,vi+1) is
an edge in E
v4
v2
vk is Trivandrum
v5

You might also like