BEST定理

離散数学の一部であるグラフ理論において、BEST 定理は、有向グラフのオイラー閉路の数の積の公式を与える。この名前は、これを発見したNG de Bruijn、Tatyana Ehrenfest、Cedric Smith 、およびWT Tutteの名前の頭文字をとったものである。

G  = ( V ,  E ) を有向グラフとします。オイラー閉路は、各辺を 1 回だけ訪れる有向の閉じた経路です。1736 年にオイラーは、 Gが連結で、すべての頂点で入次数が出次数に等しい場合に限り、 Gにオイラー閉路があることを示しました。この場合、Gはオイラーと呼ばれます。頂点vの入次数はdeg( v ) で表します。

BEST定理は、連結オイラーグラフGにおけるオイラー回路の数ec( G )が次の式で与えられること を述べている。

${\displaystyle \operatorname {ec} (G)=t_{w}(G)\prod _{v\in V}{\bigl (}\deg(v)-1{\bigr )}!.}$

ここでt _w ( G ) は樹枝の数であり、樹枝とはG内の固定された頂点wのルートに向かう木です。数t _w (G)は、有向グラフの行列木定理のバージョンによって、行列式として計算できます。連結されたオイラーグラフGのすべての 2 つの頂点vとwに対してt _v ( G ) =  t _w ( G )が成り立つのは、オイラーグラフの特性です。

BEST定理は、有向グラフのオイラー閉路の個数が多項式時間で計算できることを示している。これは無向グラフでは#P完全問題である。 ^[1]これは完全グラフと完全二部グラフ のオイラー閉路の漸近列挙にも使用される。^{[2] [3]}

^{BEST定理は、van Aardenne-Ehrenfestとde Bruijn (1951) [4]} §6、定理6によるものです。彼らの証明は一対一であり、de Bruijnシーケンスを一般化しています。「証明に追加された注記」では、各頂点でdeg(v)=2となるグラフの式を証明するSmithとTutte (1941)による以前の結果を参照しています。

• オイラー、L. (1736)、「幾何学的問題に関する解決策」、Commentarii Academiae Scientiarum Petropolitanae (ラテン語)、8 : 128–140。
• Tutte, WT ; Smith, CAB (1941)、「次数 4 のネットワークにおける一筆書きパスについて」、American Mathematical Monthly、48 : 233–237、doi :10.2307/2302716、JSTOR  2302716。
• ファン・アーデンヌ・エーレンフェスト、T . ; de Bruijn、NG (1951)、「有向線形グラフの回路とツリー」、Simon Stevin、28 : 203–217。
• Tutte, WT (1984)、グラフ理論、マサチューセッツ州レディング：Addison-Wesley。
• スタンレー、リチャード P. (1999)、列挙的組合せ論、第 2 巻、ケンブリッジ大学出版局、ISBN 0-521-56069-1定理5.6.2
• アイグナー、マーティン（2007）、列挙のコース、数学の大学院テキスト、第238巻、シュプリンガー、ISBN 3-540-39032-4。