图着色问题

来自计算思维百科
跳转至: 导航搜索
图着色问题1.png

图着色问题(Graph Coloring Problem, GCP)又称着色问题,是最著名的NP-完全问题之一。如对右图的子块进行着色,要求相邻子块的颜色不可相同。

基本概念

设无向图G无环,对G的每个顶点涂一种颜色,使相邻的顶点涂不同的颜色,称为图G的一种点着色,简称着色。若能用k种颜色给G的顶点着色,则称G是k-可着色的。

图的着色问题就是要用尽量少的颜色给图着色。

应用范围

图着色问题有着广泛的应用,例如资源分配,交通信号灯管理,物体储藏等等。

使用方法及步骤

对于一项工程,用顶点表示工作,如果两项工作不能同时进行就用一条边连接对应的顶点。工作的资源安排对应这个图的点的着色:着同一种颜色的顶点对应的工作可以安排同样的资源进行,所需的最少资源就是这个图着色所需的最少颜色数。

应用案例

应用1- 会议安排

案例:

学校的学生会下设6个部门,部门的成员如下:部门一={张,李,王},部门二={李,赵,刘},部门三={张,刘,王},部门四={赵,刘,孙},部门五={张,王},部门六={李,刘,王},每个月每个部门都要开一次会,为了确保每个人都能参加他所在部门的会议,这6个会议至少需要安排在几个不同的时间段?

解决步骤:

用顶点v1,v2…v6分别代表部门一,部门二…部门六,2个顶点之间有一条边当且仅当它们代表的委员会成员中有共同的人,如下图所示,该图可以用4种颜色着色,可以看出至少要用4种颜色,v1,v2,v3构成一个三角形,必须用3种颜色,v6和这3个顶点都有关联,必须再用一种颜色。着同一种颜色的顶点代表的部门会议可以安排在同一时间段,而不同颜色代表的部门会议必须安排在不同的时间,故这6个会议至少要安排在4个不同的时间,其中,部门一和部门四,部门二和部门五的会议可以安排在同一时间段。

图着色问题2.png

应用2-无线交换设备的波长分配

案例:

有5台设备,要给每一台设备分配一个波长。如果两台设备靠得太近,则不能给它们分配相同的波长,以防干扰。已知v1和v2,v1和v4,v2和v4,v3跟v4靠得太近。问至少需要几个发射波长。

解决步骤:

以设备为顶点构造一个图,如果两台设备靠得太近,则用一条边连接它们。于是,这个这个图的着色给出一个波长分配方案:给着同一种颜色的设备同一个波长。用顶点v1,v2…v5分别代表5台设备。画出着色图如下,可知至少需要3个发射波长。

图着色问题3.png

可以体现的计算思维

图着色问题体现了计算思维的抽象以及优化思想,把问题抽象成图,清晰条理,从而易于理解及解决。同时,图着色问题常常在解决问题时面对多种可行方案能寻找出一种最佳的方案。