[0] 記法についての注意

• 入力のグラフ \(G\) の頂点集合、辺集合をそれぞれ \(V,E\) とします。\(E\) は多重集合であることに注意してください。

• \(G\) の部分グラフ \(H\) について、その頂点集合、辺集合をそれぞれ \(V(H), E(H)\) とします。

• グラフの辺の重みづけ \(w\) を、\(E\) から \(\lbrace 0,1,\dots,L\rbrace\) への写像とみなします。また、\(E\) の部分集合 \(F = \lbrace e_{i_1},\dots,e_{i_k}\rbrace\) について、\(w(F)\) を以下のように定義します。

\[ w(F) \coloneqq \sum_{e\in F} w(e) \]

---

[1] グラフの任意の全域木の重みが等しくなる必要十分条件

まず、\(W\) を固定しないで、グラフの全ての全域木の重みが等しくなる条件について見ていきましょう。グラフの閉路に着目すると、以下の必要条件が得られます。

必要条件

全ての \(e_1,e_2\in E\) について、\(e_1,e_2\) を両方含む \(G\) の閉路 \(C\) が存在するならば \(w(e_1) = w(e_2)\) である。

この条件の必要性を確認しましょう。\(G\) の連結性より、\(E(C)\backslash \lbrace e_2\rbrace\) を含む全域木 \(T_1\) が存在します。また、\(T_1\) から \(e_1\) を抜いて \(e_2\) を加えることで得られる部分グラフを \(T_2\) とすると、\(T_2\) も全域木になります。今、グラフの全ての全域木の重みが等しいので、\(w(E(T_1)) = w(E(T_2))\) です。一方で、\(E(T_1), E(T_2)\) の差集合に注目すると、\(w(E(T_1)) - w(E(T_2)) = w(e_1) - w(e_2)\) となります。従って、\(w(e_1) = w(e_2)\) が示されました。

\(2\)-連結グラフの性質

先述の必要条件は、「\(E\) をいくつかの非交な部分集合に分解することができ、同じ部分集合内の辺の重みは全て等しい」ということを言っています。実はこの \(E\) の部分集合が、\(G\) の極大な \(2\)-連結部分グラフ \(H\) の辺集合 \(E(H)\) に対応していることを見ていきましょう。

グラフの \(2\)-連結性は、以下のように定義されます。

連結グラフ \(G\) が \(2\)-連結であるとは、「\(G\) からどの \(1\) 頂点とそれに接続する辺を除いて得られるグラフも連結である」ことである。

\(2\)-連結グラフについて、以下の性質が成り立ちます。

グラフ \(G\) が \(2\)-連結ならば、\(G\) の任意の相異なる辺 \(e_1,e_2\) について、\(e_1,e_2\) を両方含む \(G\) の閉路が存在する。

