[go: up one dir, main page]
Scribd
Upload
150 views4 pages

Design and Analysis of Algorithms: Graph Coloring Using Backtracking

The document describes an algorithm to find all Hamiltonian cycles in a graph using backtracking. It begins by defining the Hamiltonian cycle problem and providing an example. It then outlines the backtracking approach, which uses a solution vector (x1, ..., xn) to represent the visited vertices. The NextValue function determines the next possible vertex xk based on previously chosen vertices x1 through xk-1. The Hamiltonian function recursively calls NextValue and tracks visited vertices to find all cycles. The time complexity is O(n!) due to the n! possible vertex permutations. It also briefly describes the related Travelling Salesman Problem.

Uploaded by

Harsh Vardhan Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
150 views4 pages

Design and Analysis of Algorithms: Graph Coloring Using Backtracking

The document describes an algorithm to find all Hamiltonian cycles in a graph using backtracking. It begins by defining the Hamiltonian cycle problem and providing an example. It then outlines the backtracking approach, which uses a solution vector (x1, ..., xn) to represent the visited vertices. The NextValue function determines the next possible vertex xk based on previously chosen vertices x1 through xk-1. The Hamiltonian function recursively calls NextValue and tracks visited vertices to find all cycles. The time complexity is O(n!) due to the n! possible vertex permutations. It also briefly describes the related Travelling Salesman Problem.

Uploaded by

Harsh Vardhan Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Design and Analysis of

Algorithms
Study material on

Graph Coloring using Backtracking

Dilip Kumar Maity


Computer Science and Engineering
Academy of Technology
dilip.maity@aot.edu.in
June 28, 2021
Hamiltonian Cycle Problem using backtracking
What is Hamiltonian Cycle Problem?
Let G = (V, E) be a connected graph with n vertices. A Hamiltonian cycle (suggested by Sir
William Hamilton) is a round-trip path along n edges of G that visits every vertex once and re-
turns to its starting position. In other words if a Hamiltonian cycle begins at some vertex v1 ∈ G
and the vertices of G are visited in the order v1 , v2 ,...,vn+1 , then the edges (vi , vi+1 ) are in E,
1 ≤ i ≤ n, and the vi are distinct except for v1 and vn+1 , which are equal.

Example:
The graph G1 of the following gure contains the Hamiltonian cycle 1, 2, 8, 7, 6, 5, 4, 3, 1. The
graph G2 of contains no Hamiltonian cycle.

Approach:
There is no known easy way to determine whether a given graph contains a Hamiltonian cycle. We
now look at a backtracking algorithm that nds all the Hamiltonian cycles in a graph. The graph
may be directed or undirected. Only distinct cycles are output.

Algorithm:
The backtracking solution vector (x1 , ...xn ) is dened so that xi represents the ith visited vertex
of the proposed cycle. Now all we need do is determine how to compute the set of possible vertices
for xk if x1 ...xk−1 have already been chosen. If k = 1, then x1 can be any of the n vertices. To
avoid printing the same cycle n times, we require that x1 = 1. If 1 < k < n, then xk can be
any vertex v that is distinct from x1 , x2 , ..., xk−1 and v is connected by an edge to xk−1 . The
vertex xn can only be the one remaining vertex and it must be connected to both xn−1 and x1 .
We begin by presenting function NextValue(k), which determines a possible next vertex for

2
the proposed cycle. Using NextValue we can particularize the recursive backtracking schema
to nd all Hamiltonian cycles. This algorithm is started by rst initializing the adjacency matrix
G[l : n, 1 : n], then setting x[2 : n] to zero and x[1] to 1, and then executing Hamiltonian(2).

Algorithm 1: Hamiltonian
(k)
// This algorithm uses the recursive formulation of
backtracking to find all the Hamiltonian cycles of a graph.
The graph is stored as an adjacency matrix G[l : n, 1 : n].
All cycles begin at node 1.
1 repeat
// Generate values for x[k]
2 NextValue (k); // Assign a legal next value to x[k]
3 if x[k] = 0then return ; // no new vertex available

4 if k=n then Write (x[1 : n]);


5 else Hamiltonian (k + 1);
6 until false ;

Algorithm 2: NextValue
(k)
// x[1 : k − 1] is a path of k − 1 distinct vertices. If
x[k] = 0, then no vertex has as yet been assigned to x[k].
After execution, x[k] is assigned to the next highest
numbered vertex which does not already appear in x[1 : k − 1]
and is connected by an edge to x[k − 1]. Otherwise x[k] = 0.
If k = n, then in addition x[k] is connected to x[1].
1 repeat
2 x[k] := (x[k] + 1) mod (n + 1) // next vertex
;

3 if x[k] = 0 then return // all vertex have been included


;

4 if G[x[k − 1], x[k]] 6= 0 then


// Is there an edge?
5 for j := 1 k − 1 do
to
6 if x[j] = x[k] then break ;

7 end
// Check for distinctness.
8 if j = k then
// If true, then the vertex is distinct.
9 if (k < n) ((k = n) G[x[n], x[1]] 6= 0) then return
or and ;

10 end
11 end
12 until false ;

3
Time Complexity:
There are n! possible permutations of the n vertices, and therefore the running time is O(n! )
Travelling Salesman Problem:
A traveller needs to visit all the cities from a list, where distances between all the
cities are known and each city should be visited just once. What is the shortest possi-
ble route that he visits each city exactly once and returns to the origin city?

Travelling salesman problem is a problem of nding tour with minimum cost. This tour is a
Hamiltonian cycle. For the simple case of a graph all of whose edge costs are similar, Hamiltonian
will determine a minimum-cost tour if a tour exists. If the common edge cost is C , the cost of a
tour is Cn as there are n edges in a Hamiltonian cycle.

You might also like