Use the brute force algorithm to find a minimum Hamilton cir

Use the brute force algorithm to find a minimum Hamilton circuit or minimum Hamilton circuits for the graph. Determine the total weight of the minimum Hamilton circuit(s). Which Hamilton circuits are the optimal solutions? What is the weight of the optimal solution?

Solution

A Hamiltonian Circuit is a circuit that visits every vertex exactly once.

Brute-Force Method is

This method is inefficient, i.e., takes a lot of time. The reason is that if we have a complete graph, K-N, with N vertecies then there are (N-1)! circuits to list, calculate the weight, and then select the smallest from.

Note that the circuit is bidirectional. so we can cut the number of circuits by half.

A - B - C - D - A = 31+41+16+26 = 114 = A - D - C - B - A

A - B - D - C - A = 31+11+16+29 = 87 = A - C - D - B - A ( optimum solution)

A - D - B - C - A = 26+11+41+29 = 107 = A - C - B - D - A

b) The weight of optimum solution is 87