0
$\begingroup$

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.

  • 0
    why? there is **simple path** which is a distincted **path**2012-09-26

1 Answers 1

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.