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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ 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'. $\endgroup$– Pat DevlinCommented Jun 27, 2012 at 11:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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 semi-metric structure where the triangle inequality doesnt hold! $\endgroup$– K A KhanCommented Jun 27, 2012 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 semi-metric you can form on a subset of $\mathbb R^1$. Then you can form that on an edge-weighted path. $\endgroup$ Commented Aug 8, 2012 at 18:23