Advanced Analysis of
Algorithm
Course Instructor: Mirza Adnan Baig
Week # 9
Introduction to Graph
What Is a Graph?
• A graph G is an ordered pair (V, E)
consisting of:
– A vertex set V = {W, X, Y, Z}
– An edge set E = {e1, e2, e3, e4, e5, e6, e7}
X
e1
e2 e6 Graph size
W
e5 Y
parameters:
e4 n = |V|, m = |E|.
e3 e7
Z
7
Vertex & Edge
Vertex /Node
Basic Element
Drawn as a node or a dot.
Vertex set of G is usually denoted by V(G), or V or VG
Edge /Arcs
A set of two elements
Drawn as a line connecting two vertices, called end vertices, or
endpoints.
The edge set of G is usually denoted by E(G), or E or EG
Neighborhood
For any node v, the set of nodes it is connected to via an edge is called its
neighborhood and is represented as N(v)
Graph :Example
n:= 6 , m:=7
Vertices (V) :={1,2,3,4,5,6}
Edge (E) := {1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
N(4) := Neighborhood (4) ={6,5,3}
Edge types:
Undirected;
E.g., distance between two cities, friendships…
Directed; ordered pairs of nodes.
E.g ,…
Directed edges have a source (head, origin) and target (tail,
destination) vertices
Weighted ; usually weight is associated .
Graph Terminologies
Classification of Graph Terms
Global terms refer to a whole graph
Local terms refer to a single node in a graph
Connected and Isolated vertex
Two vertices are connected if there is a path
between them
Isolated vertex – not connected
1 2 3
isolated vertex 4 5 6
Adjacent nodes
Adjacent nodes -Two nodes are adjacent if they
are connected via an edge.
If edge e={u,v} ϵ E(G), we say that u and v are adjacent or neigbors
An edge where the two end vertices are the same is called a
loop, or a self-loop
Degree (Un Directed Graphs)
Number of edges incident on a node
The degree of 5 is 3
Degree (Directed Graphs)
outdeg(1)=2 outdeg(2)=2
indeg(2)=2 indeg(1)=0
outdeg(3)=1
indeg(3)=4
Walk
trail: no edge can be repeat
a
a-b-c-d-e-b-d e
d
walk: a path in which edges/nodes c
can be repeated.
a-b-d-a-b-c
A walk is considered to be Closed if
the starting vertex is the same as the
ending vertex, that is v0=vk. A walk
is considered Open otherwise.
Paths
Path: is a sequence P of nodes v1, v2, …, vk-1, vk
No vertex can be repeated
A closed path is called a cycle
The length of a path or cycle is the number of edges visited in the path
or cycle
Walks and Paths
1,2,5,2,3,4 1,2,5,2,3,2,1 1,2,3,4,6
walk of length 5 CW of length 6 path of length 4
Cycle
Cycle - closed path: cycle (a-b-c-d-a) , closed if x=y
Cycles denoted by Ck, where k is the number of nodes in
the cycle
C3 C4 C5
Loop, Multiple edges
• Loop : An edge whose endpoints are equal
• Multiple edges : Edges have the same
pair of endpoints
Multiple
edges
loop
9
Adjacent, neighbors
• Two vertices are adjacent and are
neighbors if they are the endpoints of an
edge
• Example:
– A and B are adjacent
– A and D are not adjacent
A B
C D
11
Connected and Disconnected
• Connected : There exists at least one
path between two vertices
• Disconnected : Otherwise
• Example:
– H1 and H2 are connected
– H3 is disconnected
a b a b
H1 c
H2 H3 c
e
d d
e d
Graph Theory 13
Types of Graph
Complete Graph
• Complete Graph: A simple graph in which every
pair of vertices are adjacent
• If no of vertices = n, then there are n(n-1) edges
14
Sparse/Dense Graph
• A graph is sparse if | E | |V|
• A graph is dense if | E | |V | 2.
15
Finite Graph, Null Graph
• Finite graph : an graph whose vertex set
and edge set are finite
• Null graph : the graph whose vertex set
and edges are empty
12
Simple Graph
Simple graph : A graph has no loops or multiple edges
Multiple
edges loop
It is not simple. It is a simple graph.
10
Directed Graph (digraph)
In a digraph edges have directions
16
Weighted Graph
Weighted graph is a graph for which each edge
has an associated weight, usually given by a
weight function w: E R.
1.2 2
1 2 3 1 2 3
.2 5 3
1.5 1
.5 .3
4 5 6
4 5 6
.5
17
Planar Graph
• Can be drawn on a plane such that no two edges intersect
18
Complement
Complement of G: The complement G’ of
a simple graph G :
– A simple graph
– V(G’) = V(G)
– E(G’) = { uv | uv E(G) }
u
u
y
y v v
G
G’
w x w
x
19
Subgraphs
• A subgraph of a graph G is a graph H
such that:
– V(H) V(G) and E(H) E(G) and
– The assignment of endpoints to edges in H is
the same as in G.
21
Subgraphs
• Example: H1, H2, and H3 are subgraphs
of G
a b
G c
e d
a b
a b
c H3 c
H1 H2
d e d
e d
22
Trees
An undirected graph is a tree if it is connected and does not
contain a cycle
