Mathematics of Graphs: Finding Hamiltonian Circuit in a Weighted Graph
Another method of finding a Hamiltonian circuit in a complete weighted graph is given by the following edge-picking algorithm:
• Mark the edge of smallest weight in the graph. (If two or more edges have the same weight, pick any one.)
• Mark the edge of next smallest weight in the graph, as long as it does not complete a circuit and does not add a third marked edge to a single vertex.
• Continue this process until you can no longer mark any edges. Then mark the final edge that completes the Hamiltonian circuit.
The edge-picking algorithm attempts to give a circuit of minimal total weight, although it does not always succeed.
28 фев 2021
