📂グラフ理論

二部グラフ

定義 ¹

グラフ $G$ の頂点 $V(G)$ に対して パーティション $\left\{ A,B \right\}$ が存在し、すべての $xy \in E(G)$ に対して $x \in A, y \in B$ または $x \in B , y \in A$ であれば、$G$ を二部グラフと呼び、$G = G(A,B)$ のように表示することもある。

説明

二部グラフとは、名前の通り頂点が二つのグループに分けられ、同じグループ内の頂点同士は隣接しないグラフのことだ。例えば、下の図を見ると、オレンジ色の頂点同士は隣接しないし、青色の頂点同士も隣接しない。

見ての通り、異なるパーティションにあるからといって必ず隣接している必要はない。もし隣接していれば、それを完全二部グラフと呼ぶ。パーティションが三つの集合になった場合は、三部グラフと呼ぶ。自然に$n$個のパーティションに一般化は可能だが、通常、研究対象としては二部グラフで十分である場合が多い。

一方、二部グラフは次のようにサイクルに関連した定理が知られている。

定理

$G$ を連結グラフとする。$G$ が二部グラフであることと、$G$ のすべてのサイクルの長さが偶数であることは同値である。

証明

$(\Rightarrow)$

$G = G(A,B)$ が二部グラフだとしよう。$G$ のサイクルが$A$の頂点から始まった場合、$B$ に移ってから$A$ に戻るときは、二つのエッジを通らなければならない。従って、$B$ に何度行っても、閉じたパスを形成するには、結局偶数回のエッジを通るしかない。従って、$G$ のすべてのサイクルの長さは偶数でなければならない。

---

$(\Leftarrow)$

$G$ の頂点 $v \in V(G)$ 一つを固定しよう。始点が $v$ で終点が$w$ の最短パスのうち、長さが偶数の $w \in V(G)$ を集めた集合を $A \subset V(G)$ とし、そうでない頂点の集合を$B := V(G) \setminus A$ とする。$A$ に属する二つの頂点 $a_{1}$ と$a_{2}$ が隣接していれば、次のようなサイクル $$v \to \cdots \to a_{1} \to a_{2} \to \cdots \to v$$ の長さは、$A$ の定義により奇数となる。しかし、前提で$G$ のすべてのサイクルの長さが偶数であるため、これは矛盾であり、$A$ に属する頂点同士は隣接しない。これは$B$ に属する頂点にも同じことが言える。従って、$G$ は二部グラフ$G(A,B)$ でなければならない。

■