完全2部グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
完全2部グラフ
Complete bipartite graph K3,2.svg
m=3 n =2の完全2部グラフ
頂点 n+m
mn
自己同型 2m!n! if m=n, その他 m!n!
テンプレートを表示

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

定義[編集]

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

関連項目[編集]