知识卡片
顶点着色约束相邻项不同色
顶点着色给顶点分配颜色,要求每条边两端的顶点颜色不同;若还希望颜色数最少,就是求色数。颜色可看成对不应相同分组的一种标记,满足约束和用色最少是两个不同目标。
原文chromatic number译作“全色数”不准确,这里讨论的是顶点色数,不是同时给顶点和边着色的问题。NIST色数定义(2026-11-06核验)。此段未给算法或复杂度,不补造最优求解实现。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
图着色 尝试对图的顶点着色,使得每一条边的两个顶点颜色都不相同,这个过程称为图着色。某些时候,我们只关心在这种情况下所需要的最少颜色数量,这称为图的全色数(chromatic number)。 哈密顿圈问题 如果从图中任意一点出发,经过图中的每一个顶点恰好一次,最后返回初始顶点,则称该路径为哈密顿圈
参考来源
- 位置:《算法精解:C语言描述》第11章《第11章 图》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u185-ch11-002)。
- 结论依据:185图着色完整应用段实读,NIST定义核对最少顶点颜色术语,不制造未给出的真实资源分配场景。
- 原始内容:图着色 尝试对图的顶点着色,使得每一条边的两个顶点颜色都不相同,这个过程称为图着色。某些时候,我们只关心在这种情况下所需要的最少颜色数量,这称为图的全色数(chromatic number)。 哈密顿圈问题 如果从图中任意一点出发,经过图中的每一个顶点恰好一次,最后返回初始顶点,则称该路径为哈密顿圈