Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 0 down vote accepted

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

share|cite|improve this answer
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! – reox Jun 22 '11 at 11:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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