UNIT V

Graph Theory
Representation of Graphs:

There are two different sequential representations of a graph .They are

Adjacency Matrix representation

Path Matrix representation

Adjacency Matrix Representation

Suppose G is a simple directed graph with m nodes, and suppose the nodes of G have
been ordered and are called v1, v2, . . . , vm. Then the adjacency matrix A = (aij) of the graph
G is the m x m matrix defined as follows:

1 if vi is adjacent to Vj, that is, if there is an edge (Vi, Vj)

aij=0 otherwise
Suppose G is an undirected graph. Then the adjacency matrix A of G will be a
symmetric matrix, i.e., one in which aij = aji; for every i and j.

Drawbacks
It may be difficult to insert and delete nodes in G.
If the number of edges is 0(m) or 0(m log2 m), then the matrix A will be sparse,
hence a great deal of space will be wasted.

Path Matrix Representation

Let G be a simple directed graph with m nodes, v1,v2, . . . ,vm. The path matrix of G
is the m-square matrix P = (pij) defined as follows:
1 if there is a path from Vi to Vj
Pij =0 otherwise

Graphs and Multigraphs

A graph G consists of two things:

1.A set V of elements called nodes (or points or vertices)

2.A set E of edges such that each edge e in E is identified with a unique
(unordered) pair [u, v] of nodes in V, denoted by e = [u, v] Sometimes we
indicate the parts of a graph by writing G = (V, E).
Suppose e = [u, v]. Then the nodes u and v are called the end points of e, and u and v
are said to be adjacent nodes or neighbors. The degree of a node u, written deg(u), is the
number of edges containing u. If deg(u) = 0 — that is, if u does not belong to any edge—
then u is called an isolated node.
Path and Cycle
 A path P of length n from a node u to a node v is defined as a sequence of n + 1 nodes. P
= (v0, v1, v2, . . . ,vn) such that u = v0; vi-1 is adjacent to vi for i = 1,2, . . ., n and vn = v.
Types of Path

1. SimplePath
2. CyclePath
(i) SimplePath
Simple path is a path in which first and last vertex are different (V0 ≠Vn)
(ii) CyclePath
Cycle path is a path in which first and last vertex are same (V0 = Vn).It is also called
as Closed path.
Connected Graph
A graph G is said to be connected if there is a path between any two of its nodes.

Complete Graph
A graph G is said to be complete if every node u in G is adjacent to every other node v in G.
Tree
A connected graph T without any cycles is called a tree graph or free tree or, simply, a
tree.

Labeled or Weighted Graph

If the weight is assigned to each edge of the graph then it is called as Weighted
or Labeled graph.The definition of a graph may be generalized by permitting the
following:
Multiple edges: Distinct edges e and e' are called multiple edges ifthey connect the
same endpoints, that is, if e = [u, v] and e' = [u,v].
Loops: An edge e is called a loop if it has identical endpoints, that is, if e = [u, u].
Finite Graph:Amultigraph M is said to be finite if it has a finite number of nodes and
a finite number of edges.

Directed Graphs
 A directed graph G, also called a digraph or graph is the same as a multi graph except
that each edge e in G is assigned a direction, or in other words, each edge e is identified
with an ordered pair (u, v) of nodes in G.
Outdegree and Indegree
Indegree: The indegree of a vertex is the number of edges for which v is head
Example

Indegree of 1 = 1
Indegreepf 2 = 2
Outdegree:Theoutdegree of a node or vertex is the number of edges for which v is tail.
Example

Outdegree of 1 =1
Outdegree of 2 =2
Simple Directed Graph

A directed graph G is said to be simple if G has no parallel edges. A simple graph G

may have loops, but it cannot have more than one loop at a given node.

Graph Traversal

The breadth first search (BFS) and the depth first search (DFS) are the two algorithms
used for traversing and searching a node in a graph. They can also be used to find out
whether a node is reachable from a given node ornot.

Depth First Search (DFS)

The aim of DFS algorithm is to traverse the graph in such a way that it tries to go far from the
root node. Stack is used in the implementation of the depth first search. Let’s see how depth
first search works with respect to the following graph:
 As stated before, in DFS, nodes are visited by going through the depth of the tree from the
