知识卡片

普通读书笔记卡 · 3766

相邻顶点必须异色

理解等级:初级

k-顶点着色把图中每个顶点映射到 k 种颜色之一,并要求每条边连接的两个端点颜色不同。图着色有两类相关但不同的任务:求色数是找满足该约束所需的最少颜色;给定 k 的着色是判断能否用这 k 种颜色完成分配。电路布线、工序、排课、任务分配等都可以转化成这类问题。

补充教学示例(非书中数据)。三个顶点两两相连的三角形:任意一边两端必须异色,因此至少需要 3 种颜色;若只给 k=2,不存在合法着色。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 1 . 5 . 2 基 于 模 拟 退 火 算 法 的 图 着 色 问 题 · 查看原书依据

      图k-顶点着色是指用k种颜色对图G中的所有顶点逐一上色,并且要求图中任意两个相邻的顶点的颜色互不相同。设图G(V,E)中,V=V,V,…,Vn表示n个顶点的集合,E表示边的集合,则图的k-顶点着色问题可以描述为: 12 其中X=x,x,…,xn表示V中每个顶点的颜色,xi∈{1,2,…,k}。

    参考来源

    - 位置:《智能算法导论》第 119 项《11.5.2 基于模拟退火算法的图着色问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0014.xhtml`;式 11-8) - 结论依据:正文分别说明求色数与给定 k 着色,并要求任意相邻顶点颜色不同。三角形为例为依据该约束补充的教学示例,非书中数据。 - 原始内容:图 k-顶点着色是指用 k 种颜色对图 G 中的所有顶点逐一上色,并且要求图中任意两个相邻的顶点的颜色互不相同。