0

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?

flag
1 
 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 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).

link|flag
what about semi-metric structure where the triangle inequality doesnt hold! – Kamran Jun 27 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 at 18:23

Your Answer

Get an OpenID
or

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