图着色
图形着色是将颜色分配给图形G的每个顶点的过程，以使相邻的顶点不会获得相同的颜色。目的是在给图形着色时最大程度地减少颜色数量。给图G上色所需的最小数量的颜色称为该图的色数。图形着色问题是NP完全问题。
着色图形的方法
为具有n个顶点的图G着色所需的步骤如下-
步骤1-以某种顺序排列图的顶点。
步骤2-选择第一个顶点并用第一种颜色对其进行着色。
步骤3-选择下一个顶点，并用编号最小的颜色对其进行着色，该颜色在与之相邻的任何顶点上都未着色。如果所有相邻的顶点都以此颜色上色，请为其分配新的颜色。重复此步骤，直到所有顶点都着色为止。
例
在上图中，第一个顶点a为红色。由于顶点a的相邻顶点再次相邻，因此顶点b和顶点d分别用不同的颜色（绿色和蓝色）着色。然后，将顶点c着色为红色，因为没有相邻的c顶点着色为红色。因此，我们可以用3种颜色为图表着色。因此，该图的色数为3。
图形着色的应用
图形着色的一些应用包括-
注册分配
映射着色
二部图检查
移动无线电频率指配
制作时间表等
以上是 图着色 的全部内容， 来源链接： utcz.com/z/316234.html
