オイラー路の数え上げへの帰着

はじめに、この問題をグラフの問題に帰着させることを考えます。
自然なグラフへの帰着方法として「頂点に \((0,0,0,0), \dots, (1,1,1,1)\) のラベルを張った \(16\) 頂点のグラフを作り辺を適切に張って、頂点 \((i,j,k,l)\) を通る回数が \(X_{i,j,k,l}\) 回であるようなパスを数え上げる」というものが考えられますが、この言い換え先はおそらく効率的に数えられず次数の総和の指数時間かかってしまうと思います。
そこで少し工夫して、以下の手順で \(8\) 頂点 \(N\) 辺のグラフ \(G\) を構築します。

• 頂点に \((0, 0, 0), \dots, (1, 1, 1)\) のラベルを張る。
• 全ての \((i,j,k,l)\) について、 \((i, j, k)\) から \((j, k, l)\) に向けて辺を \(X_{i,j,k,l}\) 本張る。

このとき、条件を満たす \(1\) つの数列は、グラフ上の全ての辺を経由する経路と一対一対応することが確認できます。つまり、与えられた問題を有向グラフのオイラー路を数え上げる問題に帰着することができました。

オイラー路の数え上げは始点・終点を全探索すればオイラー閉路の数え上げに帰着できるので、オイラー閉路の数え上げが高速に計算できればよいです。次章ではオイラー閉路の数え上げを頂点数に関する多項式時間で計算する方法を説明します。

有向グラフに含まれるオイラー閉路の数え上げ

\(G\) を多重辺・自己ループを認める有向グラフとします。\(G\) の全ての辺は区別できます。
\(G\) がオイラー閉路を持つ必要十分条件は「\(G\) が連結かつ全ての頂点の入次数と出次数が等しい」ことです。このようなグラフをオイラーグラフと呼びます。以下では \(G\) はオイラーグラフであるとします。このとき、\(G\) に関して次の定理が成り立ちます。

BEST 定理 (BEST theorem)

オイラーグラフ \(G\) に含まれるオイラー閉路の個数は次の式で表せる。

\[c(G, v) \cdot \prod_{w \in V} (\mathrm{outdeg}(w) - 1)!\]

ここで \(c(G, v)\) は頂点 \(v\) を根とする有向全域木(全ての辺が根の方を向いている全域木) の個数 (実は \(c(G,v)\) の値は \(v\) によらず一定なので \(v\) は任意にとって良い)、\(V\) は \(G\) の頂点集合、\(\mathrm{outdeg}(w)\) は頂点 \(w\) の出次数である。

(証明) \(v\) を始点とする辺 \(e\) を 1 つ選び、全てのオイラー閉路は \(e\) から順に辿るとみなして考えます。
オイラー閉路を 1 つ取ってきて \(C\) とします。\(C\) において頂点 \(w\) (\(w \neq v\)) を最後に出る時に使用する辺を \(e_w\) とすると、\(T = \lbrace e_w \vert w \neq v \rbrace\) は有向全域木になります。

• \(T\) が有向全域木にならないならば、\(T\) には回路 (同じ頂点を複数回通ってもよい閉路) が含まれることになります。一方、\(e_w\) の条件から、\(T\) に含まれる \(2\) 本の辺 \(e_1, e_2\) が \((e_1 の終点) = (e_2 の始点)\) となるとき、\(e_1\) を通った後に \(e_2\) が使用されたことがわかります。よって矛盾が発生します。

また、\(G\) の辺集合 \(E\) から \(e\) および \(e_w\) を全て取り除いた辺集合を \(E'\) として、\(P_i\) を「\(E'\) に含まれる辺のうち \(i\) を始点とするものを、オイラー閉路で辿る順に並べて出来る列」とします。定義より、\(C\) から \(T\) および \(P_1, P_2, \dots, P_{|V|}\) を一意に得ることが出来ます。

逆に、\(T\) および \(P_1, P_2, \dots, P_{|V|}\) を 1 つ自由に選んだとします。このとき、はじめに \(e\) を通った後に「今 \(i\) にいるとする。\(P_i\) に使われていない辺があれば、そのような辺のうち最も先頭にあるものを使用する。そうでない場合は \(T\) に含まれる辺を使用する」というルールによって辺を辿っていくことで、オイラー閉路 \(C\) を 1 つ得ることが出来ます。

