Graph Weighting Editorial

· · 题解

说明

[0] 符号注意

[1] 图的任意全域树的边权相等的必要充分条件

首先，不固定 W，来看图的所有全域树的权重相等的条件。关注图的回路，可以得到以下必要条件。

必要条件

对于所有的 e_1,e_2\in E，如果存在同时包含 e_1,e_2 的图 G 的回路 C，则 w(e_1) = w(e_2)。

我们来验证这个条件的必要性。由于 G 是连通的，存在包含 E(C)\backslash \{ e_2 \} 的全域树 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 中的一个顶点及其相连的边后得到的图仍为连通”。对于 2-连通图，以下性质成立：

如果图 G 是 2-连通的，那么对于 G 中的任意两条不同边 e_1,e_2，存在同时包含 e_1,e_2 的图 G 的回路。

我们来验证这个性质。设 G = (V,E) 是 2-连通的，任选两条不同的边 e_1,e_2。令 e_1 = \{ u_1,v_1\}, e_2 = \{ u_2,v_2\}，考虑添加新顶点 w_1,w_2 和边 e_{u,1}\coloneqq \{ u_1,w_1\},e_{v,1}\coloneqq \{ v_1,w_1\}, e_{u,2}\coloneqq \{ u_2,w_2\},e_{v,2}\coloneqq \{ v_2,w_2\} 的图 G' = (V\cup\{ w_1, w_2 \}, E\cup\{ e_{u,1},e_{v,1},e_{u,2},e_{v,2} \}\backslash \{ e_1,e_2\})。根据 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 \{ 1,\dots,k\}，图 G_i\coloneqq (V,E\backslash E(H_i)) 由 |V(H_i)| 个连通分量组成。

要证明这一点，我们需要说明在 G_i 中不存在以不同的两个顶点 v_1,v_2\in V(H_i) 为端点的路径。反过来，假设存在这样的路径 P。那么，将 P 中的顶点和边加入到 H_i 中得到的子图 H'_i 既是 2-连通的，又比 H_i 更大，这与 H_i 的极大性相矛盾。因此，引理得证。

作为该引理的推论，下述结论成立：

对于 G 的任意全域树 T 和任意 i\in \{ 1,\dots,k\}，成立 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

此外，可以在 O(N+M) 的时间内实现 G 的 2-连通成分分解。

[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 \{0,\dots,L \} \\ &\sum_{i=1}^k a_i\omega_i = W \end{aligned} \right\rbrace

如果 a_i 为唯一值的情况

如果所有的 i 的 a_i 值相同，则可以在 O((k+K/a_i)\log k) 的时间内求解上述的 f(W)，对于 W=0,\dots,K 而言。注意：如果 W 不是 a_i 的倍数，则 f(W) = +\infty。当 n > Lk 时，f(n\cdot a_i) = +\infty。此外，令多重集合 \{ b_i(2j-1)\mid i\in\{ 1,\dots,k\},j\in\{ 1,\dots,L\} \} 的元素按升序排列为 d_1,d_2,\dots,d_{Lk}，则对于 n\in\{ 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，故无须逐个显式排序并计算 d_1,\dots,d_{Lk}，可以通过使用优先级队列采用贪心法在 O((k+K/a_i)\log k) 的时间内计算出这些值。

一般情况

接下来，考虑 a_i 不必是唯一值的一般情况。对于 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 \{0,\dots,L \} \\ &\sum_{i\in S_j} a_i\omega_i = W \end{aligned} \right\rbrace 函数 $g_1,g_2\colon\{ 0,\dots,W\}\to \mathbb{Z}\cup\{+\infty\}$ 的最小加法卷积 $(g_1\oplus g_2)\colon \{ 0,\dots,W\}\to \mathbb{Z}\cup\{+\infty\}$ 定义为 $$ (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$ 进行最小加法卷积的运算）。序列的最小加法卷积也按照类似的方式定义。 ### 利用凸性进行快速的最小加法卷积 $(f_j(0),f_j(j),f_j(2j),\dots)$ 具有凸数列的特征。利用这一特性，我们来看能否在 $O(K)$ 时间内进行任意 $g\colon \{ 0,\dots,W\} \to \mathbb{Z}\cup\{+\infty\}$ 和 $f_j$ 的最小加法卷积。作为前提知识，我们会用到非凸数列和凸数列的最小加法卷积可以借助 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$ 是凸的，所以可以运用线性时间的最小加法卷积算法。此外，$f_i$ 和 $h_j$ 中的元素数量均不超过 $K/j+1$，所以我们可以在 $O(K)$ 时间内计算所有 $i$ 的 $g_i\oplus h_j$。 ### 总结 对算法进行概述。首先，将 $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})$。若在最小加法卷积中使用单调最小法算法，最终项将变为 $K\sqrt{N}\log K$，但无论如何都能高效运作。