独立システム

組合せ 数学において、独立性システム ⁠ ⁠ は、${\displaystyle S}$⁠ ⁠が有限集合であり、⁠ ⁠が⁠ ⁠のサブセット(独立集合または実行可能集合と呼ばれる)の集合である⁠ ⁠のペアであり、次の特性を備えています。 ${\displaystyle (V,{\mathcal {I}})}$${\displaystyle V}$${\displaystyle {\mathcal {I}}}$${\displaystyle V}$

1. 空集合は独立です。つまり、 です。(あるいは、 ⁠ ⁠の少なくとも 1 つの部分集合は独立です。つまり、 です。)${\displaystyle \emptyset \in {\mathcal {I}}}$${\displaystyle V}$${\displaystyle {\mathcal {I}}\neq \emptyset }$
2. 独立集合のすべての部分集合は独立です。つまり、各 に対して が成り立ちます。これは遺伝的性質、または下方閉性と呼ばれることもあります。${\displaystyle Y\subseteq X}$${\displaystyle X\in {\mathcal {I}}\Rightarrow Y\in {\mathcal {I}}}$

独立系の別名は抽象単体複体です。

• ⁠ ⁠が有限集合で⁠ ⁠ が⁠ ⁠のサブセットのコレクションであるペアは、ハイパーグラフとも呼ばれます。この用語を使用する場合、集合⁠ ⁠内の要素は頂点と呼ばれ、族⁠ ⁠内の要素はハイパーエッジと呼ばれます。したがって、独立系は簡単に下向きに閉じたハイパーグラフとして定義できます。${\displaystyle (V,{\mathcal {I}})}$${\displaystyle V}$${\displaystyle {\mathcal {I}}}$${\displaystyle V}$${\displaystyle V}$${\displaystyle {\mathcal {I}}}$
• 増加特性または独立集合交換特性と呼ばれる追加の特性を持つ独立系は、マトロイドを生成します。次の式は、項間の関係をまとめたものです。

  ハイパーグラフ⊃独立システム=抽象単体複合体⊃マトロイド。

• ボンディ、エイドリアン、マーティ、USR (2008)、グラフ理論、Graduate Texts in Mathematics、vol. 244、Springer、p. 195、ISBN 9781846289699。