Graph Theory

Characteristics of graphs:
⚫ Adjacent node: A node ‘v’ is said to be adjacent node of
node ‘u’ if and only if there exists an edge between ‘u’
and ‘v’.
⚫ Degree of a node: In an undirected graph the number of
nodes incident on a node is the degree of the node.
In case of directed graph ,Indegree of the node is
the number of arriving edges to a node.
Outdegree of the node is the number of departing edges
to a node.
 Degree of a Vertex:

⚫ The degree of a vertex is the number of edges incident on a

vertex v. The self-loop is counted twice. The degree of a
vertex is denoted by d(v).
 Degree of Vertex in a Directed Graph

⚫ In a directed graph, each vertex has an indegree and

an outdegree.
Indegree of a Graph
Indegree of vertex V is the number of edges which are
coming into the vertex V.
Notation − deg−(V).
Outdegree of a Graph
Outdegree of vertex V is the number of edges which are
going out from the vertex V.
Notation − deg+(V).
Thus, Degree of vertex is defined by sum of indegree and
Outdegree
 Graph Representations
⚫ In graph theory, a graph representation is a technique to
store graph into the memory of computer.

1. Adjacency Matrix

2. Incidence Matrix

3. Adjacency List
 1. Adjacency Matrix

⚫ It is used to represent which nodes are adjacent to each

other. i.e. is there any edge connecting nodes to a graph.
⚫ Matrix formed with the help of vertices of a graph is
called adjacency matrix
Undirected graph
 1. Adjacency Matrix

⚫ It is used to represent which nodes are adjacent to each

other. i.e. is there any edge connecting nodes to a graph.
⚫ Matrix formed with the help of vertices of a graph is
called adjacency matrix
Directed graph
 2. Incidence Matrix

⚫ Matrix formed with the help of vertices and edges of a

graph is called incidence Matrix
⚫ This matrix is filled with either 0 or 1 or -1. Where,
0 is used to represent row edge which is not connected to
column vertex.
1 is used to represent row edge which is connected as
outgoing edge to column vertex.
-1 is used to represent row edge which is connected as
incoming edge to column vertex
2. Incidence Matrix
3. Adjacency List

⚫ Adjacency list is a linked representation.

 Types of graph
1. Null Graph:
A null graph is defined as a graph which
consists only the isolated vertices.
Types of graph
2 Directed and Undirected Graph
A graph G=(V,E) is called a directed graph if
the edge set is made of ordered vertex pair and
a graph is called undirected if the edge set is
made of unordered vertex pair.
Types of graph
3 Connected and Disconnected Graph
A graph is connected if any two vertices of the
graph are connected by a path
while a graph is disconnected if at least two
vertices of the graph are not connected by a
path
 Types of graph
4 Simple graph
A graph is called simple graph/strict graph if the
graph is undirected and does not contain any loops or
multiple edges.
A simple graph is a graph which does not contains
more than one edge between the pair of vertices
 Types of graph
4 Multigraph
A graph in which multiple edges may connect the
same pair of vertices is called a multigraph.
it is a graph having at least one loop or multiple
edges.
Types of graph
5. Complete Graph:
A graph in which every vertices are connected to each other
by exactly one edge is called complete graph

The complete graph with n vertices is denoted by Kn

Draw A Graph K6
Types of graph
5. Complete Graph:
 Types of graph
6) Regular Graph
A graph is regular if all the vertices of the
graph have the same degree
A graph whose all vertices have degree 2 is
known as a 2-regular graph.
All complete graphs are regular but vice versa
is not possible.
Types of graph
6) Regular Graph
 Types of graph
7.Cycle Graph
If a graph consists of a single cycle, it is called
cycle graph
Cycles are simple graphs with vertices n>=3
The cycle graph with n vertices is denoted by Cn
Types of graph
8. Wheels Graph
A wheel is just like a cycle, with one
additional vertex which is connected to every
other vertex
Wheels of n vertices are denoted by Wn
 Types of graph
9) Bipartite Graph
A Graph is said to be Bi- Partite Graph if the vertices
are divided into two different parts such that the vertices of
first part are connected to the vertices of second part but the
vertices of same parts should not connect.
A simple graph G = (V, E) with vertex partition V = {V1,
V2} is called a bipartite graph if every edge of E joins a vertex
in V1 to a vertex in V2
 Types of graph
