图路径

图 中的路径是 的子图，它是一个 路径图 (West 2000, p. 20)。路径的长度是它包含的边的数量。

在大多数情况下，路径必须至少包含一条边，但在某些应用中（例如，定义路径覆盖数），允许长度为 0 的“退化”路径，仅由单个顶点组成 (Boesch et al. 1974)。

一个 -路径是一个路径，其端点（度数为 1 的顶点）是具有不同索引 和 的顶点。（符号 和 也常用。）可以在 Wolfram 语言 中使用以下命令找到单个 -路径FindPath[g, s, t], 而FindPath[g, s, t, kspec, n] 最多查找长度为 kspec 的 条路径（其中 kspec 可以是Infinity并且 可以是All).

对于简单图，路径等同于迹，并且完全由顶点的有序序列指定。对于简单图 ，哈密顿路径是包含 的所有顶点（且其端点不相邻）的路径。

在具有邻接矩阵 的图中，从顶点 到顶点 的（无向）-步的数量由 的 元素给出 (Festinger 1949)。为了计算图路径的数量 ，必须减去所有不是路径的闭合 -步。

前几个 -路径矩阵 可以用封闭形式给出

			(1)
			(2)
			(3)

(Luce 和 Perry 1949, Katz 1950, Ross 和 Harary 1952, Perepechko 和 Voropaev)，其中 是由 的对角线元素形成的矩阵， 表示矩阵元素级乘法。

此外，-环的数量与 的关系为

(4)

其中 表示迹。

Giscard et al. (2016) 给出了路径矩阵的公式，给出了从 到 的 -路径的数量，如下所示

(5)

其中，求和是对包含 和 的 的连通导出子图 进行的， 表示 在 中的邻居数（即 的顶点 不在 中，并且存在从 到 的顶点的至少一条边）， 表示矩阵的迹， 是 的邻接矩阵限制在连通导出子图 的 次矩阵幂的 元素，即

(6)

其中 。