Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

let R Relation: (u,v) in R iff there is a path between u and v (u and v are graph vertices)

I want to prove that Relation R is transitive, now i've seen than you cant just concatenate Pu->v to Pv->w and you have to cut those pathes at their meeting and only then concatenate.

my question is, why is that?

Thanks.

share|improve this question
1  
Do you know what "path" means? –  Chris Eagle Sep 26 '12 at 14:28
    
yeah, it meens that there is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. –  Some1Pr0 Sep 26 '12 at 14:33
    
A path is a trail in which all vertices (except perhaps the first and last ones) are distinct. –  Ali Amiri Sep 26 '12 at 14:36
    
@Some1Pr0 vertices must be distinct! –  Ali Amiri Sep 26 '12 at 14:37
    
why? there is simple path which is a distincted path –  Some1Pr0 Sep 26 '12 at 14:53
add comment

1 Answer 1

This really depends on whether your equivalence relation is formed from simple paths or just paths in general. Both formulations will form well-defined equivalence relations. As a side note, it's convention in most places to refer to simple paths as just paths, although this isn't observed everywhere.

For paths in general (allowing repetition) then concatenation of the path is perfectly fine. Given paths $$P_{uv} = (u, u_1, \cdots , u_k, v)$$ $$P_{vw} = (v, v_1 , \cdots, v_\ell, w)$$ the concatenated path $$P_{uvw}=(u, u_1, \cdots, u_k, v, v_1, \cdots, v_{\ell}, w)$$ forms the necessary path without problems.

If you want the equivalence relation formed based on simple paths, then you must not only concatenate the paths, but remove any repetitions. Suppose that $v_i$ is the first vertex encountered in the concatenated path which will be repeated at some point. Then there is a sub-path (cycle) from $v_i$ to $v_i$ in $P_{uvw}$ $$P_{uvw} = (u, \cdots ,v_{i-1}, \underbrace{v_i, \cdots, v_i}_\text{cycle}, v_{i+1}\cdots w)$$ then if we contract the cycle, we have a simplified path $$P^\prime_{uvw} = (u, \cdots, v_{i-1}, v_i, v_{i+1} \cdots w)$$ in which the mutliplicity of $v_i$ is reduced by $1$. We can continue this procedure and we can be ensured that this algorithm will eventually terminate since the path is finite. Therefore will will eventually obtain a simple path after the necessary cycle contractions.

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.