GRAPHS

M Kanyika
Motivation
 Computer networks
 Distinguish between two chemical compounds
with the same molecular formula but different
structures
 Solve shortest path problems between cities
 Scheduling exams and assign channels to
television stations
Konigsberg Bridge in 1736
Topics Covered
 Definitions
 Types
 Terminology
 Representation
 Sub-graphs
 Paths, Connectivity, Cycles and Trees
 Hamilton and Euler definitions
 Shortest Path
 Definitions - Graph

A graph G consists of two things:

 A set V = V (G) whose elements are called vertices, points, or

nodes of G.
 A set E = E(G) of unordered pairs of distinct vertices called edges
of G.

We denote such a graph by G(V,E) or equivalently by G =(V, E)

when we want to emphasize the two parts of G.
Example
Definitions – Edge Type
Directed: Ordered pair of vertices. Represented as (u, v)
directed from vertex u to v.

u v

Undirected: Unordered pair of vertices. Represented as {u, v}.

Disregards any sense of direction and treats both end vertices
interchangeably.

u v
Definitions – Edge Type
 Loop: A loop is an edge whose endpoints are equal
i.e., an edge joining a vertex to itself is called a loop.
Represented as {u, u} = {u}

 Multiple Edges: Two or more edges joining the

same pair of vertices.
Definitions – Graph Type
Simple (Undirected) Graph: consists of V, a nonempty set of
vertices, and E, a set of unordered pairs of distinct elements of
V called edges (undirected)
Representation Example: G(V, E), V = {u, v, w}, E = {{u, v}, {v,
w}, {u, w}}. How else can we present E?

u v

w
 Definitions – Graph Type


u
e1 e2 w

e3
v
Multigraph
Definitions – Graph Type
Directed Graph: G(V, E), set of vertices V, and set of Edges E,
that are ordered pair of elements of V (directed edges)
Representation Example: G(V, E), V = {u, v, w}, E = {(u, v), (v,
w), (w, u)}

u v

• Note that elements of E are ordered pairs.

• It is also called a digraph.
Definitions – Graph Type
Directed Multigraph: G(V,E), consists of set of vertices V, set
of Edges E and a function f from E to {{u, v}| u, v V}. The
edges e1 and e2 are multiple edges if f(e1) = f(e2)
Representation Example: V = {u, v, w}, E = {e1, e2, e3, e4}

u
w e4
e1 e2

v e3
Definitions – Graph Type

Type Edges Multiple Edges Loops Allowed ?

Allowed ?
Simple Graph undirected No No

Multigraph undirected Yes Yes

Directed Graph directed No No

Directed directed Yes Yes

Multigraph
Terminology – Undirected graphs
 u and v are adjacent if {u, v} is an edge, e is called incident with u and v. u
and v are called endpoints of {u, v}

 Degree of Vertex (deg (v)): the number of edges incident on a vertex. A

loop contributes twice to the degree (why?). (Convention)

 Pendant Vertex: deg (v) =1

 Isolated Vertex: deg (k) = 0

Representation Example: For V = {u, v, w} , E = { {u, w}, {u, v} }, deg (u) =

2, deg (v) = 1, deg (w) = 1, deg (k) = 0, w and v are pendant , k is isolated

u v
k

w
Terminology – Directed graphs
 For the edge (u, v), u is adjacent to v OR v is adjacent from u, u – Initial
vertex, v – Terminal vertex

 In-degree (deg- (u)): number of edges for which u is terminal vertex

 Out-degree (deg+ (u)): number of edges for which u is initial vertex

Note: A loop contributes 1 to both in-degree and out-degree (why?)

Representation Example: For V = {u, v, w} , E = { (u, w), ( v, w), (u, v) }, deg-

(u) = 0, deg+ (u) = 2, deg- (v) = 1,
deg+ (v) = 1, and deg- (w) = 2, deg+ (u) = 0

u v

w
Theorem

 Each edge is counted twice in counting the degrees of the vertices of G,

 We have the following simple but important result.

Theorem
The sum of the degrees of the vertices of a graph G is equal to twice the
number of edges in G.
 Example

We have
deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 2.
Total degree=10.

Number of edges= 5
Theorems: Undirected Graphs
Theorem 1
The Handshaking theorem:
2e   deg( v)
vV

The sum of the degrees of the vertices of a graph G is equal to twice

the number of edges in G.
 Theorems: Undirected Graphs
Theorem 2:
An undirected graph has an even number of vertices with odd
degree

