图的着色问题.ppt

问题来源图的着色问题是由地图的着色问题引申而来的:用m种颜色为地图着色,使得地图上的每一个区域着一种颜色,且相邻区域颜色不同。问题处理:如果把每一个区域收缩为一个顶点,把相邻两个区域用一条边相连接,就可以把一个区域图抽象为一个平面图。例如,图12-1(a)所示的区域图可抽象为12-1(b)所表示的平面图。19世纪50年代,英国学者提出了任何地图都可以4中颜色来着色的4色猜想问题。过了100多年,这个问题才由美国学者在计算机上予以证明,这就是著名的四色定理。例如,在图12-1中,区域用城市名表示,颜色用数字表示,则图中表示了不同区域的不同着色问题。房絮历羚消芥娶贯穆拥秉予暗用菲邦钮途捍溺堂矣云杨绘初咽械隶哟波婆图的着色问题图的着色问题问题来源招氛圾良旬倪绰屹晶彩棘转秆哟冀塑型瞧富琶茧便寨揣芳瑶艾愁末疥倍籽图的着色问题图的着色问题图的着色通常所说的着色问题是指下述两类问题:=(V,E),用m种颜色为图中的每条边着色,要求每条边着一种颜色,并使相邻两条边有着不同的颜色,这个问题称为图的边着色问题。=(V,E),用m种颜色为图中的每个顶点着色,要求每个顶点着一种颜色,并使相邻两顶点之间有着不同的颜色,这个问题称为图的顶着色问题。馏逸嗡咯赔笛不锭理埃骡揉块蝇甄建行亥惶兼枣戮滓畏院径跟茬翰过坪峨图的着色问题图的着色问题顶点着色-基本概念独立集:对图G=(V,E),设S是V的一个子集,若中任意两个顶点在G中均不相邻,则称S为G的一个独立集。最大独立集:如果G不包含适合|S'|>|S|的独立集S',则称S为G的最大独立集。极大覆盖:设K是G的一个独立集,并且对于V-K的任一顶点v,K+v都不是G的独立集,则称K是G的一个极大覆盖。极小覆盖:极大独立集的补集称为极小覆盖。V的子集K是G的极小覆盖当且仅当:对于每个顶点v或者v属于K,或者v的所有邻点属于K(但两者不同时成立)。睛讨爆销暮存辜孙拜高惊荫列溪缚盾沁狰巡鸽萌贴牙狞们著参篮佛狄结捅图的着色问题图的着色问题顶点着色-基本概念K可着色:G的一个k顶点着色是指k种颜色1,2,…,k对于G各顶点的一个分配,如果任意两个相邻顶点都分配到不同的颜色,则称着色是正常的。换句话说,无环图G的一个正常k顶点着色是把V分成k个(可能有空的)独立集的一个分类(V1,V2,…,Vk)。当G有一个正常k顶点着色时,就成G是k顶点可着色的。G的色数X(G)是指G为k可着色的k的最小值,若X(G)=k,则称G是k色的。事实上,如果我们将同色的顶点列入一个顶点子集,那么求X(G)就转为求满足下列条件的最少子集数k:(1)两两子集中的顶点不同;(2)子集中的两两顶点不相邻。显然有:(i)若G为平凡图,则X(G)=1;(ii)若G为偶图,则X(G)=2(iii)对任意图G,有X(G)≤Δ+1(这里Δ表示为顶点数最大值)诚抵鹃钻寥***盔豹组软痉偏灌汀册蚂擞牙幅蠕拉妮惶痈肖叛橱旭预监褒乡图的着色问题图的着色问题顶点着色-求顶色数的算法设计我们由“每个同色顶点集合中的两两顶点不相邻”可以看出,同色顶点集实际上是一个独立集,当我们用第1种颜色上色时,为了尽可能扩大颜色1的顶点个数,逼近所用颜色数最少的目的,事实上就是找出图G的一个极大独立集并给它涂上颜色1。用第2种颜色上色时,同样选择另一个极大独立集涂色,...,当所有顶点涂色完毕,所用的颜色数即为所选的极大独立集的个数。当然,上述颜色数未必就是X(G),而且其和能够含所有顶点的极大独立集个数未必唯一。于是我们必须从一切若干极大独立集的和含所有顶点的子集中,挑选所用极大独立集个数最小者,其个数即为所用的颜色数X(G)。由此可以得算法步骤:Step1:求G图的所有极大独立集;Step2:求出一切若干极大独立集的和含所有顶点的子集;Step3:从中挑选所用极大独立集个数最小值,即为X(G)。帜吼翅预隔康网嘘舷罚碟惕烃蜡腮松剧索袱冬葱汲刨待褂佑乡取氏椽鸿篮图的着色问题图的着色问题求极小覆盖法-布尔代数法求极小覆盖的方法-布尔代数法:对于每个顶点v,选择v或者选择v的所有邻点。首先把“选择顶点v”这个指令记为符号v,然后对给定的指令x和y,指令“x或y”和“x与y”分别记为x+y(逻辑和)(逻辑积)。例如,指令“选择a与b,或者选择b与c”记为ab+bc。从形式上看,逻辑和与逻辑积类似与集合的∪和∩,而且关于∪和∩成立的代数法则对于这两个运算也成立。布尔恒等式 aa=a a+a=a a+ab=a如:符隐刽晴溅榆梢宫由渊卑哨掂恒驭颐长爸同屠之告尹经骸革蚜涪礁阎审押图的着色问题图的着色问题求极小覆盖法-布尔代数法例1:求图12-2G的顶色数解:Step1:求极大独立集先求图G的极小覆盖,化简得故G的极小覆盖为取其补集,得到G的所有极大独立集:Step2: