二部グラフ

定義

• グラフ $G = (V,E)$ が二部グラフであるとは、$V$ の分割 $\{A,B\}$ が存在して($A \cap B = \emptyset$ かつ $A \cup B = V$)、$A$ の点どうし、もしくは $B$ の点どうしをつなぐ辺が存在しないようにできることをいう。

• 正整数 $r$ について、$G$ が $r$-部グラフであるとは、同様に $V$ の分割 $\{A_1,\ldots, A_r\}$ が存在して $1\leq i \leq r$ について頂点 $v_1, v_2 \in A_i$ を任意に選んだとき $v_1$ と $v_2$ のあいだに辺がないようにできることをいう。

information

情報源

• R. Diestel. "Graph Theory". Springer (2000).

関連項目

• グラフ