• もしこの手順でオイラー閉路が作れないと仮定します。このとき、手順に従って辺を辿っていくとオイラー閉路をなす前にある頂点で出る辺が無くなりこれ以上進めなくなることになりますが、実はこの「ある頂点」は \(v\) であることが確認できます。 (各頂点の入次数と出次数が等しいため、 \(v\) 以外の頂点で出る辺が無くなることはあり得ないため) また、\(v\) を出入りする辺も全て使い切っていることが \(v\) の出次数と入次数が等しいことからわかります。このとき、辿ってできた回路に登場する辺を \(G\) から取り除くとグラフは 1 個以上の \(v\) を含まないオイラーグラフ + いくつかの孤立点に分割されるので、オイラーグラフを 1 つ取り \(G'\) とします。このとき、辺を選ぶ順番のルールにより、\(T\) のうち \(G'\) に含まれる頂点を始点とする辺は全て \(G'\) に含まれる必要があります。すると、\(G'\) に含まれる頂点から \(G'\) に含まれない頂点へ張られた辺は \(T\) に存在しないことになり、\(T\) は \(v\) を根とする有向全域木という仮定と矛盾します。

よって、\(C\) と \(T, P_1, P_2, \dots, P_{|V|}\) の間に全単射を構成できるため、\(C\) の個数は \(T, P_1, P_2, \dots, P_{|V|}\) の個数と一致します。よって示されました。(証明終わり)

この証明によって、オイラーグラフにおいて \(v\) を根とする有向全域木の個数 \(c(G, v)\) は \(v\) によらず一定であることも確認できています。
また、\(c(G, v)\) は、\(G\) の自己ループを取り除いた後に次の定理によって通常の全域木の数え上げと同様に行列式の計算に帰着できます。

有向行列木定理(Directed Matrix-tree Theorem)

\(G\) を自己ループを含まない有向グラフとする。有向ラプラシアン行列 \(L(G)\) を

\[L_{u,v} = \begin{cases} -(u\text{ から }v\text{ へ向かう辺の本数}) & \text{if }u \neq v \\ \mathrm{outdeg}(u) & \text{otherwise} \end{cases} \]

と定義する。このとき、

\[c(G, v) = \det L_v(G)\]

が成り立つ。ただし \(L_v(G)\) は \(L(G)\) から \(v\) 行目と \(v\) 列目を取り除いて出来る行列である。

(証明) 帰納的に証明します。 \(G\) の頂点数が \(2\) の場合は実際に有向ラプラシアン行列を作って行列式を計算すれば正しいことが確認できます。
\(G\) の頂点数が \(3\) 以上の場合を考えます。\(u \neq v\) である頂点 \(u\) 、および \(u\) を始点とする辺 \(e\) を \(1\) 本選びます。 \(u\) の出次数が \(1\) の場合は、\(G\) から辺 \(e\) を縮約したグラフを \(G'\) としたときに \(\det L_v(G) = \det L_v(G')\) となることが確認できます。(行列式を丁寧に変形すると示せます、詳細は略します)
\(u\) の出次数が \(2\) 以上の場合を考えます。\(G_1\) を \(G\) から \(e\) を取り除いたグラフ、\(G_2\) を \(G\) から \(u\) を始点とする辺を \(e\) 以外全て取り除いたグラフとします。

\[c(G, v) = c(G_1, v) + c(G_2, v) = \det L_v(G_1) + \det L_v(G_2)\]

ここで \(L_v(G_1)\) と \(L_v(G_2)\) を比較すると、\(u\) 行目以外は全て一致していて、\(L_v(G_1)\) と \(L_v(G_2)\) の \(u\) 行目の和は \(L_v(G)\) の \(u\) 行目と一致しています。よって

\[\det L_v(G_1) + \det L_v(G_2) = \det L_v(G)\]

が成り立ちます。よって、\(G\) より辺数の少ないグラフの行列木定理に帰着できるため、帰納法による証明が完了しました。(証明終わり)

以上の定理を利用すればオイラー閉路の数え上げを頂点数に関する多項式時間で計算することが出来ます。 よって、これを利用することで元の問題を解くことが出来ます。(元の問題では多重辺同士が区別できない設定ですが、多重辺を同一視する分を階乗で割れば問題ないです。)
計算量は自然な実装で (グラフの頂点数を \(B = 8\) として) \(\mathrm{O}(B^4 + N)\) 程度(行列式の計算 \(\mathrm{O}(B^3)\) が高々 \(B\) 回) となり十分高速です。