5.10. 特定の頂点を終根とする有向木
特定の頂点を終根とする有向木の形式的な定義を示す:
\(D\) を多重有向グラフ、\(r\) を \(D\) の頂点とする。
-
\(D\) の各頂点 \(v\) に対して \(v\) から \(r\) の路が \(D\) に存在するとき、\(r\) を \(D\) の終根 (to-root) と呼ぶ。
-
\(r\) が \(D\) の終根で、台無向グラフ \(D^{\operatorname*{und}}\) が閉路を持たないとき、\(D\) は \(r\) を終根とする有向木 (arborescence rooted to \(r\)) と呼ばれる。
明らかに、定義 5.10.1 と定義 5.6.1 は弧の方向だけが異なる。言い換えれば、有向グラフの弧を反転させる (始点と終点を入れ替える) ことで始根は終根になり、\(r\) を根とする有向木は \(r\) を終根とする有向木となる (逆も成り立つ)。そのため、\(r\) を根とする有向木に関してこれまで証明してきた性質は、全ての弧を反転させることで \(r\) を終点とする有向木に関する性質に変換できる。
この事実をより厳密に議論したい読者に向けて、「弧の反転」の形式的な定義を示す:
\(D=\left( V,A,\psi\right) \) を多重有向グラフとする。このとき多重有向グラフ \(\left( V,A,\tau \circ\psi\right) \) を \(D^{\operatorname*{rev}}\) と表記する。ここで \(\tau\colon V\times V\rightarrow V\times V\) は組 \(\left( s,t\right) \) を \(\left( t,s\right) \) に移す写像を表す。つまり、\(D\) の弧 \(a\) が始点 \(s\) と終点 \(t\) を持つなら、\(a\) は \(D^{\operatorname*{rev}}\) の弧でもあり、\(D^{\operatorname*{rev}}\) で \(a\) は始点 \(t\) と終点 \(s\) を持つ。
多重有向グラフ \(D^{\operatorname*{rev}}\) は多重有向グラフ \(D\) の反転 (reversal) と呼ばれる。\(D\) に「弧の反転」を適用して得られる有向グラフが \(D\) の反転である。
「弧の反転」という概念があると、有向グラフの歩道も反転できるようになる: 多重有向グラフ \(D\) が頂点 \(s\) から頂点 \(t\) への歩道 \(\mathbf{w}\) を持つなら、\(\mathbf{w}\) を逆に読むことで得られる \(\mathbf{w}\) の反転 \(\operatorname{rev}\mathbf{w}\) は多重有向グラフ \(D^{\operatorname*{rev}}\) における \(t\) から \(s\) への歩道となる。同じことは「歩道」を「路」としても成り立つ。ここから次の命題が容易に分かる:
\(D\) を多重有向グラフ、\(r\) を \(D\) の頂点とする。このとき:
-
「\(r\) が \(D\) の始点」と「\(r\) が \(D^{\operatorname*{rev}}\) の終点」は同値である。
-
「\(D\) が \(r\) を根とする有向木」と「\(D^{\operatorname*{rev}}\) が \(r\) を終根とする有向木」は同値である。
定義を展開していけば容易に示せる。□
有向グラフ \(D\) の弧を反転させると、各頂点の出次数と入次数が入れ替わる。このため、有向グラフ \(D\) が平衡なら \(D^{\operatorname*{rev}}\) も平衡となる。よって BEST 定理 (定理 5.9.1) は次のように書き換えられる:
全ての頂点が \(1\) 以上の出次数を持つ平衡な多重有向グラフを \(D=\left( V,A,\psi\right) \) とする。\(D\) の弧 \(a\) を任意に取り、\(a\) の始点を \(r\) とする。\(r\) を終根とする全域有向木の個数を \(\tau\left( D,r\right) \) と表し、最初の弧が \(a\) である \(D\) のオイラー回路の個数を \(\varepsilon\left( D,a\right) \) と表すとき、次の等式が成り立つ:
これからの議論では定理 5.10.4 を証明し、その後「弧の反転」を適用することで 定理 5.9.1 を導く。
その最初の一歩として、有向木の同値性定理 (定理 5.6.5) を「\(r\) を終根とする有向木」に対するものに書き換える:
終根 \(r\) を持つ多重有向グラフを \(D=\left( V,A,\psi\right) \) とする。このとき、次の六つの命題は同値である:
-
命題 A'1: 多重有向グラフ \(D\) が \(r\) を終点とする有向木である。
-
命題 A'2: \(\left\vert A\right\vert =\left\vert V\right\vert -1\) が成り立つ。
-
命題 A'3: 多重有向グラフ \(D^{\operatorname*{und}}\) が木である。
-
命題 A'4: 各頂点 \(v \in V\) に対して、多重有向グラフ \(D\) に \(v\) から \(r\) への歩道が唯一つ存在する。
-
命題 A'5: \(D\) から任意の弧を除去すると、頂点 \(r\) が (弧を除去した後のグラフにおいて) 終根でなくなる。
-
命題 A'6: \(\deg^{+}r=0\) であり、全ての \(v\in V\setminus\left\{ r\right\} \) が \(\deg^{+}v=1\) を満たす。
\(D\) の全ての弧を反転させると、この定理は有向木の同値性定理 (定理 5.6.5) になる。□