图着色问题（递归回溯算法）（C语言）
发布时间
阅读量：
阅读量
图m着色问题
给定无向连通简单无向连通图为G及其顶点集V，并使用集合C中的m种不同的颜色对每个顶点v∈V进行染色操作。
是否存在一种染色方案使得对于每一条边uv∈E（其中u,v∈V），u和v的颜色均不相同？
这属于graph theory中的判定问题：确定是否存在一种染色方案使得对于每一条边uv∈E（其中u,v∈V），u和v的颜色均不相同？
如果一个简单无向图为G=(V,E)且满足：对于任意两个相邻顶点u,v∈V（即uv∈E），它们被分配的颜色都不相同，则称这样的染色方案为合法；进一步地，在所有可能满足条件的情况下的最小所需的颜色数目称为该简单无向图为G=(V,E) 的 chromatic number。
计算simple undirected graph所需的最小染色数目是一个重要的优化问题，在此背景下通常被称为graph coloring problem。
请绘制如图1所示的无向连通图及其色数m=3对应的解空间树，并列举所有可能的解
这是m着色问题的空间图
全部评论 (0)
还没有任何评论哟~