algorithm - 关于图中的二分集和独立集

Question

假设有一个二分图。那么我是否可以说从 V 的两个二分划分中，具有最大基数的划分是该图的最大独立集？

因为，二分图中的所有边都是切割边(穿过两个分区的黑白)，所以没有更多的边需要处理，即没有更多的节点可以添加到最大基数分区而没有一个节点的两个端点边在同一分区中，这违反了独立集的性质。

如果我们能像这样得到最大独立集，那么对于非二部图，我可以对图进行 2 着色，然后从两个分区中删除所有坏边(及其 2 个端点)并调用剩余的最大基数划分图的最大独立集？

Answer 1

对于任意二分法(即，将顶点集划分为两个独立的集)，情况并非如此。例如，一个有两个顶点且没有边的图可以分成两个单集，但最大独立集的大小为 2，而不是 1。