Paths and Cycles

A path is a sequence of vertices you can traverse by following edges. It is
how we talk about moving through a graph.

Definition 6.2.1 (notes p. 90): A path in $G = \langle V, E \rangle$ is an
$(n+1)$-tuple

The vertex $v_0$ is the start and $v_n$ is the end; the number $n$ is the
length of the path. Note: not all $v_i$ need to be different! When they are
distinct, the path is simple.

Three nested concepts:
- A walk allows repeated vertices and edges.
- A trail allows repeated vertices but distinct edges.
- A path has distinct vertices (and therefore distinct edges).

Definition 6.2.2 (notes p. 90): A path is cyclic (a cycle) if
$\text{start}(p) = \text{end}(p)$. A cycle is simple if no other vertex repeats.

Cycles cause real problems. Even a tiny cyclic graph can have paths of infinite
length — you just go around the cycle forever. This is why acyclic graphs are
often the focus in AI: parse trees, search trees, dependency graphs, causal graphs.

The length of a path matters: in a knowledge graph, a 1-hop path is a direct
relation; a 2-hop path is a relation-of-a-relation ("Paris", "capital-of", "France",
"speaks", "French"). The number of hops is a measure of how indirect the inference is.

Definition 2.5 (depth of a vertex). Let $G = \langle V, E \rangle$ be a directed graph. The depth of a vertex $v$ is the length of the longest directed path that starts at $v$:

If no path starts at $v$ (i.e. $v$ is a sink), $\text{dp}(v) = 0$. If there are arbitrarily long paths starting at $v$, $\text{dp}(v) = \infty$.

Definition 2.6 (depth of a graph). The depth of a graph is the supremum over all vertices:

Example 2.7. Consider the path graph $v_1 \to v_2 \to v_3 \to v_4 \to \cdots$ with edges $(v_i, v_{i+1})$:
- $\text{dp}(v_1) = \infty$ (we can walk forever to the right).
- $\text{dp}(v_n) = \infty$ for every $n$ — there is always a longer path to the right.
- $\text{dp}(G) = \infty$.

For a finite acyclic graph (DAG), every vertex has finite depth and $\text{dp}(G)$ is bounded by the length of the longest path.