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

There is a simple and well-defined distance measure on weighted undirected graphs, namely the least sum of edge weights on any (simple) path between two vertices.

Can one devise a meaningful distance metric for weighted directed graphs? (assume non-negative weights and that the distance must be symmetric and have the triangular property)

share|improve this question
    
Could you not do the same thing as with undirected graphs, which gives a non-symmetric metric D, and then symmetrize, i.e. define a metric d by d(x,y) = max{D(x,y), D(y,x)}? –  Tom Leinster Feb 3 '10 at 15:58
    
Yes...I had considered d(x,y) = (D(x,y)+D(y,x))/2 but that just didn't feel right. Did you mean 'min'? If so that seems much more satisfying for edge distance. but...I don't think it'll work for paths. –  Mitch Harris Feb 3 '10 at 16:07
1  
Min does not satisfy the triangle inequality, only max does. –  domotorp Feb 3 '10 at 16:23
1  
Mitch, I meant max (and agree with domotorp). And yes, I also had it in mind that you could use + to symmetrize, rather than max. It sounds like you have some kind of design criteria in mind for how this distance should behave. Maybe you could add something to the question explaining them? (There's an "edit" button.) –  Tom Leinster Feb 3 '10 at 17:24
    
That min doesn't work but max does is not obvious to me (and I can't seem to think through it). Is there a short counterexample? –  Mitch Harris Feb 3 '10 at 20:24
show 1 more comment

1 Answer

Since you're asking for what is "meaningful", I think that one can then argue against some of the question.

The value of metrics on graphs in combinatorial geometry as an area of pure mathematics are more or less the same as their value in applied mathematics, for instance in direction-finding software in Garmin or Google Maps. In any such setting, the triangle inequality is essential for the metric interpretation, but the symmetry condition $d(x,y) = d(y,x)$ is not. An asymmetric metric captures the idea of one-way distance. You can have perfectly interesting geometry of many kinds without the symmetry condition. For instance, you can study asymmetric Banach norms such that $||\alpha x|| = \alpha ||x||$ for $\alpha > 0$, but $||x|| \ne ||-x||$, or the corresponding types of Finsler manifolds.

On the other hand, if you want to restore symmetry, you can. For instance, $$d'(x,y) = d(x,y) + d(y,x)$$ has a natural interpretation as round-trip distance, which again works equally well for pure and applied purposes. You can also use max, directly, or even min with a modified formula. Namely, you can define $d'$ to be the largest-distance metric such that $$d'(x,y) \le \min(d(x,y),d(y,x))$$ for all $x$ and $y$. All of these have natural interpretations. For instance, the min formula could make sense for streets that are one-way for cars but two-way for bicycles.

share|improve this answer
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.