Matroid，唯一電路屬性

Question

對於matroid電路的唯一性，請參考此注意： http://math.mit.edu/~goemans/18433S13/matroid-notes.pdf。在定理4.1的證明中，最後2個句子「由於S也是獨立的，我們必須有| X | = | S |並且由於e∈C1-f，我們必須有X = S + e - f∈I但這意味着C2⊆S + e - f = X，這是C2以來的一個矛盾。「有人可以解釋爲什麼「| S | = | X |」爲什麼「e∈C1-f，我們必須有X = S + e-f∈I」。我不知道它是如何從幾個小時..

Answer 1

作者聲明沒有證明下面的第一頁公理的定義，最大獨立集都具有相同數量的成員。通過I2，如果你有兩個不同大小的最大獨立集合，你可以從大集合中選取一個元素並用它來增加較小的元素，這是一個矛盾。 S和X都是S + e so | S |的最大獨立集合= | X |

X是獨立的，因爲它是通過創建一個獨立集合C1-f並使其最大獨立 - 因此仍然是獨立的。 f不是X的元素，因爲它會重新創建它內部的C1，我們知道它是依賴的。但是如果| X | = | S |，只有總共有| S | +1元素可以玩X不包含f，它大部分包含e。