完全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部グラフ G:=(V_1 + V_2, E) は2部グラフであり、任意の2つの頂点 v_1 \in V_1v_2 \in V_2 について G 内の辺 v_1 v_2 が存在する。完全2部グラフのパーティションの大きさが \left|V_1\right|=m\left|V_2\right|=n であるとき、これを K_{m,n} と表記する。

[編集]

  • 任意の k について、K_{1,k}と呼ぶ。でもある完全2部グラフは、全て星である。
  • グラフ K_{1,3}と呼ぶ。
  • グラフ K_{3,3}utility graph と呼ぶ。
星グラフ S3, S4, S5, S6

特性[編集]

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

関連項目[編集]