### 图的 m 着色问题 Python 实现 对于图的 m 着色问题，目标是在给定无向图 G 中找到一种方法来分配颜色使得相邻顶点的颜色不同，并且使用的颜色总数不超过 m 种。下面是一个简单的回溯法解决方案[^1]： ```python class GraphColoring: def __init__(self, vertices, colors): self.V = vertices # 节点数量 self.m = colors # 颜色数目 self.graph = [[0 for column in range(vertices)] for row in range(vertices)] def is_safe(self, v, color, c): """检查当前节点v着色c是否安全""" for i in range(self.V): if self.graph[v][i] and color[i] == c: return False return True def graph_color_util(self, m, color, v): """递归函数用于尝试为所有顶点上色""" if v == self.V: return True for c in range(1, self.m + 1): if self.is_safe(v, color, c): color[v] = c if self.graph_color_util(m, color, v + 1): return True color[v] = 0 return False def graph_coloring(self): """初始化并调用graph_color_util()""" color = [0] * self.V if not self.graph_color_util(self.m, color, 0): return False print("Solution exist:") for idx, val in enumerate(color): print(f"Node {idx} -> Color {val}") return True # 测试案例 if __name__ == "__main__": g = GraphColoring(4, 3) # 创建一个有四个节点和三种可用颜色的对象实例 g.graph = [ [0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0] ] g.graph_coloring() ``` 此代码定义了一个 `GraphColoring` 类，该类接收两个参数：一个是图形中的顶点数 (`vertices`) 和另一个是要应用的不同颜色的数量(`colors`). 使用邻接矩阵表示输入图表结构。