5.9. BEST 定理: 主張

目次

続いて、これまでに示してきたものよりずっと意外性の高い結果を紹介する。

定義 4.7.3 を思い出そう: 多重有向グラフ \(D\) の各頂点 \(v\) が \(\deg^{-}v=\deg ^{+}v\) を満たすとき、かつそのときに限って \(D\) は平衡 (balanced) と呼ばれる。平衡性はオイラー回路の存在の必要条件であり、\(D\) が弱連結なら十分条件でもある (定理 4.7.2 (a) より)。

驚くべきことに、オイラー回路の個数を与える式が存在する:

定理 5.9.1

[BEST 定理 (BEST theorem)] 各頂点が \(1\) 以上の入次数を持つ平衡な多重有向グラフを \(D=\left( V,A,\psi\right) \) とする。\(D\) の弧 \(a\) を任意に取り、\(a\) の終点を \(r\) とする。\(r\) を根とする全域有向木の個数を \(\tau\left( D,r\right) \) と表し、最後の弧が \(a\) である \(D\) のオイラー回路の個数を \(\varepsilon \left( D,a\right) \) と表すとき、次の等式が成り立つ:

\[ \varepsilon\left( D,a\right) =\tau\left( D,r\right) \cdot\prod_{u\in V}\left( \deg^{-}u-1\right) ! \]

「BEST」は de Bruijn, van Aardenne–Ehrenfest, Smith, Tutte らの頭文字を表す。彼らは 20 世紀の中頃に BEST 定理を発見した1。なお、「最後の弧が \(a\) である \(D\) のオイラー回路の個数」は「回転して一致する回路を同一視するときの \(D\) が持つオイラー回路の個数」に等しいことを指摘しておく。実際、\(D\) の任意のオイラー回路は必ず弧 \(a\) をちょうど一度だけ含むので、そのオイラー回路を \(a\) で終わるようにする回転が唯一つ存在する。

これから BEST 定理を証明するために、その主張を「\(r\) を根とする有向木」ではなく「\(r\) を終根とする有向木」を使って書き換える。この書き換えは数学的には必要ない (全ての弧の向きが反転するだけで議論に本質的な変化はない) ものの、こうするとオイラー回路を順方向にたどりながら議論できるようになるので証明が直感的に分かりやすくなる。

  1. 正確には、Smith と Tutte による結果を一般化したものとして Ehrenfest と de Bruijn が 1951 年に発見した。 ↩︎

広告
このページの文章はテキストゆれないくんを使って校正されました。