starting node. If we do the depth first traversal of the above graph and print the visited node, it
will be “A B E F C D”. DFS visits the root node and then its children nodes until it reaches the
end node, i.e. E and F nodes, then moves up to the parent nodes.

Algorithmic Steps

6. Step 1: Push the root node in the Stack.

7. Step 2: Loop until stack is empty.
8. Step 3: Peek the node of the stack.
9. Step 4: If the node has unvisited child nodes, get the unvisited child node, mark
it as traversed and push it on stack.
10. Step 5: If the node does not have any unvisited child nodes, pop the node from
thestack.

Breadth First Search (BFS)

This is a very different approach for traversing the graph nodes. The aim of BFS algorithm is to
traverse the graph as close as possible to the root node. Queue is used in the implementation of the
breadth first search. Let’s see how BFS traversal works with respect to the following graph:

If we do the breadth first traversal of the above graph and print the visited node as the
output, it will print the following output. “A B C D E F”. The BFS visits the nodes level by level,
so it will start with level 0 which is the root node, and then it moves to the next levels which are
B, C and D, then the last levels which are E and F.
Algorithmic Steps
1. Step 1: Push the root node in theQueue.
2. Step 2: Loop until the queue isempty.
3. Step 3: Remove the node from theQueue.
4. Step 4: If the removed node has unvisited child nodes, mark them as visited and
insert the unvisited children in thequeue.
Based upon the above steps, the following Java code shows the implementation of
the BFS algorithm:
Spanning Trees:
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G
is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally, a
spanning tree of G is a selection of edges of G that form a tree spanning every vertex. That is,
every vertex lies in the tree, but no cycles (or loops) are formed. On the other hand, every bridge
of G must belong to T.
A spanning tree of a connected graph G can also be defined as a maximal set of
edges of G that contains no cycle, or as a minimal set of edges that connect all vertices.
Example:

A spanning tree (blue heavy edges) of a grid graph.

Spanning forests

A spanning forest is a type of sub graph that generalizes the concept of a spanning tree.
However, there are two definitions in common use. One is that a spanning forest is a sub graph
that consists of a spanning tree in each connected component of a graph. (Equivalently, it is a
maximal cycle-free sub graph.) This definition is common in computer science and optimization.
It is also the definition used when discussing minimum spanning forests, the generalization to
disconnected graphs of minimum spanning trees. Another definition, common in graph theory, is
that a spanning forest is any sub graph that is both a forest (contains no cycles) and spanning
(includes every vertex).

Counting spanning trees

The number t(G) of spanning trees of a connected graph is an important invariant. In some cases,
it is easy to calculate t(G) directly. It is also widely used in data structures in different computer
languages. For example, if G is itself a tree, then t(G)=1, while if G is the cycle graph Cn with n
vertices, then t(G)=n. For any graph G, the number t(G) can be calculated using Kirchhoff's
matrix-tree theorem (follow the link for an explicit example using the theorem).
Planar Graphs
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can
be drawn on the plane in such a way that its edges intersect only at their endpoints.
A planar graph already drawn in the plane without edge intersections is called a plane graph or
planar embedding of the graph. A plane graph can be defined as a planar graph with a
mapping from every node to a point in 2D space, and from every edge to a plane curve, such that
the extreme points of each curve are the points mapped from its end nodes, and all curves are
disjoint except on their extreme points. Plane graphs can be encoded by combinatorialmaps.
It is easily seen that a graph that can be drawn on the plane can be drawn on the sphere as well,
and vice versa.
The equivalence class of topologically equivalent drawings on the sphere is called a planar
map. Although a plane graph has an external or unbounded face, none of the faces of a planar
map have a particular status.
Applications
Telecommunications – e.g. spanning trees
Vehicle routing – e.g. planning routes on roads without underpasses
VLSI – e.g. laying out circuits on computer chip.
The puzzle game Planarity requires the player to "untangle" a planar graph so that none
of its edges intersect.

Butterfly graph

The completegraph
K4 is planar

Example graphs Planar ,Nonplanar

K3,3
K5
Basic Concepts Isomorphism:
Let G1 and G1 be two graphs and let f be a function from the vertex set of G1 to the vertex
set of G2. Suppose that f is one-to-one and onto &f(v) is adjacent to f(w) in G2 if and only if v is
adjacent to w in G1.

