问一个平面图G，用大O记号求B的m的尺寸的上界
EN

Stack Overflow用户

提问于 2018-02-25 18:05:45

回答 1查看 48关注 0票数 0

设A是平面图G的顶点集，B是使R中每个顶点都能被赋予一种颜色且没有两个相邻的颜色被赋予同一颜色的最小颜色集合，用大O记法求B的m的大小的上界。边界应尽可能地紧凑。

答案是O(2^n)吗？我不知道。我不太熟悉这种类型的任务，不知道我应该从哪里开始解决这样的任务？我粗略地阅读了“计算几何”、“数据结构和算法”、“GIS -计算视角”。但我就是想不通。任何意见都是值得感谢的。谢谢。

回答已采纳

发布于 2018-02-25 18:22:13

正如我所发现的，平面图顶点着色需要最少的颜色。有一个定理叫做Four Color Theorem。它说所有的平面图都可以用4种颜色着色。

此外，您还可以查看Five Color Theorem。因此它是|B| = O(1)的，与平面图的顶点数无关。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/48972308

复制

相似问题

问一个平面图G，用大O记号求B的m的尺寸的上界EN