偏ったグラフ

数学において、バイアスグラフとは、区別された円（単純閉路の辺集合）のリストを持つグラフであり、リスト内の 2 つの円がシータグラフに含まれている場合、シータグラフの 3 番目の円もリストに含まれます。バイアスグラフは、ゲイングラフ、特に符号付きグラフの組み合わせ論的本質を一般化したものです。

正式には、バイアスグラフΩ は ( G、B ) のペアであり、 B は円の線形クラスです。これは定義により、上記のシータグラフ特性を満たす円のクラスです。

すべての円がB内にある（そして半辺を含まない）サブグラフまたは辺集合はバランスが取れていると呼ばれます。たとえば、Bに属する円はバランスが取れており、 Bに属さない円は不均衡です。

バイアスグラフは、主にマトロイドのため興味深いものですが、多項式準群との関連でも興味深いものです。以下を参照してください。

バイアス グラフには、ハーフ エッジ(1 つのエンドポイント) とルーズ エッジ(エンドポイントなし) がある場合があります。2 つのエンドポイントを持つエッジには 2 種類あります。リンクには 2 つの異なるエンドポイントがあり、ループには 2 つの一致するエンドポイントがあります。

円の線形クラスは、マトロイド内の回路の線形サブクラスの特殊なケースです。

• すべての円がBに属し、半辺がない場合、Ω はバランスが取れています。バランスの取れたバイアスグラフは、（ほとんどの目的では）通常のグラフと本質的に同じです。
• Bが空の場合、Ω は対比バランスと呼ばれます。対比バイアスグラフは、双円マトロイドに関連しています。
• B が偶数の長さの円で構成されている場合、Ω は反平衡と呼ばれ、すべて負の符号付きグラフから得られる偏りのあるグラフです。
• 線型類B は加法性があり、つまり、反復対称差（結果が円の場合）に対して閉じており、それは B が符号付きグラフの正円の類である場合に限ります。
• Ω は、すべての辺が 2 倍になった長さn ≥ 3のサイクルである基底グラフを持つ場合があります。これを偏りのある 2 C _nと呼びます。このような偏りのあるグラフでは、どの二角形(長さ 2 の円) もバランスが取れておらず、スパイクや渦が発生します (以下のマトロイドを参照)。
• いくつかの種類のバイアスグラフはゲイングラフから得られるか、特殊な種類のゲイングラフの一般化です。後者には、グループ展開グラフを一般化するバイアス展開グラフが含まれます。

バイアス付きグラフ Ω = ( G , B ) のマイナーは、サブグラフを取得してエッジ セットを縮小する任意のシーケンスの結果です。バイアス付きグラフの場合、グラフと同様に、サブグラフ (グラフ全体の場合もあります) を取得してから、エッジ セット (空セットの場合もあります) を縮小するだけで十分です。

Ω のサブグラフは、基になるグラフGのサブグラフHで構成され、バランスの取れた円クラスはHにあるバランスの取れた円で構成されます。Ω − Sと表記されるエッジ セットSの削除は、 Sの頂点とエッジを除くすべての頂点とエッジを持つサブグラフです。

Ω の縮約は比較的複雑です。1 つのエッジeを縮約する場合、手順はエッジeの種類によって異なります。e がリンクの場合は、 G で縮約します。縮約G / eの円Cは、 CまたはGのバランスの取れた円のいずれかがバランスの取れた円である場合にバランスが取れています。eがバランスの取れたループまたはルーズ エッジの場合は、単に削除されます。アンバランスなループまたはハーフ エッジの場合は、そのループとその頂点vが削除されます。vを端点とする他の各エッジはその端点を失います。そのため、一方の端点がvであるリンクはもう一方の端点でハーフ エッジになり、vでのループまたはハーフ エッジはルーズ エッジになります。 ${\displaystyle C\cup e}$

任意の辺集合Sによる縮約 Ω/ Sにおいて、辺集合はE − Sである。( G = ( V , E )とする。) 頂点集合は、 Ω のサブグラフ ( V , S ) のバランスの取れた成分の頂点集合のクラスである。つまり、 ( V , S ) が頂点集合V ₁ , ... , V _kのバランスの取れた成分を持つ場合、 Ω/ S はk個の頂点V ₁ , ..., V _kを持つ。 Sにない Ω の辺e はΩ/ Sの辺になり、あるV _iに属するΩ のeの各端点v _iはΩ/ Sのeの端点 V i になる。_{したがって}、 ( V , S ) のバランスの取れた成分にないeの端点は消える。 ( V , S )のバランスの取れたコンポーネントに 1 つのエンドポイントのみを持つエッジは、ハーフエッジになります。異なるバランスの取れたコンポーネントに属する 2 つのエンドポイントを持つエッジはリンクになり、同じバランスの取れたコンポーネントに属する 2 つのエンドポイントを持つエッジはループになります。

バイアス付きグラフに関連付けられたマトロイドには 2 種類あり、どちらもグラフのサイクル マトロイドを一般化します (Zaslavsky、1991)。