Then we say that the function f is an isomorphism and that the two graphs G1 and G2 are
isomorphic. So two graphs G1 and G2 are isomorphic if there is a one-to-one correspondence
between vertices of G1 and those of G2 with the property that if two vertices of G1 are adjacent
then so are their images in G2. If two graphs are isomorphic then as far as we are concerned they
are the same graph though the location of the vertices may be different. To show you how the
program can be used to explore isomorphism draw the graph in figure 4 with the program (first
get the null graph on four vertices and then use the right mouse to add edges).

Save this graph as Graph 1 (you need to click Graph then Save). Now get the circuit graph with 4
vertices. It looks like figure 5, and we shall call it C(4).
Example:

The two graphs shown below are isomorphic, despite their different looking drawings.

Graph G Graph H An isomorphism

between G and H

ƒ(a) = 1

ƒ(b) = 6

ƒ(c) = 8

ƒ(d) = 3

ƒ(g) = 5

ƒ(h) = 2

ƒ(i) = 4

ƒ(j) = 7

Sub graphs:

A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose
adjacency relation is a subset of that of G restricted to this subset. In the other direction, a
supergraphof a graph G is a graph of which G is a subgraph. We say a graph G contains
another graph H if some subgraph of G is H or is isomorphic to H.

A subgraphH is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G.
We say H spans G.

A subgraphH of a graph G is said to be induced if, for any pair of vertices x and y of H, xyis an
edge of H if and only if xyis an edge of G. In other words, H is an induced subgraph of G if it has
all the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of
V(G), then H can be written as G[S] and is said to be induced byS.

A graph that does not contain H as an induced subgraph is said to be H-free.

A universal graph in a class K of graphs is a simple graph in which every element in K can be
embedded as a subgraph.
K5, a complete graph. If a subgraph looks like this, the vertices in that subgraph form a clique
of size 5.

Multi graphs:

In mathematics, a multigraphor pseudographis a graph which is permitted to have multiple

edges, (also called "parallel edges"), that is, edges that have the same end nodes. Thus two
vertices may be connected by more than one edge. Formally, a multigraphG is an ordered pair
G:=(V, E) with

V a set of vertices ornodes,

E a multisetof unordered pairs of vertices, called edges orlines.

Multigraphs might be used to model the possible flight connections offered by an airline. In this
case the multigraph would be a directed graph with pairs of directed parallel edges connecting
cities to show that it is possible to fly both to and from these locations.
A multigraph with multiple edges (red) and a loop (blue). Not all authors allow multigraphs to
have loops.

Euler circuits:

In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly
once. Similarly, an Eulerian circuit is an Eulerian trail which starts and ends on the same
vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of
Königsberg problem in 1736. Mathematically the problem can be stated like this:

Given the graph on the right, is it possible to construct a path (or a cycle, i.e. a path starting and
ending on the same vertex) which visits each edge exactly once?

Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in
the graph have an even degree, and stated without proof that connected graphs with all vertices
of even degree have an Eulerian circuit. The first complete proof of this latter claim was
published in 1873 by CarlHierholzer.

The term Eulerian graph has two common meanings in graph theory. One meaning is a graph
with an Eulerian circuit, and the other is a graph with every vertex of even degree. These
definitions coincide for connected graphs.

For the existence of Eulerian trails it is necessary that no more than two vertices have an odd
degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree,
all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails
start at one of them and end at the other. Sometimes a graph that has an Eulerian trail but not an
Eulerian circuit is calledsemi-Eulerian.

An Eulerian trail, Eulerian trail or Euler walk in an undirected graph is a path that uses each
edge exactly once. If such a path exists, the graph is called traversable or semi-eulerian.

An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses
each edge exactly once. If such a cycle exists, the graph is called unicursal. While such graphs
are Eulerian graphs, not every Eulerian graph possesses an Eulerian cycle.

For directed graphs path has to be replaced with directed path and cycle with directed cycle.

The definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as
well.
This graph is not Eulerian, therefore, a solution does not exist.

Every vertex of this graph has an even degree, therefore this is an Eulerian graph. Following the
edges in alphabetical order gives an Eulerian circuit/cycle.

