MHB Finding the shortest Hamiltonian cycle in a complete graph

[Adhil]

[SOLVED]

Okay so I have an assignment to do with only 1 question left incomplete because we have not covered this section yet, non the less it is due soon and I can't find any helpful resources on how to do this question. I know it has something to do with graphs but I'm still lost. So if anyone can give me some helpful resources to learn about this topic I'd really appreciate it, if you can answer it whilst explaining why, it'd be even more helpful. If you are going to answer it please only do 1.1 and nothing more https://uploads.tapatalk-cdn.com/20180427/321a0fea1a560f81f05517632eef038c.jpg

 

[Evgeny.Makarov]

If I understand the terms "ring" and "full loop" correctly, they mean a Hamiltonian cycle in the terminology of graph theory, that is, a path that begins and ends at the same vertex and visits each each vertex exactly once. When edges have lengths, finding the shortest Hamiltonian cycle is known as the traveling salesman problem. This problem is computationally hard, and no solution is known that is more efficient than a brute-force search through all cycles. Maybe that's why the problem was assigned without giving you any specific method of solving it. Since the graph is complete (i.e., each pair of vertices is connected by an edge), each permutation of the five vertices gives a Hamiltonian cycle. Perhaps you can write a program that searches through all $5!=120$ such permutations and finds the shortest cycle. According to my calculations, the length of the shortest cycle is 23.3.

 

[Adhil]

If I understand the terms "ring" and "full loop" correctly, they mean a Hamiltonian cycle in the terminology of graph theory, that is, a path that begins and ends at the same vertex and visits each each vertex exactly once. When edges have lengths, finding the shortest Hamiltonian cycle is known as the traveling salesman problem. This problem is computationally hard, and no solution is known that is more efficient than a brute-force search through all cycles. Maybe that's why the problem was assigned without giving you any specific method of solving it. Since the graph is complete (i.e., each pair of vertices is connected by an edge), each permutation of the five vertices gives a Hamiltonian cycle. Perhaps you can write a program that searches through all $5!=120$ such permutations and finds the shortest cycle. According to my calculations, the length of the shortest cycle is 23.3.

Thank you Evgeny after hours of research I've finally managed to do it. The Hamiltonian cycle was the key word