Module 3
Fundamentals of graphs
Why Graph
Theory ?
Graphs used to model pair wise relations
between objects
Generally a network can be represented
by a graph
Many practical problems can be easily
represented in terms of graph theory
Definition:
Graph
A graph is a collection of nodes and
edges
Denoted by G = (V, E).
V = nodes (vertices, points).
E = edges (links, arcs) between pairs of
nodes.
Graph size parameters: n = |V|, m = |
E|.
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 V
G
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 :Examp
le
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 .
Empty Graph / Edgeless
graph
No
edge
Null graph
No nodes
Obviously no
edge
Simple Graph
(Undirected)
Simple Graph are undirected graphs without
loop or multiple edges
Complete Graph
Subgraph
Subgrap
h
Vertex and edge sets are subsets of those
of G
a supergraph of a graph G is a graph that
contains G as a subgraph.
Types of subgraph
Isomorphic Graph
Ex:
ex
1. Walk
A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a
walk.
Note: Vertices and Edges can be repeated.
Here, 1->2->3->4->2->1->3 is a walk.
Walk can be open or closed.
Open walk- A walk is said to be an open walk if the starting and ending vertices
are different i.e. the origin vertex and terminal vertex are different.
Closed walk- A walk is said to be a closed walk if the starting and ending
vertices are identical i.e. if a walk starts and ends at the same vertex, then it is
said to be a closed walk.
In the above diagram:
1->2->3->4->5->3 is an open walk.
1->2->3->4->5->3->1 is a closed walk.
2. Trail –
Trail is an open walk in which no edge is repeated.
Vertex can be repeated.
Here 1->3->8->6->3->2 is trail
Also 1->3->8->6->3->2->1 will be a closed trail
3. Circuit –
Traversing a graph such that not an edge is repeated but vertex can be
repeated and it is closed also i.e. it is a closed trail.
Vertex can be repeated.
Edge can not be repeated.
Here 1->2->4->3->6->8->3->1 is a circuit.
Circuit is a closed trail. These can have repeated vertices only.
4. Path –
It is a trail in which neither vertices nor edges are repeated i.e. if we traverse a
graph such that we do not repeat a vertex and nor we repeat an edge. As path is
also a trail, thus it is also an open walk.
Vertex not repeated
Edge not repeated
Here 6->8->3->1->2->4 is a Path
5. Cycle –
Traversing a graph such that we do not repeat a vertex nor we repeat a edge but the
starting and ending vertex must be same i.e. we can repeat starting and ending vertex
only then we get a cycle.
Vertex not repeated
Edge not repeated
Here 1->2->4->3->1 is a cycle.
Cycle is a closed path. These can not have repeat anything (neither edges
nor vertices).
Table
ex
Reachability
ss
Connectedness in directed graphs
Ex
ex
ex
ex
