たまに Matroid の問題が出るがわかっていないのでわかりたい。
参考資料たち

• maspy さん
• drken さん

• Matroid は集合に対する構造の一つ。

Def.

有限集合 M とその部分集合族 I について、(M, I) が matroid である ことは、以下を満たすことと同値。

1. \emptyset \subset M
2. Y \subset I について、\forall X \subset Y, X \subset I
3. X, Y \subset I (|X| > |Y|) について、\exists e \in X \backslash Y, Y \cup \{e\} \in I

また、I の部分集合を「独立」と呼び、 (M, I) について、1 と 2 を満たすならば「独立性システム」、2 と 3 を満たすならば「Greedoid」と呼ぶ。