如何贪婪地检查拟阵条件

Question

我正在以下 link.

阅读有关拟阵的信息

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}, {empty}}

非拟阵的例子

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

I2 = {{1,2 3}; {3, 4, 5} {1,2} {1,3} {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

编辑：您错误复制了原始拟阵 -> 上面的反例仅对您的 post 有效，对 link 无效！

link的反例： 以下需要有效：

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!

如何贪婪地检查拟阵条件

how to check matroid condition in greedy

algorithm

greedy