完全2部グラフ

テンプレート:Infobox graph 完全2部グラフ（英: complete bipartite graph）は、グラフ理論において、2部グラフのうち特に第1の集合に属するそれぞれの頂点から第2の集合に属する全ての頂点に辺が伸びているものをいう。bicliqueとも。

定義

完全2部グラフ [math]G:=(V_1 + V_2, E)[/math] は2部グラフであり、任意の2つの頂点 [math]v_1 \in V_1[/math] と [math]v_2 \in V_2[/math] について [math]G[/math] 内の辺 [math]v_1 v_2[/math] が存在する。完全2部グラフのパーティションの大きさが [math]\left|V_1\right|=m[/math] と [math]\left|V_2\right|=n[/math] であるとき、これを [math]K_{m,n}[/math] と表記する。

例

• 任意の k について、[math]K_{1,k}[/math] をスターと呼ぶ。木でもある完全2部グラフは、全てスターである。
• グラフ [math]K_{1,3}[/math] を爪と呼ぶ。
• グラフ [math]K_{3,3}[/math] を utility graph と呼ぶ。

ファイル:Star graphs.svg

星グラフ S₃, S₄, S₅, S₆

• Complete bipartite graph K1,1.svg

  K_1,1

• Complete bipartite graph K2,1.svg

  K_2,1

• Complete bipartite graph K2,2.svg

  K_2,2

• Complete bipartite graph K3,1.svg

  K_3,1

• Complete bipartite graph K3,2.svg

  K_3,2

• Complete bipartite graph K3,3.svg

  K_3,3

• Star network 7.svg

  K_7,1

特性

• 2部グラフから、辺数 [math]m\cdot n[/math] が最大となる完全2部部分グラフ [math]K_{m,n}[/math] を求める問題は、NP完全問題である。
• 平面グラフは [math]K_{3,3}[/math] をマイナーとして含むことができない。外平面 (outerplanar) グラフは [math]K_{3,2}[/math] をマイナーとして含むことができない（これらは平面性や外平面性の十分条件ではないが、必要条件である）。
• 完全2部グラフ [math]K_{n,n}[/math] は[math](n,4)[/math]-cage である。
• 完全2部グラフ [math]K_{n,n}[/math] または [math]K_{n,n+1}[/math] は Turán graph である。
• 完全2部グラフ [math]K_{m,n}[/math] の頂点被覆数は [math]\min \lbrace m,n \rbrace[/math]、辺被覆数は [math]\max\lbrace m,n\rbrace[/math] である。
• 完全2部グラフ [math]K_{m,n}[/math] の最大独立集合の大きさは [math]\max\lbrace m,n\rbrace[/math] である。
• 完全2部グラフ [math]K_{m,n}[/math] の隣接行列の固有値は [math]\sqrt{nm}[/math]、[math]-\sqrt{nm}[/math]、0であり、重複度はそれぞれ 1、1、n+m-2 である。
• 完全2部グラフ [math]K_{m,n}[/math] のラプラシアン行列の固有値は n+m、n、m、0 であり、重複度はそれぞれ 1、m-1、n-1、1 である。
• 完全2部グラフ [math]K_{m,n}[/math] には m^n-1 n^m-1 の全域木がある。
• 完全2部グラフ [math]K_{m,n}[/math] には大きさ [math]\min\lbrace m,n\rbrace[/math] の最大マッチングがある。
• 完全2部グラフ [math]K_{n,n}[/math] にはラテン方格に対応した n色の辺彩色が存在する。
• 最後の2つは、k-正則2部グラフに結婚定理を適用することで得られる系である。

関連項目

• 閉路グラフ
• 完全グラフ
• 空グラフ
• 隣接行列