Definition:Path (Category Theory)
Jump to navigation
Jump to search
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.
Sources
There are no source works cited for this page. Source citations are highly desirable, and mandatory for all definition pages. Definition pages whose content is wholly or partly unsourced are in danger of having such content deleted. To discuss this page in more detail, feel free to use the talk page. |