完全2部グラフのソースを表示

{{Infobox graph
 | name = 完全2部グラフ
 | image = [[File:Complete bipartite graph K3,2.svg|160px]]
 | image_caption = ''m''=3 ''n'' =2の完全2部グラフ
 | automorphisms    = 2''m''!''n''! if ''m''=''n'', その他 ''m''!''n''!
 | vertices = ''n''+''m''
 | edges = ''mn''
}}
'''完全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> を [[:en:Water, gas, and electricity|utility graph]] と呼ぶ。

[[ファイル:Star graphs.svg|class=skin-invert-image|thumb|650px|left|星グラフ ''S''<sub>3</sub>, ''S''<sub>4</sub>, ''S''<sub>5</sub>, ''S''<sub>6</sub>]]

<gallery class="skin-invert-image">
ファイル:Complete bipartite graph K1,1.svg|''K''<sub>1,1</sub>
ファイル:Complete bipartite graph K2,1.svg|''K''<sub>2,1</sub>
ファイル:Complete bipartite graph K2,2.svg|''K''<sub>2,2</sub>
ファイル:Complete bipartite graph K3,1.svg|''K''<sub>3,1</sub>
ファイル:Complete bipartite graph K3,2.svg|''K''<sub>3,2</sub>
ファイル:Complete bipartite graph K3,3.svg|''K''<sub>3,3</sub>
ファイル:Star network 7.svg|''K''<sub>7,1</sub>
</gallery>

== 特性 ==
* 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>-[[:en:cage (graph theory)|cage]] である。
* 完全2部グラフ <math>K_{n,n}</math> または <math>K_{n,n+1}</math> は [[:en:Turán graph|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> には m<sup>n-1</sup> n<sup>m-1</sup> の[[全域木]]がある。
* 完全2部グラフ <math>K_{m,n}</math> には大きさ <math>\min\lbrace m,n\rbrace</math> の[[マッチング (グラフ理論)|最大マッチング]]がある。
* 完全2部グラフ <math>K_{n,n}</math> には[[ラテン方格]]に対応した ''n''色の[[グラフ彩色|辺彩色]]が存在する。
* 最後の2つは、[[正則グラフ|''k''-正則]]2部グラフに[[結婚定理]]を適用することで得られる系である。

== 関連項目 ==
* [[閉路グラフ]]
* [[完全グラフ]]
* [[空グラフ]]
* [[隣接行列]]

{{DEFAULTSORT:かんせんにふくらふ}}

[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]