5.1. 成分と閉路の性質

5.1.1バックトラックフリー歩道: 再考

木を説明する前に、一般的な多重グラフに関する事実をいくつか復習・学習する。まず、定理 2.10.7 の証明で登場したバックトラックフリー歩道を思い出してほしい:

この概念は次の性質を持つ:

[証明] 単純グラフに対する同様の命題 (命題 2.10.4) を以前に証明した。この命題も同様の議論で証明できる。 [単純グラフと多重グラフでは閉路の定義が少し異なるので、全く同じ議論が使えるわけではない。] □

[証明] 単純グラフに対する同様の命題 (定理 2.10.7 の証明における Claim 1) は以前に示した。この命題も同様の議論で証明できる。□

5.1.2成分の数え上げ

続いて、グラフの成分の個数に関する性質をいくつか証明する。ここでも仕事の大部分はこれまでに終わっているので、証明は簡単にできる。まず、グラフの成分の個数に名前を付ける:

例えば、多重グラフ \(G\) が \(\operatorname*{conn}G=1\) を満たすのは \(G\) が連結なとき、かつそのときに限る。また、\(\operatorname*{conn}G=0\) を満たすのは \(G\) が頂点を持たないとき、かつそのときに限る。

続いて定義 3.3.17 と定理 3.3.18 を思い出してほしい (後者は多重グラフに対する定理 2.12.2 であり、証明も同様だった)。定理 3.3.18 からは次の結果が得られる:

[証明] (a) は定理 3.3.18 (a) から、(b) は定理 3.3.18 (b) から分かる。(c) は (a) と (b) から従う。 □

[証明] \(\left\vert E\right\vert \) に関する数学的帰納法で示す。

ベースケース: \(\left\vert E\right\vert =0\) なら \(\operatorname*{conn}G=\left\vert V\right\vert \) である (\(\left\vert E\right\vert =0\) より \(G\) は辺を持たないので、路連結な二頂点は存在しない)。\(\left\vert E\right\vert =0\) なので \(\operatorname*{conn}G=\left\vert V\right\vert -\left\vert E\right\vert \) も成り立つ。これで系 5.1.6 はベースケースに対して証明された。

再帰ステップ: \(k \in \mathbb{N}\) として、系 5.1.6 が \(\left\vert E\right\vert =k\) のとき成り立つと (帰納法の仮定として) 仮定する。\(\left\vert E\right\vert =k+1\) の場合でも系 5.1.6 が成り立つと示す必要がある。

\(\left\vert E\right\vert =k+1\) を満たす多重グラフ \(G=\left( V,E,\varphi\right) \) を考える。\(\left\vert E\right\vert =k+1\geq1>0\) より \(G\) は辺を少なくとも一つ持つので、任意に \(e \in E\) を取る。多重グラフ \(G \setminus e\) の辺集合は \(E\setminus \left\{ e\right\} \) より、辺の個数は \(\left\vert E\setminus\left\{ e\right\} \right\vert =\left\vert E\right\vert -1=k\) である。よって帰納法の仮定より、次の不等式が成り立つ:

[多重グラフ \(G\setminus e\) の頂点集合は \(V\) であり、辺集合は \(E\setminus\left\{ e\right\} \) であるため。] 一方で系 5.1.5 (c) からは \(\operatorname*{conn}\left( G\setminus e\right) \leq\operatorname*{conn}G+1\) が分かるので、次の不等式を得る:

これで再帰ステップが完了したので、系 5.1.6 は証明された。□

[証明] 系 5.1.6 の証明を少しだけ変えれば示せる: \(G\) が閉路を持たないので、\(G\) の任意の辺 \(e\) に対して \(e\) を含む閉路は存在しないと分かる。そのため系 5.1.5 の (c) ではなく (b) を適用できる。また、帰納法の仮定が利用できることは \(G\) が閉路を持たないとき \(G \setminus e\) も閉路を持たない事実から分かる。系 5.1.5 (b) を使うと証明の最後にある式変形の \(\leq\) が \(=\) に置き換わり、結果は \(\operatorname*{conn}G=\left\vert V\right\vert -\left\vert E\right\vert \) となる。□

[証明] \(G\) は少なくとも一つの閉路を持つので、閉路に含まれる辺 \(e \in E\) を取れる。このとき系 5.1.5 (a) より \(\operatorname*{conn}\left( G\setminus e\right) =\operatorname*{conn}G\) が分かる。一方で系 5.1.6 を \(G \setminus e\) と \(E\setminus\left\{ e\right\} \) に適用すると次の不等式が分かる:

\(\operatorname*{conn}\left( G\setminus e\right) =\operatorname*{conn}G\) だったから、\(\operatorname*{conn}G\geq\left\vert V\right\vert -\left\vert E\right\vert +1\) を得る。□

ここまでに証明してきた事実を一つの便利な定理としてまとめておく:

[証明] (a): 系 5.1.6 である。

(b) \(\Longleftarrow\): 系 5.1.7 である。

(b) \(\Longrightarrow\): \(\operatorname*{conn}G=\left\vert V\right\vert -\left\vert E\right\vert \) と仮定する。\(G\) が閉路を持つなら系 5.1.8 より \(\operatorname*{conn}G\geq\left\vert V\right\vert -\left\vert E\right\vert +1>\left\vert V\right\vert -\left\vert E\right\vert \) が成り立つものの、これは \(\operatorname*{conn}G=\left\vert V\right\vert -\left\vert E\right\vert \) と矛盾する。よって \(G\) は閉路を持たない。□