マトロイドの基礎

数学において、マトロイドの基底はマトロイドの最大の独立集合、つまり他のどの独立集合にも含まれない独立集合です。

例として、次の独立集合を持つ基底集合R ² (2 次元ユークリッド平面のベクトル) 上のマトロイドを考えます。

これには 2 つの基底があり、集合 {(0,1),(2,0)}、{(0,3),(2,0)} です。これらは包含に関して最大​​となる唯一の独立集合です。

この基底は、いくつかの特殊なマトロイドの種類において特殊な名前を持っています: ^[1]

• グラフィック マトロイドでは、独立集合がフォレストであり、基底はグラフの全域フォレストと呼ばれます。
• 横断マトロイドでは、独立集合が与えられた二部グラフ内のマッチングの終点となり、基底は横断と呼ばれます。
• 線形マトロイドでは、独立集合は与えられたベクトル空間内のベクトルの線形独立集合であり、基底は単にベクトル空間の基底と呼ばれます。したがって、マトロイドの基底の概念は、線型代数の基底の概念を一般化したものです。
• 一様マトロイドでは、独立集合はすべて濃度が最大でk (ある整数kに対して) である集合であり、基底はすべて濃度が正確にkである集合です。
• 分割マトロイドでは、要素はカテゴリに分割され、独立集合は各カテゴリ c から最大でk _c個の要素を含む集合であり、基底はカテゴリcから正確にk _{c 個の}要素を含む集合です。
• 自由マトロイドでは、基底集合Eのすべての部分集合は独立しており、唯一の基底はEです。

すべてのマトロイドは、任意の2つの異なる基底とに対して、次の性質を満たす：^{[2] [3]}${\displaystyle A}$${\displaystyle B}$

• 基底交換特性: の場合、 が基底となるような要素が存在する。${\displaystyle a\in A\setminus B}$${\displaystyle b\in B\setminus A}$${\displaystyle (A\setminus \{a\})\cup \{b\}}$
• 対称基底交換特性： ならば、 と が両方とも基底となるような元が存在する。Brualdi ^{[4] は}、これが実際には基底交換特性と同等であることを示した。${\displaystyle a\in A\setminus B}$${\displaystyle b\in B\setminus A}$${\displaystyle (A\setminus \{a\})\cup \{b\}}$${\displaystyle (B\setminus \{b\})\cup \{a\}}$
• 多重対称基底交換特性: の場合、 と が両方とも基底であるようなサブセットが存在します。Brylawski、Greene、および Woodall は、それが実際には基底交換特性と同等であることを (独立に) 示しました。${\displaystyle X\subseteq A\setminus B}$${\displaystyle Y\subseteq B\setminus A}$${\displaystyle (A\setminus X)\cup Y}$${\displaystyle (B\setminus Y)\cup X}$
• 全単射基底交換特性:からへの全単射が存在し、任意の に対して は基底となる。Brualdi [ ^{4] は}、これが基底交換特性と同値であることを示した。${\displaystyle f}$${\displaystyle A}$${\displaystyle B}$${\displaystyle a\in A\setminus B}$${\displaystyle (A\setminus \{a\})\cup \{f(a)\}}$
• 分割基底交換特性:をm個の部分に分割するたびに、をm個の部分に分割するが存在し、任意のに対しては基底となる。^[5]${\displaystyle (A_{1},A_{2},\ldots ,A_{m})}$${\displaystyle A}$${\displaystyle (B_{1},B_{2},\ldots ,B_{m})}$${\displaystyle B}$${\displaystyle i\in [m]}$${\displaystyle (A\setminus A_{i})\cup B_{i}}$

しかし、対称かつ全単射である基底交換特性は、すべてのマトロイドによって満たされるわけではなく、基底順序付け可能なマトロイドによってのみ満たされます。

一般に、対称基底交換特性では、要素は一意である必要はありません。正則マトロイドは一意の交換特性を持ち、これはあるに対して、対応するbが一意であることを意味します。^[6]${\displaystyle b\in B\setminus A}$ ${\displaystyle a\in A\setminus B}$

基底交換特性から、 のどの要素も他の要素の適切な部分集合になることはできないことがわかります。 ${\displaystyle {\mathcal {B}}}$

