关于图中的双配体和独立集
关于图中的双配体和独立集
提问于 2018-10-16 11:19:24
假设有一个二分图。那么，从V的两个二分划分中，具有最大基数的划分是该图的最大独立集吗？
由于二分图中的所有边都是切边(横过b/w的两个分区)，因此没有更多的边需要处理，也就是说，没有更多的节点添加到最大基数划分中，而边的两个端点都在同一分区中，这违反了独立集的性质。
如果我们可以得到像这样的最大独立集，那么对于一个非二部图，我可以对该图进行2色化，然后从这两个分区中删除所有坏边(以及它们的两个端点)，并将剩余的最大基数划分称为图的最大独立集吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-10-16 12:23:11
对于任意的二分分区(即将顶点集划分为两个独立集)，情况并非如此。例如，具有两个顶点且没有边的图可以分为两个单点集，但最大独立集的大小为2，而不是1。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52834272
复制相关文章
相似问题
腾讯云开发者
