Skiena关于算法的书的问题：
图 G = (V,E) 的顶点覆盖是顶点 V 的子集？V 使得 E 中的每条边都包含来自 V 的至少一个顶点。一组独立的图 G = (V,E) 是顶点 V 的子集？V 使得 E 中没有边包含来自 V 的两个顶点
一个独立的顶点覆盖是顶点的一个子集，它既是一个独立的集合又是 G 的一个顶点覆盖。给出一个有效的算法来测试 G 是否包含一个独立的顶点覆盖。这简化为什么经典图问题？
有谁知道这个问题的答案？
谢谢。
更新
（需要关于这个想法的建议）
到目前为止，我认为这与检查图形是否可以使用 2 种颜色着色有关，即它是否是二分的？如果使用 BFS 变体为图形着色，例如白色和黑色，那么具有这些颜色之一的顶点（例如白色）在某些情况下也会形成顶点覆盖。
你的想法是正确的。这是检查给定图是否是二分图的问题。
二部图没有奇数长度的环，因此如果使用 BFS 为图着色，相同颜色的顶点将是独立的集合。
来自维基百科：
如果二分图是连通的，则它的二分可以通过距任意选择的顶点 v 的距离的奇偶性来定义：一个子集由距 v 偶数距离的顶点组成，另一个子集由距 v 奇数距离的顶点组成。
因此，可以通过使用这种奇偶校验技术将顶点分别分配给图的每个连接组件内的两个子集 U 和 V，然后检查每条边以验证它是否具有分配给不同的端点，从而有效地测试图是否是二分图。子集。
有趣的事实是，独立集是 Np 完全的，并且也是顶点覆盖的，但是验证图是否是二分图是多项式的。
将来，对于此类问题，https://cs.stackexchange.com/也是一个提问的好地方。