Loading AI tools
在圖中一組起點與終點相同的路徑 来自维基百科,自由的百科全书
若環上任意兩頂點都不會被不屬於環的邊相連,則稱之為圖中的無弦環或洞,其補稱作反洞(antihole)。無弦環可用於刻畫完美圖:根據強完美圖定理,圖是完美圖的充要條件是其不存在頂點數為奇數的洞或反洞。弦圖是一種特殊的完美圖,其不存在頂點數大於等於3的無弦環。
圖的圍長是圖中最短環的長度。由此,最短環一定是無弦的。籠是給定圍長和度後最小的正則圖。
邊環是圖上具有一些特殊性質的環:連接任意兩個不在環上的頂點的路徑必須經過這個環上的頂點。若圖不是由環加一條邊構成的,則邊環一定是導出環。
「環」也可指圖的環空間的元素。有很多環空間,每個係數域或環都有一個。最常見的是二元環空間(常簡稱為「環空間」),由每個頂點具有偶數度的邊集組成;其在2元素有限域上形成了向量空間。據維布倫定理,環空間的每個元素都可由簡單環的邊不交並形成。圖的環基是形成環空間的基的簡單環集合。[1]
有向圖和無向圖上的環可用深度優先搜索(DFS)探測:尋找一條連接當前頂點與之前頂點的邊(它包含了一條後向邊)。[3]DFS跳過的所有後向邊都屬於某個環。[4]無向圖上,指向父節點的邊不能算作後向邊,但找到已經過的頂點意味著後向邊的存在。找到n階無向圖上的環只需要O(n)時間。
許多拓撲排序算法也要探測環,因為它們將是拓撲排序的障礙。另外,若有向圖被分為幾個強連通分量,那麼環只會存在於這些分量內,而不會連接,因為環本身就是強連接的。[4]
對有向圖,還可使用基於分布式信息的算法。其思路是,從一個頂點發出的信息可通過環回到這個頂點。分布式環檢測算法十分適於在計算機集群上用分布式圖處理系統來處理大規模的圖。
上述用深度優先搜索查找循環的方法可描述為:
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)不重複地經過每條邊的充要條件是:圖是強連接的,且每個頂點出入度相等。在這兩個情況下,環或漫遊稱作歐拉環。對有限無向圖(無論連通),若其每個頂點的度都是偶數,則可以找到一組簡單的環不重複地覆蓋每一條邊,這就是維布倫定理。[6]即使連通圖不滿足歐拉定理的條件,仍可以在多項式時間內通過解郵遞員問題,找到長度最短的閉漫遊,經過每一條邊至少一次。
在圖上找到不重複地過每個頂點的簡單環,要更加困難,這樣的環是哈密頓環,確定圖上是否存在哈密頓環是NP完全問題。[7]很多研究已經找到了一些種類的圖,其上一定能找到哈密頓環。例如奧爾定理:若圖上每對不相鄰頂點的度之和大於等於圖的階數,則圖中有哈密頓環。 [8]
循環雙覆蓋猜想可表述為:對無橋圖,存在由簡單環組成的多重集,使它們一起能覆蓋每條邊恰好兩次。目前這個猜想仍未證明或證偽。[9]
有一些重要的圖的類型可以被環來刻畫和定義。它們包括:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.