專著

已有熱心人士撰寫專著，介紹擬陣：

《Combinatorial Optimization: Algorithms and Complexity》

《Combinatorial Optimization》

《Combinatorial Optimization: Polyhedra and Efficiency》

第一本圖片豐富。第二本文字簡短。第三本理論完善。

Set

先暖身一下。

集合。set
{1,2,3,4}

所有子集合。subsets of set
{}, {1}, {2}, {3}, {4},
{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4},
{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}

所有子集合，挑選一部分。family of subsets of set
{{}, {1}, {1,2}, {2,3}}

Matroid

「擬陣」。所有子集合，挑選一部分。必須滿足兩條規則：

一、挑選了一個子集，也必須挑選其所有子集（大小差一）。

例如挑了{1,2,3}，也必須挑選{1,2}和{1,3}和{2,3}。

二、挑選了兩個子集（大小差一）。大子集減小子集，從中找到一個適當元素，放入小子集，形成新子集。也必須挑選這個新子集。

例如挑了{1,2,3}和{1,4}。大子集減小子集{2,3}，從中找到一個適當元素2（也可以是3）。也必須挑選{1,2,4}。

反覆套用兩條規則。「大小差一」改成「大小差一以上」再改成「大小不同」，規則意義仍然相同。

擬陣是人工數學。制定特殊規則，得以使用貪心法設計演算法。

Ground Set與Independent Sets

數學家替集合們取了名字。

「基準集」。原本的集合。

「獨立集」。挑選的子集合們。

Independent Sets省略了字首sub-。

Matroid範例

各種數學領域當中，可以找到一些特殊事物，恰好是擬陣。

數學家已經發現各式各樣的擬陣。這裡舉三個例子。

一、線性代數之線性擬陣Linear Matroid。

基準集：矩陣的直條。獨立集：直條互相線性獨立。

二、集合論之分割擬陣Partition Matroid。

基準集：集合的元素。獨立集：各區塊最多取一個元素。

三、圖論之圖擬陣Graphic Matroid。

基準集：無向圖的邊。獨立集：森林（無向無環圖）。

Matroid冷門範例

額外補充六個例子。後面章節不會用到。

一、線性代數之二元擬陣Binary Matroid。

矩陣數值皆是GF(2)的線性擬陣。

二、集合論之均勻擬陣Uniform Matroid。

基準集：集合的元素。獨立集：子集合，尺寸在特定值以下。

三、集合論之橫截擬陣Transversal Matroid。

基準集：集合的元素。獨立集：各子集各取一個相異元素。

四、圖論之匹配擬陣Matching Matroid。

基準集：無向圖的點。獨立集：匹配邊所覆蓋的點。

五、圖論之伽瑪擬陣Gammoid（互斥路徑擬陣Disjoint Path Matroid）。

基準集：無向圖的點。獨立集：點（邊）互斥路徑，以特定的起點，所抵達的終點。

六、圖論之環空間擬陣Cycle Space Matroid。

基準集：無向圖的環。獨立集：任意組合的XOR皆非空。

Matroid並非用來描述獨立，只是借用了名字。

擬陣的設計靈感，源自線性代數。

例如名稱「擬陣matroid」借自「矩陣matrix」。名稱「獨立集independent sets」借自「線性獨立linear independent」。

然而，擬陣跟獨立其實沒有關係。

例如獨立集Independent Set、支配集Dominating Set、點覆蓋Vertex Cover、邊覆蓋Edge Cover，通通不是擬陣。

擬陣是一種特殊的遞迴結構，故意設計成可以套用貪心法。

例如森林Forest是擬陣。

演算法：判斷是否為獨立集（Independence Oracle）

給定一個子集，卜杯請示神明，判斷是否為獨立集。

各種擬陣各有演算法。我們沒有深入考慮是哪一種擬陣，也沒有深入考慮演算法細節，直接從冥冥之中獲得正解，故取名oracle。

各種擬陣各有時間複雜度。一律簡單地標記為O(Q)。

演算法：找出所有獨立集

窮舉所有子集，一一檢查是否屬於擬陣。

