2グラフ

数学において、2 グラフは有限の頂点集合 Xから選ばれた順序付けられていない 3 つの集合であり、Xのすべての順序付けられていない 4 つ組には、2 グラフの 3 つの組が偶数個含まれる。正則2 グラフは、すべての頂点のペアが 2 グラフの 3 つの組に同じ数だけ含まれるという性質を持つ。2 グラフは、等角線との関連から研究されており、正則 2 グラフの場合は強正則グラフ、また多くの正則 2 グラフが興味深い自己同型群を持つことから有限群としても研究されている。

2 グラフはグラフではないため、2 正則グラフなど、グラフ理論で2 グラフと呼ばれる他のオブジェクトと混同しないでください。

頂点集合 {1,...,6} 上の次の順序なし 3 つの集合は 2 次元グラフです。

123 124 135 146 156 236 245 256 345 346

この 2 グラフは、異なる頂点の各ペアがちょうど 2 つの 3 つ組に一緒に現れるため、通常の 2 グラフです。

単純グラフG = ( V , E ) が与えられたとき、誘導された部分グラフが奇数の辺を持つ頂点集合Vの三つ組の集合は、集合V上の2グラフを形成します。すべての2グラフはこのように表すことができます。^[1]この例は、単純グラフから2グラフを作成する標準的な方法と呼ばれています。

より複雑な例として、Tを辺集合Eを持つ木とします。Tのパスに含まれないEのすべての三つ組の集合は、集合E上の2グラフを形成します。^[2]

2 グラフはグラフのスイッチング クラスと同等であり、符号付き完全グラフの (符号付き) スイッチング クラスとも同等です。

(単純な) グラフ内の頂点の集合を切り替えるということは、一方が集合内にあり他方が集合内にない頂点の各ペアの隣接関係を逆にすることを意味します。したがって、隣接するペアが隣接しなくなり、隣接しないペアが隣接するように辺の集合が変更されます。両端の端点が両方とも集合内にある、または両方とも集合内にない辺は変更されません。グラフは、切り替えによって一方から他方を取得できる場合、切り替え等価です。切り替えによるグラフの同値クラスは、切り替えクラスと呼ばれます。切り替えは van Lint & Seidel (1966) によって導入され、Seidel によって開発されました。これは、符号付きグラフの切り替えと区別するためなどから、グラフ切り替えまたはSeidel 切り替えと呼ばれてきました。

上記の単純なグラフから 2 つのグラフを標準的に構築する場合、2 つのグラフがスイッチングに関して同等である場合、つまり同じスイッチング クラスにある場合にのみ、同じ 2 つのグラフが生成されます。

Γ を集合X上の2グラフとする。 Xの任意の要素xに対して、 { x , y , z } が Γ に含まれる場合かつその場合に限り、頂点集合Xが頂点yとzに隣接しているようなグラフを定義する。このグラフでは、x は孤立頂点となる。この構築は可逆的である。つまり、単純なグラフGが与えられ、新しい要素x をGの頂点集合に同じ辺集合を保持したまま追加し、上記の標準的な構築を適用する。この2グラフは、設計理論の用語ではGのxによる拡張と呼ばれる。^[3]通常の2グラフのグラフの与えられた切り替えクラスにおいて、 Γ _{x を、}頂点 x のない孤立頂点としてx を持つ唯一のグラフとする（これは常に存在するので、クラス内の任意のグラフを取り、xの開近傍を切り替えるだけである）。つまり、2グラフは Γ x_のxによる拡張である。上記の正則2次元グラフの最初の例では、Γx_はxの任意の選択に対して5次元閉路となる。^[4]

グラフGには、同じ頂点集合上の符号付き完全グラフ Σ が対応します。このグラフの辺は、 Gに含まれる場合は負に符号付き、含まれない場合は正に符号付きます。逆に、G は、すべての頂点とすべての負の辺で構成される Σ のサブグラフです。 G の 2 グラフは、Σ内の負の三角形 (負の辺が奇数個の三角形) をサポートする頂点の 3 つの集合として定義することもできます。2 つの符号付き完全グラフは、切り替え時に同等である場合に限り、同じ 2 グラフを生成します。

Gと Σ の切り替えは関連しています。両方の同じ頂点を切り替えると、グラフHとそれに対応する符号付き完全グラフが生成されます。

2 グラフの隣接行列は、対応する符号付き完全グラフの隣接行列です。したがって、対称で、対角線上ではゼロ、対角線から ±1 離れた位置にエントリがあります。Gが符号付き完全グラフ Σ に対応するグラフである場合、この行列は G の (0, −1, 1) 隣接行列またはザイデル隣接行列と呼ばれます。ザイデル行列は、主対角線上にエントリが 0 個、隣接する頂点に対しては -1 個、隣接しない頂点に対しては +1 個のエントリがあり ます。

