如何检查贪心中的拟阵条件

Question

我在下面的链接上读到关于拟阵的文章。

https://www.cse.buffalo.edu/~hungngo/classes/2004/531/notes/matroids.pdf

读了几遍之后，我没有办法回答以下问题

拟阵M1 = ( S1；I1)的例子，其中S1= {1，2；3}和I1 = {{1,2}，{2，3}，{1}，{2}，{3}，{空}

非拟阵的例子

M2 = ( S2；I2)其中S2= {1，2，3，4，5，}和

I2 = {1,2}；{3，4，5} {1，2} {2,3} {3,4}，{4,5}，{1}，{2}，{3}，{4}，{5}，{空}

为什么M2不是一个马特罗？

我的问题是为什么M1是拟阵的而M2不是拟阵的？

Answer 1

这一定义告诉我们，应适用以下规定：

Hereditary: B ∈ I and A ⊆ B imply A ∈ I.

让我们看看I2：

• 取B为{3,4,5}
• 然后取A= {3,5} -> A⊆B有效
• 但以下内容无效，但必须是：{3,5}∈i

编辑：您错误地复制了原始的matroids ->，上面的反示例只对您的帖子有效，而不是对链接有效！

链接的反例：以下需要有效：

Exchange property: if A ∈ I and B ∈ I and |A| < |B|, then ∃x ∈ B − A so that A ∪ {x} ∈ I.

- take A = {5}, B = {1,2} -> A ∈ I, B ∈ I, |A| < |B|
- then: B-A = {1,2} -> BUT:
  A = {5} ∪ {1} NOT ∈ I
  A = {5} ∪ {2} NOT ∈ I
  -> implication invalid!