この性質を確認していきましょう。\(G = (V,E)\) が \(2\)-連結として、相異なる \(2\) 辺 \(e_1,e_2\) を任意に取ります。\(e_1 = \lbrace u_1,v_1\rbrace, e_2 = \lbrace u_2,v_2\rbrace\) として、新たな頂点 \(w_1,w_2\) と辺 \(e_{u,1}\coloneqq \lbrace u_1,w_1\rbrace,e_{v,1}\coloneqq \lbrace v_1,w_1\rbrace, e_{u,2}\coloneqq \lbrace u_2,w_2\rbrace,e_{v,2}\coloneqq \lbrace v_2,w_2\rbrace\) を追加したグラフ \(G' = (V\cup\lbrace w_1, w_2 \rbrace, E\cup\lbrace e_{u,1},e_{v,1},e_{u,2},e_{v,2} \rbrace\backslash \lbrace e_1,e_2\rbrace)\) を考えると、\(G\) の \(2\)-連結性より \(G'\) も \(2\)-連結となります。従って、Menger の定理より \(w_1\) と \(w_2\) を端点とする \(G'\) の内素なパス \(P_1,P_2\) が存在します。\(P_1,P_2\) を適切につなぎ合わせることで \(G'\) の閉路 \(C'\) が得られますが、\(w_1,w_2\) の次数は \(2\) なので \(C'\) は \(e_{u,1},e_{v,1},e_{u,2},e_{v,2}\) を全て含みます。\(C'\) の\(e_{u,1},e_{v,1}\) を \(e_1\) に、\(e_{u,2},e_{v,2}\) を \(e_2\) にそれぞれ置き換えて得られる \(G\) の閉路を \(C\) とすると、\(C\) は \(e_1,e_2\) を両方含みます。従って、主張が示されました。

\(2\)-連結成分分解

\(G\) の極大な \(2\)-連結部分グラフを \(H_1,\dots,H_k\) としましょう。\(H_i\) は \(G\) の \(2\)-連結成分と呼ばれます。\(2\)-連結成分の性質として、\(i\neq j\) ならば \(E(H_i)\cap E(H_j) = \emptyset\) であるということが重要です。この性質は、\(E(H_i)\cap E(H_j) \neq \emptyset\) ならば、部分グラフ \((V(H_i)\cup V(H_j),E(H_i)\cup E(H_j))\) も \(2\)-連結となるため \(H_i\) または \(H_j\) の極大性に矛盾することから従います。

前述の \(2\)-連結グラフの性質と必要条件より、\(G\) の全ての全域木の重みが等しくなるには、\(E(H_i)\) に含まれる全ての辺の重みが等しいことが必要です。

実は、この必要条件は十分条件になっています。十分性を確認するために、以下の補題を示します。

任意の \(i\in \lbrace 1,\dots,k\rbrace\) について、グラフ \(G_i\coloneqq (V,E\backslash E(H_i))\) は \(|V(H_i)|\) 個の連結成分からなる。

これを言うためには、\(G_i\) において相異なる \(2\) 頂点 \(v_1,v_2\in V(H_i)\) を端点とするパスが存在しないことを言えばよいです。逆に、そのようなパス \(P\) が存在すると仮定しましょう。 すると、\(P\) に含まれる頂点・辺を \(H_i\) に加えて得られる部分グラフ \(H'_i\) は \(2\)-連結かつ \(H_i\) よりも真に大きくなるため、\(H_i\) の極大性に矛盾します。従って、補題が示されました。

補題の系として、以下が成立します。

\(G\) の任意の全域木 \(T\) と任意の \(i\in \lbrace 1,\dots,k\rbrace\) について、\(E(T)\cap E(H_i) = |V(H_i)|-1\) が成立する。

\(E(H_1),E(H_2),\dots,E(H_k)\) が \(E\) の分割になっていることと合わせて、十分性が確認できました。

必要十分条件まとめ

\(G\) の辺の重みづけ \(w\colon E\to \{0,\dots,L\}\) について、\(G\) の全ての全域木の重みが等しくなる必要十分条件は、以下の通りです。

\(G\) の \(2\)-連結成分を \(H_1,\dots,H_k\) として、\(e_1,e_2\in E(H_i)\) ならば \(w(e_1) = w(e_2)\) である。

さらに、\(E(H_i)\) に含まれる辺の重みを \(\omega_i\) とすると、\(G\) の任意の全域木 \(T\) の重みは

\[ w(E(T_i)) = \sum_{i=1}^{k} (|V(H_i)|-1)\omega_i \]

となります。

また、\(G\) の \(2\)-連結成分分解は \(O(N+M)\) 時間で行えます。

---

[2] 最適化アルゴリズム

\(G\) の各 \(2\)-連結成分 \( H_i\) について、\(a_i\coloneqq |V(H_i)|-1, b_i\coloneqq |E(H_i)|\) とします。\(W = 0,1,\dots,K\) について、以下で定義される \(f(W)\) を求められればよいです。ただし、\(\min\) の中身が空のときは \(f(W) = +\infty\) とします。

\[ f(W)\coloneqq \min\left\lbrace \sum_{i=1}^{k} b_i(\omega_i)^2 ~\middle | ~ \begin{aligned} &\omega_i\in \lbrace{0,\dots,L \rbrace} \\ &\sum_{i=1}^k a_i\omega_i = W \end{aligned} \right\rbrace \]

\(a_i\) が \(1\) 種類の場合

全ての \(i\) について \(a_i\) が同じ値である場合、上記の \(f(W)\) を \(W=0,\dots,K\) 全てについて、\(O((k+K/a_i)\log k)\) 時間で解くことができます。\(W\) が \(a_i\) の倍数でないときは \(f(W) = +\infty\) となることに注意してください。

\(n > Lk\) ならば \(f(n\cdot a_i) = +\infty\) です。また、多重集合 \(\lbrace b_i(2j-1)\mid i\in\lbrace 1,\dots,k\rbrace,j\in\lbrace 1,\dots,L\rbrace \rbrace\) の要素を小さい順に \(d_1,d_2,\dots,d_{Lk}\) とすると、\(n\in\lbrace 0,\dots,Lk\}\) について

\[ f(n\cdot a_i) = \sum_{\ell = 1}^{n} d_{\ell} \]

となります。ここで、\(b_i(2j-1)\) は \(b_i\cdot j^2\) と \(b_i(j-1)^2\) の差に相当していて、この値が \(j\) に関して単調増加となっているのが肝要です。また、数列 \((f(0),f(a_i),f(2a_i),\dots)\) は (下に) 凸になります。

実際には \(n\cdot a_i\leq K\) を満たす \(j\) のみについて \(f(n\cdot a_i)\) が計算できれば良いので、陽にソートして \(d_1,\dots,d_{Lk}\) を計算する必要はなく、優先度付きキューを用いた貪欲法によって \(O((k+K/a_i)\log k)\) 時間でこれらを計算することができます。

一般の場合

次に、\(a_i\) が \(1\) 種類とは限らない一般の場合を考えましょう。\(j=1,\dots,K\) について、\(a_i = j\) となる \(i\) の集合を \(S_j\) とします。\(\sum_{i=1}^{k}a_i = N-1\) なので、\(S_j\neq\emptyset\) なる \(j\) の種類数は \(O(\sqrt{N})\) であることに注意してください。

\(S_j\neq\emptyset\) である \(j\) について、\(f_j(W)\) を以下のように定めます。

\[ f_j(W)\coloneqq \min\left\lbrace \sum_{i\in S_j} b_i(\omega_i)^2 ~\middle | ~ \begin{aligned} &\omega_i\in \lbrace{0,\dots,L \rbrace} \\ &\sum_{i\in S_j} a_i\omega_i = W \end{aligned} \right\rbrace \]

\(f_j(W)\) と \(f(W)\) の違いは、\(i\) の動く範囲のみです。\(a_i\) が一種類の場合の考察より、\(0\leq nj\leq W\) を満たす全ての整数 \(n\) についての \(f_j(nj)\) を \(O((|S_i| + K/j)\log |S_i|)\) 時間で計算できます。よって、全ての \(j\) についての \(f_j\) の計算を \(O(N\log N+K\log K\log N)\) 時間で行えます。

関数 \(g_1,g_2\colon\lbrace 0,\dots,W\rbrace \to \mathbb{Z}\cup\lbrace+\infty\rbrace\) の min-plus convolution \((g_1\oplus g_2)\colon \lbrace 0,\dots,W\rbrace \to \mathbb{Z}\cup\lbrace+\infty\rbrace\) を

\[ (g_1\oplus g_2)(z) := \min\lbrace g_1(x) + g_2(y)\mid x+y=z \rbrace \]

とすると \(f = f_1\oplus f_2\oplus\cdots\oplus f_K\) と書けるので、この右辺を計算することができればよいです (実際には \(S_j\) が空でない \(j\) 全ての min-plus convolution をすればよいです)。数列の min-plus convolution も同様に定義します。

凸性を利用した高速な min-plus convolution

\((f_j(0),f_j(j),f_j(2j),\dots)\) は凸数列であるという特徴を有します。この性質を利用することで、任意の \(g\colon \lbrace 0,\dots,W\rbrace \to \mathbb{Z}\cup\lbrace+\infty\rbrace\) と \(f_j\) の min-plus convolution を \(O(K)\) 時間で行えることを見ていきましょう。前提知識として、凸とは限らない数列と凸数列の min-plus convolution が、SMAWK アルゴリズムを用いて線形時間で実現できることを用います。

\(i = 0,\dots,j-1\) について、数列 \(g_i\) を \(g_i = (g(i),g(j+i),g(2j+i)\dots)\) とします。また、数列 \(h_j\) を \(h_j = (f_j(0),f_j(j),f_j(2j),\dots)\) とします。\(x\) が \(j\) の倍数でないとき \(f_j(x) = +\infty\) なので、このような \(x\) からは遷移を考える必要がないことに注意すると、\((g\oplus f_j)(nj+i) = (g_i\oplus h_j)_n\) となります。従って、全ての \(i\) について \(g_i\oplus h_j\) が計算できれば \(g\oplus f_j\) が求められます。

\(h_j\) は凸なので、線形時間の min-plus convolution アルゴリズムを用いることができます。また、\(f_i\) と \(h_j\) はいずれも要素数が \(K/j+1\) 以下であるため、全ての \(i\) についての \(g_i\oplus h_j\) を \(O(K)\) 時間で計算できることがわかりました。

まとめ

アルゴリズムを総括しましょう。まず、\(g\) を \(g(0) = 0\)、それ以外では \(+\infty\) を取る関数として初期化します。そして、\(S_j\neq\emptyset\) である全ての \(j\) について、順に \(f_j\) を計算し、\(g\leftarrow g\oplus f_j\) と更新します。最終的に得られる \(g\) が問題の答えになります。

注目する \(j\) は \(O(\sqrt N)\) 個なので、全体の計算量は \(O(N\log N + K\log K\log N + K\sqrt{N})\) となります。min-plus convolution で monotone minima アルゴリズムを用いると最終項が \(K\sqrt{N}\log K\) になりますが、いずれの場合も十分高速に動作します。