双円マトロイド

グラフGの双円マトロイド。各独立集合は擬似森を形成し、各連結成分は最大で1つの閉路を含む。与えられたマトロイドにおける唯一の従属集合は、グラフG全体を記述する集合であり、これはシータグラフを形成する。${\displaystyle \{1,2,3,4,5\}}$

数学の分野であるマトロイド理論において、グラフGの双円マトロイドは、点がGのエッジであり、独立集合がGの疑似フォレストのエッジ集合、つまり、各接続コンポーネントに最大で 1 つのサイクルが含まれるエッジ集合であるマトロイド B (G)です。

双円マトロイドはシモエス＝ペレイラ（1972）によって導入され、マシューズ（1977）らによってさらに研究が進められました。これは、バイアス付きグラフのフレームマトロイドの特殊なケースです。

回路

このマトロイドの回路、つまり最小従属集合は、双円グラフ(または自転車、ただしグラフ理論ではこの用語は他の意味を持ちます) です。これらは、回路ランクがちょうど 2 である連結グラフです。

双円グラフには 3 つの異なる種類があります。

• シータグラフは、同じ 2 つの頂点を結合するが、互いに交差しない 3 つのパスで構成されます。
• 8の字グラフ (またはタイトハンドカフ) は、共通の頂点を 1 つだけ持つ 2 つのサイクルで構成されます。
• ルーズ ハンドカフ (またはバーベル) は、2 つの分離したサイクルと最小限の接続パスで構成されます。

これらの定義はすべてマルチグラフに適用されます。つまり、複数のエッジ (同じエンドポイントを共有するエッジ) とループ (2 つのエンドポイントが同じ頂点であるエッジ) が許可されます。

フラット

グラフGの双円マトロイドの閉集合（フラット）は、 GのフォレストFとして記述することができ、 V ( G ) − V ( F )の誘導部分グラフにおいて、すべての連結成分が閉路を持つ。マトロイドのフラットは、集合包含によって部分的に順序付けされると幾何学的格子を形成するため、 Gのこれらのフォレストも幾何学的格子を形成する。この格子の半順序付けにおいて、F ₁ ≤ F ₂が成り立つ場合、

• F ₁の各構成要素木はF ₂のどの木にも含まれるか、またはどの木とも頂点独立であり、
• F ₂の各頂点はF ₁の頂点です。

最も興味深い例として、G  ^{o を}、すべての頂点にループを追加したGとします。すると、 B ( G  ^o )のフラットは、全域グラフか非全域グラフかを問わず、 Gのすべての森になります。したがって、グラフGのすべての森は、幾何格子、すなわちGの森格子を形成します(Zaslavsky 1982)。

横断マトロイドとして

双円マトロイドは、各集合要素が最大で2つの集合に属する集合族から生じる横断マトロイドとして特徴付けることができます。つまり、マトロイドの独立集合は、集合の一部またはすべてに対して、異なる代表の体系を形成するために使用できる要素の部分集合です。この記述では、要素はグラフの辺に対応し、頂点ごとに1つの集合があり、辺の集合はその頂点を端点とします。

未成年者

一般的な横断マトロイドとは異なり、双円マトロイドはマイナー閉クラスを形成します。つまり、双円マトロイドの任意のサブマトロイドまたは縮約も双円マトロイドであり、これはバイアス グラフ(Zaslavsky 1991) の観点での記述からわかります。基礎となるグラフの観点からのエッジの削除と縮約の説明は次のとおりです。マトロイドからエッジを削除するには、グラフからエッジを削除します。縮約のルールは、エッジの種類によって異なります。マトロイド内のリンク (ループではないもの) を縮約するには、通常の方法でグラフ内で縮約します。頂点vでループeを縮約するには、eとvを削除しますが、 v に接する他のエッジは削除しません。むしろ、vおよび別の頂点wに接する各エッジは、 wでループになります。vでのその他のグラフ ループはマトロイド ループになります。これをグラフで正しく記述するには、ハーフエッジとルーズ エッジが必要です。バイアス グラフ マイナーを参照してください。

特性多項式

双円マトロイドB ( G ^{o )の}特性多項式は、 Gの各サイズにおける全域森（ Gのすべての頂点を含む森）の数を簡潔に表す。式は以下の通りである。  

${\displaystyle p_{B(G)}(\lambda ):=\sum _{k=0}^{n}(-1)^{k}f_{k}(\lambda -1)^{n-k},}$

ここでf _{k は}G内のk辺全域森林の数に等しい。Zaslavsky (1982) を参照。

ベクトル表現

双円マトロイドは、他のすべての横断マトロイドと同様に、任意の無限体上のベクトルで表現できます。しかし、グラフマトロイドとは異なり、正則ではありません。つまり、任意の有限体上のベクトルで表現することはできません。双円マトロイドがベクトル表現できる体に関する問題は、グラフが乗法ゲインを持つ体を見つけるという、ほとんど未解決の問題につながります。Zaslavsky (2007) を参照してください。

参考文献

• マシューズ、ローレンス・R. (1977)、「双円マトロイド」、Quarterly Journal of Mathematics、第2シリーズ、28 (110): 213– 227、doi :10.1093/qmath/28.2.213、MR  0505702。
• Simões-Pereira、JMS (1972)、「マトロイド セルとしてのサブグラフについて」、Mathematische Zeitschrift、127 (4): 315–322、doi :10.1007/BF01111390、MR  0317973。
• ザスラフスキー、トーマス（1982）、「双円幾何学とグラフの森の格子」、Quarterly Journal of Mathematics、第2シリーズ、33（132）：493–511、doi：10.1093/qmath/33.4.493、MR  0679818。
• ザスラフスキー、トーマス（1991）、「バイアスグラフ。II. 3つのマトロイド」、組合せ理論ジャーナル、シリーズB、51（1）：46-72、doi：10.1016/0095-8956（91）90005-5、MR  1088626。
• Zaslavsky, Thomas (2007)、「バイアスグラフ VII. 対平衡と反電圧」、Journal of Combinatorial Theory、シリーズB、97 (6): 1019– 1040、doi : 10.1016/j.jctb.2007.03.001、MR  2354716。