---
tag: 0J8XE7W68F
kind: definition
name: Reachability
msc: [05C40]
defines: 0FDKRX9M9Y
uses: [0VJZM0F9YM]
sources:
  - url: https://en.wikipedia.org/wiki/Reachability
    locator: Definition
---

## Definition

Let $G$ be a [[graph|0JD5C82QMB]] and let $u, v$ be vertices of $G$.
The vertex $v$ is reachable from $u$ if there is a [[walk|0VJZM0F9YM]] in $G$ from $u$ to $v$.

## Remarks

Reachability is an equivalence relation on the vertices. It is reflexive by the walk of length $0$, symmetric by reversal of a walk, and transitive by concatenation.
Its equivalence classes are the [[connected components|01VVP10MWJ]] of $G$.
For a [[directed graph|0R5HTV7REV]], reachability along arcs is reflexive and transitive, but in general it is not symmetric.

## Explanations

### L1 human

A vertex is reachable from another one when you can go from the first to the second along edges.
On a map of islands with bridges, two places are reachable from each other when they are on islands linked by bridges.