導入
マトロイドの概念 (ホイットニーによって 1935 年に導入) は、当初、線形独立性の概念の本質を捉えることを目的としていました。したがって、線形代数 (すでに語彙レベルでは独立、基底、ランク) に自然にリンクされており、また本質的にグラフ理論(回路、サイクル)、アルゴリズム(大食い)、および幾何学(関連するさまざまな質問について) にもリンクされています。代表者へ）。
例: 表現可能なマトロイド
したがって、マトロイドの最も数学的に言えばペア(S, I )です。ここで、 S は特定のフィールド上の行列の列のインデックスのセットに対応し、 I は線形に対応するサブセット d のインデックスの集合に対応します。独立したベクトル。このようなマトロイドは表現可能であると言われています。表現できないマトロイドもあります。 2 要素ボディのみを使用して表現できるマトロイドは、バイナリと呼ばれます。 Tutte と Whitney はこれらのマトロイドの特徴を示しました。任意の物体上で表現できるマトロイドは、通常と呼ばれます。トゥッテはそれらを特徴づけました。
独立したものの多面体: ポリマトロイド
任意のマトロイドに対して、空間内の独立した多面体を|と関連付けることができます。 S |次元。これは、独立ベクトルの固有ベクトル ( {0,1}のS乗) の凸包です。エドモンズは、この多面体が陽性度と順位の線形不等式によって記述できることを示しました。マトロイドの独立したポリトープであるポリトープをポリマトロイドと呼びます。
定義
マトロイドを (公理的に) 定義するには、さまざまな方法がありますが、すべて同等です。 1 つ目は、独立集合が満たさなければならない公理を与えることから構成されます。また、基底の公理 (つまり、包含に対する最大の独立系) を定義したり、回路の公理 (グラフとの対応のため、包含に対する最小の従属系を回路と呼びます) を定義することもできます。 。最後に、他の定義は、ランク関数( Sの任意のサブセットUに、 Uに含まれる独立関数の最大カーディナリティを関連付けます)、または閉包演算子(Mac Lane の交換特性 – Steinitz を満たす) にも関係します。マトロイドのランク関数の重要な特性は、そのサブモジュール性です。
バイナリ マトロイドの場合、マトロイドのサイクル(つまり、回路の素結合) に基づいたさらに別の定義があります。これらは正確にペア(S, C )であり、 C は対称差に関して閉じたSの部分集合の集合です。
元の定義 (Whitney、1935)
S を空でない有限集合、 I をS の部分の空でない族とする。次の 2 つの公理を満たす場合、カップル(S, I )はマトロイドと呼ばれます。
- 遺伝: Iの任意の要素Xについて、 Xの任意の部分集合YもIに属します。
- 交換: XとYがIの 2 つの要素で、 Y がIの要素よりも多くの要素を持つ場合。
Iの要素は独立要素と呼ばれます。基底は最大独立です。すべての基底が同じ基数を持つことを示すことができます。
一例は均一マトロイドです。2 つの非ゼロ整数nとkが与えられると、 Sにn 個の任意の要素のセットとk未満のカーディナリティのサブセットを独立として取得することによってマトロイドを取得します。
グラフィックマトロイド
グラフィック マトロイドは、 S がグラフGのエッジと全単射であり、 G内でフォレストを形成する場合にSの部分集合が独立するようなマトロイドです (非巡回部分グラフ)。回路 (マトロイド理論の意味で) は、 Gの回路 (グラフ理論の意味で) に対応します。グラフィック マトロイドはバイナリです ( Gの入射行列を取得するだけです)。それらは規則的でもあります ( G を任意に配向し、出現行列を取得するだけです)。
グラフのカットのセットは、コグラフィックマトロイドと呼ばれるマトロイドのサイクルのセットを構成します。
アルゴリズムの定義
マトロイドはまさに遺伝の公理を満たすカップル(S, I )であり、 Sの各要素に重み(実数) を関連付ける関数について、貪欲なアルゴリズムにより最大重みに依存せずに決定することが可能になります。