---
# System prepended metadata

title: Matroid
tags: [研究所, 資演]

---

:::info
### Definition
:::

![image](https://hackmd.io/_uploads/HJeZgwUvp.png)

:::info
#### heredity
:::

I: 收集 S 的 independent subsets
如果 B 是一個 S 的 independent subset → B ∈ I
假如有另一個 A，是 B 的subset (A 沒有其他條件限制)，A 也是 S 的independent subset


:::info
#### exchange property
:::

如果有兩個 independent subset A, B ⊆ S
W.L.O.G 假設 A 比 B 小（A 的元素個數比 B 少）
則必存在 x 在 B 中但不在 A 中，且將 A 聯集此 x，也會是一個 S 的independent subset

---

![image](https://hackmd.io/_uploads/S1kGZvUPp.png)

>Graphic Matroid 常用於 MST，為打字方便以下都以 M(G)表示
---
:::success
### Thm
:::
![image](https://hackmd.io/_uploads/S1m6SDIw6.png)


![image](https://hackmd.io/_uploads/ryyEjU8v6.png)
> Pf: 
> 假設 A 是一個 maximal independent subset，suppose ∃B: 另一個 maximal independent subset，因為matroid有exchange property，所以∃x ∈ B-A，代表我們可以再將 A 擴大成 A∪{x}
> 矛盾 A 是 maximal independent subset