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

1$\begingroup$ Well of course you can get a bunch of "trivial" semimetrics (just get a semimetric 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 semimetric to have. Your question is presumably "is there a 'nice' semimetric?", and it would help to have your definition of 'nice'. $\endgroup$ – Pat Devlin Jun 27 '12 at 11:05
2
$\begingroup$
$\endgroup$
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).

$\begingroup$ what about semimetric structure where the triangle inequality doesnt hold! $\endgroup$ – K A Khan Jun 27 '12 at 10:09

$\begingroup$ 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 semimetric you can form on a subset of $\mathbb R^1$. Then you can form that on an edgeweighted path. $\endgroup$ – Andrew D. King Aug 8 '12 at 18:23