algorithm - 拟阵，独特的电路特性

Question

关于拟阵中电路的唯一性，请参考这篇笔记： 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 的最大独立集，所以 |S| = |X|

X 是独立的，因为它是通过取一个独立的集合 C1-f 并使其最大独立而创建的——因此仍然是独立的。f 不是 X 的元素，因为这会在其中重新创建 C1，我们知道这是依赖的。但是总共只有 |S|+1 个元素可以使用，所以如果 |X|=|S| X 不包含 f，它最多包含 e。