時間複雜度O(2ᴺQ)。N是基準集大小。Q是卜杯時間。

Cardinality

一個獨立集的「基數」是元素數目。

「基數」源自集合論，意義是集合的大小。

Weight

令基準集每個元素擁有權重。一個獨立集的「權重」是元素權重總和。

「權重」源自組合最佳化，意義是使用代價。

Maximum Independent Set

「最大獨立集」。基數最大的獨立集。通常有許多個。

Maximum Weight Independent Set

「最大權獨立集」。權重最大的獨立集。可能有許多個。

Maximum Weight Maximum Independent Set

「最大權最大獨立集」。基數最大、然後權重最大的獨立集。可能有許多個。

Maximum Independent Set範例

各種數學領域當中，可以找到一些特殊事物，恰好是最大獨立集、最大（小）權獨立集、最大（小）權最大獨立集。

數學家已經發現各式各樣的最大獨立集。這裡舉一個例子。

森林Forest：圖擬陣的獨立集。

生成森林Spanning Forest：最大獨立集。

最小權森林Minimum Weight Forest：最小權獨立集。

最小生成森林Minimum (Weight) Spanning Forest：最小權最大獨立集。

如果是連通圖，生成森林就是生成樹。大家應該很熟悉了。

Maximal Independent Set（Base）

「極大獨立集」簡稱「基底」。「無論增加哪個元素、都不再是獨立集」的獨立集。通常有許多個。

名稱借自線性代數之「基底basis」。

Greedy Method

擬陣相當特別，所有極大獨立集恰巧一樣大。

換句話說，所有極大獨立集恰巧都是最大獨立集。所有局部極值恰巧都是全域極值。Maximal = Maximum。

原理是規則二。兩個子集，令較小的子集是極大獨立集，令較大的子集是最大獨立集。不斷從差集找到一個適當元素，加入到較小的子集，直到兩個子集一樣大。從極大獨立集一路灌到最大獨立集。

再引入規則一。從任意獨立集都能一路灌到最大獨立集。

擬陣是人工數學。制定特殊規則，得以使用貪心法設計演算法。

演算法：找出一個最大獨立集

窮舉所有元素，一一嘗試納入當前獨立集，檢查是否屬於擬陣。是則納入，否則捨棄。

時間複雜度O(NQ)。N是基準集大小。Q是卜杯時間。

演算法：找出一個最大（小）權獨立集

權重由大到小，窮舉所有元素，捨棄負權重元素，其餘同前。

排序O(NlogN)，N次卜杯O(NQ)，時間複雜度是兩者相加O(NlogN + NQ)。

演算法：找出一個最大（小）權最大獨立集

依照權重大小，窮舉所有元素，其餘同前。

排序O(NlogN)，N次卜杯O(NQ)，時間複雜度是兩者相加O(NlogN + NQ)。

各種擬陣各有演算法。這裡舉一個例子。

圖論之圖擬陣Graphic Matroid。最小權最大獨立集，就是Minimum Spanning Forest。此演算法，就是Kruskal's Algorithm。

一邊窮舉所有元素，一邊使用Disjoint-sets Forest累計成果，以便降低卜杯時間。時間複雜度O(NlogN + Nα(V)) = O(NlogN)。N是邊數，也是基準集大小。

Disjoint Independent Sets

「互斥獨立集」。選擇多個獨立集，兩兩交集都是空集合。

M = (S, I)
D = (D₁, D₂, ...) where Dᵢ∈I for all i
                        Dᵢ∩Dⱼ = ∅ for all i ≠ j

Partitionable Set

「可分割集」。K個互斥獨立集的聯集。K是給定常數。

換句話說，基準集的所有子集合當中，得以分割成K個互斥獨立集者。通常有許多個。

M = (S, I)
U₍ₖ₎ = { D₁∪D₂∪...∪Dₖ : Dᵢ∈I for all i          }
       {                Dᵢ∩Dⱼ = ∅ for all i ≠ j }

Maximum Partitionable Set

「最大可分割集」。互斥獨立集大小沒有限制，聯集盡量大。

Greedy Method

首先以圖擬陣當作範例。圖擬陣是森林，大家比較熟悉森林。