Proof is left as an assignment.

 Theorems: directed Graphs
 Theorem 3:  deg + (u) =  deg - (u) = |E|

Find the in-degree and out degree of each vertex in the graph G with
directed edges shown below
 Theorems: directed Graphs
 Theorem 3:  deg + (u) =  deg - (u) = |E|

Find the in-degree and out degree of each vertex in the graph G with
directed edges shown below
Recap
 Definition of graph
 Vertices and edges
 Directed and undirected edges
 Multiple edges
 Simple graph
 Multigraph
 Digraph
 Adjacency and incidence
 Degree of a vertex
 In- and out- degree
 Handshaking Theorem
Simple graphs – special cases
 Complete graph: Kn, is the simple graph that contains exactly
one edge between each pair of distinct vertices.

Representation Example: K1, K2, K3, K4

K1 K2 K3
K4
Simple graphs – special cases
 Cycle: Cn, n ≥ 3 consists of n vertices v1, v2, v3 … vn and edges
{v1, v2}, {v2, v3}, {v3, v4} … {vn-1, vn}, {vn, v1}
Representation Example: C3, C4

C3 C4
Simple graphs – special cases


W3 W4
Clear now?
Simple graphs – special cases


10 11

0 1

00 01

Q1 Q2
Bipartite graphs
 In a simple graph G, if V can be partitioned into two disjoint
sets V1 and V2 such that every edge in the graph connects a
vertex in V1 and a vertex V2 (so that no edge in G connects
either two vertices in V1 or two vertices in V2)
Application example: Representing Relations
Representation example: V1 = {v1, v2, v3} and V2 = {v4, v5, v6},

v4
v1

v5
v2

v6
v3

V1 V2
Complete Bipartite graphs
 Km,n is the graph that has its vertex set portioned into two
subsets of m and n vertices, respectively. There is an edge
between two vertices if and only if one vertex is in the first
subset and the other vertex is in the second subset.
Representation example: K2,3, K3,3

K2,3 K3,3
 Subgraphs
 A subgraph of a graph G = (V, E) is a graph H =(V’, E’) where V’ is a subset of
V and E’ is a subset of E
Representation example: V = {u, v, w}, E = ({u, v}, {v, w}, {w, u}}, H1 , H2

u u u

v w v w v

G H1 H2
Subgraphs
 G = G1 U G2 wherein E = E1 U E2 and V = V1 U V2, G, G1 and G2 are
simple graphs of G

Representation example: V1 = {u, w}, E1 = {{u, w}}, V2 = {w, v},

