问题描述

给定无重边,正边权,无向图\(G = (V, E)\),求\(G\)的边权和最小的连通生成子图。

如果,每个点的度没有限制,那么就相当于求\(G\)的最小生成树,存在多项式时间最优算法。

但如果,每个点的度存在限制,这个问题就没有那么简单了。

不妨设第\(i\)个点的度为\(deg(i)\),度限制为\(d(i)\)

那么就有如下两个问题:

问题一:求\(G\)的边权和最小的连通生成子图,且\(deg(i) \leq d(i)\)

问题二:求\(G\)的边权和最小的连通生成子图,且\(deg(i) = d(i)\)

显然,对于问题二,如果所有的\(d(i) = 2\),那么这个问题相当于\(TSP\)问题。

不幸的是,这两个问题都是\(NP-hard\)的,甚至目前没有找到多项式时间的近似算法。

但是,我们可以对\(G\)加一些限制条件,使得多项式时间的近似算法成为可能。

问题重述

给定无重边,正边权,无向完全图\(G = (V, E)\)且边集满足三角形不等式

问题一(BMST):求\(G\)的边权和最小的连通生成子图,且\(deg(i) \leq d(i)\)

问题二(ConnFact):求\(G\)的边权和最小的连通生成子图,且\(deg(i) = d(i)\)

问题一解决

\(V_{=1}\)\(d(i) = 1\)的点的集合,\(V_{\geq 2}\)\(d(i) \geq 2\) 的点的集合。 称满足\(deg(i) \leq d(i)\)\(G\)的连通生成子图为\(d-bounded \space tree\),其中,边权和最小的为\(Tree_d\)

不妨设\(|V_{\geq 2}| \geq 2\) ,否则可以通过分类讨论解决。

不妨设已知\(Tree_d\)的一条边\(e_0\),两端点分别为\(i_0\)\(j_0\)

\(G\)的基础上,考虑最小费用流问题\(MCF_{e_{0}}\)

  1. 汇点\(r\)
  2. \(G\)中删去边\(e_0\)
  3. 对于\(G\)的所有边,容量为\(1\),费用为边权。
  4. 对于所有\(V_{\geq 2}\)中的点\(i\),点容量限制为\(d_i - 1\)
  5. 对于所有\(V_{\geq 2} \backslash\{ i_0, j_0 \}\) 中的点\(i\),连一条边\({(i, r)}\) ,容量为\(d_i - 2\),费用为\(0\)
  6. 对于\(i_0\)\(j_0\),连一条边\((i, r)\),容量为\(d_i - 1\),费用为\(0\)
  7. 对于所有\(V_{=1}\),有流量\(1\)

显然,\(Tree_d\)删去边\(e_0\)是该费用流问题的一个解。

那么设\(f^\ast\)\(MCF_{e_0}\) 的一个整数最优解,且满足\(f^\ast\)的支配图\(S^\ast\)所含点数最少。

那么有如下性质:

  1. \(w(S^\ast) \leq w(Tree_d)\)
  2. \(S^\ast\)是森林。
  3. \(deg(i_0) \leq d(i_0) - 1\)\(deg(j_0) \leq d(j_0) - 1\)
  4. 对于每一个连通分量,若不包含点\(i_0\)\(j_0\),则其一定包含\(V_{\geq 2} \backslash\{ i_0, j_0 \}\) 中的点\(i\),且\(deg(i) \leq d_i - 2\)

\(i_0\)为起点\(j_0\)为终点,将每一个连通分量中满足性质\(4\)的点通过类似\(Metric \space TSP\)问题的解法连接成路径\(P\)

\(w(T) \leq w(S^ast) + w(P) \leq w(Tree_d) + 2w(Tree_d) \leq 3w(Tree_d)\)

comments powered by Disqus