Post by vsiap on Nov 26, 2014 4:04:57 GMT
For R to be an equivalence relation we must show that it is reflexive, symmetric and transitive.
Reflexive: We need to see that there exists a path from vertex u to itself.
A path from u to itself must exist as by definition every point has a length zero path to itself.
Symmetric: We need to see that if there exists a path from u to v that there exists a path from v to u.
Assuming a path exists from u to v and considering that the graph is an undirected graph, we can simply take the reverse of the path from u to v and will then have a path from v to u. This means that if some path with i intermediate vertices u, x1, x2, . . . , xi, v exists from u to v, then by traveling through the nodes in reverse order, v, xi, . . . , x2, x1, u we have constructed a path from v to u.
Transitive: We need to see that if there exists a path from u to v and that there exists a path from v to z, that there exists a path from u to z.
The important thing to note here is that we cannot simply travel along the path from u to v and then along the path from v to z as these paths may share vertices and thus when combining the two may create a walk, not a path. The following is one method for constructing a valid path from u to z given the information stated previously. Travel along the path from u to v until you reach the first intersection with the path from v to z, call this intersection point xi. After you have reached xi, travel along the path from v to z until you reach z. We cannot cross the portion of the path from u to v we have selected as we chose the first intersection at which to leave the path.
Reflexive: We need to see that there exists a path from vertex u to itself.
A path from u to itself must exist as by definition every point has a length zero path to itself.
Symmetric: We need to see that if there exists a path from u to v that there exists a path from v to u.
Assuming a path exists from u to v and considering that the graph is an undirected graph, we can simply take the reverse of the path from u to v and will then have a path from v to u. This means that if some path with i intermediate vertices u, x1, x2, . . . , xi, v exists from u to v, then by traveling through the nodes in reverse order, v, xi, . . . , x2, x1, u we have constructed a path from v to u.
Transitive: We need to see that if there exists a path from u to v and that there exists a path from v to z, that there exists a path from u to z.
The important thing to note here is that we cannot simply travel along the path from u to v and then along the path from v to z as these paths may share vertices and thus when combining the two may create a walk, not a path. The following is one method for constructing a valid path from u to z given the information stated previously. Travel along the path from u to v until you reach the first intersection with the path from v to z, call this intersection point xi. After you have reached xi, travel along the path from v to z until you reach z. We cannot cross the portion of the path from u to v we have selected as we chose the first intersection at which to leave the path.