问题描述

给定无重边,正边权,无向图 \(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)\)

Read More