Hamiltonian graphs:
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in
an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or
Hamiltonian circuit) is a cycle in an undirected graph which visits each vertex exactly once and
also returns to the starting vertex. Determining whether such paths and cycles exist in graphs is
the Hamiltonian path problem which isNP-complete.

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the
Icosian game, now also known as Hamilton's puzzle, which involves finding a Hamiltonian cycle
in the edge graph of the dodecahedron. Hamilton solved this problem using the Icosian Calculus,
an algebraic structure based on roots of unity with many similarities to the quaternions (also
invented by Hamilton). This solution does not generalize to arbitrarygraphs.

A Hamiltonian path or traceable path is a path that visits each vertex exactly once. A graph that
contains a Hamiltonian path is called a traceable graph. A graph is Hamilton-connected if for
every pair of vertices there is a Hamiltonian path between the two vertices.
A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that
visits each vertex exactly once (except the vertex which is both the start and end, and
so is visited twice). A graph that contains a Hamiltonian cycle is called a
Hamiltonian graph.

Similar notions may be defined for directed graphs, where each edge (arc) of a path or
cycle can only be traced in a single direction (i.e., the vertices are connected with arrows
and the edges traced "tail-to-head").

A Hamiltonian decomposition is an edge decomposition of a graph into Hamiltonian

circuits.

Examples
a complete graph with more than two vertices is
Hamiltonian every cycle graph is Hamiltonian
every tournament has an odd number of
Hamiltonian paths every platonic solid, considered
as a graph, is Hamiltonian

Chromatic Numbers:

In graph theory, graph coloring is a special case of graph labeling; it is an

assignment of labels traditionally called "colors" to elements of a graph subject to certain
constraints. In its simplest form, it is a way of coloring the vertices of a graph such that
no two adjacent vertices share the same color; this is called a vertex coloring. Similarly,
an edge coloring assigns a color to each edge so that no two adjacent edges share the
same color, and a face coloring of a planar graph assigns a color to each face or region
so that no two faces that share a boundary have the same color.

Vertex coloring is the starting point of the subject, and other coloring problems
can be transformed into a vertex version. For example, an edge coloring of a graph is just
a vertex coloring of its line graph, and a face coloring of a planar graph is just a vertex
coloring of its planar dual. However, non-vertex coloring problems are often stated and
studied as is. That is partly for perspective, and partly because some problems are best
studied in non-vertex form, as for instance is edge coloring.

The convention of using colors originates from coloring the countries of a map,
where each face is literally colored. This was generalized to coloring the faces of a graph
embedded in the plane. By planar duality it became coloring the vertices, and in this form
it generalizes to all graphs. In mathematical and computer representations it is typical to
use the first few positive or nonnegative integers as the "colors". In general one can use
any finite set as the "color set". The nature of the coloring problem depends on the
number of colors but not on what theyare.

Graph coloring enjoys many practical applications as well as theoretical

challenges. Beside the classical types of problems, different limitations can also be set on
the graph, or on the way a colors assigned, or even on the color itself. It has even reached
popularity with the general public in the form of the popular number puzzle Sudoku.
Graph coloring is still a very active field of research.

A proper vertex coloring of the Petersen graph with 3 colors, the minimum number
possible.

Vertex coloring

When used without any qualification, a coloring of a graph is almost always a proper
vertex coloring, namely a labeling of the graph’s vertices with colors such that no two
vertices sharing the same edge have the same color. Since a vertex with a loop could
never be properly colored, it is understood that graphs in this context are loop less.

The terminology of using colors for vertex labels goes back to map coloring. Labels like
red and blue are only used when the number of colors is small, and normally it is
understood that the labels are drawn from the integers {1,2,3,...}.
A coloring using at most k colors is called a (proper) k-coloring. The smallest number of
colors needed to color a graph G is called its chromatic number, χ(G). A graph that can
be assigned a (proper) k-coloring is k-colorable, and it is k-chromatic if its chromatic
number is exactly k. A subset of vertices assigned to the same color is called a color
class, every such class forms an independent set. Thus, a k-coloring is the same as a
partition of the vertex set into k independent sets, and the terms k-partite and k-colorable
have the same meaning.
This graph can be 3-colored in 12 different ways.
The following table gives the chromatic number for familiar classes of graphs.

Graph complete graph cycle graph ,

star graph , 2

wheel graph ,
, 2

wheel graph ,