完全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部グラフに結婚定理を適用することで得られる系である。

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

Category:グラフ理論のグラフ
Category:数学に関する記事