5.12. 全域有向木に関する系

BEST 定理 (および BEST' 定理) を使って有向グラフが持つオイラー回路の個数を数える前に、全域有向木の個数に関する系を一つ証明しておく:

系 5.12.1

\(D=\left( V,A,\psi\right) \) を平衡な多重有向グラフとする。任意の頂点 \(r \in V\) に対して \(r\) を終根とする \(D\) の全域有向木の個数を \(\tau\left( D,r\right) \) とする。このとき \(\tau\left( D,r\right) \) は \(r\) に依存しない。

[証明] \(\left\vert V\right\vert \leq 1\) のとき示したい命題は自明なので、一般性を失うことなく \(\left\vert V\right\vert >1\) と仮定する。もし頂点 \(v \in V\) が \(\deg^{+}v = 0\) を満たすなら、\(D\) は平衡より \(\deg^{-}v = 0\) が成り立つ。このとき \(v\) 以外の任意の頂点から \(v\) への路が存在しないので、任意の頂点 \(r \in V\) を終根とする全域有向木は \(D\) に存在しない。よって一般性を失うことなく任意の頂点 \(v \in V\) で \(\deg^{+}v>0\) だと仮定する。言い換えれば、全ての頂点が \(1\) 以上の出次数を持つと仮定する。

\(D\) の頂点 \(r\), \(s\) を任意に取る。\(\tau\left( D,r\right) =\tau\left( D,s\right) \) を示せばよい。

\(r\) を始点とする弧を任意に取って \(a\) とする (\(\deg^{+}r>0\) より \(a\) は存在する)。\(s\) を始点とする弧を任意に取って \(b\) とする (\(\deg^{+}s>0\) より \(b\) は存在する)。

BEST' 定理 (定理 5.10.4) を適用すると、次の二つの等式が分かる:

\[ \begin{aligned} \varepsilon\left( D,a\right) & =\tau\left( D,r\right) \cdot\prod_{u\in V}\left( \deg^{+}u-1\right) ! \\ \varepsilon\left( D,b\right) & =\tau\left( D,s\right) \cdot\prod_{u\in V}\left( \deg^{+}u-1\right) ! \end{aligned} \]

一方、\(a\) で始まるオイラー回路の個数は \(b\) で始まるオイラー回路の個数と等しい (任意のオイラー回路は任意の弧から始まるように一意に回転できるため)。よって \(\varepsilon\left( D,a\right) =\varepsilon\left( D,b\right) \) が分かる。ここから次の等式が分かる:

\[ \begin{aligned} \tau\left( D,r\right) \cdot\prod_{u\in V}\left( \deg^{+}u-1\right) ! &=\varepsilon\left( D,a\right) \\ & = \varepsilon\left( D,b\right) =\tau\left( D,s\right) \cdot\prod_{u\in V}\left( \deg^{+}u-1\right) ! \end{aligned} \]

両辺を (\(0\) でない！) \(\prod\limits_{u\in V}\left( \deg^{+}u-1\right) !\) で割れば \(\tau\left( D,r\right) =\tau\left( D,s\right) \) を得る。以上で系 5.12.1 は証明された。□