REPRESENTATION OF GRAPHS

1
REPRESENTATION OF GRAPHS
 Adjacency List
 Adjacency Matrix

 Incidence matrix

2
ADJACENCY LIST REPRESENTATION

3
ADJACENCY LIST REPRESENTATION

4
ADJACENCY MATRIX

 The adjacency matrix of a graph G with n vertices is an n by n binary

matrix X=[xij] such that
xij=1, if there is an edge between ith and jth vertices
xij=0, if there is no edge between them
 Also known as connection matrix

5
 v3
v2
e4 v4 e8

e3 e5
e1
v5 e7
e2

e6 v6
v1

V1 v2 v3 v4 v5 v6

V1 0 1 0 0 1 1
V2 1 0 0 1 1 0
V3 0 0 0 1 0 0
V4 0 1 1 0 1 1
V5 1 1 0 1 0 0
V6 1 0 0 1 0 0
6
 MATRIX REPRESENTATION OF GRAPHS

 Incidence matrix
• Let G be a graph with n vertices , e edges.
• Define an n by e matrix A=[aij], whose n rows correspond to the n
vertices and the e columns correspond to the e edges, as follows:
a ij=1, if j th edge ej is incident on ith vertex vi,
aij=0, otherwise
• Such a matrix A is called vertex-edge incident matrix
• The incidence matrix contains only two elements 0 and 1. such a matrix is
called a binary matrix or a (0,1) matrix.

7
 v3
a
h
v6
Example v2 e b
v4
f g c
v1 d v5

a b c d e f g h
V1 0 0 0 1 0 1 0 0
V2 0 0 0 0 1 1 1 1
v3 0 0 0 0 0 0 0 1
v4 1 1 1 0 1 0 0 0
V5 0 0 1 1 0 0 1 0
V6 1 1 0 0 0 0 0 0
8
 Since every edge is incident on exactly two vertices, each column
(representing an edge )has exactly two 1’s.
 The number of 1’s in each row equals the degree of the
corresponding vertex
 A row with all zeros, therefore, represents an isolated vertex

 Parallel edges in a graph produce identical columns in incidence

matrix.

9
 Walk
 An alternate sequence of vertices and edges, beginning and ending with
vertices, such that each edge is incident with the vertices preceding and
following it.
 In the following fig: v1 a v2 b v3 c v3 d v4 e v2 f v5 is a walk
v1

g a

v3
c
b v2

e
d f

10
h
v4
v5
Walk

 Vertices with which a walk begins and end is called its

terminal vertices.
 Length of the walk is the number of edges in the walk.
 A walk in which terminal vertices are the same is called
a closed walk

11
 Path
 If no vertex of the walk appears more than once, then the walk is called a
path.
 Eg: v1 a v2 b v3 d v4 is a path

 The number of edges in a path is called the length of a path

v1

g a
v3
c
b v2

e
d f
12
h
v4
v5
• Circuit
– A walk which starts and ends at the same vertex.
– No repetition of edges in a circuit.
– Every vertex in a circuit is of degree 2.
Eg: v2 b v3 d v4 e v2 is a circuit
Cycle
A circuit that does not contain any repetition of
vertices except the starting and ending vertex is
called a cycle. v 1

g a
c v3
b v2

e
d f 13

v4 h
v5
Cycles with 3 ,4,5,6 Vertices

14
WHEELS

When an additional vertex is added to the cycle

Cn, for n>=3 and connect this new vertex to each
of the n vertices in Cn by new edges , we obtain
a Wheel.

15
IN-DEGREE & OUTDEGREE
 Let G=(V,E) be a directed graph.
 The incoming or in-degree of v is the number of edges
in G that are incident into v and is denoted by id(v).
 The outgoing or outdegree of v is the number of edges
in G that are incident from v and is denoted by od(v).

If the directed graph has one or more loops, each loop at a

given vertex v contributes a count of 1 to each of id(v)
and od(v).
16
What are the in-degrees and out-degrees of the vertices a, b, c, d in
this graph:
id(b) = 4
a od(b) = 2
id(a) = 1 b
od(a) = 2

id(d) = 2 id(c) = 0
od(d) = 1 d c od(c) = 2

17