グラフGとHが同じスイッチングクラスにある場合、GとHの2つのザイデル隣接行列の固有値の多重集合は、行列が類似しているため一致する。^[5]

集合V上の2次元グラフが正則であるためには、その隣接行列がちょうど2つの異なる固有値ρ ₁ > 0 > ρ ₂（ただしρ ₁ ρ ₂ = 1 - | V |）を持つ必要がある。^[6]

あらゆる 2 次元グラフは、ある次元ユークリッド空間内の各直線が同じ角度で交わる直線の集合に等しい。n 頂点の2次元グラフから構成される直線の集合は、次のようにして得られる。2 次元グラフのザイデル隣接行列Aの最小の固有値を -ρ とし、その重複度をn - dとする。すると、行列ρ I + Aは階数dの半正定値となり、ユークリッドd空間内のnベクトルの内積のグラム行列として表すことができる。これらのベクトルは同じノルム (つまり、 ) と相互内積 ±1 を持つため、それらが張る n 本の直線の任意のペアは、cos φ = 1 /ρ である同じ角度 φ で交わる。逆に、ユークリッド空間内の直交しない等角直線の任意の集合から 2 次元グラフを生成できる (構築方法については等角直線を参照)。 ^[7]${\displaystyle {\sqrt {\rho }}}$

上記の表記法では、最大濃度nはn ≤ d (ρ ² - 1)/(ρ ² - d )を満たし、2次元グラフが正則である場合にのみ境界が達成されます。

Xのすべての可能な 3 つ組と X の 3 つ組を含まない2グラフは、正規の 2 グラフであり、自明な2 グラフであると見なされます。

集合X上の非自明な2グラフについて、その2グラフが正則であるためには、X内の任意のxに対してグラフ Γ _xがk = 2μ （任意の頂点の次数が、隣接していない任意の頂点ペアの両方に隣接する頂点の数の2倍である）の強正則グラフとなる必要がある。この条件がX内の1つのxに対して成り立つ場合、 Xのすべての要素に対して成り立つ。^[8]

したがって、非自明な正則 ​​2 グラフには偶数個の点があることになります。

Gが正則グラフであり、その2グラフ拡張がn点を持つΓである場合、 Gがn = 2( k - r )またはn = 2( k - s )を満たす固有値k、r、sを持つ強正則グラフである場合に限り、 Γは正則2グラフである。^[9]

• Brouwer, AE、Cohen, AM、および Neumaier, A. (1989)、 距離正規グラフ。 シュプリンガー・フェルラーク、ベルリン。セクション 1.5、3.8、7.6C。
• Cameron, PJ; van Lint, JH (1991)、「デザイン、グラフ、コードとそのリンク」、ロンドン数学会学生テキスト22、ケンブリッジ大学出版局、ISBN 978-0-521-42385-4
• Colbourn, Charles J; Corneil, Derek G. (1980). 「グラフのスイッチング同値性の決定について」Disc. Appl. Math . 2 (3): 181–184. doi :10.1016/0166-218X(80)90038-4.
• コルボーン、チャールズ J.、ディニッツ、ジェフリー H. (2007)、コンビナトリアル デザイン ハンドブック (第 2 版)、ボカラトン: チャップマン & ホール/CRC、pp. 875–882、ISBN 1-58488-506-8
• Godsil, Chris : Royle, Gordon (2001)、 「代数グラフ理論」。Graduate Texts in Mathematics、第 207 巻。Springer-Verlag、ニューヨーク。第 11 章。
• Mallows, CL; Sloane, NJA (1975). 「2 グラフ、スイッチング クラス、およびオイラー グラフの数は等しい」。SIAM J. Appl. Math . 28 (4): 876–880. CiteSeerX  10.1.1.646.5464 . JSTOR  2100368.
• Seidel、JJ (1976)、2 つのグラフの調査。所蔵: Colloquio Internazionale sulle Teorie Combinatorie (議事録、ローマ、1973)、Vol. I、481–511ページ。アッティ デイ コンヴェーニ リンセイ、No. 17。ローマ、国立アカデミア ナツィオナーレ デイ リンセイ。 Seidel (1991)、146 ～ 176 ページに再版。
• Seidel, JJ (1991)、「幾何学と組合せ論：JJ Seidel の選集」、DG Corneil と R. Mathon 編。Academic Press、ボストン、1991 年。
• Taylor, DE (1977)、「Regular 2-graphs」、ロンドン数学会紀要(3)、第35巻、pp.257-274。
• van Lint, JH; Seidel, JJ (1966)、「楕円幾何学における正三角形の点集合」、Indagationes Mathematicae、Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69、28 : 335–348