Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
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 '12 at 11:05
add comment

1 Answer

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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