Definition:Path (Category Theory)

Definition

Let $\GG$ be a graph.

A (non-empty) path in $\GG$ is a (finite) sequence $\tuple {i, a_1, \ldots, a_n, j}$ such that:

$n > 1$

$a_1, \ldots, a_n$ are edges of $\GG$

$i$ is the source of $a_1$

$j$ is the destination of $a_n$

For $1 \le k < n$ the destination of $a_k$ is the source of $a_{k + 1}$

This is usually written in the form:

$i \stackrel {a_1} \longrightarrow * \stackrel {a_2} \longrightarrow \cdots \stackrel {a_{n - 1} } \longrightarrow * \stackrel {a_n} \longrightarrow j$

For any vertex $i$ the empty path from $i$ to $i$ is the pair $\tuple {i, i}$.

Paths are composed by concatenation:

$\tuple {j, b_1, \ldots, b_n, k} \tuple {i, a_1, \ldots, a_m, j} = \tuple {i, a_1, \ldots, a_m, b_1, \ldots, b_n, k}$

Here we have used the somewhat awkward but more common right-to-left notation for composition.