Path: Continuous Path vs. Path in a Graph
“Path” has two common meanings, one in topology and one in graph theory. A continuous path is a continuous function $\gamma : [0, 1] \to X$ into a topological space $X$, so a continuous path passes through infinitely many points, unless the path stays at one point. A path in a graph is a finite sequence of distinct vertices such that each pair of consecutive vertices is joined by an edge.
Definitions
A path is a way of moving continuously from one point to another, described by the position $\gamma(s)$ at each value of a parameter $s$ that goes from $0$ to $1$.
Consider a topological space $X$. A path in $X$ is a continuous function
\[\gamma : [0, 1] \to X.\]The points $\gamma(0)$ and $\gamma(1)$ are the start and the end of the path.
Examples
-
The half circle $\gamma$ is a continuous path from $(1, 0)$ to $(-1, 0)$, because $\gamma$ is a continuous function from $[0, 1]$ to $\reals^2$.
Non-examplesThings that may be mistaken for examples of this term.
-
The vertex sequence $a, b, a$ is not a continuous path, because it is not a continuous function from $[0, 1]$ to a topological space.
-
The vertex sequence $a, b, c$ is not a continuous path, because it is a finite list of vertices, not a continuous function from $[0, 1]$ to a topological space.
Properties
- Every path is a curve, parametrized by the interval $[0, 1]$.
- A space is path connected if every two points of the space are joined by a path.
Imagine a network drawn as dots joined by lines, like a map of cities and roads. A path is a route that goes from dot to dot along the lines and never visits the same dot twice.
Consider a graph $G = (V, E)$. A path in $G$ is a sequence $v_0, v_1, \dots, v_k$ of distinct vertices such that each pair of consecutive vertices is joined by an edge:
\[\setdef{v_{i - 1}, v_i} \in E \quad \text{for } i = 1, 2, \dots, k.\]The path starts at $v_0$ and ends at $v_k$. The length of the path is $k$, which is the number of edges that the path uses.
Examples
-
The vertex sequence $a, b, a$ is not a path in the triangle graph, because $a, b, a$ visits the vertex $a$ twice; a sequence of vertices joined by edges that may repeat vertices is called a walk.
-
The vertex sequence $a, b, c$ is a path from $a$ to $c$ in the triangle graph, because the vertices $a$, $b$, $c$ are distinct and the edges $\setdef{a, b}$ and $\setdef{b, c}$ join consecutive vertices.
Non-examplesThings that may be mistaken for examples of this term.
-
The half circle $\gamma$ is not a path in a graph, because $\gamma$ is a function on the interval $[0, 1]$, not a sequence of vertices of a graph.
Properties
- A graph is connected if every two vertices of the graph are joined by a path.
Examples
Is the object a path in the ___ sense?
Notes
- The two meanings share a picture: when a graph is drawn in the plane with each edge drawn as a curve, a path in the graph traces a continuous path through the drawing, from the first vertex to the last.
- A continuous path may cross itself, but a path in a graph visits each vertex at most once. A sequence of vertices joined by edges that may repeat vertices is called a walk.