グラフィックマトロイド

マトロイドの数学的理論において、グラフィックマトロイド（サイクルマトロイドまたはポリゴンマトロイドとも呼ばれる）は、与えられた有限の無向グラフ内の森を独立集合とするマトロイドである。グラフィックマトロイドの双対マトロイドは、コグラフィックマトロイドまたは結合マトロイドと呼ばれる。^{[1]グラフィックかつコグラフィックであるマトロイドは、}平面マトロイドと呼ばれることがある（ただし、平面の点構成を一般化するランク3のマトロイドと混同してはならない）。これらはまさに平面グラフから形成されるグラフィックマトロイドである。

マトロイドは、部分集合に関して閉じており、「交換特性」を満たす有限集合の族（マトロイドの「独立集合」と呼ばれる）として定義できます。集合と が両方とも独立しており、 がより大きい場合、が独立のままであるような要素が存在します。 が無向グラフであり、 が内のフォレストを形成するエッジの集合の族である場合、 は明らかに部分集合に関して閉じています（フォレストからエッジを削除すると、別のフォレストが残ります）。 また、交換特性も満たします。と が両方ともフォレストであり、 のエッジが より多い場合、 は連結成分が少なくなるため、鳩の巣原理によ​​り、の 2 つ以上の成分からの頂点を含むの成分が存在します。の 1 つの成分の頂点から別の成分の頂点までの 内の任意のパスに沿って、2 つの成分に端点を持つエッジが存在する必要があり、このエッジを に追加して、より多くのエッジを持つフォレストを作成できます。 したがって、 はマトロイドの独立集合を形成し、またはのグラフィック マトロイドと呼ばれます。より一般的には、マトロイドは、その要素がグラフのエッジであるかどうかに関係なく、グラフのグラフィックマトロイドと同型である場合にグラフィックと呼ばれます。 ^[2]${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x\in A\setminus B}$${\displaystyle B\cup \{x\}}$${\displaystyle G}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$${\displaystyle B}$${\displaystyle B}$${\displaystyle F}$${\displaystyle G}$${\displaystyle M(G)}$

グラフィックマトロイドの基底はの全スパニングフォレストであり、 の回路はの単純サイクルです。グラフの辺の集合における階数はであり、は の辺によって形成されるサブグラフの頂点の数であり、は同じサブグラフの接続された成分の数です。^{[2]グラフィックマトロイドのコランクは}回路階数またはサイクロマティック数として知られています。 ${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle X}$${\displaystyle G}$${\displaystyle r(X)=nc}$${\displaystyle n}$${\displaystyle X}$${\displaystyle c}$

内の辺の集合の閉包は 、 から独立していない辺（つまり、 内のパスによって互いに接続された端点を持つ辺）で構成される平面です。この平面は、 の頂点をによって形成されるサブグラフの連結成分に分割したものと同一視できます。 と同じ閉包を持つすべての辺の集合は、同じ頂点の分割を生じ、頂点の分割から復元できます。これは、端点が両方とも分割内の同じ集合に属する辺で構成されるためです。このマトロイドの平面の格子では、平面 に対応する分割が 平面 に対応する分割の改良である 場合は常に順序関係があります。 ${\displaystyle \operatorname {cl} (S)}$${\displaystyle S}$${\displaystyle M(G)}$${\displaystyle S}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \operatorname {cl} (S)}$${\displaystyle x\leq y}$${\displaystyle x}$${\displaystyle y}$

グラフィックマトロイドのこの側面では、完全グラフ のグラフィックマトロイドが特に重要です。これは、頂点集合のあらゆる可能な分割を、ある部分グラフの連結成分の集合として形成できるためです。したがって、のグラフィックマトロイドの平面の格子は、要素集合の分割の格子と自然に同型です。マトロイドの平面の格子はまさに幾何学的格子であるため、分割の格子も幾何学的であることを意味します。^[3]${\displaystyle K_{n}}$${\displaystyle K_{n}}$${\displaystyle n}$

グラフのグラフィックマトロイドは、任意の有向接続行列の列マトロイドとして定義できます。このような行列には、各頂点に対して 1 行、各辺に対して 1 列があります。辺の列には、一方の端点に対しては行に、もう一方の端点に対しては行に、その他の端点に対しては行に、その他の端点に対しては行にそれぞれ 1 つずつあります。どの端点にどの符号を付けるかについては任意に選択できます。この行列の列マトロイドには、列の線形独立なサブセットが独立集合として存在します。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle e}$${\displaystyle +1}$${\displaystyle -1}$${\displaystyle 0}$

エッジの集合にサイクルが含まれている場合、対応する列（サイクルの周囲にエッジを一貫して再配置する必要がある場合は を乗算）の合計は 0 になり、独立ではありません。逆に、エッジの集合がフォレストを形成する場合、このフォレストから繰り返し葉を削除することで、対応する列の集合が独立していることを帰納的に示せます。したがって、列行列は と同型です。 ${\displaystyle -1}$${\displaystyle M(G)}$

