完全2部グラフ

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

定義

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

例

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

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

• 
  K_1,1
• 
  K_2,1
• 
  K_2,2
• 
  K_3,1
• 
  K_3,2
• 
  K_3,3
• 
  K_7,1

特性

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

関連項目

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