一叢森林，添加一條邊，要嘛形成環、要嘛沒有形成環。

一、形成環：移除環上一條邊，又變成森林，大小相同。

二、沒有形成環：仍是森林，大小加一。

定義「交換exchange」：添加一條邊、移除環上一條邊。

實施數次交換，可以得到各種一樣大的森林（總是形成環），甚至更大一點的森林（沒有形成環）。

只要嘗試各種交換方式，從任意森林都可以一路灌到最大森林。

順帶一提，最小有向生成樹演算法，也用了交換。作者同一人。

Minimal Dependent Set（Circuit）

對於任意擬陣，將環改成「極小相依集」即可。

「極小相依集」簡稱「迴路」。「無論減少哪個元素、都必定是獨立集」的非獨立集。通常有許多個。

名稱借自圖論之「環cycle」。

演算法：找出一個最大可分割集

時間複雜度O(NQ)。【尚待確認】

專著

《Handbook of Combinatorics》

Disjoint Independent Sets from k Matroids

「分別來自K個擬陣的互斥獨立集」。K個擬陣，基準集相同，獨立集未必相同。K個擬陣，各自選擇一個獨立集，讓K個獨立集彼此互斥。

（如果基準集不一樣，那麼基準集聯集即可。）

M₁ = (S, I₁)
M₂ = (S, I₂)
   :
Mₖ = (S, Iₖ)
D = (D₁, D₂, ..., Dₖ) where Dᵢ∈Iᵢ for all i
                            Dᵢ∩Dⱼ = ∅ for all i ≠ j

Partitionable Set from k Matroids（Matroid Partition）

「分別來自K個擬陣的可分割集」簡稱「擬陣分割」。

「擬陣分割」這個詞彙用得不太精準。後面章節會介紹正確的「擬陣分割」是什麼。

（如果基準集不一樣，那麼基準集聯集即可。）

M₁ = (S, I₁)
M₂ = (S, I₂)
   :
Mₖ = (S, Iₖ)
U = { D₁∪D₂∪...∪Dₖ : Dᵢ∈Iᵢ for all i          }
    {                Dᵢ∩Dⱼ = ∅ for all i ≠ j }

Matroid Disjoint Union（Matroid Sum）

「擬陣互斥聯集」簡稱「擬陣和」。基準集相同，獨立集兩兩互斥聯集，若不互斥則不計入。

（如果基準集不一樣，那麼基準集聯集即可。）

M₁ = (S, I₁)
M₂ = (S, I₂)
M₁+M₂ = (S, I)
where I = { D₁∪D₂ : D₁∈I₁ , D₂∈I₂ , D₁∩D₂ = ∅ }

換句話說，新獨立集是可分割集。

M₁ = (S, I₁)
M₂ = (S, I₂)
M₁+M₂ = (S, U₁₂)

擬陣相加，仍是擬陣。

Matroid Union

「擬陣聯集」。基準集相同，獨立集兩兩聯集。

（如果基準集不一樣，那麼基準集聯集即可。）

M₁ = (S, I₁)
M₂ = (S, I₂)
M₁∪M₂ = (S, I)
where I = { D₁∪D₂ : D₁∈I₁ , D₂∈I₂ }

擬陣聯集等同擬陣和。根據規則一，我們總是可以找到更小的子集，使得獨立集互斥。

Matroid k-Fold Sum

「擬陣k重和」。K個相同擬陣，連加起來。

M = (S, I)
M₍ₖ₎ = (S, U₍ₖ₎)

Matroid k-Fold Sum範例

一、k重森林k Edge-Disjoint Forests：圖擬陣k重和。

如果是連通圖、如果邊足夠多，k重生成樹k Edge-Disjoint Spanning Trees是最大獨立集。

二、k重有向森林k Edge-Disjoint Directed Forests：圖擬陣k重和、分割擬陣k重和，兩者交集。

如果是連通圖、如果邊足夠多，k重有向生成樹k Edge-Disjoint Directed Spanning Trees是最大共同獨立集。

Disjoint Independent Sets的交換操作

定義「連鎖交換」：

