二部グラフ

定義

• グラフ $G = (V,E)$ が二部グラフ (bipartite graph) であるとは、$V$ の分割 $V=A\cup B$, $A\cap B=\emptyset$ が存在して、$A$ の点どうし、もしくは $B$ の点どうしをつなぐ辺が存在しないようにできることをいう。
• 正整数 $r$ について、$G$ が $r$-部グラフ ($r$-partite graph) であるとは、同様に $V$ の分割 $V=\bigcup_{i=1}^r A_i$ （$i\neq j$ のとき $A_i\cap A_j=\emptyset$）が存在して $1\leq i \leq r$ について頂点 $v_1, v_2 \in A_i$ を任意に選んだとき $v_1$ と $v_2$ のあいだに辺がないようにできることをいう。このとき $A_i$ を頂点のクラス (class)という。

完全 $r$-部グラフ

完全 $r$-部グラフ (complete $r$-partite graph) とは、異なるクラスの頂点をすべて辺で結んだグラフをいう。つまり、頂点のクラスが $A_i ~ (i=1, \ldots, r)$ である完全 $r$-部グラフとは、
$$V=\bigcup_{i=1}^r A_i, ~ E=\{(v, w): v\in A_i, w\in A_j ~ \exists i, j[1\leq i< j\leq r]\}$$
によって定まるグラフである。
$\abs{A_i}=n_i$ となる完全 $r$-部グラフを $K(n_1, \ldots, n_r)$ によりあらわす。完全二部グラフ $K(p, q)$ を $K_{p, q}$ と、完全 $r$-部グラフ $K(t, \ldots, t)$ を $K_r(t)$ とかくこともある。

完全 $r$-部グラフ $K(n_1, \ldots, n_r)$ は、グラフの和を用いて
$$K(n_1, \ldots, n_r)=E_{n_1}+E_{n_2}+\cdots +E_{n_r}$$
とあらわされる。とくに完全二部グラフ $K_{p, q}$ は
$$K_{p, q}=E_p+E_q=\overline{(K_p+K_q)}$$
とあらわされる。