路徑

路徑是一個序列 , , , ..., 的 圖頂點 和 圖邊 ，使得對於 , 邊 的端點為 和 (West 2000, p. 20)。路徑的長度是它的邊數。

一個 -路徑 是一個以頂點 為起點，頂點 為終點的路徑，其中 和 被稱為端點。每個 -路徑 都包含一個 -圖路徑 (West 2000, p. 21)。

如果一個路徑的端點相同，則稱該路徑是閉合的。在一個具有鄰接矩陣 的圖中，(無向) 閉合 -路徑 的數量由 給出，其中 表示矩陣的跡。為了計算 個 -圖環 的數量 ，必須減去所有不是 環 的閉合 -路徑。 類似地，為了計算圖路徑的數目 ，必須減去所有不是圖路徑的 -路徑（因為它們包含冗餘頂點）（參見 Festinger 1949, Ross and Harary 1952）。

對於一個簡單圖（沒有重邊），一個路徑可以完全由頂點的有序列表指定（West 2000, p. 20）。

跡 是一條沒有重複邊的路徑。