さらに、与えられたマトロイドのすべての基底は同じ基数を持ちます。線形マトロイドでは、すべての基数の基数はベクトル空間の 次元と呼ばれます。

すべてのマトロイドは次の性質を満たすと推測される：^[2] t ≥ 1 の任意の整数に対して、BとB' が同じ多重集合の和集合を持つt組の基底である場合、 BをB'に変換する対称交換のシーケンスが存在する。

マトロイドの基底はマトロイドを完全に特徴づける。集合が独立であるためには、それが基底のサブセットでなければならない。さらに、マトロイドを のペアとして定義することもできる。ここで は基底集合であり、は のサブセットの集合であり、これらは「基底」と呼ばれ、以下の特性を持つ。^{[7] [8]}${\displaystyle M}$${\displaystyle (E,{\mathcal {B}})}$${\displaystyle E}$${\displaystyle {\mathcal {B}}}$${\displaystyle E}$

(B1) 少なくとも 1 つの基底があり、空ではありません。${\displaystyle {\mathcal {B}}}$

(B2)と が異なる基底であり、である場合、 が基底となるような元が存在する(これは基底交換特性である)。${\displaystyle A}$${\displaystyle B}$${\displaystyle a\in A\setminus B}$${\displaystyle b\in B\setminus A}$${\displaystyle (A\setminus \{a\})\cup \{b\}}$

(B2)は、任意の2つの基底AとBが与えられた場合、単一の要素の交換シーケンスによってAをBに変換できることを意味します。特に、これはすべての基底が同じ濃度を持つ必要があることを意味します。

が有限マトロイドである場合 、集合を の 基底と呼び、その補集合が にある場合に限り直交マトロイドまたは双対マトロイドを定義できます。 がマトロイドであることは検証できます。定義から、 の双対がであることが直ちにわかります。^{[9] : 32  [10]}${\displaystyle (E,{\mathcal {B}})}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$${\displaystyle {\mathcal {B}}^{*}}$${\displaystyle {\mathcal {B}}}$${\displaystyle (E,{\mathcal {B}}^{*})}$${\displaystyle (E,{\mathcal {B}}^{*})}$${\displaystyle (E,{\mathcal {B}})}$

双対性を利用すると、特性(B2)を次のように置き換えることができることが証明できます。

(B2*)と が異なる基底であり、である場合、 が基底となるような元が存在する。${\displaystyle A}$${\displaystyle B}$${\displaystyle b\in B\setminus A}$${\displaystyle a\in A\setminus B}$${\displaystyle (A\setminus \{a\})\cup \{b\}}$

基底の双対概念は回路です。マトロイドの回路は最小の従属集合、つまり、その適切な部分集合がすべて独立している従属集合です。この用語は、グラフィック マトロイドの回路が対応するグラフ内のサイクルであるため、生まれました。

マトロイドはのペアと定義することができ、ここで は基底集合であり、は のサブセットの集合であり、「回路」と呼ばれ、次の特性を持つ: ^[8]${\displaystyle M}$${\displaystyle (E,{\mathcal {C}})}$${\displaystyle E}$${\displaystyle {\mathcal {C}}}$${\displaystyle E}$

(C1) 空集合は回路ではない。

(C2) 回路の適切な部分集合は回路ではない。

(C3) C ₁と C _{2 が}異なる回路であり、x がそれらの交差の要素である場合、回路が含まれます。${\displaystyle C_{1}\cup C_{2}\setminus \{x\}}$

回路のもう1つの特性は、ある集合が独立で、その集合が従属的である場合（つまり、要素を追加すると従属的になる）、回路 には一意の回路 が含まれ、回路 には が含まれるということです。この回路はについての基本回路と呼ばれます。これは、独立したベクトル集合にベクトルを追加すると従属的になる場合、 に等しいの要素の一意の線形結合が存在するという線型代数の事実に似ています。^[10]${\displaystyle J}$${\displaystyle J\cup \{x\}}$${\displaystyle x}$${\displaystyle J\cup \{x\}}$${\displaystyle C(x,J)}$${\displaystyle x}$${\displaystyle x}$${\displaystyle J}$${\displaystyle x}$${\displaystyle J}$${\displaystyle J}$${\displaystyle x}$

• マトロイド多面体- R ⁿ内の多面体（nはマトロイドの要素数）であり、その頂点はマトロイドの基底の指示ベクトルです。