2
$\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)?

1 Answers 1

1

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

  • 0
    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!2011-06-22