グラフィックマトロイドを表現するこの方法は、入射が定義されているフィールドに関係なく機能します。したがって、グラフィックマトロイドは、すべての可能なフィールドにわたって表現を持つマトロイドである通常のマトロイドのサブセットを形成します。^[2]

グラフィック マトロイドの平面の格子は、超平面配置の格子として実現することもできます。これは、実際には、超平面が対角線である組紐配置のサブセットです。つまり、 の頂点がである場合、が の辺であるときはいつでも、超平面を含めます。 ${\displaystyle H_{ij}=\{(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}\mid x_{i}=x_{j}\}}$${\displaystyle G}$${\displaystyle v_{1},\ldots ,v_{n},}$${\displaystyle H_{ij}}$${\displaystyle e=v_{i}v_{j}}$${\displaystyle G}$

マトロイドは、2つの小さなマトロイドの直和でない場合、連結されていると言われます。つまり、マトロイドのランク関数がこれらの別々のサブセットのランクの合計に等しくなるような2つの要素のサブセットが存在しない場合にのみ、連結されています。グラフィックマトロイドは、基礎となるグラフが連結かつ2頂点連結である場合にのみ連結されています。^[2]

マトロイドがグラフィックであるためには、そのマイナーに5 つの禁制マイナー (一様マトロイド 、ファノ平面またはその双対、完全グラフおよび完全二部グラフから定義されるとの双対) が含まれない必要があります。^{[2] [4] [5]}最初の 3 つは、正則マトロイドの禁制マイナーであり、^[6]と の双対は正則ですがグラフィックではありません。 ${\displaystyle U{}_{4}^{2}}$${\displaystyle M(K_{5})}$${\displaystyle M(K_{3,3})}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$${\displaystyle M(K_{5})}$${\displaystyle M(K_{3,3})}$

マトロイドがグラフィックである場合、その双対（「コグラフィックマトロイド」）には、これら5つの禁制マイナーの双対を含めることはできません。したがって、双対も正則でなければならず、2つのグラフィックマトロイドとをマイナーとして含めることはできません。^[2]${\displaystyle M(K_{5})}$${\displaystyle M(K_{3,3})}$

この特徴付けと、平面グラフをまたはグラフマイナー を持たないグラフとして特徴付けるワグナーの定理により、 が平面である場合に限り、グラフィックマトロイドは共グラフィックであることが分かります。これがホイットニーの平面性基準です。が平面である場合、 の双対はの双対グラフのグラフィックマトロイドです。 には複数の双対グラフがある場合がありますが、それらのグラフィックマトロイドはすべて同型です。^[2]${\displaystyle K_{5}}$${\displaystyle K_{3,3}}$ ${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle G}$

グラフィックマトロイドの最小重み基底は、最小全域木（または、基礎となるグラフが切断されている場合は、最小全域森）である。最小全域木を計算するアルゴリズムは集中的に研究されており、比較計算モデルで線形ランダム化期待時間で問題を解決する方法や、^[7]エッジの重みが小さな整数で、そのバイナリ表現でビット単位の演算が可能な計算モデルで線形時間で問題を解決する方法が知られている。^[8]決定論的アルゴリズムで証明された最も速い既知の時間境界は、わずかに超線形である。^[9]

与えられたマトロイドがグラフィックかどうかをテストするためのアルゴリズムを研究した著者は数人いる。^{[10] [11] [12]}たとえば、Tutte (1960) のアルゴリズムは、入力がバイナリマトロイドであることがわかっている場合にこの問題を解決します。Seymour (1981) は、独立性オラクル、つまり与えられたセットが独立であるかどうかを判断するサブルーチンを通じてのみマトロイドにアクセスできる任意のマトロイドに対してこの問題を解決します。

マトロイドのいくつかのクラスは、よく知られたグラフの族から、マトロイドに一般的に意味をなす言葉でこれらのグラフの特徴を述べることによって定義されてきた。これらには、すべての回路が偶数である二部マトロイドや、互いに素な回路に分割できるオイラーマトロイドが含まれる。グラフィックマトロイドが二部グラフである場合に限り、グラフィックマトロイドは二部グラフであり、グラフィックマトロイドがオイラーグラフである場合に限り、グラフィックマトロイドはオイラーグラフである。グラフィックマトロイド（およびより一般的にはバイナリマトロイド）内では、これら2つのクラスは双対である。つまり、グラフィックマトロイドが二部である場合に限り、その双対マトロイドがオイラーであり、グラフィックマトロイドがオイラーである場合に限り、その双対マトロイドが二部である。^[13]

グラフィックマトロイドは1次元の剛性マトロイドであり、剛体の梁が出会う頂点で自由に回転できる構造の自由度を記述するマトロイドです。1次元では、このような構造の自由度の数は、接続されたコンポーネントの数（頂点の数からマトロイドのランクを引いた数）に等しく、高次元では、n頂点を持つd次元構造の自由度の数はdnからマトロイドのランクを引いた数です。2次元の剛性マトロイドでは、ラマングラフがグラフィックマトロイドにおけるスパニングツリーの役割を果たしますが、2次元を超える剛性マトロイドの構造は十分に理解されていません。^[14]