D₁         D₂         D₃             Dₖ
(+e₁, -e₂) (+e₂, -e₃) (+e₃, -e₄) ... (+eₖ, -e₁)

所有互斥集，總共添加同一堆邊、總共移除同一堆邊。

連鎖交換宛如網路流的擴充環。

實施連鎖交換，可以得到各種一樣大的可分割集（總是形成擴充環），甚至更大一點的可分割集（形成擴充路徑）。

只要嘗試各種連鎖交換方式，從任意可分割集都可以一路灌到最大可分割集。

演算法：找出一個最大可分割集（擬陣聯集的最大獨立集）

建立一張交換圖：

一、點：
　點：集合。
二、源匯：
　起點：追加點s。
　終點：追加點t。
三、邊：
　起點：若a不屬於當前的互斥獨立集D=D₁∪D₂∪...∪Dₖ，則建立邊sa。
　中間：若Dᵢ+a不屬於第i擬陣，且Dᵢ+a-b屬於第i擬陣，則建立邊ab。
　終點：若Dᵢ+b屬於第i擬陣，則建立邊bt。

演算法宛如最大流。找到一條s點到t點的最短擴充路徑。根據拜訪的邊，調整對應的互斥獨立集，加入點a、減去點b，就得到更大一點的互斥獨立集，整體大小增加一。因為互斥獨立集改變了，所以每回合進行擴充之後，都要重新建圖。找不到擴充路徑，那麼K個互斥獨立集通通聯集，就是最大可分割集。

事實上，每條邊只會出現一次又消失一次。每回合不必重新建圖，只需稍微修圖。

時間複雜度：找出一個最大可分割集（擬陣聯集的最大獨立集）

邊數O(N²K)，尋找擴充路徑O(N²)，最多N回合。時間複雜度O(N³KQ + N³Q) = O(N³KQ)。

重新建圖改成稍微修圖，時間複雜度降為O(N²KQ + N³Q) = O(N²(N+K)Q)。

令最大可分割集的基數是C，時間複雜度可以寫得更精準。

邊數O(C(N-C)K) = O(NCK)，尋找擴充路徑O(NC)，總共C+1回合。時間複雜度O(NCKQ + NCCQ) = O(NC(C+K)Q)。

O(N C (C+K) Q)     Shortest Augmenting Path Algorithm [Edmonds 1970]
O(N sqrtC (C+K) Q) Blocking Flow Algorithm [Cunningham 1986]

Common Independent Set（Matroid Intersection）

「共同獨立集」簡稱「擬陣交集」。每個擬陣都擁有的獨立集。

（如果基準集不一樣，那麼基準集聯集即可。）

M₁ = (S, I₁)
M₂ = (S, I₂)
M₁∩M₂ = (S, I₁∩I₂)

M₁ = (S, I₁)
M₂ = (S, I₂)
M₁∩M₂ = (S, I)
where I = { J₁ : J₁∈I₁ , J₂∈I₂ , J₁=J₂ }

擬陣交集，通常不再是擬陣。

Maximum Common Independent Set

「最大共同獨立集」。基數最大的共同獨立集。通常有許多個。

Matroid Intersection範例

各種數學領域當中，可以找到一些特殊事物，恰好是擬陣交集。

數學家已經發現各式各樣的擬陣交集。這裡舉三個例子。

一、二分匹配Bipartite Matching：下述兩個擬陣的交集。

甲、Partition Matroid：X側各點的鄰邊，至多各選一條。

乙、Partition Matroid：Y側各點的鄰邊，至多各選一條。

最大二分匹配Maximum Bipartite Matching是最大共同獨立集。

二、有向森林Directed Forest：下述兩個擬陣的交集。

甲、Graphic Matroid：無向森林。

乙、Partition Matroid：各點入邊，至多各選一條。

如果是連通圖，有向生成樹Directed Spanning Tree是最大共同獨立集。

三、互斥有向路徑與環Vertex Disjoint Directed Paths/Cycles：下述三個擬陣的交集。

甲、Graphic Matroid：無向森林。

乙、Partition Matroid：各點入邊，至多各選一條。

