博文
图着色
||
图着色的贪婪算法
1）G的顶点排序（编号）x_1，x_2，x_3，....，x_n
2）颜色按照排个序1,2,3,4，
3）把x_1染成1色
4）把x_2相邻的，并在x_2之前的顶点没有着色的最小号颜色赋予点x_2
5）x_3,类似
注：点的不同编号，有不同的着色
定理 G是图，点的最大度为K，用贪婪算法可以得到G的K+1—着色（上界）
星图是2—着色
图着色的应用
安排任务 把有冲突的任务放在同一个时间段内，前提是任务之间无前后关系，无先后顺序
若任务之间有前后关系先后顺序的话，就是有向图
https://blog.sciencenet.cn/blog-1277062-977569.html
上一篇：检索方法
下一篇：三角函数——诗
扫一扫，分享此博文
全部精选博文导读
相关博文
- • 学者的经济社会贡献率-- 兼谈“神奇药丸”的价值
- • 中国传媒大学校庆及中传学者文库出版发行
- • Philosophical Challenges vs.DIKWP Semantic Mathematics（初学者版）
- • Compare DIKWP Semantic Mathematics with Related Models（初学者版）
- • Building an Artificial Consciousness System with DIKWP（初学者版）
- • Cognitive Development and Mechanism of DIKWP Semantics（初学者版）