5顶点8边无向图测试用例的最小顶点覆盖集大小是多少

测试用例基础信息 #

本次测试的边集输入如下：

1 4
1 5
1 2
4 1
2 4
3 4
5 2
1 3

首先对无向图的重复输入边做去重处理，最终有效边共7条：(1,2)、(1,3)、(1,4)、(1,5)、(2,4)、(2,5)、(3,4)，图共包含5个顶点。

正确结论 #

你对最小顶点覆盖概念的理解完全正确，该图的真实最小顶点覆盖大小为3。
你枚举的{1,2,4}、{1,4,5}都是合法的最小顶点覆盖集，以{1,2,4}为例做覆盖校验：

• 边(1,2)：两个端点都在集合中
• 边(1,3)：端点1在集合中
• 边(1,4)：两个端点都在集合中
• 边(1,5)：端点1在集合中
• 边(2,4)：两个端点都在集合中
• 边(2,5)：端点2在集合中
• 边(3,4)：端点4在集合中
  所有边均被覆盖。同时可以通过枚举验证：不存在大小为2的顶点覆盖，任意选取2个顶点最多只能覆盖6条边，必然剩余至少1条边的两个端点都不在所选集合中。

不同平台返回结果偏差的原因 #

你在两个不同在线平台得到5、4的错误结果，原因分别是：

• 返回结果为5的平台，要么是题目本身是顶点覆盖的变体问题（比如额外要求覆盖集同时是独立集等特殊约束），要么是平台的用例解析、判题逻辑存在bug，例如错误将无向边识别为有向边、顶点编号映射错误。
• 返回结果为4的平台，实现的是顶点覆盖的2倍近似算法，而非精确求解算法。该近似算法的逻辑是反复选取未被覆盖的边，将边的两个端点都加入覆盖集，本身就不保证返回全局最优解，返回大小为4的结果属于该近似算法的正常误差范围，不代表真实最小覆盖大小。

内容的提问来源于stack exchange，提问作者Noob_Coder