I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum spanning tree). Also if anyone of you can post some lecture note or paper links so that i can study these graphs.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Less cryptography in the title, please. $\endgroup$– Dave ClarkeApr 15, 2011 at 20:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If the weight of the MST is $W$, then the weight of all edges is $\le \binom n 2 \cdot W$, because every edge in the graph is bounded by the unique path in the MST connecting the two nodes of the edge by the triangle inequality.
This is tight: Consider a line with edge weights all being equal to $1$ and let the metric be the shortest path metric induced by this line. Then the MST is this line and has weight $n-1$, on the other hand there are $\Omega(n^2)$ pairs of nodes with a distance of $\Omega(n)$.
