问题描述

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