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)?


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$.

  • $\begingroup$ eh yes, metric should mean "value for a distance (distance because in general these are the km between cities) = 1 in my graph, or weight function (in my case mostly f(x) = x)" but anyway thank you! $\endgroup$ – reox Jun 22 '11 at 11:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.