实验12图m的着色问题.doc

给定 无向连通图G=(V,E) 和 c种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果一个图最少需要c种颜色才能使图中每条边连接的2个顶点着不同颜色，则称c为该图的色数。  著名的 四色定理 就是指每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。