Number of hamiltonian cycles in a complete graph

In graph theory, a Hamiltonian cycle is a path in a graph that visits each vertex exactly once and returns to the starting vertex. In this article, we will discuss how to calculate the number of Hamiltonian cycles in a complete graph. A complete graph is a graph where each pair of distinct vertices is connected by an edge.

Problem Statement

Given a complete graph with n vertices, we want to calculate the number of Hamiltonian cycles in the graph.

Let's consider an example to better understand the problem. Suppose we have a complete graph with 6 vertices:

    1 -- 2
   / \   |
  /   \  |
 6 -- 5 -3
  \   /  |
   \ /   |
    4 --- 

In the above graph, there are multiple Hamiltonian cycles:

• 1-2-3-4-5-6-1
• 1-6-5-4-3-2-1
• 1-5-2-3-4-6-1
• and more...

Our goal is to calculate the total number of Hamiltonian cycles in the graph.

Algorithm

To calculate the number of Hamiltonian cycles in a complete graph, we can use the following algorithm:

1. Initialize a variable 'count' to 1.
2. Initialize a variable 'i' to n - 1.
3. Calculate the factorial of 'i' and update the 'count' variable by multiplying it with 'i' in each iteration.
4. Divide the 'count' by 2.
5. Print the number of nodes and the calculated number of Hamiltonian cycles.

Pseudocode

function hamiltonianCycle(node):
    count = 1
    i = node - 1
    while i > 0:
        count = count * i
        i = i - 1
    print("Number of nodes: ", node)
    print("Hamiltonian Cycles: ", count / 2)

Explanation

In the given code, the function 'hamiltonianCycle' takes an input 'node', which represents the number of vertices in the complete graph. It calculates the number of Hamiltonian cycles using the factorial of (node - 1) and then divides it by 2.

The factorial is calculated by starting from 'node - 1' and multiplying it with the previous number in each iteration until reaching 1. For example, if 'node' is 6, the factorial would be 5 * 4 * 3 * 2 * 1 = 120.

Since a Hamiltonian cycle can be traversed in both directions (clockwise and counterclockwise), we divide the calculated count by 2 to get the actual number of unique Hamiltonian cycles.

The code then prints the number of nodes and the calculated number of Hamiltonian cycles for each test case.

Program Solution

• C
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// C Program
// Number of hamiltonian cycles in a complete graph
#include <stdio.h>

