Closure
Closure
「閉包」。導出子圖,沒有聯外邊。可能有許多個。
Minimum Closure / Maximum Closure
「最小閉包」。點數最少的閉包,即是空圖,缺乏討論意義。
「最大閉包」。點數最多的閉包,即是原圖,缺乏討論意義。
無向圖的情況下,閉包是連通分量,缺乏討論意義。
有向圖的情況下,收縮強連通分量,得到DAG,容易找閉包。
Maximum Weight Closure
「最大權閉包」。一張圖上,點有權重、邊無權重,點的權重總和最大的閉包。只有唯一一個。
無向圖演算法:權重最大的連通分量。
有向圖演算法:重新打造一張圖,求最小源匯割。我不知道為什麼這樣做,真是不好意思。
新增超級源點、超級匯點。源點連向所有正點,容量是正點權重;所有負點連向匯點,容量是負點權重變號;原圖的邊,容量是無限大。
最小源匯割不會包含容量無限大的邊。也就是說,源點側到匯點側,沒有容量無限大的邊、沒有原圖的邊。源點側沒有連外邊。源點側是閉包。源點側去掉源點即是最大權閉包。
Separator🚧
Separator(Separating Set)(Cut-set)
「分隔」、「分隔集」。細分為點和邊兩種版本:
點集合,將連通圖分離成兩個以上連通分量。
邊集合,將連通圖分離成兩個以上連通分量。
Minimum Separator(Minimum Separating Set)
「最小分隔」。細分為點和邊兩種版本:
一張圖上點數最少的點分隔。可能有許多個。
一張圖上邊數最少的邊分隔。可能有許多個。
ICPC 4322 3811
(a,b)-Separator
「ab分隔」。細分為點和邊兩種版本:
斷開a點到b點,使之不連通的點集合。
斷開a點到b點,使之不連通的邊集合。
事先指定兩點ab。ab不相同、不相鄰才有討論意義。
Connectivity
「連通度」。細分為點和邊兩種版本:
欲讓圖不連通,至少需要拿掉的點數。
欲讓圖不連通,至少需要拿掉的邊數。
其點數、邊數,即是最小點分隔、最小邊分隔。
換句話說,一張圖上隨意拿掉「Vertex Connectivity減一」個點,一定還是連通的。
κ(G) ≤ λ(G) ≤ min δ(v)。點連通度小於等於邊連通度小於等於最小的度數。
Menger's Theorem
「ab點互斥路徑(點不重複、端點ab除外)的數量最大值」=「ab點分隔的點數最小值」。
「ab邊互斥路徑(邊不重複)的數量最大值」=「ab邊分隔的邊數最小值」。
邊連通度演算法(Max-Flow Min-Cut Theorem)
點容量為一:最大st流=最小st割=最大st互斥路徑=最小st分隔 邊容量為一:最大st流=最小st割=最大st互斥路徑=最小st分隔
窮舉所有點對,分別求最小分隔的大小,取最小值即得。
無向圖O(VE)。Stoer–Wagner Algorithm。
有向圖O(VEVlogV)。Hao–Orlin Algorithm。【尚待確認】
https://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf https://www.zhihu.com/question/265186138/answer/290977527 图是unweighted graph, 则可以先找k-certificate然后再用SW算法. 可以O(m)时间把边 的个数变成O(kn)个. 所以k很小的话速度还蛮快的.
邊連通度演算法(Dominating Set)
《Determining edge connectivity in O(mn)》
無向圖O(VE)或者O(λV²)。Matula's Algorithm。
《Finding the edge connectivity of directed graphs》
有向圖O(VE)或者O(λ²V²)。Mansour–Schieber Algorithm。
邊連通度演算法(Matroid Intersection)
《A matroid approach to finding edge connectivity and packing arborescences》
無向圖O(E + λ²VlogV)。有向圖O(λElogV)。Gabow's Algorithm。
邊連通度演算法(Local Search)
《Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms》
《An Experimental Study of Algorithms for Computing the Edge Connectivity of a Directed Graph》
無向圖Õ(λ²E)。有向圖Õ(λ²E)。近似演算法。
Partition🚧
Partition
Strength
強壯程度。分割之間的邊數量、分割數量(減一),兩者比值的最大值。
https://en.wikipedia.org/wiki/Strength_of_a_graph
Toughness
堅韌程度。刪除tk點無法得到k個連通分量。
https://en.wikipedia.org/wiki/Graph_toughness
Maximum Cut: Kernighan–Lin Algorithm
用途
無向圖或有向圖,指定兩側點數,求出其中一個最大割。
近似演算法,讓答案盡量準確。
演算法
隨機創造一個割,逐步改成最大割。不斷對調異側兩點,盡量讓割權重變大,直到無法變大。
Maximum Cut: Goemans–Williamson Algorithm🚧
用途
無向圖,求出其中一個最大割。
近似演算法,讓答案盡量準確。
Maximum Cut
0.878 max cut https://zhuanlan.zhihu.com/p/69126787