丙、Partition Matroid：各點出邊，至多各選一條。

如果是連通圖、如果邊足夠多，有向生成環Directed Hamilton Cycle是最大共同獨立集。

Common Independent Set的交換操作

擬陣交集，通常不再是擬陣，無法使用原來的貪心法：從任意的獨立集，一路灌到最大獨立集。

利用「交換exchange」，得到新的貪心法：從任意的共同獨立集，一路灌到最大共同獨立集。

首先以圖擬陣當作範例。圖擬陣是森林，大家比較熟悉森林。

兩張子圖的兩叢森林一齊實施相同交換，從任意共同森林一路灌到最大共同森林。

然而兩叢森林不見得可以一齊實施相同交換。添加同一條邊，第一叢森林形成環，第二叢森林卻沒有形成環。

解決方式是「錯位交換」：

森林一 (+a₁, -b₁) (+a₂, -b₂) (+a₃, -b₃) ... (+aₙ , -bₙ)
森林二 (+a₂, -b₁) (+a₃, -b₂) (+a₄, -b₃) ... (+a₁ , -bₙ)

兩叢森林，添加同一堆邊、移除同一堆邊。

錯位交換宛如二分匹配的擴充環。

實施錯位交換，可以得到各種一樣大的共同森林（總是形成擴充環），甚至更大一點的共同森林（形成擴充路徑）。

只要嘗試各種錯位交換方式，從任意共同森林都可以一路灌到最大共同森林。

Augmenting Path與Augmenting Cycle

對於任意擬陣，證明過程冗長，我沒有深究。讀者可自行研究：

證明過程的起點是Base Exchange Property：

兩個最大獨立集A與B。A-B存在元素a，B-A存在元素b，使得A-a+b仍是最大獨立集。

演算法：找出一個最大共同獨立集

建立一張交換圖：

一、二分圖：
　左側：當前的共同獨立集I。以下標作點x。
　右側：其餘元素S-I。以下標作點y。
二、源匯：
　起點：追加點s，位在極右。
　終點：追加點t，也位在極右。
三、邊：
　起點：若I+y  屬於第二擬陣，則建立邊sy。
　左向：若I+y-x屬於第一擬陣，則建立邊yx。
　右向：若I+y-x屬於第二擬陣，則建立邊xy。
　終點：若I+y  屬於第一擬陣，則建立邊yt。

演算法宛如最大二分匹配。找到一條s點到t點的最短擴充路徑。當前的共同獨立集，減去左側點x、加入右側點y，就得到更大一點的共同獨立集，大小增加一。因為當前的共同獨立集改變了，所以每回合都要重新建圖。找不到擴充路徑，就是最大共同獨立集。

實作時，不必事先建圖。一邊卜杯、一邊尋找擴充路徑。

時間複雜度：找出一個最大共同獨立集

邊數O(N²)，尋找擴充路徑O(N²)，最多N回合。時間複雜度O(N³Q)。

令最大共同獨立集的基數是C，時間複雜度可以寫得更精準。

邊數O(C(N-C)) = O(NC)，尋找擴充路徑O(NC)，總共C+1回合。時間複雜度O(NC²Q)。

matroid:
O(N C C Q)        Shortest Augmenting Path Algorithm [Edmonds 1970]
O(N C sqrtC Q)    Hopcroft–Karp Algorithm [Cunningham 1986]
O(N logN sqrtC Q) Admissible Graph [Chakrabarty et al. 2019]

linear matroid:
O(N Cω-1)         Matrix Multiplication [Harvey 2009]

graphic matroid:
O(N logC sqrtC)   Hopcroft–Karp Algorithm [Gabow–Xu 1989]

兩個擬陣的交集是P問題。三個以上擬陣的交集，通通等價，都是NP-complete問題。

演算法：找出一個最大權共同獨立集

改為找最大權擴充路徑。

建立點權重：左側點x權重變號，右側點y權重不變。

《Exact and Approximation Algorithms for Weighted Matroid Intersection》

專論

Disjoint Independent Sets / Independent Set Partition / Independent Set Packing / Independent Set Cover

「互斥獨立集」。選擇多個獨立集，彼此互斥。

