完全2部グラフ

完全2部グラフ
m=3 n =2の完全2部グラフ
頂点	n+m
辺	mn
自己同型	2m!n! if m=n, その他 m!n!

完全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 \lbrace m,n\rbrace$、辺被覆数は $\max \lbrace m,n\rbrace$ である。
• 完全2部グラフ $K_{m,n}$ の最大独立集合の大きさは $\max \lbrace m,n\rbrace$ である。
• 完全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 \lbrace m,n\rbrace$ の最大マッチングがある。
• 完全2部グラフ $K_{n,n}$ にはラテン方格に対応した n色の辺彩色が存在する。
• 最後の2つは、k-正則2部グラフに結婚定理を適用することで得られる系である。

関連項目

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