图的着色 – 潘登同学的图论笔记

• 图的着色

对简单图G的每个顶点赋予一种颜色使得相邻的顶点颜色不同，称图G的一种点着色。对简单图G进行点着色所需的最少颜色数称为G的点色数，记为$\chi (G)$

（注：对于n阶简单图，显然有$\chi (G)\le n$）

• 边着色

对简单图G的每条边赋予一种颜色，使得相邻边颜色不同,称为图G的一种边着色

• 面着色

对无桥平面图图G的每个面赋予一种颜色,使得相邻的面颜色不同，称为图G的一种面着色

(利用对偶图，可以把平面图G的面着色问题转化为研究对偶图G’的点着色问题； 而通过下面的线图概念，也可以将图的边着色问题转化为点着色问题)

• 线图

假设G是简单图，构造图$L（G）$，G中的边和$L（G）$中的顶点一 一对应 ，如果G中的边$e_1和e_2$相邻，则L（G）中与$e_1和e_2对应的两个顶点间连一条边，称L（G）是G的线图

• 例子：
  (a)χ(G)=1 当且仅当G是离散图

(b)χ(Kn) = n

©(圈图)χ(Cn) = 2, n是偶数时， χ(Cn) = 3，n是奇数时 （n≥3）

(d)(轮图)χ(Wn) = 3 ，n是偶数时， χ(Wn) = 4，n是奇数时 （n≥3）

(e)χ(Gn)=2 当且仅当G是二部图

而点着色问题是NP完全问题Non-deterministic Polynomial，尚不存在有效的方法求解

（给出近似算法）

• (算法)韦尔奇-鲍威尔算法 Welch_Powell（G）

输入: 简单图

输出：图G的一个着色方案

①将图中顶点按度数不增的方式排成排列

②使用一种新颜色对序列的一个顶点进行着色，并且按照序列次序，对与已着顶点不相邻的每一顶点着同样颜色，直至序列末尾。然后从序列中去掉已着色的顶点，得到一个新的序列

③对新序列重复步骤② ， 直至得到空序列

上代码!!!

#%%韦尔奇-鲍威尔算法
import networkx as nx
import matplotlib.pyplot as plt
from Vertex import Vertex
from Graph import Graph
import matplotlib as mplclass New_Vertex(Vertex):  # 某一个具体问题的数据结构需要继承原有数据结构def __init__(self, key):super().__init__(key)self.degree = 0   # 新增类属性(用于节点排序)self.color = 'white'  # 新增类属性(用于记录节点的颜色)# 重写类方法def addNeighbor(self, nbr, weight=0):   # 增加相邻边，默认weight为0'''input:nbr: Vertex objectweight: intreturn:None'''self.connectedTo[nbr] = weightself.degree += 1# 新增类方法 (查看degree)def getDegree(self):return self.degree# 新增类方法, 设置节点颜色def setColor(self, color):self.color = color# 新增类方法, 查看节点颜色def getColor(self):return self.colorclass colorGraph(Graph):def __init__(self):super().__init__()# 重载方法  因为原先Graph中新增节点用的是Vertex节点,但现在是用New_Vertexdef addVertex(self, key):   # 增加节点'''input: Vertex key (str)return: Vertex object'''self.numVertices = self.numVertices + 1newVertex = New_Vertex(key)   # 创建新节点self.vertList[key] = newVertexreturn newVertex# 队列数据结构
class Queue():def __init__(self):self.queue = []def enqueue(self, item):self.queue.append(item)def dequeue(self):return self.queue.pop(0)def isEmpty(self):return self.queue == []def size(self):return len(self.queue)def __iter__(self):return iter(self.queue)# 查看队首元素def see(self):return self.queue[0]class Solution():def createGraph(self, a_dict):graph = colorGraph()for i in a_dict:for j in a_dict[i]:graph.addEdge(i, j)return graph# 排序算法 -快速排序def quickSort(self, a_list):if len(a_list) <= 1:  # 有可能出现left或者right是空的情况return a_listelse:mid = a_list[len(a_list)//2]left = []right = []a_list.remove(mid)for i in a_list:if i[1] > mid[1]:right.append(i)else:left.append(i)return self.quickSort(left) + [mid] + self.quickSort(right)def Welch_Powell(self, g):queue = Queue()Vertices_keys = g.getVertices()Vertices_obj = [g.getVertex(k) for k in Vertices_keys]# 用于储存顶点和他的degreeVertices_deg = [[i, i.getDegree()] for i in Vertices_obj]# 对Vertices_deg进行排序, 然后扔进队列里for i in self.quickSort(Vertices_deg)[::-1]:queue.enqueue(i[0])# 当队列非空color = 0  # 颜色标记# 已着色顶点color_done_vertex = []while not queue.isEmpty():# 对第一个点进行着色frist_vertex = queue.dequeue()frist_vertex.setColor(color)color_done_vertex.append(frist_vertex)for _ in range(queue.size()):# 如果color_done_vertex与i这个节点有连接Connections = []for k in color_done_vertex:Connections += list(k.getConnections())if queue.see() in Connections:# 将节点从队首加到队尾queue.enqueue(queue.dequeue())else:temp = queue.dequeue()temp.setColor(color)color_done_vertex.append(temp)color += 1# 输出结果result = []while Vertices_obj:temp_vertex = Vertices_obj.pop()result.append((temp_vertex.getId(), temp_vertex.getColor()))print(temp_vertex.getId(), ' 的颜色是:', temp_vertex.getColor())return resultif __name__ == '__main__':a_dict = {'a':['b', 'g', 'h'],'b':['a', 'd', 'g', 'h'],'c':['d', 'e'],'d':['b', 'c', 'f'],'e':['c', 'f'],'f':['d', 'e'],'g':['a', 'b', 'h'],'h':['a', 'b', 'g']}s = Solution()graph = s.createGraph(a_dict)result = s.Welch_Powell(graph)G = nx.Graph()for i in a_dict:for j in a_dict[i]:G.add_edge(i, j)color = list(mpl.colors.TABLEAU_COLORS.values())node_color = []for i in result:node_color.append(color[i[1]])plt.clf()pos = nx.spring_layout(G)nx.draw(G, pos, node_color=node_color, font_size= 35,with_labels=True)

结果如下:

很明显这个不是最优解,把f可以换成棕色，c可以换成橙色，这样就用4种颜色来着色

之所以产生这样的问题，其一是：这个算法本身就是一种贪心策略的算法，难免会掉入局部最优

其次是这个算法的第一步是对顶点进行排序，排序的时候相同度数的顶点的顺序其实是不确定的，也会导致结果不优

图的着色就是这么多了，继续学习下一章吧！