gpt4 book ai didi

algorithm - 检查着色图所需的最少颜色数(2-正则图中的色数)

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:06:25 24 4
gpt4 key购买 nike

我的任务是检查图形着色中使用的最少颜色数,即图形的色数。我的无向图是 2 正则图(每个顶点都是 2 度)。我找到了解决方案

(最大独立集数)/顶点数=颜色数(色数)

https://imgur.com/a/ZtyP4v9 - 看起来如何

如您所见,如果结果为 2,则它可以是 2 色;如果结果大于 2,则它可以是 3 色。

但我不知道如何在这样的图中找到最大独立集。

最佳答案

2-正则图只不过是不相交循环的并集。如果任何循环的长度为奇数,则色数为 3,否则为 2。就这么简单。您不需要算法。

关于algorithm - 检查着色图所需的最少颜色数(2-正则图中的色数),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56771076/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com