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?

  • 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 Devlin
    Jun 27 '12 at 11:05

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 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 semi-metric you can form on a subset of $\mathbb R^1$. Then you can form that on an edge-weighted path. $\endgroup$ Aug 8 '12 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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