一个顶点覆盖(Vertex Cover, VC)是一个连通的无向加权/无向无权图G的顶点子集V,使得G中的每一条边,至少有一个端点在V中。图G的最小顶点覆盖(Minimum Vertex Cover, MVC)(对于加权变体,是最小权重顶点覆盖(Minimum Weight Vertex Cover, MWVC))是所有可能的VC中,具有最小基数(如果是无权的)或总权重(如果是加权的)的VC。一个图可以有多个VC,但其MVC/MWVC的基数/总权重是唯一的。
还有另一个问题叫做最大独立集(Maximum Independent Set, MIS),它试图找到一个加权/无权图G中没有任何相邻顶点的最大顶点子集。有趣的是,一个图的MVC的补集就是一个MIS。
在每次可视化结束时,当一个算法突出显示当前显示的图的MVC解决方案时,它会以橙色高亮显示。对于非近似解,可视化还将突出显示MIS解(即V \\ MVC),并以浅蓝色高亮显示。
MVC,MWVC,MIS,(和MWIS)都是NP-hard组合优化问题。
有两种可用的模式:无权重(默认)和有权重。您可以通过点击相应的标签来在两种模式之间切换。
有些算法在两种模式下都能工作,也有些算法只能在某一种模式下工作。
在这里查看所选MVC算法的可视化。
最初,输入图中的所有顶点和边都用标准黑色轮廓着色。随着可视化的进行,浅蓝色将被用来表示已覆盖的边,而边上的橙色将被用来显示已遍历的边。
在所选MVC算法结束时,如果它找到一个最小 VC,它将用橙色高亮显示MVC顶点,用浅蓝色高亮显示非MVC顶点(也称为MIS顶点)。否则,如果找到的顶点覆盖未被证明为最小的(例如,使用的算法是近似算法),它将用橙色高亮显示属于找到的顶点覆盖的顶点,而不高亮显示MIS顶点。
有两种不同的方式来指定输入图:
暴力法:它尝试所有可能的 2^V 顶点子集。在每次迭代中,它检查当前选定的顶点子集是否是一个有效的顶点覆盖,通过遍历所有 E 边并在 O(E) 中检查所有边是否被当前选定的子集中的顶点覆盖。这种暴力算法保持有效顶点覆盖的最小大小作为答案。
这种暴力算法在加权和未加权版本中都可用。
它的时间复杂度是 O(2^V × E),即,极其慢。我们正在改进可视化,以便剪掉"无聊"的非改进部分,只突出显示重要的"候选 VC"子集。
讨论:但是,如果我们被告知 k '不是那么大',那么有一个替代的 O(2^k × E) 参数化解决方案。
遗憾的是,这部分还没有被数字化/可视化,正在进行中。
请参阅 CS4234 的讲义以获取详细信息。
树上的DP:如果图是一棵树,那么MVC问题可以被构造为一个动态规划问题,其中的状态是(位置,取当前顶点)。
然后,可以看出:
DP(u, take) = cost[u] + sum(min(DP(v, take), DP(v, not_take))) ∀child v of u, 和
DP(u, not take) = sum(DP(v, take)) ∀child v of u
这个DP算法在加权和未加权版本中都可用。
它的时间复杂度是O(V),即非常快,但前提是输入图是一棵树。
树上的贪心 MVC:再次强调,如果图是一个无权重的树,我们可以通过观察到,如果有任何 MVC 解决方案包含一个叶子顶点,我们可以通过取代该叶子顶点的父顶点来得到一个“不差”的解决方案。在移除所有被覆盖的顶点后,我们可以应用同样的观察并重复它,直到每个顶点都被覆盖。
这种贪心 MVC 算法只在无权重模式下可用。
它的时间复杂度是 O(V),即非常快,但前提是输入图是一个无权重的树。
柯尼希定理:根据柯尼希定理,无权二分图中的最小顶点覆盖(MVC)的大小等于二分图的最大匹配的基数。在加权二分图的情况下,我们可以看到这个定理也同样成立,只是我们构建图的方式有所改变。在这个可视化中,我们使用减少到最大流问题来获取MVC的值。
这个算法在加权和无权版本中都可用。
它的时间复杂度是 O(V × E)(对于无权版本;预处理后可能会更小)或 O(E^2 × V)/O(V^2 × E)(对于加权版本,取决于使用的最大流算法)。
我们有几种已知的 MVC 近似算法:
请注意,这些算法只能得到一个"近似"的 MVC,意味着它们并不是真正的最小顶点覆盖,但足够好。
遗憾的是,这部分还没有数字化,正在进行中。
请查看 CS4234 的讲义以获取详细信息。