完全2部グラフ

完全2部グラフ
	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_1$ と $v_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 と呼ぶ。

星グラフ S₃, S₄, S₅, S₆

K_1,1
K_2,1
K_2,2
K_3,1
K_3,2
K_3,3
K_7,1

特性[編集]

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}$ には m^n-1 n^m-1 のスパニング木がある。
完全2部グラフ $K_{m,n}$ には大きさ $\min\lbrace m,n\rbrace$ の最大マッチングがある。
完全2部グラフ $K_{n,n}$ にはラテン方格に対応した n色の辺彩色が存在する。
最後の2つは、k-正則2部グラフに結婚定理を適用することで得られる系である。