完全二部グラフ

完全二部グラフ
m = 5、n = 3の完全二部グラフ
頂点	ん+ m
エッジ	分
半径	${\displaystyle \left\{{\begin{array}{ll}1&m=1\vee n=1\\2&{\text{otherwise}}\end{array}}\right.}$
直径	${\displaystyle \left\{{\begin{array}{ll}1&m=n=1\\2&{\text{otherwise}}\end{array}}\right.}$
胴回り	${\displaystyle \left\{{\begin{array}{ll}\infty &m=1\lor n=1\\4&{\text{otherwise}}\end{array}}\right.}$
自己同型	${\displaystyle \left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&{\text{otherwise}}\end{array}}\right.}$
彩度数	2
色指数	最大{ m , n }
スペクトラム	${\displaystyle \left\{0^{n+m-2},(\pm {\sqrt {nm}})^{1}\right\}}$
表記	K { m , n }
グラフとパラメータの表

数学のグラフ理論の分野において、完全二部グラフまたは二クリークは、最初の集合のすべての頂点が2番目の集合のすべての頂点に接続されている特別な種類の二部グラフです。 ^{[1] [2]}

グラフ理論自体は、レオンハルト・オイラーの1736年の『ケーニヒスベルクの七つの橋』に始まると一般的に考えられている。しかし、完全な二部グラフの図は、アタナシウス・キルヒャーが編集したラモン・リュイの著作の版に関連して、1669年にはすでに印刷されていた。^{[3] [4]リュイ自身も、3世紀前に同様の}完全グラフの図を描いていた。^[3]

完全二部グラフは、頂点を 2 つの部分集合V ₁とV ₂に分割できるグラフで、両方の端点が同じ部分集合内にない辺と、異なる部分集合の頂点を結ぶ可能性のあるすべての辺がグラフの一部であるグラフです。つまり、すべての 2 つの頂点 v 1 ∈ V 1 と v 2 ∈ V 2 に対して、 v 1 v 2 が E 内の辺であるような二部グラフ ( _V 1 、_V 2 、_E )です_。分割サイズ_| V 1 _| = mおよび| V ₂ | = _nの完全二部グラフはK m_、 nと表記され_ます。[ 1 _{] [ 2} ]同じ^表記の2 つのグラフはすべて同型です。

• 任意のk、K ₁に対して、 _kはスターと呼ばれます。^[2]木であるすべての完全な二部グラフはスターです。
  • グラフK _1,3はクローと呼ばれ、クローフリーグラフを定義するために使用されます。^[5]
• グラフK _3,3はユーティリティグラフと呼ばれます。この用法は、 3つのユーティリティをそれぞれ3つの建物に接続する必要がある標準的な数学パズルに由来しています。K _3,3は非平面であるため、交差なしで解くことは不可能です。^[6]
• 関係の有向グラフのサブグラフとして見つかった最大の二分枝は、概念と呼ばれます。これらのサブグラフの交わりと結合によって束が形成されると、関係は誘導概念束を持ちます。このタイプの関係の分析は、形式概念分析と呼ばれます。

• 二部グラフが与えられたとき、パラメータ iに対して完全な二部グラフK _{i , i}が含まれているかどうかをテストすることはNP完全問題である。^[8]
• 平面グラフはK _3,3をマイナーとして含むことができない。また、外平面グラフはK _3,2をマイナーとして含むことができない（これらは平面性と外平面性の十分条件ではないが、必要条件である）。逆に、すべての非平面グラフはK _3,3または完全グラフ K ₅のいずれかをマイナーとして含む。これはワーグナーの定理である。^[9]
• すべての完全な二部グラフ。Kn _、nはムーアグラフであり、( _n、4)ケージである。^[10]
• 完全二部グラフK _{n , n}とK _{n , n +1}は、頂点の数が同じすべての三角形のないグラフの中で、辺の数が最も多くなります。これがマンテルの定理です。マンテルの結果は、 k部グラフと、トゥランの定理のサブグラフとして大きなクリークを避けるグラフに一般化され、これら 2 つの完全二部グラフは、このより一般的な問題に対する極値グラフであるトゥラングラフの例です。^[11]
• 完全二部グラフK _{m , n}は、頂点被覆数がmin { m , n }で、辺被覆数がmax { m , n }です。
• 完全二部グラフK _{m , n}には、サイズmax { m , n } の最大独立集合が存在します。
• 完全二部グラフKm _{, nの}隣接行列は、固有値がそれぞれ√nm、−√nm、0であり、重複度はそれぞれ1、1、n + m − 2である。^[12]
• 完全二部グラフK _{m , n}のラプラシアン行列には、固有値n + m、n、m、 0 があり、重複度はそれぞれ 1、m − 1、n − 1、 1 です。
• 完全二部グラフKm _{, nに}はmn ^{− 1nm} − ^1本 の全域木が存在する。^[13]
• 完全二部グラフK _{m , n}には、サイズmin { m , n } の最大マッチングがあります。
• 完全二部グラフKn _{, nはラテン}方陣に対応する適切なn辺彩色を持つ。^[14]
• すべての完全な二部グラフはモジュラーグラフです。つまり、すべての頂点の三つ組には、各頂点のペア間の最短経路に属する中央値があります。^[15]

• 二部クリークフリーグラフ、完全な二部グラフを避けることで定義される疎グラフのクラス
• クラウングラフ、完全二部グラフから完全マッチングを取り除いて形成されるグラフ
• 完全多部グラフ、完全二部グラフを2つ以上の頂点集合に一般化したもの
• 二派閥攻撃