void hamiltonianCycle(int node)
{
	int count = 1;
	int i = node - 1;
	// Calculate factorial
	while (i > 0)
	{
		count = count *i;
		i--;
	}
	// Display number of nodes
	printf("\n Number of node : %d", node);
	// Display calculated result
	printf("\n hamiltonian Cycle : %d", (count / 2));
}
int main()
{
	// Test
	hamiltonianCycle(6);
	hamiltonianCycle(7);
	hamiltonianCycle(4);
	return 0;
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

// Java Program 
// Number of hamiltonian cycles in a complete graph
public class Cycle
{
	public void hamiltonianCycle(int node)
	{
		int count = 1;
		int i = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count * i;
			i--;
		}
		// Display number of nodes
		System.out.print("\n Number of node : " + node);
		// Display calculated result
		System.out.print("\n hamiltonian Cycle : " + (count / 2));
	}
	public static void main(String[] args)
	{
		Cycle task = new Cycle();
		// Test
		task.hamiltonianCycle(6);
		task.hamiltonianCycle(7);
		task.hamiltonianCycle(4);
	}
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

// Include header file
#include <iostream>
using namespace std;
// C++ Program 
// Number of hamiltonian cycles in a complete graph
class Cycle
{
	public: void hamiltonianCycle(int node)
	{
		int count = 1;
		int i = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count *i;
			i--;
		}
		// Display number of nodes
		cout << "\n Number of node : " << node;
		// Display calculated result
		cout << "\n hamiltonian Cycle : " << (count / 2);
	}
};
int main()
{
	Cycle *task = new Cycle();
	// Test
	task->hamiltonianCycle(6);
	task->hamiltonianCycle(7);
	task->hamiltonianCycle(4);
	return 0;
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

// Include namespace system
using System;
// Csharp Program 
// Number of hamiltonian cycles in a complete graph
public class Cycle
{
	public void hamiltonianCycle(int node)
	{
		int count = 1;
		int i = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count * i;
			i--;
		}
		// Display number of nodes
		Console.Write("\n Number of node : " + node);
		// Display calculated result
		Console.Write("\n hamiltonian Cycle : " + (count / 2));
	}
	public static void Main(String[] args)
	{
		Cycle task = new Cycle();
		// Test
		task.hamiltonianCycle(6);
		task.hamiltonianCycle(7);
		task.hamiltonianCycle(4);
	}
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

package main
import "fmt"
// Go Program 
// Number of hamiltonian cycles in a complete graph

func hamiltonianCycle(node int) {
	var count int = 1
	var i int = node - 1
	// Calculate factorial
	for (i > 0) {
		count = count * i
		i--
	}
	// Display number of nodes
	fmt.Print("\n Number of node : ", node)
	// Display calculated result
	fmt.Print("\n hamiltonian Cycle : ", (count / 2))
}
func main() {

	// Test
	hamiltonianCycle(6)
	hamiltonianCycle(7)
	hamiltonianCycle(4)
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

<?php
// Php Program 
// Number of hamiltonian cycles in a complete graph
class Cycle
{
	public	function hamiltonianCycle($node)
	{
		$count = 1;
		$i = $node - 1;
		// Calculate factorial
		while ($i > 0)
		{
			$count = $count * $i;
			$i--;
		}
		// Display number of nodes
		echo("\n Number of node : ".$node);
		// Display calculated result
		echo("\n hamiltonian Cycle : ".((int)($count / 2)));
	}
}

function main()
{
	$task = new Cycle();
	// Test
	$task->hamiltonianCycle(6);
	$task->hamiltonianCycle(7);
	$task->hamiltonianCycle(4);
}
main();

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

// Node JS Program 
// Number of hamiltonian cycles in a complete graph
class Cycle
{
	hamiltonianCycle(node)
	{
		var count = 1;
		var i = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count * i;
			i--;
		}
		// Display number of nodes
		process.stdout.write("\n Number of node : " + node);
		// Display calculated result
		process.stdout.write("\n hamiltonian Cycle : " + (parseInt(count / 2)));
	}
}

function main()
{
	var task = new Cycle();
	// Test
	task.hamiltonianCycle(6);
	task.hamiltonianCycle(7);
	task.hamiltonianCycle(4);
}
main();

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

#  Python 3 Program 
#  Number of hamiltonian cycles in a complete graph
class Cycle :
	def hamiltonianCycle(self, node) :
		count = 1
		i = node - 1
		#  Calculate factorial
		while (i > 0) :
			count = count * i
			i -= 1
		
		#  Display number of nodes
		print("\n Number of node : ", node, end = "")
		#  Display calculated result
		print("\n hamiltonian Cycle : ", (int(count / 2)), end = "")
	

def main() :
	task = Cycle()
	#  Test
	task.hamiltonianCycle(6)
	task.hamiltonianCycle(7)
	task.hamiltonianCycle(4)

if __name__ == "__main__": main()

 Number of node :  6
 hamiltonian Cycle :  60
 Number of node :  7
 hamiltonian Cycle :  360
 Number of node :  4
 hamiltonian Cycle :  3

#  Ruby Program 
#  Number of hamiltonian cycles in a complete graph
class Cycle 
	def hamiltonianCycle(node) 
		count = 1
		i = node - 1
		#  Calculate factorial
		while (i > 0) 
			count = count * i
			i -= 1
		end

		#  Display number of nodes
		print("\n Number of node : ", node)
		#  Display calculated result
		print("\n hamiltonian Cycle : ", (count / 2))
	end

end

def main() 
	task = Cycle.new()
	#  Test
	task.hamiltonianCycle(6)
	task.hamiltonianCycle(7)
	task.hamiltonianCycle(4)
end

main()

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

// Scala Program 
// Number of hamiltonian cycles in a complete graph
class Cycle()
{
	def hamiltonianCycle(node: Int): Unit = {
		var count: Int = 1;
		var i: Int = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count * i;
			i -= 1;
		}
		// Display number of nodes
		print("\n Number of node : " + node);
		// Display calculated result
		print("\n hamiltonian Cycle : " + (count / 2));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Cycle = new Cycle();
		// Test
		task.hamiltonianCycle(6);
		task.hamiltonianCycle(7);
		task.hamiltonianCycle(4);
	}
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

// Swift 4 Program 
// Number of hamiltonian cycles in a complete graph
class Cycle
{
	func hamiltonianCycle(_ node: Int)
	{
		var count: Int = 1;
		var i: Int = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count * i;
			i -= 1;
		}
		// Display number of nodes
		print("\n Number of node : ", node, terminator: "");
		// Display calculated result
		print("\n hamiltonian Cycle : ", (count / 2), terminator: "");
	}
}
func main()
{
	let task: Cycle = Cycle();
	// Test
	task.hamiltonianCycle(6);
	task.hamiltonianCycle(7);
	task.hamiltonianCycle(4);
}
main();

 Number of node :  6
 hamiltonian Cycle :  60
 Number of node :  7
 hamiltonian Cycle :  360
 Number of node :  4
 hamiltonian Cycle :  3

// Kotlin Program 
// Number of hamiltonian cycles in a complete graph
class Cycle
{
	fun hamiltonianCycle(node: Int): Unit
	{
		var count: Int = 1;
		var i: Int = node - 1;
		// Calculate factorial
		while (i > 0)
		{
			count = count * i;
			i -= 1;
		}
		// Display number of nodes
		print("\n Number of node : " + node);
		// Display calculated result
		print("\n hamiltonian Cycle : " + (count / 2));
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Cycle = Cycle();
	// Test
	task.hamiltonianCycle(6);
	task.hamiltonianCycle(7);
	task.hamiltonianCycle(4);
}

 Number of node : 6
 hamiltonian Cycle : 60
 Number of node : 7
 hamiltonian Cycle : 360
 Number of node : 4
 hamiltonian Cycle : 3

Output Explanation

The given code is tested with three different test cases: 6, 7, and 4.

For the first test case with 6 nodes, the code calculates the factorial of 5 (6-1) which is 120. Since a complete graph with 6 nodes has 120 different Hamiltonian cycles, dividing it by 2 gives us the output 60.

Similarly, for the second test case with 7 nodes, the code calculates the factorial of 6 (7-1) which is 720. Dividing 720 by 2 gives us the output 360.

For the last test case with 4 nodes, the code calculates the factorial of 3 (4-1) which is 6. Dividing 6 by 2 gives us the output 3.

Time Complexity

The time complexity of the given algorithm depends on the value of 'node'. Since the factorial is calculated using a loop that iterates from 'node-1' to 1, the time complexity can be considered as O(n) where 'n' is the number of vertices in the complete graph.

As a result, the time complexity of the code is linear, making it efficient for practical purposes even for larger values of 'node'.