### Python 中解决图着色问题的方法 #### 方法一：使用回溯算法求解图着色问题 回溯法是一种通过尝试所有可能的颜色组合来找到有效着色方案的技术。这种方法适用于较小规模的图，因为随着节点数量增加，计算复杂度会迅速增长。 ```python class Graph(): def __init__(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] \ for row in range(vertices)] # A utility function to check if the current color assignment is safe for vertex v. def is_safe(self, v, colour, c): for i in range(self.V): if self.graph[v][i] and colour[i] == c: return False return True # A recursive utility function to solve m coloring problem def graph_colour_util(self, m, colour, v): if v == self.V: return True for c in range(1, m + 1): if self.is_safe(v, colour, c) == True: colour[v] = c if self.graph_colour_util(m, colour, v + 1) == True: return True colour[v] = 0 def graph_colouring(self, m): colour = [0] * self.V if not self.graph_colour_util(m, colour, 0): return False # Print the solution print("Solution exist and Following are the assigned colours:") for c in colour: print(c), return True # Driver Code g = Graph(4) g.graph = [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0]] m = 3 # Number of colors g.graph_colouring(m)[^2] ``` 此代码实现了基于回溯方法的图着色解决方案，并展示了如何为给定图形分配最多三种不同的颜色。 #### 方法二：利用遗传算法处理大规模实例 对于较大尺寸的问题实例，可以采用进化类元启发式搜索技术——比如遗传算法（GA）。这类方法模仿自然选择过程，在种群中迭代改进候选解答直至达到满意程度为止。 ```python import random from deap import base, creator, tools, algorithms def create_individual(num_vertices, num_colors): """Create a new individual (solution candidate).""" return [random.randint(1, num_colors) for _ in range(num_vertices)] def evaluate(individual, adjacency_matrix): """Evaluate fitness based on number of conflicts.""" conflict_count = sum(adjacency_matrix[u][v] and individual[u]==individual[v] for u in range(len(individual)) for v in range(u+1,len(individual))) return float(conflict_count), creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.FitnessMin) toolbox = base.Toolbox() num_vertices = ... # Define your own value here num_colors = ... adjacency_matrix = ... toolbox.register("attr_color", lambda: random.randint(1,num_colors)) toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_color, n=num_vertices) toolbox.register("population", tools.initRepeat, list, toolbox.individual) toolbox.register("mate", tools.cxTwoPoint) toolbox.register("mutate", tools.mutUniformInt, low=1, up=num_colors, indpb=0.05) toolbox.register("select", tools.selTournament, tournsize=3) toolbox.register("evaluate", evaluate, adjacency_matrix=adjacency_matrix) pop = toolbox.population(n=300) hof = tools.HallOfFame(1) stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("avg", numpy.mean) stats.register("std", numpy.std) stats.register("min", numpy.min) stats.register("max", numpy.max) algorithms.eaSimple(population=pop, toolbox=toolbox, cxpb=0.7, mutpb=0.2, ngen=40, stats=stats, halloffame=hof, verbose=True)[^3] best_solution = hof[0] print(f'Best found solution with {len(set(best_solution))} distinct colors used.') for idx,color in enumerate(best_solution): print(f'vertex {idx}: color {color}') ``` 上述脚本构建了一个简单的DEAP框架下的遗传算法用于寻找近似最优解。它定义了个体编码方式、适应度评估函数以及其他必要组件以执行标准的选择交叉变异操作循环直到满足终止条件。 #### 使用现成库简化开发工作 除了自行编写算法外，还可以借助第三方库如NetworkX来进行更高效的编程实践： ```python import networkx as nx import matplotlib.pyplot as plt G=nx.Graph() edges=[('A','B'),('B','C'),('C','D'),('D','E')] colors=['red', 'green', 'blue'] nx.add_edges_from(edges) node_colors = [] for node in G.nodes(): neighbors=G.neighbors(node) neighbor_colors={G.node[n]['color'] for n in neighbors} available=set(colors)-neighbor_colors try: chosen=list(available)[0] except IndexError: raise Exception("Not enough colors provided.") G.node[node]['color']=chosen node_colors.append(chosen) pos=nx.spring_layout(G,k=.8,iterations=20) plt.figure(figsize=(8,6)) nx.draw_networkx_nodes(G,pos,node_size=700,node_color=node_colors,cmap=plt.cm.RdYlBu) nx.draw_networkx_labels(G,pos,font_size=20,font_family='sans-serif') nx.draw_networkx_edges(G,pos,width=2,alpha=0.5,edge_color='black') plt.show()[^1] ``` 这段程序片段展示了一种简单直观的方式绘制已上色后的网络结构并可视化结果。这里采用了贪心策略逐个顶点挑选可用色彩完成整个染色流程。