一个顶点覆盖（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组合优化问题。
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
有两种可用的模式：无权重（默认）和有权重。您可以通过点击相应的标签来在两种模式之间切换。
有些算法在两种模式下都能工作，也有些算法只能在某一种模式下工作。
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
在这里查看所选MVC算法的可视化。
最初，输入图中的所有顶点和边都用标准黑色轮廓着色。随着可视化的进行，浅蓝色将被用来表示已覆盖的边，而边上的橙色将被用来显示已遍历的边。
在所选MVC算法结束时，如果它找到一个最小 VC，它将用橙色高亮显示MVC顶点，用浅蓝色高亮显示非MVC顶点（也称为MIS顶点）。否则，如果找到的顶点覆盖未被证明为最小的（例如，使用的算法是近似算法），它将用橙色高亮显示属于找到的顶点覆盖的顶点，而不高亮显示MIS顶点。
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
有两种不同的方式来指定输入图：
- 编辑图：您可以将当前显示的无向图（对于MWVC模式为加权）编辑为任何其他无向图（对于MWVC模式为加权）。
- 示例图：您可以从示例无向图（对于MWVC模式为加权）的列表中选择，以便开始。
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
暴力法：它尝试所有可能的 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 近似算法：
- 对于无权版本，我们有确定性的2倍近似或概率性的2倍近似（期望值），
- 对于加权版本，我们有 Bar-Yehuda 和 Even 的2倍近似算法。
请注意，这些算法只能得到一个"近似"的 MVC，意味着它们并不是真正的最小顶点覆盖，但足够好。
遗憾的是，这部分还没有数字化，正在进行中。
请查看 CS4234 的讲义以获取详细信息。
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
编辑图表
图示
暴力法
树上的MVC
在二部图上的MVC
估计