Graphs

Week 15 and 16
Dr. sohail
Objectives
• Today’s lecture objectives include:

– Graph introduction

– Directed vs. Undirected graph

– Few graph terminologies

– Bipartite Graph

– Adjacency Matrix

Data Structures & Algorithms 2

Graph – Introduction
• A graph G = (V, E) is composed of:

V: set of vertices

E: set of edges connecting the vertices in V

• An edge e = (u, v) is a pair of vertices

• Example:
V = {a, b, c, d, e}
E = {(a, b), (a, c),
(a, d), (b, e),
(c, d), (c, e),
(d, e)}

Data Structures & Algorithms 3

Graph – Introduction…
• Edges connect two Example: The following picture is
a graph. List its vertices and
vertices. edges.
• Edges only intersect at A
D
vertices.

• Edges joining a vertex C

to itself are called

loops.

B
Data Structures & Algorithms 4
Graph – Introduction…
Example
• This is also a graph. The vertices just happen to have
people’s names (e.g., first character).
• Such a graph could represent friendships (or any kind
of relationship).
F B L

R A P

Data Structures & Algorithms 5

Graph – Introduction…
• Now check out the graph below.
• What can we say about it in comparison to the
previous figure?

L R

F
Previous figure
A F B L
B
P Z Z

R A P
Data Structures & Algorithms 6
Graph – Introduction…
Moral of the Story

• One graph may be drawn in (infinitely) many ways,

but it always provides us with the same information.

• Graphs are a structure for describing relationships

between objects.
– The vertices denote the objects and the edges represent the
relationship.

Data Structures & Algorithms 7

Directed vs. Undirected graphs
• When the edges in a graph have no direction, the graph
is called undirected. For example, Graph1

• When the edges in a graph have a direction, the graph is

called directed (or digraph). For example, Graph2

Warning: if the graph is directed, the order

of the vertices in each edge is important !!
Data Structures & Algorithms 8
Trees vs. Graphs
• Trees are special cases of graphs!!

Data Structures & Algorithms 9

Graphs Terminologies
• Adjacent nodes: two nodes are adjacent if they are
connected by an edge
5 adjacent to 7

7 is adjacent from 5

• Path: a sequence of vertices that connect two nodes in a

graph

• Complete graph: a graph in which every vertex is directly

connected to every other vertex

Data Structures & Algorithms 10

Graphs Terminologies…
• Weighted graph: a graph in which each edge carries a
value

Data Structures & Algorithms 11

Bipartite Graphs
• A simple graph is bipartite if V can be partitioned into
V = V1  V2 so that any two adjacent vertices are in
different parts of the partition.

• Another way of expressing the same idea is

bichromatic: vertices can be colored using two colors
so that no two vertices of the same color are adjacent.

Data Structures & Algorithms 12

Bipartite Graphs…
• And so is bipartite, if we redraw it:

Data Structures & Algorithms 13

Complete Bipartite - Km,n
• When all possible edges exist in a simple bipartite graph
with m red vertices and n green vertices, the graph is called
complete bipartite and the notation Km,n is used.

K2,3 K4,5

Data Structures & Algorithms 14

Adjacency Matrix
• For a digraph G = (V,E ) define matrix AG by:
• Value at i th row and j th column is
– 1 if i th vertex connects to j th vertex (i → j )
– 0 otherwise

R digraph(R) MR

2 1 1 1 1
1 1  
2 2 0 1 1 1
3 
1
1
3 3 0 0 1
 
4 4 0 1
4  0 0
Data Structures & Algorithms 15
Adjacency Matrix
Q: What is the adjacency matrix?

1 4 3

0 3 0 1
 
A: 0 1 2 0
0 1 2 0
 
0 0 
 0 0
Data Structures & Algorithms 16
Graph Applications
• Modelling a road network with vertices as towns and edge costs as
distances.

• Modelling a water supply network.

• Dynamically modelling the status of a set of routes by which traffic might

be directed over the Internet.

• Minimising the cost and time taken for air travel when direct flights don't
exist between starting and ending airports.

• Using a directed graph to map the links between pages within a website
and to analyse ease of navigation between different parts of the site.

Data Structures & Algorithms 17

 Graph traversal algorithms

Breadth-First Search (BFS) and Depth-

First Search (DFS) are two fundamental
graph traversal algorithms
They are used to explore and traverse
graphs or trees
BFS explores all the vertices of a DFS explores as far as possible along
graph level by level. It starts at a a branch before backtracking. It starts
source vertex and visits all its at a source vertex and visits a vertex,
neighbors before moving on to the then recursively visits its neighbors.
neighbors of those neighbors. This This process continues until a dead
process continues until all vertices end is reached, at which point the
have been visited. algorithm backtracks.

Data Structures & Algorithms 18

Data Structures & Algorithms 19
Data Structures & Algorithms 20
Summary
• Graph introduction

• Directed vs. Undirected graph

• Few graph terminologies

• Bipartite Graph

• Adjacency Matrix

Data Structures & Algorithms 21

THANK YOU

Data Structures & Algorithms 22