Reachability
Builds on Walk
Definition
Let be a graph and let be vertices of . The vertex is reachable from if there is a walk in from to .
Remarks
Reachability is an equivalence relation on the vertices. It is reflexive by the walk of length , symmetric by reversal of a walk, and transitive by concatenation. Its equivalence classes are the connected components of . For a directed graph, reachability along arcs is reflexive and transitive, but in general it is not symmetric.
Reading path
To understand this page from the ground up, read these 3 pages in order. The foundations come first.
Show the path as a graph
- no evidence level
- Graph definition
- Walk definition
- Reachability definition
Where this leads
33 pages build on this one.
- Connected component
- Euler's theorem on Eulerian circuits
- K5 and K3,3 are not planar
- Every connected graph has a spanning tree
- Tutte's theorem
- Unique paths in trees
- Forest
- Prüfer sequence
- Trees are bipartite
- Rooted tree
- Bridge
- Connected graph
- Characterization of bridges
- Spanning tree
- Every finite tree with at least two vertices has a leaf
- Kuratowski's theorem
- Cayley's formula
- Tree
- Edge bound for planar graphs
- A tree on n vertices has n − 1 edges
- Euler's formula for planar graphs
- Distance in a graph
- Minimum spanning tree
- Crossing number inequality
- Net of a polyhedron
- Unit distance problem
- Treewidth
- Digital topology
- Cheeger constant
- k-vertex-connected graph
- Petersen's theorem
- Graph minor
- Kruskal's tree theorem
Further reading
- Web https://en.wikipedia.org/wiki/Reachability, Definition
About this page
| Tag | 0J8XE7W68F |
|---|---|
| URI | m2://0J8XE7W68F |
| Kind | definition |
| Writing | W0 stub |
| MSC | 05C40 |
| Defines | Reachability |
| Uses | Walk |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.