12.8 連結性

定義 12.8.1

グラフ \(G\) で二頂点が接続 (connected) とは、それらを結ぶ路が \(G\) に存在することを言う。慣習により、全ての頂点は長さ \(0\) の路で自身と接続とみなされる。任意の二頂点が接続なグラフを連結 (connected) なグラフと呼ぶ。

12.8.1 連結成分

連結性はグラフの優れた性質である。例えば、連結なグラフでは任意の二頂点間の移動や通信が可能となる。

しかし、連結でないグラフもある。例えば、頂点が都市を表し辺が高速道路による接続関係を表すグラフはアメリカの都市だけを考えるなら連結かもしれないが、オーストラリアの都市を考えに入れるなら明らかに連結でない。同じことはインターネットのような通信ネットワークに対しても言える ── コンピューターウイルスの拡散を防ぐために、一部の国家ネットワークはインターネットから完全に隔離されている。

連結でないグラフの例を図 \(\text{12.15}\) に示す。この図は一つのグラフを表しており、そのグラフは三つの連結な部分を持つ。この連結な部分は連結成分 (connected component) と呼ばれる:

定義 12.8.2

\(G\) をグラフ、\(v\) を \(G\) の頂点とする。\(v\) と接続な全ての頂点およびそれらに接続する全ての辺からなる \(G\) の部分グラフを \(G\) の連結成分 (connected component) と呼ぶ。

この定義から、グラフが連結なのは連結成分が一つしか存在しないとき、かつそのときに限ると分かる。連結なグラフと対照的なのが空グラフである: \(n\) 頂点の空グラフは \(n\) 個の連結成分を持ち、それぞれが \(1\) 個の頂点しか持たない。

12.8.2 奇数閉路と \(2\)-彩色可能性

先述したように、グラフの彩色数を求める問題は非常に難しい。ただ、この問題が非常に簡単になる特殊ケースが一つ存在する:

定理 12.8.3

グラフに関する次の性質は同値である:

奇数長の閉路を持つ。
\(2\)-彩色可能でない。
奇数長の閉歩道を持つ。

言い換えれば、この三つの性質のどれか一つを持つグラフは、必ず三つの性質を全て持つ。

これから次の論理的含意を示すことで定理 12.8.3 を証明する:

\[ \text{1.} \ \ \longrightarrow \ \ \text{2.} \ \ \longrightarrow \ \ \text{3.} \ \ \longrightarrow \ \ \text{1.} \]

この関係が成り立つとき任意の一つの性質が他の二つの性質を含意するので、三つの性質は同値である。

証明 [\(\text{1.} \to \text{2.}\)] 等式 \(\text{(12.4)}\) から従う。

[\(\text{2.} \to \text{3.}\)] 考えているグラフの各連結成分に対して個別に含意を証明すれば十分である。そこでグラフの連結成分を任意に選んで \(G\) として、さらに \(G\) の頂点 \(r\) を任意に選択する。\(G\) は連結より、任意の頂点 \(u \in V(G)\) に対して \(u\) から \(r\) への路 \(\textbf{w}_{u}\) が存在する。\(G\) の各頂点 \(u\) に次の規則で色を割り当てる:

\[ \text{\(u\) の色} = \begin{cases} \text{黒} & |\textbf{w}_{u}| \text{ が偶数のとき} \\ \text{白} & \text{それ以外のとき} \end{cases} \]

仮定より \(G\) は \(2\)-彩色可能でないので、この色の割り当ては正当な彩色でない。よって同じ色で塗られた隣接する二頂点 \(u\), \(v\) が存在する。このとき、\(u\) で始まって \(u\) で終わる次の閉歩道が存在する:

\[ \textbf{w}_{u} \;\widehat{\,\phantom{\text{\small l}}\,}\, \operatorname{reverse}(\textbf{w}_{v}) \;\widehat{\,\phantom{\text{\small l}}\,}\, \langle v\>\text{---}\>u \rangle \]

この長さは

\[ |\textbf{w}_{u}| + |\textbf{w}_{v}| + 1 \]

である。\(u\) と \(v\) が同じ色で塗られていることから \(|\textbf{w}_{u}|\) と \(|\textbf{w}_{v}|\) の偶奇は一致するので、この長さは奇数である。

[\(\text{3.} \to \text{1.}\)] グラフに奇数長の閉歩道が存在するとき、最短の奇数長の閉歩道の存在が整列原理から言える。この閉歩道を \(\textbf{w}\) として、\(\textbf{w}\) が閉路だと背理法で示す。\(\textbf{w}\) が閉路でないと仮定する。このとき、\(\textbf{w}\) に複数回現れる頂点が始点と終点以外に存在する。この頂点が始点と一致するかどうかを分けて考える。\(\textbf{w}\) の始点かつ終点を \(x\) とする。

\(x\) が \(\textbf{w}\) の始点と終点以外の個所で現れるなら、\(\textbf{w}\) は次の形をしている:

\[ \textbf{w} = \textbf{f} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,x\,}\ \textbf{r} \]

\(\textbf{f}\) は \(x\) で終わる長さが正の閉歩道、\(\textbf{r}\) は \(x\) で始まる長さが正の閉歩道である。\(\textbf{w}\) は奇数長より、

\[ |\textbf{w}| = |\textbf{f}| + |\textbf{r}| \]

は奇数である。よって \(\textbf{f}\) と \(\textbf{r}\) のちょうど一方のみが奇数長だと分かる。しかしこのとき、奇数長である方が \(\textbf{w}\) より短い奇数長の閉歩道となって仮定と矛盾する。
頂点 \(y \neq x\) が \(\textbf{w}\) で複数回現れるなら、\(\textbf{w}\) は次の形をしている:

\[ \textbf{w} = \textbf{f} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,y\,}\ \textbf{g} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,y\,}\ \textbf{r} \]

ここで \(\textbf{f}\) は \(x\) から \(y\) への歩道、\(\textbf{g}\) は長さが正の閉歩道、\(\textbf{r}\) は \(y\) から \(x\) への歩道である。\(\textbf{w}\) の定義より、\(\textbf{w}\) より短い閉歩道 \(\textbf{g}\) は奇数長でない。よって \(g\) は偶数長である。しかしこのとき、\(\textbf{f} \ \widehat{\vphantom{\phantom{\text{\small l}}}\,y\,}\ \textbf{r}\) が \(\textbf{w}\) より短い奇数長の閉歩道となって仮定と矛盾する。

以上で定理 12.8.3 の証明が完了した。 ■