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

完全2部グラフ
Complete bipartite graph K3,2.svg
m=3 n =2の完全2部グラフ
頂点 n+m
mn
自己同型 2m!n! if m=n, その他 m!n!
テンプレートを表示

定義編集

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

編集

  • 任意の k について、 スターと呼ぶ。でもある完全2部グラフは、全てスターである。
  • グラフ  と呼ぶ。
  • グラフ  utility graph と呼ぶ。
 
星グラフ 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部グラフに結婚定理を適用することで得られる系である。

関連項目編集