進一步衍生三個問題：

「獨立集分割」。選擇多個獨立集，彼此互斥，涵蓋基準集。

「獨立集填裝」。選擇多個獨立集，彼此互斥。

「獨立集覆蓋」。選擇多個獨立集，涵蓋基準集。

三者皆等價。根據規則一，我們總是可以選擇更小的子集，直到彼此互斥、直到涵蓋基準集。

Partition範例

森林分解Forest Decomposition：圖擬陣分割。

演算法：找出一組分割

隨便找到一組不互斥獨立集，修改成互斥獨立集。

一、隨便找到一組不互斥獨立集。依序窮舉基準集元素。每當遇到尚未涵蓋的元素，那就一路灌到最大獨立集，將它當作一個新的不互斥獨立集。

二、修改成互斥獨立集。演算法宛如正規正交化。根據規則一，令D₁ = B₁、D₂ = B₂ - B₁、D₃ = B₃ - B₂ - B₁、……。

演算法：找出一組最小分割

獨立集大小沒有限制，獨立集數量盡量小。

使用Matroid Union演算法。K=1開始試誤，K逐次加一。

最初設置一個空的互斥獨立集。當前的互斥獨立集，不斷嘗試增加整體大小，直到涵蓋基礎集。如果無法增加整體大小，那麼增設一個空的互斥獨立集。

演算法不必重新開始。時間複雜度仍然相同。

Disjoint Bases / Base Partition / Base Packing / Base Cover

「互斥最大獨立集」簡稱「互斥基底」。選擇多個最大獨立集，彼此互斥。

進一步衍生三個問題：

「最大獨立集分割」簡稱「基底分割」。選擇多個最大獨立集，彼此互斥，涵蓋基準集。

「最大獨立集填裝」簡稱「基底填裝」。選擇多個最大獨立集，彼此互斥。

「最大獨立集覆蓋」簡稱「基底覆蓋」。選擇多個最大獨立集，涵蓋基準集。

因為每個最大獨立集都一樣大，所以可以輕易地初步判斷最大獨立集分割是否存在。

因為通常不存在，所以大家轉為討論填裝和覆蓋。

填裝數量最大值≤分割數量（如果有）≤覆蓋數量最小值。

Base Packing範例

生成樹填裝Spanning Tree Packing：圖擬陣基底填裝。

演算法：判斷是否可以填裝K個最大獨立集

令最大獨立集的大小是B。看看最大可分割集的大小，是否等於KB。

換句話說，K個互斥獨立集的大小皆到達上限，K個互斥獨立集皆是最大獨立集。

UVa 12370

演算法：判斷最多可以填裝幾個最大獨立集

K=1開始試誤，K逐次加一。

演算法不必重新開始。時間複雜度仍然相同。

Disjoint Common Independent Sets

「互斥共同獨立集」。給定兩個擬陣，基準集相同。選擇數個共同獨立集，彼此互斥。

分割、填裝、覆蓋，仍是懸案。少數的特殊擬陣則是P問題。

《The Matroid Intersection Cover Problem》

Disjoint Common Bases

「互斥共同最大獨立集」。給定兩個擬陣，基準集相同，最大獨立集恰好一樣大、恰好一部分相同。選擇數個共同最大獨立集，彼此互斥。

分割、填裝、覆蓋，仍是懸案。少數的特殊擬陣則是P問題。

《On Disjoint Common Bases in Two Matroids》

專著

《Combinatorial Optimization: Networks and Matroids》

Matroid Parity

「擬陣奇偶」。基準集元素事先兩兩配對。嘗試選擇其中幾對，使得合併之後恰是某個獨立集。

Matroid Parity範例

匹配Matching：Partition Matroid的擬陣奇偶。

演算法：最大配對

NP-complete問題。少數的特殊擬陣則是P問題。

Base（Maximal Independent Set）

「極大獨立集」簡稱「基底」。「無論增加哪個元素、都不再是獨立集」的獨立集。通常有許多個。

名稱借自線性代數之「基底basis」。

所有獨立集可以等價交換為所有Base，反之亦然。

Circuit（Minimal Dependent Set）

「極小相依集」簡稱「迴路」。「無論減少哪個元素、都必定是獨立集」的非獨立集。通常有許多個。

名稱借自圖論之「環cycle」。

所有獨立集可以等價交換為所有Circuit，反之亦然。

Independent Subset

「獨立子集」。給定一個集合，其所有子集當中，恰是獨立集者。通常有許多個。

Rank（Cardinality of Maximum Independent Subset）

「最大獨立子集的基數」簡稱「秩」。

名稱借自線性代數之「秩rank」。

所有獨立集可以等價交換為所有基準子集及其Rank，反之亦然。

Span（Closure）（Maximum Superset with Same Rank）

「擁有相同秩的最大超集」簡稱「生成」或「閉包」。

名稱借自線性代數之「生成span」。

Matroid Rank Function

輸入：基礎集的每一種子集。輸出：Rank。

恰巧是遞增函數Monotonic Function。

恰巧是次模函數Submodular Function。

Matroid Rank Function相關定理

以下列出Matroid Rank Function的各種定理，證明省略。

Matroid Rank Function性質強大。數學家經常利用這些定理，進一步證明各式各樣的數學定理。

∙ Rank Function of Matroid

  rank(X) = max |A|
            A⊆X
            A∈I

∙ Rank Function of Dual Matroid

  rank*(X) = |X| + rank(S-X) - rank(X)

∙ Rank Function of Matroid Contraction

  rankM/Z(X) = rank(S-Z) - rank(Z)

∙ Rank Function by Disjoint Matroid Restrictions

  rank(X) = min { |X-A| + sum { rank(Sᵢ∩A) } }   where S₁∪…∪Sₖ = S
            A⊆X            i                           Sᵢ∩Sⱼ = ∅

∙ Rank Function of Matroid Union

  rankᵤ(X) = min { rankᵤ(X-A) + sum { rankᵢ(Sᵢ∩A) } }
  X⊆S₁∪…∪Sₖ  A⊆X                 i

  rankᵤ(X) = min { rankᵤ(X-A) + sum { rankᵢ(A) } }   when S₁ = … = Sₖ
     X⊆S     A⊆X                 i

∙ Maximum Rank of Matroid Union

    max |I| = min { |S-A| + sum { rankᵢ(A) } }   when S₁ = … = Sₖ
  I∈I₁∪…∪Iₖ   A⊆S            i

    max |I| = min ​{ |S-A| + k rank(A) }   when M₁ = … = Mₖ
  I∈I₁∪…∪Iₖ   A⊆S

∙ Rank Function of Matroid Sum

  rank₊(X) = min { |X-A| + sum { rankᵢ(A) } }
    X⊆S      A⊆X            i

∙ Maximum Rank of Matroid Intersection

    max |I| = min ​{ rank₁​(A) + rank₂​(S-A) }
  I∈I₁∩I₂     A⊆S

∙ Rank Function of Matroid Partition (Edmonds 1965)
  《Minimum Partition of a Matroid Into Independent Subsets》

  minimum partition is k
  iff every X⊆S satisfies |X| ≤ k rank(X)

∙ Rank Function of k Matroid Partition (Edmonds–Fulkerson 1965)
  《Transversals and Matroid Partition》

  k-partitionable
  iff every X⊆S satisfies |X| ≤ sum rankᵢ(X)

∙ Forest Decomposition (Nash-Williams 1961)

  a graph can be partitioned to k forests
  iff every X⊆V satisfies f(X) ≤ k (|X| - 1)
  where f(X) is the edge number of induced subgraph from X

∙ Directed Spanning Tree Decomposition (Edmonds 1965)

  a directed graph can be partitioned to
  k edge disjoint spanning trees (with common root r)
  iff all in-degrees are equal to k (excluding root)

∙ Rank Function of Matroid Base Packing

  maximum base packing is k
  iff every A⊆S satisfies k (rank(S) - rank(A)) ≤ |S-A|

∙ Spanning Tree Packing
  https://math.stackexchange.com/questions/2507816/

  every 2ᵏ-edge-connected graph has k edge disjoint spanning trees

