圖路徑

圖 中的路徑是 的子圖，它是一個 路徑圖 (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)

其中 。