路径

路径是一个序列 , , , ..., 的 图顶点 和 图边 ，使得对于 , 边 的端点为 和 (West 2000, p. 20)。路径的长度是它的边数。

一个 -路径 是一个以顶点 为起点，顶点 为终点的路径，其中 和 被称为端点。每个 -路径 都包含一个 -图路径 (West 2000, p. 21)。

如果一个路径的端点相同，则称该路径是闭合的。在一个具有邻接矩阵 的图中，(无向) 闭合 -路径 的数量由 给出，其中 表示矩阵的迹。为了计算 个 -图环 的数量 ，必须减去所有不是 环 的闭合 -路径。 类似地，为了计算图路径的数目 ，必须减去所有不是图路径的 -路径（因为它们包含冗余顶点）（参见 Festinger 1949, Ross and Harary 1952）。

对于一个简单图（没有重边），一个路径可以完全由顶点的有序列表指定（West 2000, p. 20）。

迹 是一条没有重复边的路径。