图的m着色问题

01问题描述

图着色问题定义问题定义图m可着色判定问题：给定无向连通图G和m种颜色，为每个顶点分配一种颜色，要求相邻顶点颜色不同。优化问题图m可着色优化问题：求最小颜色数m，使图满足上述条件，该最小值称为图的色数。

四色猜想与平面图010203四色猜想平面图转化模型意义任何平面或球面地图仅需四种颜色即可使相邻区域颜色不同。将地图着色转化为平面图着色问题：每个国家抽象为顶点，相邻关系抽象为边。抽象图论模型在解决实际地理问题中具有强大表达能力，四色猜想推动了图着色研究的发展。

02建立模型

邻接矩阵与颜色编码用邻接矩阵a表示无向图G=(V,E)，a[i][j]=1表示顶点i与j相邻