擬陣（matroid）理論背後的motivation是什麼？

01-28

曾經兩次在seminar中接觸過matroid這個概念，覺得這個東西綜合了組合和線性代數中很多很重要但又比較直觀的元素。但是因為概念的描述比較複雜，始終不能把握這個數學對象的內涵。有做組合方面的知友來介紹下定義matroid背後的motivation以及想用它來解決的一些問題么？

你「感覺」沒錯。Matroid 就是對「獨立」這個概念的抽象。「獨立」這個概念廣泛存在於圖論和線性代數中。我們試圖抽離出「獨立」這個概念的本質，使其不再依賴具體的對象（比如圖、矩陣、線性空間等），這就是提出 matroid 的動機。

我覺得提出這個概念並不是刻意的要去「解決」什麼問題。但是，既然我們做了抽象這個動作，就產生了許多問題：抽象後的 matroid，能否在我們已經熟知的數學中找到對應呢？能找到的話，如何對應？不一定能找到的話，多出的那些是什麼呢？這就是 matroid 的表示問題。

這個問題關係到 matroid 能覆蓋多少數學領域，用於描述多少數學概念。結果表明，matroid 這個概念還是很成功的。可表示的 matroid，成了不同數學領域間的橋樑，其後果就是不同領域間的許多結果就互通有無，解決了許多問題。不能表示的那些，本身就成了有趣的課題。

我個人比較熟悉的是 oriented matroid，雖然比 matroid 更強一些，但還是推薦 Bjorner, Las Vergnas 等著的 "Oriented Matroids" 一書，特別是前兩章 Orientation 充分展現了 matroid 在各領域間的橋樑作用。

我是學計算機的。我見過擬陣的應用。在演算法理論，擬陣作為工具用來討論那些問題可能適用貪心演算法，嘗試為適用於貪心演算法的問題（many, but not all）提煉出一個抽象的結構。這部分可能會給出擬陣應用很直觀的感受。詳見 Introduction to Algorithm關於貪心演算法的部分。

書本詳細信息：