Calculate appr. weight of hamilton cycle

$\begingroup$

can i approximate the weight of a hamilton line in a complete weighted graph without implementing any algorithm like NN or calculate the MST? I know the average distance of each node and the metric which is used.

could i just do (average distance) * (metric) * (num of nodes)?

$\endgroup$

1 Answer

$\begingroup$

I am not sure what "distance" means in a completed graph, since each node is connected to every other. Similarly I am not sure how "metric" relates to "weight".

If there are $n$ nodes, then Hamiltonian paths have $n-1$ edges and Hamiltonian cycles have $n$ edges. Among the lists of Hamiltonian paths and cycles of a completed graph, each edge appears as often as every other.

So if the average weight of an edge is $w$ then the average weight of a Hamiltonian path is $(n-1)w$ and the average weight of a Hamiltonian cycle is $nw$.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy