# 擬陣 Matroid

Matroid 是個很神奇的東西，在我們競程當中彷彿只有[題解](https://atcoder.jp/contests/abc399/editorial/12569)才能看到這個名詞。事實上，這個東西已經大到變成一個領域，要講完這東西至少要花半個學期。如果是組合學可能也要幾堂課的篇幅。寫這篇的目的是為了記錄我讀到的 matroid 的知識，順便看看能不能用我想用的脈絡寫完這篇。畢竟這是競程筆記，不常見的東西我就不放進來了以免讓人搞錯重點又多掉進一個坑

事實上，matroid 在競程上只有兩種使用情境，第一種是在那種超難的題目颯爽地使用 matroid intersection 這個工具。第二種是在一般的 greedy 題，明明 AC 了卻渾然不知自己用了 matroid 的觀念

Matroid 是個極為抽象的概念，如果沒有一些例子作為範例，很容易看不懂。建議在看這篇以前，先多看幾個貪心法、圖論的例子，並在大學的線性代數及格，否則這篇對你來說真的太早了

## Matroid 簡介

### 亂講
matroid 中文翻譯叫做「擬陣」，當初看這個單字以為是跟 centroid 一夥的，~~或是直接聯想到[密特羅德](https://en.wikipedia.org/wiki/Metroid)。||因為都很像阿有什麼辦法不聯想。||~~ Matroid 強調的是「獨立」與「非獨立」的關係，以及大集合與小集合之間的關係。實際讀下來，感覺像是用點集拓樸的方式一般化線性代數與圖論的一種物件，有種在讀抽象代數的既視感。需要一般化這些東西，自然是因為他們都具有一些共同的性質，以下就來介紹一下

### 定義
我們先不管這東西是什麼、能做什麼。二話不說，先來看看定義 :

給一個有限的 ground set $E$，與一些 $E$ 的子集合所形成的集合 $\mathcal{I}$ (即 family of subsets of $E$，我找不到比較好的翻譯)，我們稱所有 $X\in \mathcal{I}$ 是獨立的 (independent)。有限的 matroid $M=(E, \mathcal{I})$ 要符合以下性質 :

- 非空性 (Def1) : $\emptyset\in\mathcal{I}$
- 繼承性 (Def2) : 對每個 $A'\subseteq A$，若 $A\in \mathcal{I}$，則 $A'\in \mathcal{I}$
- 擴張性 (I) : 若兩個獨立集 $A,B$，$|A|<|B|$，則存在 $b\in B\setminus A$ 使得 $A\cup\{b\}\in \mathcal{I}$

我們把所有獨立集的集合寫作 $\mathcal I$，所有相依集的集合寫作$\mathcal D$。我們可以從定義變出以下性質 :
- (I1) : 若 $X\subseteq Y$ 且 $Y\in \mathcal I$，則 $X\in \mathcal I$ (從 (I) 可知)
- (D1) : 若 $X\subseteq Y$ 且 $X\in \mathcal D$，則 $Y\in \mathcal D$ (不然會與獨立的定義違背)

### 獨立集?

再次強調，matroid 的獨立集不是圖論當中的獨立集，他們都叫做 independent set，但意義完全不同
- matroid 的獨立集 : ground set $E$ 的子集合，也是在 $\mathcal{I}$ 當中的元素
- 圖論的獨立集 : 節點之間沒有一條邊直接相連所形成的集合

### 舉個例子
像是圖論當中的生成樹就是最好的例子。假設我們有以下的圖

<center>


</center>

這個 matroid 中，我們把
- $E$ : 邊的集合當作 ground set
- $\mathcal I$ : 定義「沒有環的子圖」為獨立集

那就會有以下幾種獨立集

<center>


</center>

總共有 $14$ 個獨立集，寫成符號就會是 $M=(E,\mathcal{I})$，其中

$$E=\{e_1, e_2, e_3, e_4\}$$

$$
\begin{split}
\mathcal{I}=\{
&\{e_2, e_3, e_4\},\{e_1, e_3, e_4\},\{e_1, e_2, e_3\}\\
&\{e_3,e_4\},\{e_2,e_4\},\{e_2,e_3\},\{e_1,e_3\},\{e_1,e_2\},\{e_3,e_4\}\\
&\{e_1\},\{e_2\},\{e_3\},\{e_4\},\emptyset\}
\end{split}
$$

從集合論的定義我們可以知道 $E$ 的 power set $2^E$ 有 $2^4=16$ 個，而我們上面列舉了其中 $14$ 種都是獨立集，因此剩下 $2$ 種就會是相依集 (dependent，不獨立)

$$
\mathcal D = 2^E\setminus\mathcal{I}=\{\{e_1,e_2,e_4\},\{e_1,e_2,e_3,e_4\}\}
$$

可以發現這些子集都有環，因此根據定義，他們的確不是獨立集

<center>


</center>

我們來驗證一下 matroid 的三個性質 (非空性、繼承性、擴張性) 是否能套用在這個例子上，是的話我們才能說這是一個 matroid

- (Def1) : 顯然，$\emptyset\in\mathcal{I}$
- (Def2) : 無環圖的子圖當然也是無環圖，根據我們列舉的獨立集也能看出來，因此符合
- (I) : 根據我們列舉的所有獨立集，都符合

## 基底與迴路 Bases and Circuit
### 基底 Bases
極大的獨立集被稱作基底，我們把所有基底的集合寫作 $\mathcal{B}$，可以從這個定義知道以下性質 :
- 基底沒辦法再增加新的元素進去 (因為他是極大)
- (B1) : 若 $B_1,B_2\in \mathcal{B}$，且 $B_1\subseteq B_2$，則 $B_1=B_2$
- 若有兩個或以上的基底，則這些基底都大小皆相同 (否則就不是最大)
- 一個獨立集一定是某個基底的子集 (根據 (I) 可知)

### 迴路 Circuit
極小的相依集就是迴路，我們把所有迴路的集合寫作 $\mathcal{C}$，從定義可以得到以下性質 :
- 拿掉一個元素後，集合就會是獨立集 (因為他是極小)
- (C1) : 若 $C_1, C_2\in \mathcal C$ 且 $C_1\subseteq C_2$，則 $C_1=C_2$
- 迴路的每一個 proper subset 都會是獨立集 (根據定義)
- 不會有存在兩個迴路 $C_1, C_2$ 使得 $C_1\subset C_2$ (會與上一點矛盾)
- 所有的相依集都至少包含了一個迴路作為子集

### 舉上面那個例子
利用[上面那個例子](#舉個例子)來說一下。此 matroid 的基底為
$$\mathcal B=\{\{e_2, e_3, e_4\},\{e_1, e_3, e_4\},\{e_1, e_2, e_3\}\}$$

也可以發現迴路集 :

$$
\mathcal C=\{\{e_1, e_2, e_4\}\}
$$

但是 $\{e_1, e_2, e_3, e_4\}$ 卻不是迴路，因為若去除 $e_3$，集合仍是相依

## Rank 函數
rank 又稱秩，但是我覺得這個名詞可能用 rank 比較直觀一點
### 定義
對於基底 $X$，其 rank $r(X)$ 就是 $X$ 中所包含的最大獨立集的大小。用符號表示就是 :

$$
r(X)=\max\{|Y| : Y\subseteq X \text{ and }Y \in \mathcal I\}
$$

### 性質

根據定義會有以下性質 :
- (R1) : 若 $e\in E$ 且 $X\subseteq E$，則 $r(X)\le r(X\cup\{e\})\le r(X)+1$ (根據 (I))
- (R2) : 對於所有 $X\subseteq E$ 都存在 $Z\subseteq X$，使得 $|X|\ge r(X)=r(Z)=|Z|$
- 空集合 : $r(\emptyset) = 0$
- 單調性 : 若 $A \subseteq B$，則 $r(A) \le r(B)$
- \(R) : $r(A) + r(B) \ge r(A \cup B) + r(A \cap B)$

這些不知道怎麼舉例，反正就代入驗驗看吧!

### Vector Matroid
#### 簡介
向量 matroid (又稱作 linear matroid) 算是研究 matroid theory 的源頭之一。當初很多獨立、相依的想法應該就是從這裡來的。Matroid 把已經很抽象的向量空間再次抽象化變成向量擬陣，這就是為什麼我覺得應該要先讀過線性代數的原因

- Ground Set $S$ : 矩陣 $A$ 的向量集合 $\{v_1, v_2, \dots, v_n\}$
- 獨立集 $\mathcal I$ : 若一組列向量是線性獨立的，則它們就是獨立集

#### 比較

稍微對應一下向量空間 vs matroid 的名詞好了

| 線性代數名詞 | 擬陣名詞 | 線性代數意義 |
| --- | --- | --- |
| 線性獨立集 | 獨立集 | 向量之間不存在非平凡的線性組合等於零向量 |
| 基底 (極大線性獨立集) | 基底 | 能張開該向量空間的最大集合，數量等於矩陣的 rank |
| 極小線性相依集 | 迴路 | 一組向量本身相關，但去掉任何一個就變無關 |
| 維度 (Dimension) | Rank | 集合中最大線性獨立集的大小 |

#### 驗一下

可以來驗一下一開始定義的性質 (I)，看向量 matroid 是不是合理的 matroid。假設 $I_1$ 和 $I_2$ 是向量空間 $V$ 中的兩組線性獨立的向量集合

**考慮 Span**

- 令 $W_1 = \text{span}(I_1)$，則 $\dim(W_1) = |I_1|$
- 令 $W_2 = \text{span}(I_2)$，則 $\dim(W_2) = |I_2|$

**使用反證法**
假設 $|I_1| < |I_2|$ 且我們無法從 $I_2 \setminus I_1$ 中找到任何元素 $e$ 加入 $I_1$ 後仍保持獨立。這代表對於所有 $e \in I_2$，$e$ 都已經落在 $W_1$ 裡面了 (因為如果 $e \notin W_1$，則 $I_1 \cup \{e\}$ 必定線性獨立)

如果 $I_2$ 中的每一個向量都屬於 $W_1$，那麼整個 $I_2$ 所張開的空間 $W_2$ 必定也是 $W_1$ 的子空間，即 $W_2 \subseteq W_1$。根據線性代數性質，子空間的維度不能超過母空間的維度，因此 $|I_2|=\dim(W_2) \le \dim(W_1)=|I_1|$

但這與我們的已知條件 $|I_2| > |I_1|$（即 $\dim(W_2) > \dim(W_1)$）矛盾！因此，在 $I_2$ 中一定至少存在一個向量 $e$，它不在 $W_1$ 的張開範圍內。將這個 $e$ 加入 $I_1$，得到的集合 $I_1 \cup \{e\}$ 必定保持線性獨立

## 等價的性質
### 一些性質
從上面的 vector matroid 可以發現，似乎有許多性質都可以從性質 (I) 推出來，或甚至有可能等價!? 先講結論 : 對，沒錯，確實有很多性質是等價的。接下來列舉一些。我們通常要驗一個定義是不是 matroid 的時候，只要驗他們的其中一個性質是否符合就好

#### 這些是講過的
- (I) 擴張性 augmentation : 若兩個獨立集 $A,B$，$|A|<|B|$，則存在 $b\in B\setminus A$ 使得 $A\cup\{b\}\in \mathcal{I}$
- \(R) 子模性 submodularity : 若 $A,B\in E$，則 $r(A) + r(B) \ge r(A \cup B) + r(A \cap B)$

#### 這邊是沒講過的
- (U) 均勻性 uniformity : 對任意 $X\subseteq E$，$X$ 的極大獨立集 (基底) 都有相同大小
- (B) 基底交換性 base exchange : 若 $B_1, B_2\in \mathcal B$ 且 $e\in B_1\setminus B_2$，則存在 $f\in B_2\setminus B_1$ 使得 $(B_1\setminus\{e\})\cup\{f\}\in \mathcal B$
- (A) 弱吸收性 weak absorption : 若 $r(X)=r(X\cup \{e\})=r(X\cup \{f\})$，則 $r(X\cup \{e, f\})=r(X)$
- (A') 強吸收性 strong absorption : 對 $X, Y\subseteq E$，若 $r(X\cup\{e\})=r(X)$ 對於所有 $e\in Y$ 都成立，則 $r(X\cup Y)=r(X)$
- \(C) 弱消去性 weak elimination : 對兩個相異的迴路 $C_1, C_2\in \mathcal C$ 及 $e\in C_1\cap C_2$，$(C_1\cup C_2)\setminus\{e\}\in\mathcal C$
- (J) 導出迴路 induced circuit : 若 $I\in \mathcal I$，則 $I\cup \{e\}$ 最多包含一個迴路
- (G) 貪心法 greedy algorithm : 對 $E$ 上的任意非負權重函數，利用貪心法都可以求得一個權重最大的獨立集

### 證明
我手上有兩本書 (都有附在[參考資料](#參考資料)) 都有寫這些東西要怎麼證明，他們的證明步驟是

<center>

(U)$\Rightarrow$(B)$\Rightarrow$(I)$\Rightarrow$(A)$\Rightarrow$(A')$\Rightarrow$(U)$\Rightarrow$\(R)$\Rightarrow$\(C)$\Rightarrow$(J)$\Rightarrow$(G)$\Rightarrow$(I)

</center>

而[底下 CF 文章](#參考資料)從性質 (I) 開始講，比較好懂但沒寫證明。為了好理解 matroid，我是參考 CF 的文章，因此以下證明步驟會跟書上的不同，稍做一點調整，有些是我自己寫的。還有就是這邊只給框架，我懶得詳細的證

以下是我證明的步驟 :

<center>


</center>

為了更清楚每段證明要證什麼，有再重新說明。想看再點開來看吧!

#### 1. $(I) \implies (U)$

:::spoiler
**欲證** :
對於任何 $X \subseteq E$，$X$ 的所有極大獨立集大小相同
**證明** :
假設 $X$ 有兩個極大獨立集 $A, B$ 且 $|A| < |B|$。根據 (I)，存在 $b \in B \setminus A$ 使得 $A \cup \{b\} \in \mathcal{I}$。由於 $A, B \subseteq X$，則 $A \cup \{b\} \subseteq X$。這與 $A$ 在 $X$ 中的「極大性」矛盾。因此，必有 $|A| = |B|$
:::

#### 2. $(U) \implies (R)$
:::spoiler
**欲證** :
$r(A) + r(B) \ge r(A \cup B) + r(A \cap B)$
**證明** :
取 $X = A \cap B$ 的一個基底 $I_{A \cap B}$。根據 (U)，可將其擴展為 $A \cup B$ 的基底 $I_{A \cup B}$。令 $I_A = I_{A \cup B} \cap A$ 且 $I_B = I_{A \cup B} \cap B$。顯然 $I_A \in \mathcal{I}$ 且 $I_B \in \mathcal{I}$，故
$$r(A) \ge |I_A|\text{ 且 }r(B) \ge |I_B|$$

因為 $I_A \cup I_B = I_{A \cup B}$ 且 $I_A \cap I_B = I_{A \cap B}$。根據排容原理 :
$$|I_A| + |I_B| = |I_A \cup I_B| + |I_A \cap I_B| = r(A \cup B) + r(A \cap B)$$
因此 $$r(A) + r(B) \ge |I_A| + |I_B| = r(A \cup B) + r(A \cap B)$$
:::

#### 3. $(R) \implies (A')$
:::spoiler
**欲證** :
對 $X, Y\subseteq E$，若 $r(X\cup\{e\})=r(X)$ 對於所有 $e\in Y$ 都成立，則 $r(X\cup Y)=r(X)$
**證明** :
設 $Y = \{y_1, y_2, \dots, y_k\}$。利用性質 \(R) 遞迴 :
$$
\begin{split}
r(X \cup \{y_1, y_2\}) &\le r(X \cup \{y_1\}) + r(X \cup \{y_2\}) - r(X) \\
&= r(X) + r(X) - r(X) \\
&= r(X)
\end{split}
$$

根據單調性 (R2)，得 $r(X \cup \{y_1, y_2\}) = r(X)$。依此類推用數學歸納法，可得 $r(X \cup Y) = r(X)$ 得證
:::

#### 4. $(A') \implies (A)$
:::spoiler
**證明** :
此為 $(A')$ 在 $Y = \{e, f\}$ 時的特例，直接成立
:::

#### 5. $(A) \implies (A')$
:::spoiler
**欲證** :
對 $X, Y\subseteq E$，若 $r(X\cup\{e\})=r(X)$ 對於所有 $e\in Y$ 都成立，則 $r(X\cup Y)=r(X)$
**證明** :
可以對 $|Y\setminus X|$ 做數學歸納法
- 當 $|Y\setminus X|\le 1$ 時顯然成立
- 若 $|Y\setminus X|\ge 2$，取不同 $e,f\in Y\setminus X$，並令 $Y'=Y\setminus\{e,f\}$。由歸納法可知
$$
r(X)=r(X\cup Y')=r(X\cup Y'\cup\{e\})=r(X\cup Y'\cup\{f\})
$$
所以根據 (A) 可以得

$$
r(X\cup Y')=r(X\cup Y)=r(Y)
$$
:::

#### 6. $(A') \implies (U)$
:::spoiler
**欲證** :
對於任何 $X \subseteq E$，$X$ 的所有極大獨立集大小相同
**證明** :
如果 $Y$ 是 $X$ 的最大獨立子集，則對所有 $e\in X$，$r(Y\cup \{e\})=r(Y)$ 都成立。由強吸收性 (A') 可知 $r(X)=r(Y)=|Y|$，因此所有 $Y$ 大小皆相同
:::

#### 7. $(I) \iff (B)$
:::spoiler
**證明** :
- $(I) \implies (B)$ :
取 $I = B_1 \setminus \{e\}$，因 $|I| < |B_2|$，由 (I) 補入 $f \in B_2 \setminus I$ 使其成為基底 (極大獨立集)
- $(B) \implies (I)$ :
這需要利用基底交換性反向構造，這邊就只給個思路。若 $|A| < |B|$，將 $A, B\in \mathcal I$ 分別擴展為基底 $B_A, B_B$，多次套用 (B) 可證明必能從 $B_B$ 中找回元素填補 $A$ 的空位
:::

#### 8. $(U)\implies (B)$
:::spoiler
**欲證** :
若 $B_1, B_2\in \mathcal B$ 且 $e\in B_1\setminus B_2$，則存在 $f\in B_2\setminus B_1$ 使得 $(B_1\setminus\{e\})\cup\{f\}\in \mathcal B$
**證明** :
考慮 $X=(B_1\setminus\{e\})\cup B_2$。由於 $B_2$ 也是 $X$ 的基底，根據 (U)，必存在一個包含 $B_1\setminus\{e\}$ 的基底 $B_3$ 使得 $|B_3|=|B_2|$，而 $B_3$ 是由某個 $f\in X\setminus(B_1\setminus\{e\})$ 形成的
:::

#### 9. $(I) \implies (A)$
:::spoiler
**證明** :
令 $A$ 是 $X$ 的最大獨立集，$B$ 是 $X\cup\{e,f\}$ 的最大獨立集。若 $|A|<|B|$，則存在 $b\in B\setminus A$ 使得 $A\cup \{b\}\in \mathcal I$，所以 $b\in \{e,f\}$。但這與 $r(X)=r(X\cup\{e\})=r(X\cup\{f\})$ 矛盾，所以 $|A| = |B|$，也就是 $r(X)=r(X\cup\{e,f\})$
:::

#### 10. $(I) \implies (J)$
:::spoiler
**欲證** :
若 $I\in \mathcal I$，則 $I\cup \{e\}$ 最多包含一個迴路
**證明** :
假設 $I \cup \{e\}$ 有兩個迴路 $C_1, C_2$，則 $e \in C_1 \cap C_2$。取 $f \in C_1 \setminus C_2$。可以證明 $I \cup \{e\} \setminus \{f\}$ 仍然包含 $C_2$，但其大小與 $I$ 相同，這會導致基底交換性質的崩潰，矛盾
:::

#### 11. $(J)\implies (C)$
:::spoiler
**欲證** :
對兩個相異的迴路 $C_1, C_2\in \mathcal C$ 及 $e\in C_1\cap C_2$，$(C_1\cup C_2)\setminus\{e\}\in\mathcal C$
**證明** :
已知 $e \in C_1 \cap C_2$。令 $I \subseteq (C_1 \cup C_2) \setminus \{e\}$ 為極大獨立集。若 $(C_1 \cup C_2) \setminus \{e\}$ 不含迴路，則 $I = (C_1 \cup C_2) \setminus \{e\}$。
考慮 $I \cup \{e\} = C_1 \cup C_2$。根據 (J)，此集合應只有唯一迴路，但它包含相異的 $C_1, C_2$，矛盾。故 $(C_1 \cup C_2) \setminus \{e\}$ 必含迴路
:::

#### 12. $(C)\implies (J)$
:::spoiler
**證明** :
假設 $I\cup\{e\}$ 裡面有兩相異迴路 $C, C'$，那麼兩個迴路都包含 $e$。根據 \(C)，$(C_1 \cup C_2) \setminus \{e\}$ 包含一個迴路，但這與 $(C_1 \cup C_2) \setminus \{e\}\subseteq I$ 矛盾
:::

#### 13. $(A) \implies (G)$
:::spoiler
**證明** :
令 $G$ 為貪心法選出的獨立集 $\{g_1, g_2, \dots, g_k\}$ (權重遞減排序)，$O$ 為最優獨立集 $\{o_1, o_2, \dots, o_m\}$
- 假設 $G$ 不是最優，必存在第一個 $i$ 使得 $w(g_i) < w(o_i)$。考慮集合 $G_{i-1} = \{g_1, \dots, g_{i-1}\}$ 與 $O_i = \{o_1, \dots, o_i\}$
- 根據 (A) 的性質，若 $O_i$ 中所有元素都不能加入 $G_{i-1}$，則 $r(G_{i-1} \cup O_i) = r(G_{i-1}) = i-1$。但 $r(O_i) = i$，與單調性 $r(G_{i-1} \cup O_i) \ge r(O_i) = i$，產生矛盾
- 故存在 $o_j \in O_i$ 使得 $G_{i-1} \cup \{o_j\} \in \mathcal{I}$。由於 $w(o_j) \ge w(o_i) > w(g_i)$，這與貪心法在第 $i$ 步選取 $g_i$ 矛盾
:::

#### 14. $(G) \implies (I)$
:::spoiler
**證明** :
- 假設 (I) 不成立。存在 $A, B \in \mathcal{I}$ 且 $|B| = |A| + 1$，但 $\forall b \in B \setminus A, A \cup \{b\} \notin \mathcal{I}$
- 設定權重如下 : 對於 $e \in A$，令 $w(e) = 1 + \epsilon$。對於 $e \in B \setminus A$，令 $w(e) = 1$，其餘 $w(e) = 0$
- 貪心法會先選完 $A$ 中的所有元素 (總重 $(1+\epsilon)|A|$)，接著因為無法從 $B$ 中加入任何元素，它將無法達到權重和 $|B| = |A| + 1$ (只要 $\epsilon$ 夠小)
- 但 $B$ 本身是獨立集，權重更高，這與 (G) 矛盾

:::

#### 15. $(R)\implies (C)$
:::spoiler
**證明** :
由於 $C_1, C_2$ 是迴路，根據定義 :
$$r(C_1) = |C_1| - 1\text{ 且 }r(C_2) = |C_2| - 1$$

因為 $C_1$ 和 $C_2$ 是相異的迴路，所以 $C_1$ 不可能是 $C_2$ 的子集。根據迴路的極小定義，迴路的任何 proper subset 都是獨立的，因此 :
$$r(C_1 \cap C_2) = |C_1 \cap C_2|$$
套用 \(R) 的性質 :

$$
\begin{split}
r(C_1 \cup C_2) &\le r(C_1) + r(C_2) - r(C_1 \cap C_2)\\
&=(|C_1| - 1) + (|C_2| - 1) - |C_1 \cap C_2|\\
&=|C_1| + |C_2| - |C_1 \cap C_2| - 2\\
&=|C_1 \cup C_2| - 2
\end{split}
$$

因此可知 $(C_1\cup C_2)\setminus\{e\}$ 不獨立，所以 $(C_1\cup C_2)\setminus\{e\}$ 含有迴路

:::

## 常見的 Matroid
這邊來說幾個競程 or 資工會遇到的 matroid

### 環擬陣 Cycle Matroid / 圖擬陣 Graphic Matroid
這兩個名詞是相同的，只是在不同地方會寫不一樣而已。這種就是[前面](#舉個例子)的例子。對於一個圖 $G=(V, E)$，ground set 是邊集 $E$，獨立集是不含環的邊集合

### 線性擬陣 Linear Matroid
這也是[前面](#Vector-Matroid)有說過的東西。考慮一個向量空間 $V$ 的非空有限子集 $E$。定義他的獨立集就是線性代數中的線性獨立集。若 $C=\{v_1, v_2, \cdots, v_r\}$ 是一個迴路，則存在不為 $0$ 的純量 $a_1, a_2, \cdots, a_r$，使得 $\sum\limits_{i=1}^r a_iv_i=0$。設 $C$ 與 $C'$ 是兩相異迴路，且 $v\in C\cap C'$，則

$$
v=\sum_{v_i\in C\setminus\{v\}} b_iv_i=\sum_{v_j\in C'\setminus\{v\}} c_jv_j
$$

其中 $b_i$ 與 $c_j$ 都不為零。由於 $C$ 與 $C'$ 是兩相異迴路，所以存在不完全為零的 $d_k$ 使得

$$
\sum_{w_k\in (C\cup C')\setminus \{v\}} d_kw_k=0
$$

所以 $(C\cup C')\setminus \{v\}$ 是線性相依的，一定包含一個迴路。根據某本書的說法，擬陣 matroid 就是從「擬似矩陣」而來

### 橫斷擬陣 Transversal Matroid
假設 $A_1, A_2, \cdots, A_m$ 是 $m$ 個集合，聯集是 ground set。稱 $A_1, A_2, \cdots, A_m$ 的「相異代表集」是一個集合 $X$，它是從每個 $A_i$ 中各取出一個相異元素組成的。我們定義 $\mathcal I=\{X\subseteq E : X \text{ 是某一些 } A_i \text{ 的相異代表集}\}$

<center>


</center>

不難發現這也可以用一個二分圖匹配來描述。考慮一個二分圖有兩集合 $E$ 與 $E'=\{1,2,\cdots,m\}$，對於 $e\in E$ 與 $i\in E'$，把他們連邊若且為若 $e\in A_i$，那麼獨立集就是 $\mathcal I=\{X\subseteq E : X \text{ 是某個匹配 } M \text{ 在 }E\text{ 上的端點集}\}$

這顯然是個 matroid，因為如果 $X,Y\in \mathcal I$ 且 $|X|<|Y|$，設他們的匹配是 $M, M'$，則 $|M|<|M'|$。因為 $M$ 不是最大匹配，根據 [Berge 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#Berge-%E5%AE%9A%E7%90%86)，存在一個 $y\in Y\setminus X$ 形成一個交錯路徑形成新的匹配端點集為 $X\cup\{y\}$。這樣就符合性質 (I)，驗完了

這個 matroid 如果去討論 rank 函數的話，會討論出 [Hall 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#%E9%9C%8D%E7%88%BE%E5%8C%B9%E9%85%8D%E6%A2%9D%E4%BB%B6-Halls-Matching-Condition)，很神奇

### 均勻擬陣 Uniform Matroid
令集合 $E$ 有 $n$ 個元素，取 $k\le n$，並且 $\mathcal I=\{X\subseteq E : |X|\le k\}$，這顯然是個 matroid，所以就不驗了

### 分割擬陣 Partition Matroid / 染色擬陣 Colorful Matroid
假設 $E_1, E_2, \cdots, E_k$ 是集合 $E$ 的分割，定義 $\mathcal I=\{X\subseteq E : |X\cap E_i|\le 1,\,\forall E_i\}$

這顯然是 transversal matroid 的特例，所以是 matroid 沒錯。如果用「把一些物品染色」方式去詮釋，那也講得通

### 子集裡的擬陣 Matroid on a subset
如果你有一個大的擬陣 $M$ (ground set 為 $E$)，你可以隨便挑一個子集 $S \subseteq E$，並宣告 :「現在只玩 $S$ 裡面的元素」那這也會是一個 matroid，因為 :
- 性質保證 : 因為獨立集的定義具有「子集繼承性」，如果在全域 $E$ 中某個集合 $A \subseteq S$ 是獨立的，那麼在縮小後的 $S$ 中它依然是獨立的
- 規則不變 : 這點非常直觀

### 擬陣和 Direct Matroid Sum
假設擬有兩個 matroid $M_1, M_2$，他們比此的 ground set $X_1, X_2$ 不相交，那麼定義
$$M_1 \oplus M_2 = \langle X_1 \cup X_2, \{ I_1 \cup I_2 : I_1 \in \mathcal{I}_1, I_2 \in \mathcal{I}_2 \} \rangle$$

也是一個 matroid。這可以想成是一張圖有兩個連通塊 $G_1, G_2$，我們可以去討論他們到底有沒有環

### 其他擬陣
你可以自己去創造，只要能夠驗證符合那堆性質的其中一個就對了

## 擬陣相交 Matroid Intersection :banana:
這段話是擬陣論在演算法領域的重頭戲。它解釋了為什麼我們要費力將問題抽象化為擬陣，因為擬陣香蕉提供了一個統一且強大的框架。有時候會發現一個問題可能有兩個限制，這樣的事情數不勝數。在競程中，如果只有一個限制還很簡單，直接 greedy 就完事了，但是兩個的話通常就很難解

### 定義
給定兩個定義在同一個 ground set $X$ 上的擬陣 $M_1 = (X, \mathcal{I}_1 )$ 和 $M_2 = (X, \mathcal{I}_2 )$。目標是找到一個子集 $S \subseteq X$，滿足 :
- $S \in \mathcal{I}_1 \cap \mathcal{I}_2$ (在兩個擬陣中同時獨立)
- $|S|$ 最大

### 例子
給一些例子

#### 彩色生成樹 Colorful Spanning Tree
- $M_1$ (Graphic Matroid) : 選出的邊不能形成環
- $M_2$ (Colorful Matroid) : 每一種顏色的邊最多選一條

交集意義 : 找到一棵樹，且這棵樹是「彩色」的

#### 二分圖最大匹配 Bipartite Maximum Matching
二分圖最大匹配可以看作兩個分割擬陣 Partition Matroid 的交集 :
- $M_1$ : 確保左側的每個點最多連出一條邊
- $M_2$ : 確保右側的每個點最多連出一條邊

交集意義 : 同時滿足左右兩側點的「唯一性」，這就是匹配

### 3-Matroid Intersection
兩個 matroid 的交集可以在多項式時間內解決，但三個 (或以上) matroid 的交集是 NP-Hard。為什麼呢? 我們可以將 Hamiltonian path problem 看作是邊集滿足以下三個擬陣的交集 :
- 出度限制 (Out-degree $\le 1$) : 每個點最多連出一條邊 (分割擬陣)
- 入度限制 (In-degree $\le 1$)：每個點最多連入一條邊 (分割擬陣)
- 無環限制 (Graphic Matroid)：將有向圖看作無向圖，不能有環且必須連通

因為哈密頓路徑是 NP-Complete 問題，這反過來證明了我們無法在多項式時間內解決三個 matroid 的交集問題

### 備註
在大多數時候，matroid intersection 不會得到 matroid。因此我們會傾向用酷酷的演算法 (像是 max-flow) 來解掉這些問題

### 交換圖 Exchange Graph
假設我們有兩個定義在同一個 ground set $S$ 上的擬陣 $M_1 = (S, \mathcal{I}_1)$ 和 $M_2 = (S, \mathcal{I}_2)$。當我們有一個共同獨立集 $I \in \mathcal{I}_1 \cap \mathcal{I}_2$ 時，交換圖 $D_{M_1, M_2}(I)$ 是一個有向二分圖，其中 :
- 點 : 基礎集合 $S$ 中的所有元素
- 邊 :
- 從 $I$ 內部指向外部 ($y \to x$) :
若 $y \in I, x \notin I$，且 $I - \{y\} + \{x\} \in \mathcal{I}_1$，則連一條從 $y$ 到 $x$ 的邊。這代表在 $M_1$ 中，可以用 $x$ 替換 $y$
- 從外部指向 $I$ 內部 ($x \to y$) :
若 $y \in I, x \notin I$，且 $I - \{y\} + \{x\} \in \mathcal{I}_2$，則連一條從 $x$ 到 $y$ 的邊。這代表在 $M_2$ 中，可以用 $x$ 替換 $y$

如果在圖中找到一條從「可加入 $M_1$ 的元素」到「可加入 $M_2$ 的元素」的有向路徑，這條路徑就是 Augmenting Path。跟 Berge 定理有點像，Edmonds 說交換圖中不存在從 $X_1$ 到 $X_2$ 的有向路徑若且為若 $I$ 是目前最大的共同獨立集

### Edmonds-Lawler 定理
給兩個 matroid $M_1 = (E, \mathcal{I}_1)$ 和 $M_2 = (E, \mathcal{I}_2)$，其 rank 函數分別為 $r_1$ 和 $r_2$，則
$$\max_{I \in \mathcal{I}_1 \cap \mathcal{I}_2} |I| = \min_{S \subseteq E} \{ r_1(S) + r_2(E \setminus S) \}$$

- 左式 (最大化) : 我們想找一個最大的集合 $I$，它必須同時在 $M_1$ 和 $M_2$ 中都保持獨立 (就是 matroid intersection)
- 右式 (最小化) : 我們將 ground set $E$ 切成兩部分 $S$ 與 $E \setminus S$
- 在 $S$ 這邊，最多只能選出 $r_1(S)$ 個元素滿足 $M_1$ 的限制
- 在剩餘的 $E \setminus S$ 這邊，最多只能選出 $r_2(E \setminus S)$ 個元素滿足 $M_2$ 的限制

定理告訴我們，這個「瓶頸」限制了最大獨立集的大小。像是二分圖匹配中的，考慮二分圖 $G = (U \cup V, E)$ 的匹配 :
- $M_1$ : 限制每個 $U$ 側頂點只能連 $1$ 條邊 (Partition Matroid)
- $M_2$ : 限制每個 $V$ 側頂點只能連 $1$ 條邊 (Partition Matroid)

那麼根據 Edmonds-Lawler 定理就會得到

<center>

二分圖的最大匹配大小 $=$ 二分圖最小點覆蓋大小

</center>

熟悉的 [Kőnig's Theorem](https://hackmd.io/@ShanC/konig-theorem) 就出現了

## 競程實戰建議
### 怎麼用?
回到競程，講了那麼多東西，matroid 該怎麼在競程中使用呢? 其實秘密就藏在一堆[等價的性質](#等價的性質)，因為所有這些性質都等價於貪心法性質 (G)，當我們看到題目時可以驗驗看以下幾個 matroid 個 :
- (Def1) : 空集必須是獨立的，即 $\emptyset \in \mathcal{I}$。這在題中通常最是顯然的
- (Def2) : 如果一個方案合法，拿掉其中一個元素後，剩下的方案是否依然合法?
- (I) : 如果有一個比較小的合法方案，則永遠可以從一個比較大的合法方案中找一個元素加進去，而不會破壞合法性
- (B) : 在許多最佳解當中，是否能夠替換成其他元素而拿到最佳解?

### 注意
- (Def1) 與 (Def2) 是必要的性質，其他性質只要挑一個就好
- Greedy 分兩種「動態」與「靜態」，其中動態的 greedy 通常不會是 matroid，所以不能驗

### 舉例 : [Zerojudge a567. 死線排程](https://zerojudge.tw/ShowProblem?problemid=a567)

#### 轉化
將問題抽象化為 $(E, \mathcal{I})$ :
- ground set $E$ : 所有的作業集合 $\{1, 2, \dots, n\}$
- independent sets $\mathcal{I}$ : 一個作業集合 $A \subseteq E$ 屬於 $\mathcal{I}$，若且唯若存在一種排程，使得 $A$ 中的所有作業都能在各自的截止日期 $d_i$ 前完成

#### 驗證
- (Def2) : 如果一組作業可以準時完成，去掉其中任何一項，剩下的顯然也可以
- (I)：假設兩個可完成的作業集 $A, B$ 且 $|B| > |A|$。在單位時間作業的情況下，因為 $B$ 包含更多元素，必定存在某個時間點 $t$，使得 $B$ 中 deadline $\le t$ 的作業數量大於 $A$，從而保證能從 $B$ 中挑選出一個元素加入 $A$ 而不破壞可排程性

### 反例 : [Zerojudge b606. Add All](https://zerojudge.tw/ShowProblem?problemid=b606)
因為每次合併都會改變 ground set 的元素，所以無法形成 matroid。但這不代表他不能用 greedy 的策略解出來

## 後記
之前讀到 matroid 覺得很帥，想說來整理一下很多文獻中不同的說法。這篇整理到一半就開學不想整理了，放久就忘了。期中考後去 NYCU Theory Day 之後，又想起這篇還沒完成，剛好不知道為什麼燃起了鬥志就寫完了這篇

----

## 參考資料
- D.B.West - Introduction to Graph Theory 2/e
- 張鎮華、蔡牧村 - 演算法觀點的圖論 (修訂版)
(這本的脈絡跟 West 差不多，只是多增加了很多歷史細節)
- [List of common Matroids + Matroid Intersection problems](https://codeforces.com/blog/entry/117810)
- [[Tutorial] Matroid intersection in simple words](https://codeforces.com/blog/entry/69287)
- [Jack Edmonds (1970). "Submodular functions, matroids, and certain polyhedra". In: Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alberta, 1969), Gordon and Breach, New York, pp. 69–87.](https://scispace.com/pdf/submodular-functions-matroids-and-certain-polyhedra-53q1tge8w1.pdf)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2026/4/24