バイアス グラフM (Ω) (Zaslavsky、1989) のフレーム マトロイド (バイアス マトロイドと呼ばれることもある) は、基底集合としてエッジ セット E を持ちます。各コンポーネントに円がまったく含まれていないか、または 1 つの円しか含まれていない場合 (つまりアンバランスである場合)、エッジ セットは独立です。(マトロイド理論では、ハーフ エッジはアンバランス ループのように動作し、ルーズ エッジはバランス ループのように動作します。) M (Ω) は抽象的な意味でのフレーム マトロイドであり、少なくとも 1 つの基底に対して、基底要素のペアによって生成される線の集合がマトロイド全体をカバーするマトロイドのサブマトロイドであることを意味します。逆に、すべての抽象的なフレーム マトロイドは、何らかのバイアス グラフのフレーム マトロイドです。

マトロイドの回路はフレーム回路またはバイアス回路と呼ばれます。4 種類あります。1 つはバランスの取れた円です。他の 2 種類は、2 つの円が互いに素であるか (接続パスは各円と 1 つの端を共有し、それ以外は両方の円と素である)、または 1 つの共通頂点のみを共有する (この場合、接続パスはその 1 つの頂点です) ような、接続する単純なパスを伴う不均衡な円のペアです。4 つ目の種類の回路は、すべての円が不均衡なシータ グラフです。

辺集合Sのランクはn − bです。ここで、nはGの頂点の数、b はSのバランスの取れた成分の数（孤立した頂点もバランスの取れた成分として数えます）です。

フレームマトロイドのマイナーはバイアスグラフのマイナーと一致します。つまり、M (Ω− S ) = M (Ω)− SおよびM (Ω/ S ) = M (Ω)/ Sです。

フレームマトロイドは、グループに関連付けられたダウリングジオメトリを一般化します (Dowling、1973)。バランスの取れた二角形を持たない偏りのある 2 C _n (上記の例を参照)のフレームマトロイドは、渦巻きと呼ばれます。これはマトロイド構造理論で重要です。

拡張リフトマトロイド L ₀ (Ω) は、基底集合として集合E _{0 を}持ちます。これは、Eと追加点 e _{0の和集合です。}リフトマトロイド L (Ω) は、 Eに制限された拡張リフトマトロイドです。追加点は、不均衡なループまたはハーフエッジとまったく同じように動作するため、リフトマトロイドのみを説明します。

エッジ セットに円がまったく含まれていないか、または 1 つの円しか含まれていない場合 (不均衡)、エッジ セットは独立しています。

回路とは、バランスの取れた円、互いに交わっていないか頂点が 1 つだけ共通している不均衡な円のペア、またはすべての円が不均衡なシータ グラフです。

辺集合Sの階数はn − c + εです。ここで、 c は孤立した頂点を数えたSの成分数であり、 ε はSがバランスが取れている場合は 0、バランスが取れていない場合は 1 です。

リフトマトロイドと拡張リフトマトロイドのマイナーは、バイアスグラフのマイナーと部分的に一致します。削除は一致します: L (Ω− S ) = L (Ω)− S。縮約はバランスの取れたエッジセットに対してのみ一致します: Sがバランスが取れている場合はM (Ω/ S ) = M (Ω)/ Sですが、バランスが取れていない場合は一致しません。S がバランスが取れていない場合、M (Ω/ S ) = M ( G )/ S = M ( G / S ) であり、グラフのM は通常のグラフィックマトロイドを表します。

バランスの取れた二角形を持たない2 C _nのリフトマトロイド(上記の例を参照) はスパイクと呼ばれます。スパイクはマトロイド構造理論において非常に重要です。

完全グラフK _nの群展開が群を符号化するのと同様に (ダウリング幾何学を参照)、長さn + 1の単純なサイクルを展開するその組み合わせ類似物はn元 (多元)準群を符号化します。偏りのあるグラフ (Zaslavsky, ta) によって多元準群に関する定理を証明することができます。

• TA Dowling (1973)、「有限群に基づく幾何学的格子のクラス」 Journal of Combinatorial Theory、シリーズ B、第 14 巻、pp. 61–86。
• Thomas Zaslavsky (1989)、「バイアスグラフ。I. バイアス、バランス、ゲイン」。Journal of Combinatorial Theory、シリーズ B、第 47 巻、pp. 32–52。
• Thomas Zaslavsky (1991)、「バイアスグラフ。II. 3つのマトロイド」。Journal of Combinatorial Theory、シリーズ B、第51巻、pp. 46–72。
• Thomas Zaslavsky (1999)。符号付きグラフとゲイングラフおよび関連領域の数学的書誌。1999 年版: Electronic Journal of Combinatorics、Dynamic Surveys in Combinatorics、#DS8、アーカイブ。最新版: Electronic Journal of Combinatorics、Dynamic Surveys in Combinatorics、#DS8。
• Thomas Zaslavsky (2012)、多項準群の結合性: 偏った展開の方法。 Aequationes Mathematicae、Vol. 83、1–66ページ。