10) Complete Bipartite Graph
A Graph is said to be Complete Bi- Partite Graph if the
vertices are divided into two different parts such that the
All vertices of first part are connected to the All vertices of
second part but the vertices of same parts should not
connect.

The complete bipartite graph is denoted

by Kx,y where the graph G contains x vertices in
the first set and y vertices in the second set.
 Types of graph
10) Complete Bipartite Graph
Draw K3,4 Graph
Types of graph
11) Weighted Graph
A weighted graph is a graph in which each
branch is given a numerical weight. A weighted
graph is therefore a special type of labeled
graph in which the labels are numbers (which
are usually taken to be positive).
 Adjacency matrix Connectivity Algorithm.
Step One: Mark any row in the adjacency matrix and cross out
each
entry in the corresponding column to that row.
Step Two:
If all the entries in the matrix are crossed out,
stop: the graph is connected.
If all the entries in all the marked rows are 0, and there are still
unmarked rows
stop: the graph is not connected.
Otherwise, pick some non-zero entry in a marked row.
Step Three:
if you picked entry Ar,s (i.e. the row r was marked, and the
number in position s was non-zero) cross out column s, and
mark row s.
Example
Example - Cont
⚫ First, mark row 1 and cross out column 1

⚫ Row 1 is marked, and we have a non-zero entry

which is not crossed out in column 2. So we
mark row 2 and cross out column 2.
.
 Example-Cont
⚫ So we mark row 2 and cross out column 2.

⚫ Row 1 has a non-zero entry which is not crossed out

in column 4. So we mark row 4 and cross out column
4.
Example-Cont
⚫ So we mark row 4 and cross out column 4.

⚫ Row 1 has a non-zero entry which is not crossed out in

column 5. So we mark row 5 and cross out column 5.
Example-Cont
⚫ So we mark row 5 and cross out column 5.

⚫ Row 1 has no non-zero entry which are not crossed out.

⚫ But Row 2 has a non-zero entry which is not crossed out in
column 3.
Example-Cont
⚫ So we mark row 3 and cross out column 3.

All columns are now crossed out:

so the graph is connected.
Example 2
Example - Cont

⚫ we start off with row one: we mark row one, and cross out
column one.

⚫ In row one, we have non-zero entries in columns three and

four, so we mark those rows and cross out those columns
Example - Cont

⚫ But at this point, all remaining entries in marked rows are

zero, and not all rows are marked, so the graph is not
connected.
Task
⚫ What happens if we start with the second
row, second column?
Dijkstra’s Algorithm For shortest Path
Planar Graph
⚫ A graph that can be drawn on a plane without
intersecting its edges is called Planar Graph
⚫ A planar Graph is divided into number of regions
called Faces
⚫ One of these faces is unbounded, and is called the
infinite face.
⚫ If a connected planar graph G has e edges and v
vertices, then
3v-e≥6.
Planar Graph

⚫ Show that complete graph K4 is planar.

Planar Graph
⚫ Show that complete graph K4 is planar.

Fig(i) : Non-Planar Graph fig(ii) : Planar

Graph

The complete graph K4 contains 4 vertices and 6

edges.
We know that 3v-e≥6
we have 3x4-6=6 which satisfies the property
Euler’s Formula For Planar Graph
⚫ Let G be a connected planar graph,
and let V, E and F denote,
respectively, the numbers of vertices,
edges, and faces in a plane drawing of
G.

Then V - E + F = 2.
 Graph Coloring
⚫ Graph coloring problem is to assign colors to certain
elements of a graph subject to certain constraints.
⚫ Vertex coloring is the most common graph coloring
problem
⚫ A vertex coloring of Graph G= (V,E) is an assignment of
colors to the vertices of G such that adjacent vertices have
different colors.
⚫ Chromatic number of G: The minimum number of colors
needed to produce a proper coloring of a graph G is called
the chromatic number of G and is denoted by x(G).
Example- Graph Coloring

⚫ Chromatic Number x(G)=2

⚫ Chromatic Number x(G)=3

Example- Graph Coloring : Region Coloring
Assignment: Define and
Draw
Walks, Trails, Paths,
Cycles and Circuits in
Graph ?