完全2部グラフ

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

定義 完全2部グラフ は2部グラフであり、任意の2つの頂点 と について 内の辺 が存在する。完全2部グラフのパーティションの大きさが と であるとき、これを と表記する。

例 任意の k について、 をスターと呼ぶ。木でもある完全2部グラフは、全てスターである。 グラフ を爪と呼ぶ。 グラフ を utility graph と呼ぶ。

class=skin-invert-image|thumb|650px|left|星グラフ S3, S4, S5, S6

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

関連項目 閉路グラフ 完全グラフ 空グラフ 隣接行列