Module-2

Connectivity
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

[Link]
vertices is more desirable than information about the edges. These two
representations are also most popular since information about the
vertices is often more desirable than edges in most applications
Representation- Incidence Matrix
 G = (V, E) be an unditected graph. Suppose that v 1, v2, v3, …, vn are the vertices and e1, e2, …, em are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the nx m matrix M = [m ij], where

Can also be used to represent :

Multiple edges: by using columns with identical entries, since these edges are incident with the same pair of vertices
Loops: by using a column with exactly one entry equal to 1, corresponding to the vertex that is incident with the loop

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
Representation- Adjacency Matrix

 There is an N x N matrix, where |V| = N , the Adjacenct Matrix (NxN) A = [a ij]

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

• Adjacency is chosen on the ordering of vertices. Hence, there as are as

many as n! such matrices.
• The adjacency matrix of simple graphs are symmetric (aij = aji) (why?)
• When there are relatively few edges in the graph the adjacency matrix
is a sparse matrix
• Directed Multigraphs can be represented by using aij = number of
edges from vi to vj
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

• 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
nod Adjacency List
e
u v,w

v w
v w, u

w u,v
Graph - Isomorphism
• G1 = (V1, E2) and G2 = (V2, E2) are isomorphic if:
• There is a one-to-one and onto function f from V1 to V2 with the property that
• a and b are adjacent in G1 if and only if f (a) and f (b) are adjacent in G2, for all a and b
in V1.
• Function f is called isomorphism

Application Example:
In chemistry, to find if two compounds have the same structure
Graph - Isomorphism
Representation example: G1 = (V1, E1) , G2 = (V2, E2)
f(u1) = v1, f(u2) = v4, f(u3) = v3, f(u4) = v2,

u1 u2 v1 v2

u3 u4 v4
v3
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 if determining whether a message can be sent between two
computer using intermediate links
- Efficiently planning routes for data delivery in 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 of length n (> 0) from u to v in G is a sequence of n edges e 1, 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, 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

Circuit/Cycle: u = v, length of path > 0

Simple Path: does not contain an edge more than once

Connectivity – Connectedness

Undirected Graph
An undirected graph is connected if there exists is a
simple path between every pair of 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
Undirected Graph

• Articulation Point (Cut vertex): removal of a vertex produces a

subgraph with more connected components than in the original graph.
The removal of a cut vertex from a connected graph produces a graph
that is not connected
• Cut Edge: An edge whose removal produces a subgraph with more
connected components than in the original graph.
Representation example: G (V, E), v3 is the articulation point or edge
{v2, v3}, the number of connected components is 2 (> 1)
v3
v5
v1

v2
v4
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
undirected graph representation of G2 or G1

G1 G2 G3
Connectivity – Connectedness
• Directed Graph
Strongly connected Components: subgraphs of a Graph G
that are strongly connected
Representation example: G1 is the strongly connected
component in G

G G1
Isomorphism - revisited

A isomorphic invariant for simple graphs is the existence of

a simple circuit of length k , k is an integer > 2 (why ?)
Representation example: G1 and G2 are isomorphic since we have the
invariants, similarity in degree of nodes, number of edges, length of
circuits

G1 G2
Counting Paths
• Theorem: Let G be a graph with adjacency matrix A with respect to the ordering
v1, v2, …, Vn (with directed on undirected edges, with multiple edges and loops
allowed). The number of different paths of length r from Vi to Vj, where r is a
positive integer, equals the (i, j)th entry of (adjacency matrix) Ar.

Proof: By Mathematical Induction.

Base Case: For the case N = 1, aij =1 implies that there is a path of length 1. This is true since
this corresponds to an edge between two vertices.

We assume that theorem is true for N = r and prove the same for N = r +1. Assume that the
(i, j)th entry of Ar is the number of different paths of length r from v i to vj. By induction
hypothesis, bik is the number of paths of length r from vi to vk.
Counting Paths
Case r +1: In Ar+1 = Ar. A,
The (i, j)th entry in Ar+1 , bi1a1j + bi2 a2j + …+ bin anj
where bik is the (i, j)th entry of Ar.

By induction hypothesis, bik is the number of paths of length r from vi to vk.

The (i, j)th entry in Ar+1 corresponds to the length between i and j and the length is r+1. This path is made up
of length r from vi to vk and of length from vk to vj. By product rule for counting, the number of such paths is
bik* akj The result is bi1a1j + bi2 a2j + …+ bin anj ,the desired result.
Counting Paths

a ------- b
| |
| |
c -------d

A=0110 A4 = 8 0 0 8
1001 0880
1001 0880
0110 8008

Number of paths of length 4 from a to d is (1,4) th entry of A 4 = 8.

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