出典: フリー百科事典『ウィキペディア(Wikipedia)』
完全2部グラフ(かんぜんにぶグラフ、英: complete bipartite graph)は、グラフ理論において、2部グラフのうち特に第1の集合に属するそれぞれの頂点から第2の集合に属する全ての頂点に辺が伸びているものをいう。bicliqueとも。
完全2部グラフ
は2部グラフであり、任意の2つの頂点
と
について
内の辺
が存在する。完全2部グラフのパーティションの大きさが
と
であるとき、これを
と表記する。
- 任意の k について、
をスターと呼ぶ。木でもある完全2部グラフは、全てスターである。
- グラフ
を爪と呼ぶ。
- グラフ
を utility graph と呼ぶ。
星グラフ S3, S4, S5, S6
-
K1,1
-
K2,1
-
K2,2
-
K3,1
-
K3,2
-
K3,3
-
K7,1
- 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部グラフに結婚定理を適用することで得られる系である。