ゲイングラフ

ゲイングラフは、その辺がグループGの要素によって「可逆的」または「方向付け可能」にラベル付けされているグラフです。つまり、ある方向の辺eにラベルg (グループ要素) が付けられている場合、他の方向の辺 e にはラベルg  ⁻¹が付けられます。したがって、ラベル関数φは、辺eの 2 つの異なる方向、つまり方向によって、独立ではなく異なる定義がされるという特性があります。グループGはゲイン グループと呼ばれ、φはゲイン関数、値φ ( e ) はeのゲイン(指定された方向) です。ゲイン グラフは、ゲイン グループGが 2 つの要素のみを持つ、符号付きグラフの一般化です。Zaslavsky (1989、1991) を参照してください。

ゲインは、エッジの方向とは無関係な値を持つエッジの 重みと混同しないでください。

ゲイン グラフに興味を持つ理由としては、組み合わせ最適化におけるネットワーク フロー理論、幾何学、物理学との関連性が挙げられます。

• ゲインを持つネットワーク、または一般化ネットワークの数学は、ゲイン グラフのフレーム マトロイドと関連しています。
• R  ⁿにx _j = g x _iという形式の方程式で与えられる超平面がいくつかあるとします。超平面の幾何学は、次のゲイン グラフを使用して処理できます。頂点セットは {1,2,..., n } です。方程式x _j = gx _iの各超平面には、ゲインg ( iからjの方向)を持つエッジijがあります。これらの超平面は、ゲイン グラフのフレーム マトロイドを通じて処理されます (Zaslavsky 2003)。
• あるいは、x _j = x _i + gという形式の方程式で与えられる超平面があるとします。これらの超平面の幾何学は、方程式x _j = x _i + gの各超平面に対して、同じ頂点セットとゲインg ( iからjの方向)を持つエッジijを持つゲイン グラフを使用して処理できます。これらの超平面は、ゲイン グラフのリフト マトロイドを介して研究されます (Zaslavsky 2003)。
• ゲイン グループがセットQに作用するとします。各頂点にQの要素s _{i を}割り当てると、ゲイン グラフの状態が得られます。ゲインg ( iからjの方向)を持つ各エッジijについて、方程式s _j = s _i  gが満たされている場合、エッジは満たされています。それ以外の場合は、フラストレートしています。すべてのエッジが満たされている場合、状態は満たされています。物理学では、このような状態が存在する場合、これは基底状態 (最低エネルギーの状態) に対応します。物理学、特にスピン グラスの理論における重要な問題は、フラストレートしたエッジが最も少ない状態を決定することです。

トポロジカル グラフ理論で表面へのグラフ埋め込みを構築する手段として使用されるゲイン グラフは、「電圧グラフ」として知られています (Gross 1974、Gross と Tucker 1977)。「ゲイン グラフ」という用語は、バイアス グラフ理論やマトロイド理論などの他のコンテキストではより一般的です。グループ ラベル付きグラフという用語も使用されていますが、「グループ ラベル」は重みとして扱われる可能性があり、実際に扱われているため、あいまいです。

ゲイン グラフの理論の多くはバイアス グラフの理論の特殊なケースであるため (また、バイアス グラフの理論の多くはゲイン グラフの理論の一般化であるため)、詳しい情報や例についてはバイアス グラフに関する記事を参照してください。

• Jonathan L. Gross (1974)、「電圧グラフ」、 離散数学、第9巻、pp. 239-246。
• JL Gross と TW Tucker (1977)、「順列電圧割り当てによるすべてのグラフ被覆の生成」、 離散数学、第 18 巻、pp. 273–283。
• Thomas Zaslavsky (1989)、「バイアスグラフ。I. バイアス、バランス、ゲイン」。Journal of Combinatorial Theory、シリーズ B、第 47 巻、32 ～ 52 ページ。
• Thomas Zaslavsky (1991)、「バイアスグラフ。II. 3つのマトロイド」。Journal of Combinatorial Theory、シリーズ B、第51巻、46～72ページ。
• Thomas Zaslavsky (1999)。符号付きグラフとゲイングラフおよび関連領域の数学的参考文献。Electronic Journal of Combinatorics、Dynamic Surveys in Combinatorics、#DS8。
• Thomas Zaslavsky (2003)、「バイアスグラフIV: 幾何学的実現」、Journal of Combinatorial Theory、シリーズB、第89巻、第2号、pp. 231–297。