Take the 2-minute tour ×

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?

share|improve this question
Well of course you can get a bunch of "trivial" semi-metrics (just get a semi-metric that has almost nothing to do with the tree structure) (or get a metric and then mess it up a little), and you can get the (useful) metric with path of least weight [but in a tree, there's exactly one path between any two vertices anyway]. It would help to know what types of properties you would like the semi-metric to have. Your question is presumably "is there a 'nice' semi-metric?", and it would help to have your definition of 'nice'. –  Pat Devlin Jun 27 '12 at 11:05

1 Answer 1

Yes, it is possible. If we define the distance between two vertices in a graph as being the smallest sum of the weights of the edges connecting both, that would form a metric (if the graph is connected).

share|improve this answer
what about semi-metric structure where the triangle inequality doesnt hold! –  Kamran Jun 27 '12 at 10:09
Let the distance between $x$ and $y$ be the square of the sum of the weights on the path between them. Then, as you can see with a path on three vertices where both edges have weight 1, the triangle inequality does not hold. Think of any semi-metric you can form on a subset of $\mathbb R^1$. Then you can form that on an edge-weighted path. –  Andrew D. King Aug 8 '12 at 18:23

Your Answer