∙ Independent Spanning Tree Conjecture 
  http://lemon.cs.elte.hu/egres/open/Independent_trees

  every k-edge-connected graph has k r-path disjoint spanning trees

∙ Shannon Switching Game
  http://www.misojiro.t.u-tokyo.ac.jp/~tzik/shannon/index.xhtml.en

  Short wins
  iff any subgraph containing s and t has 2 edge disjoint spanning trees

Dual Matroid

「對偶擬陣」。找到所有的最大獨立集。原本擬陣的各個最大獨立集的補集，就是對偶擬陣的各個最大獨立集。反推所有的獨立集。

Dual Matroid範例

各種數學領域當中，可以找到一些特殊事物，恰好是對偶擬陣。

數學家已經發現各式各樣的對偶擬陣。這裡舉一個例子。

平面圖的森林：原本擬陣的獨立集。平面圖的圖擬陣。

對偶圖的森林：對偶擬陣的獨立集。恰巧也是圖擬陣。

平面圖的生成樹：原本擬陣的最大獨立集。

對偶圖的生成樹：對偶擬陣的最大獨立集。

此例源自平面對偶。大家應該很熟悉了。

平面圖的情況下，圖擬陣的對偶擬陣恰巧也是圖擬陣。一般圖的情況下，圖擬陣的對偶擬陣，通常不是圖擬陣，也沒有特別命名。

Dual Matroid冷門範例

Submatroid

「子擬陣」。基準集挑選一部分，獨立集挑選一部分，仍然滿足兩條規則，形成新擬陣。

得到子擬陣的三種經典操作：

一、截斷Truncation。

基準集：相同。獨立集：基數小於等於常數k。

二、限制Restriction。

基準集：子集合。獨立集：所有元素都在基準集當中。

三、收縮Contraction。

基準集：相同。獨立集：對偶、補集Restriction、對偶。

truncation t(M): I' = { A ∈ I : |A| ≤ k }
restriction M|Z: I' = { A ∈ I : A - Z = ∅ }
contraction M/Z: M/Z = (M*|(S-Z))*

Submatroid範例

邊數為k的森林Forests with k Edges：圖擬陣的截斷。

導出子圖的森林Forests in Induced Subgraph：圖擬陣的限制。

次圖的森林Forests in Graph Minor：圖擬陣的收縮。

Matroid Intersection → Matroid Union

順帶一提，最大可分割集可以求得最大共同獨立集。

M₁與M₂*的最大可分割集B = J₁∪J₂。

（M₁+M₂*的最大獨立集B = J₁∪J₂。）

其中J₁來自M₁，J₂來自M₂*，兩者互斥。

將J₂一路灌到M₂*的最大獨立集B₂。

M₁和M₂的最大共同獨立集B-B₂。

擬陣對偶只適合人腦推導，不適合電腦計算。沒人採用此方法。

Matroid Union → Matroid Intersection

擬陣限制只適合人腦推導，不適合電腦計算。沒人採用此方法。

Submodular Function

「次模函數」。所有子集合，滿足特殊規則：自身、交集、聯集之間的大小關係。

     modular function: f(A) + f(B) = f(A ∪ B) + f(A ∩ B)
  submodular function: f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B)
supermodular function: f(A) + f(B) ≤ f(A ∪ B) + f(A ∩ B)
                       for all A and B

次模函數是一種特殊的遞迴結構，故意設計成可以套用貪心法。

Submodular Function解讀方式

次模函數有許多種解讀方式。

marginal effect
https://www.zhihu.com/question/34720027

area cover
https://zhuanlan.zhihu.com/p/106576120

optimization
https://people.seas.harvard.edu/~yaron/AM221-S16/schedule.html

Submodular Function範例

各種數學領域當中，可以找到一些特殊事物，恰好是次模函數。

數學家已經發現各式各樣的次模函數。這裡舉三個例子。

一、Cut的權重。有向圖或無向圖，圖上只有正邊、零邊。

二、Coverage Function。一個大集合涵蓋的小集合數量。

三、Matroid Rank Function。

Submodular Function Minimization

有空再來整理。