完全2部グラフ

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

定義

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

例

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

特性

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

関連項目

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