知识卡片

普通读书笔记卡 · 5654.d.1.f.3.a · 生成模型:未记录

顶点着色约束相邻项不同色

理解等级:中级

顶点着色给顶点分配颜色,要求每条边两端的顶点颜色不同;若还希望颜色数最少,就是求色数。颜色可看成对不应相同分组的一种标记,满足约束和用色最少是两个不同目标。

原文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)。 哈密顿圈问题 如果从图中任意一点出发,经过图中的每一个顶点恰好一次,最后返回初始顶点,则称该路径为哈密顿圈