完全2部グラフ

提供: miniwiki
移動先:案内検索

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

定義

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

  • 任意の k について、[math]K_{1,k}[/math]スターと呼ぶ。でもある完全2部グラフは、全てスターである。
  • グラフ [math]K_{1,3}[/math]と呼ぶ。
  • グラフ [math]K_{3,3}[/math]utility graph と呼ぶ。
ファイル:Star graphs.svg
星グラフ S3, S4, S5, S6

特性

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

関連項目