環 (圖論)

有向迴路

圖論中，環是只有首末頂點重複的非空路徑。沒有環的圖稱作無環圖，沒有有向環的有向圖稱為有向無環圖；無環連通圖稱作樹。

定義

迴路，環

• 迴路是一條非空的路徑， 其中首末頂點頂點是同一點。令圖$G=(V,E,\varnothing )$，迴路是非空路徑$(e_{1},e_{2},\ldots ,e_{n})$，其頂點序列為$(v_{1},v_{2},\ldots ,v_{n},v_{1})$
• 環路或簡單迴路是只有首末頂點相同的迴路。
• 迴路和環的長度是經過的邊數。

有向迴路，有向環路

• 有向迴路是非空的有向路徑，其首末頂點相同。令有向圖$G=(V,E,\varnothing )$，迴路是非空有向路徑$(e_{1},e_{2},\ldots ,e_{n})$，其頂點序列為$(v_{1},v_{2},\ldots ,v_{n},v_{1})$。
• 有向環路或簡單有向迴路，是只有首末頂點重複的有向迴路。

無弦環

若環上任意兩頂點都不會被不屬於環的邊相連，則稱之為圖中的無弦環或洞，其補稱作反洞（antihole）。無弦環可用於刻畫完美圖：根據強完美圖定理，圖是完美圖的充要條件是其不存在頂點數為奇數的洞或反洞。弦圖是一種特殊的完美圖，其不存在頂點數大於等於3的無弦環。

圖的圍長是圖中最短環的長度。由此，最短環一定是無弦的。籠是給定圍長和度後最小的正則圖。

邊環是圖上具有一些特殊性質的環：連接任意兩個不在環上的頂點的路徑必須經過這個環上的頂點。若圖不是由環加一條邊構成的，則邊環一定是導出環。

環空間

「環」也可指圖的環空間的元素。有很多環空間，每個係數域或環都有一個。最常見的是二元環空間（常簡稱為「環空間」），由每個頂點具有偶數度的邊集組成；其在2元素有限域上形成了向量空間。據維布倫定理，環空間的每個元素都可由簡單環的邊不交並形成。圖的環基是形成環空間的基的簡單環集合。

利用代數拓撲的思想，二元循環空間可推廣到其他環（如整數、有理數或實數環等等）上的向量空間或模。

在圖上探測環

有向圖和無向圖上的環可用深度優先搜索（DFS）探測：尋找一條連接當前頂點與之前頂點的邊（它包含了一條後向邊）。DFS跳過的所有後向邊都屬於某個環。無向圖上，指向父節點的邊不能算作後向邊，但找到已經過的頂點意味著後向邊的存在。找到n階無向圖上的環只需要O(n)時間。

許多拓撲排序算法也要探測環，因為它們將是拓撲排序的障礙。另外，若有向圖被分為幾個強連通分量，那麼環只會存在於這些分量內，而不會連接，因為環本身就是強連接的。

對有向圖，還可使用基於分布式信息的算法。其思路是，從一個頂點發出的信息可通過環回到這個頂點。分布式環檢測算法十分適於在計算機集群上用分布式圖處理系統來處理大規模的圖。

環檢測的應用如用wait-for graph檢測並行系統的死鎖。

算法

上述用深度優先搜索查找循環的方法可描述為：

For every vertex v: visited(v) = finished(v) = false
For every vertex v: DFS(v)

其中

DFS(v) =
  if finished(v): return
  if visited(v):
    "Cycle found"
    return
  visited(v) = true
  for every neighbour w: DFS(w)
  finished(v) = true

對於無向圖，「鄰接」指與v相連的所有頂點，遞歸調用DFS(v)的除外。這種省略可避免算法找到形如v→w→v的平凡環，其存在於所有有多條邊的無向圖中。

用廣度優先搜索的變體將找到長度儘可能小的環。

用環覆蓋圖

1736年，歐拉在關於柯尼斯堡七橋問題的論文中證明，要使有限無向圖中的閉合走法能精確訪問每條邊（使其成為閉合軌跡）一次，必須同時滿足：除孤立頂點外是連通的（即所有邊都包含在一個分量中），同時每個點的度都是偶數。而對有向圖，存在閉漫遊（closed walk）不重複地經過每條邊的充要條件是：圖是強連接的，且每個頂點出入度相等。在這兩個情況下，環或漫遊稱作歐拉環。對有限無向圖（無論連通），若其每個頂點的度都是偶數，則可以找到一組簡單的環不重複地覆蓋每一條邊，這就是維布倫定理。即使連通圖不滿足歐拉定理的條件，仍可以在多項式時間內通過解郵遞員問題，找到長度最短的閉漫遊，經過每一條邊至少一次。

在圖上找到不重複地過每個頂點的簡單環，要更加困難，這樣的環是哈密頓環，確定圖上是否存在哈密頓環是NP完全問題。很多研究已經找到了一些種類的圖，其上一定能找到哈密頓環。例如奧爾定理：若圖上每對不相鄰頂點的度之和大於等於圖的階數，則圖中有哈密頓環。

循環雙覆蓋猜想可表述為：對無橋圖，存在由簡單環組成的多重集，使它們一起能覆蓋每條邊恰好兩次。目前這個猜想仍未證明或證偽。

由環刻畫的圖類別

有一些重要的圖的類型可以被環來刻畫和定義。它們包括：

• 二分圖，不存在奇數長的環的圖
• 仙人掌圖，a graph in which every nontrivial biconnected component is a cycle
• 環圖，一個環組成的圖
• 弦圖，不存在長度大於3的導出環（induced cycle）的圖
• 有向無環圖，a directed graph with no cycles
• 線完美圖，每一個奇數長度的簡單環都是一個三角形
• 完美圖，不存在長度大於3的洞(hole)或反洞(antihole)
• Pseudoforest，a graph in which each connected component has at most one cycle
• 絞窄圖，a graph in which every peripheral cycle is a triangle
• 強連通圖，一個有向圖，其中每一條邊都是環的一部分
• 無三角形圖，a graph without three-vertex cycles

參見

• 環空間
• 環基
• 迭代函數值序列中的環探測