E1 = {{w, v}}, V = {u, v ,w}, E = {{{u, w}, {{w, v}}

u
u

w v
w w v

G1 G2 G
Example
 Graph Representation
 Incidence (Matrix): Most useful when information about
edges is more desirable than information about vertices.

 Adjacency (Matrix/List): Most useful when information

about the vertices is more desirable than information about the
edges.
Example- Undirected Graph
 Use adjacency lists to describe the simple graph shown below:
Example- Undirected Graph
 Use adjacency lists to describe the simple graph shown below:
Example-Directed Graph
Representation- Incidence Matrix


1 when edge ej is incident w ith v i

m ij  
0 otherwise
Representation- Incidence Matrix
 Representation Example: G = (V, E)

e1 e2 e3
u
v 1 0 1
e1 e2
u 1 1 0

v w w 0 1 1
e3
Another example
Representation- Adjacency Matrix
 There is an N x N matrix, where |V| = N , the Adjacency Matrix
(NxN) A = [aij]

For undirected graph

1 if {vi, vj} is an edge of G
a ij  
0 otherwise
 For directed graph
1 if (vi, vj) is an edge of G
a ij  
0 otherwise

 This makes it easier to find subgraphs, and to reverse graphs if needed.

Representation- Adjacency Matrix


/Dense?
Representation- Adjacency Matrix
 Example: Undirected Graph G (V, E)

v u w
u
v 0 1 1

u 1 0 1
v w
w 1 1 0
Representation- Adjacency
Matrix
Representation- Adjacency Matrix
 Example: directed Graph G (V, E)

v u w
u
v 0 1 0

u 0 0 1
v w
w 1 0 0
Representation- Adjacency List
Each node (vertex) has a list of which nodes (vertex) it is adjacent

Example: undirectd graph G (V, E)

u
node Adjacency List

u v,w

v w, u
v w
w u,v
Connectivity
 Basic Idea: In a Graph Reachability among vertices
by traversing the edges
Application Example:
- In a city to city road-network, if one city can be
reached from another city.
- Problems of determining whether a message can be
sent between two computer using intermediate links
- Efficiently planning routes for data delivery on the
Internet
Connectivity – Path
A Path is a sequence of edges that begins at a vertex
of a graph and travels along edges of the graph,
always connecting pairs of adjacent vertices.

Representation example: G = (V, E), Path P

represented, from u to v is {{u, 1}, {1, 4}, {4, 5}, {5,
v}}

2
1 v
3
u

4 5
 Connectivity – Path
Definition for Directed Graphs
A Path (walk) of length n (> 0) from u to v in G is a sequence
of n edges e1, e2 , e3, …, en of G such that f (e1) = (xo, x1), f (e2)
= (x1, x2), …, f (en) = (xn-1, xn), where x0 = u and xn = v. A path is
said to pass through x0, x1, …, xn or traverse e1, e2 , e3, …, en

For Simple Graphs, the sequence is x0, x1, …, xn

In directed multigraphs when it is not necessary to distinguish

between their edges, we can use sequence of vertices to
represent the path
 Connectivity – Path
 Circuit/Cycle: u = v, length of path > 0

 Simple Path (trail): does not contain an edge more

than once.

Other authors:
 A simple path is a path in which all vertices are distinct.
 A Trail is a path in which all edges are distinct.

 Ifeyo? The former!

Connectivity – Connectedness
Undirected Graph
An undirected graph is connected if there exists a
simple path between any two of its of its vertices

Representation Example: G (V, E) is connected since

for V = {v1, v2, v3, v4, v5}, there exists a path
between {vi, vj}, 1 ≤ i, j≤ 5

v4
v1 v3

v2 v5
Connectivity – Connectedness
Directed Graph
 A directed graph is strongly connected if there is a path from
a to b and from b to a whenever a and b are vertices in the
graph
 A directed graph is weakly connected if there is a
(undirected) path between every two vertices in the underlying
undirected path

A strongly connected Graph can be weakly connected but the

vice-versa is not true (why?)
Connectivity – Connectedness
Directed Graph
Representation example: G1 (Strong component), G2 (Weak
Component), G3 is an undirected graph representation of G2 or G1

G1 G2 G3
 The Seven Bridges of Königsberg, Germany
 The residents of Königsberg, Germany, wondered if it
was possible to take a walking tour of the town that
crossed each of the seven bridges over the Presel river
exactly once. Is it possible to start at some node and
take a walk that uses each edge exactly once, and
ends at the starting node?
 The Seven Bridges of Königsberg, Germany
You can redraw the original picture as long as for every edge between
nodes i and j in the original you put an edge between nodes i and j in
the redrawn version (and you put no other edges in the redrawn
version).

Original:

2 3

4
Redrawn: 2

4 1
3
 The Seven Bridges of Königsberg, Germany

Euler:

 Has no tour that uses each edge exactly once.

 (Even if we allow the walk to start and finish in different places.)
 Can you see why?
Euler - definitions
 An Eulerian path (Eulerian trail, Euler walk) in a graph is a
path that uses each edge precisely once. If such a path exists,
the graph is called traversable.

 An Eulerian cycle (Eulerian circuit, Euler tour) in a graph

is a cycle that uses each edge precisely once. If such a cycle
exists, the graph is called Eulerian (also unicursal).

 Representation example: G1 has Euler path a, c, d, e, b, d, a, b

a b

c d e
 Another example

Which of the graphs above have an Euler Circuit?

 The problem in our language:

Show that is not Eulerian.

In fact, it contains no Euler trail.

Euler - theorems
1. A connected graph G is Eulerian if and only if G is connected
and has no vertices of odd degree.

2. A connected graph G has an Euler trail from vertex a to some

other vertex b if and only if G is connected and a  b are the
only two vertices of odd degree.
Euler – theorems (=>)
Assume G has an Euler trail T from node a to node b (a and b
not necessarily distinct).

For every node besides a and b, T uses an edge to exit for each
edge it uses to enter. Thus, the degree of the node is even.

1. If a = b, then a also has even degree.  Euler circuit

2. If a  b, then a and b both have odd degree.  Euler path

Euler - theorems
1. A connected graph G is Eulerian if and only if G is connected
and has no vertices of odd degree

a b

f c d

Building a simple path:

e {a,b}, {b,c}, {c,f}, {f,a}

Euler circuit constructed if all edges

are used. True here?
Euler - theorems
1. A connected graph G is Eulerian if and only if G is connected
and has no vertices of odd degree

c d

e
Delete the simple path:
{a,b}, {b,c}, {c,f}, {f,a}

C is the common vertex for this

sub-graph with its “parent”.
Euler - theorems
1. A connected graph G is Eulerian if and only if G is connected
and has no vertices of odd degree

c d

Constructed subgraph may not be connected.

e C is the common vertex for this sub-graph

with its “parent”.

C has even degree.

Start at c and take a walk:

{c,d}, {d,e}, {e,c}
Euler - theorems
1. A connected graph G is Eulerian if and only if G is connected
and has no vertices of odd degree

a b

f c d
“Splice” the circuits in the 2 graphs:
{a,b}, {b,c}, {c,f}, {f,a}
“+”
e {c,d}, {d,e}, {e,c}
“=“
{a,b}, {b,c}, {c,d}, {d,e}, {e,c}, {c,f}
{f,a}
 Hamiltonian Graph
 Hamiltonian path (also called traceable path) is a path that visits
each vertex exactly once.

 A Hamiltonian cycle (also called Hamiltonian circuit, vertex tour or

graph cycle) is a cycle that visits each vertex exactly once (except for
the starting vertex, which is visited once at the start and once again at
the end).

 A graph that contains a Hamiltonian path is called a traceable graph.

A graph that contains a Hamiltonian cycle is called a Hamiltonian
graph. Any Hamiltonian cycle can be converted to a Hamiltonian path
by removing one of its edges, but a Hamiltonian path can be extended
to Hamiltonian cycle only if its endpoints are adjacent.
Hamiltonian Graph
 Hamiltonian Graph

This one has a Hamiltonian path, but not a

Hamiltonian tour.
Hamiltonian Graph

This one has an Euler tour, but no Hamiltonian tour.

 Hamiltonian Graph
 Similar notions may be defined for directed graphs, where edges (arcs)
of a path or a cycle are required to point in the same direction, i.e.,
connected tail-to-head.

 The Hamiltonian cycle problem or Hamiltonian circuit problem in graph

theory is to find a Hamiltonian cycle in a given graph. The Hamiltonian
path problem is to find a Hamiltonian path in a given graph.

 There is a simple relation between the two problems. The Hamiltonian

path problem for graph G is equivalent to the Hamiltonian cycle
problem in a graph H obtained from G by adding a new vertex and
connecting it to all vertices of G.
Hamiltonian Graph
 DIRAC’S Theorem: if G is a simple graph with n
vertices with n ≥ 3 such that the degree of every
vertex in G is at least n/2 then G has a Hamilton
circuit.

 ORE’S Theorem: if G is a simple graph with n

vertices with n ≥ 3 such that deg (u) + deg (v) ≥ n
for every pair of nonadjacent vertices u and v in G,
then G has a Hamilton circuit.
Labelled and weighted Graphs
 A graph G is called a labeled graph if its edges and/or vertices
are assigned data of one kind or another.

 G is called a weighted graph if each edge e of G is assigned a

nonnegative number w(e) called the weight or length of v.

 The weight (or length) of a path in such a weighted graph G is

defined to be the sum of the weights of the edges in the path.
Shortest Path
 Generalize distance to weighted setting
 Digraph G = (V,E) with weight function W: E  R (assigning
real values to edges)
 Weight of path p = v1  v2  …  vk is
k 1
w( p )   w(vi , vi 1 )
i 1

 Shortest path = a path of the minimum weight

 Applications
 static/dynamic network routing

 robot motion planning

 map/route generation in traffic

Shortest-Path Problems
 Shortest-Path problems
 Single-source (single-destination). Find a
shortest path from a given source (vertex s) to
each of the vertices. The topic of this lecture.
 Single-pair. Given two vertices, find a shortest
path between them. Solution to single-source
problem solves this problem efficiently, too.
 All-pairs. Find shortest-paths for every pair of
vertices. Dynamic programming algorithm.
 Unweighted shortest-paths – BFS.
Example
Dijkstra’s Algorithm
Solution to Single-source (single-destination).

 Input: Graph G, start vertex s

Dijkstra(G,s)
01 for each vertex u  G.V()
02 [Link]()
03 [Link](NIL)
04 [Link](0)
05 S   // Set S is used to explain the
algorithm
06 [Link](G.V()) // Q is a priority queue ADT
07 while not [Link]()
08 u  [Link]()
09 S  S  {u} relaxing
10 for each v  [Link]() do
edges
11 Relax(u, v, G)
12 [Link](v)
Dijkstra’s Algorithm
To find the shortest path between S and T