《数学建模之着色精品文稿.ppt》由会员分享，可在线阅读，更多相关《数学建模之着色精品文稿.ppt（100页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模之着色第1页，本讲稿共100页记为记为 正常着色就是相邻的边用不同的颜色着，所用的最少正常着色就是相邻的边用不同的颜色着，所用的最少颜色数就是边色数。颜色数就是边色数。目前为止，还没有一个好目前为止，还没有一个好的算法求一般图的边色数。的算法求一般图的边色数。第2页，本讲稿共100页例例设设n个人中有些要进行俩俩会谈，每次会谈需要一个个人中有些要进行俩俩会谈，每次会谈需要一个单元时间。问最少要用多少单元时间才能安排完所有会单元时间。问最少要用多少单元时间才能安排完所有会谈？谈？第3页，本讲稿共100页例例设设n是正整数，且是正整数，且Ai(i=1,2,2n+1)是某集合是某集合B的子集
2、的子集,且设且设(a)Ai=2n;(b)AiAj=1,1i j2n+1;(c)B中每个元素至少属于两个子集中每个元素至少属于两个子集Ai.问对怎样的问对怎样的n，可以对，可以对B中每个元素贴一张写有中每个元素贴一张写有0或或1的标签，使得每个的标签，使得每个Ai中恰有中恰有n个贴了个贴了0标签的元素标签的元素?解解 A1,A2,A2n+1为顶点集合，当且仅当为顶点集合，当且仅当Ai与与Aj有共有共同元素同元素bk时，在时，在Ai与与Aj之间连一条边，此边的两个端点之间连一条边，此边的两个端点为为Ai与与Aj之间的元素之间的元素bk.由由(b)知，得到知，得到第4页，本讲稿共100页得到了一个完
3、全图得到了一个完全图K2n+1,由已知，由已知，B中每个元素都对中每个元素都对应应K2n+1中的一条边。约定标中的一条边。约定标0的元素着红色，标的元素着红色，标1的的元素着绿色，连接两红元素的边着红色，连接两绿元素着绿色，连接两红元素的边着红色，连接两绿元素的边着绿色。问题转化为完全图元素的边着绿色。问题转化为完全图K2n+1，的边用，的边用红、绿两种颜色着色，使得每个顶红、绿两种颜色着色，使得每个顶Ai皆与皆与n条红边相条红边相关联。关联。K2n+1共有共有n(2n+1)条边，当条边，当n为奇数时，无解为奇数时，无解.对于对于n为偶数时，用数学归纳法证明问题有解。为偶数时，用数学归纳法证明
4、问题有解。假设假设n=2时，时，K2n+1=5,每个每个Ai有有4个元素，这时有解。个元素，这时有解。第5页，本讲稿共100页证明证明n=2(k+1)时成立时成立.假设假设n=2k时问题有解。时问题有解。第6页，本讲稿共100页引理引理1设设G不是奇圈的连通图，则不是奇圈的连通图，则G存在一个二边着色，存在一个二边着色，使两种颜色在每个度数不小于使两种颜色在每个度数不小于2的顶点上表现。的顶点上表现。若与顶点若与顶点v关联的某边染有颜色关联的某边染有颜色i，则称颜色，则称颜色i在顶点在顶点v上上表现表现。证明证明假设假设G是非平凡图。是非平凡图。G是是Euler图时。若图时。若G是偶圈，则是偶
5、圈，则G的正常的正常2边着边着色具有所要求的性质。否则，色具有所要求的性质。否则，G必有一个度数至必有一个度数至少为少为4的点的点v0.设设v0e1v1e2env0是是G的的Euler环游，并环游，并且设且设 E1=eii是奇数是奇数，E2=eii是偶数是偶数第7页，本讲稿共100页则则G的二边着色的二边着色(E1，E2)具有所要求的性质，因为具有所要求的性质，因为G的每个顶点都是的每个顶点都是v0e1v1e2env0的内点。的内点。(2)G不是不是Euler图时，则添加一个新的顶点图时，则添加一个新的顶点v0,并将它和并将它和G的每个奇数度的点连接起来，构成一个新图的每个奇数度的点连接起来，
6、构成一个新图G*。显然。显然G*是是Euler图。设图。设v0e1v1e2en*v0是是G*的的Euler环游，并且环游，并且类似地构造类似地构造E1,E2,易证二边着色易证二边着色(E1E，E2E)具有所要求的性质具有所要求的性质.第8页，本讲稿共100页定义定义若若C1,C2是对是对G的两种的两种k边着色，且满足边着色，且满足其其中中c1(v)是是C1着着色色时时，顶顶点点v关关联联的的边边中中的的颜颜色色数数，其其中中c2(v)是是C2着着色色时时，顶顶点点v关关联联的的边边中中的的颜颜色色数数,则则称称C2是是对对C1的一种的一种改善改善，不能改善的，不能改善的k边着色称为边着色称为最
7、佳最佳k边着色边着色。第9页，本讲稿共100页引理引理2设设C=(E1,E2,Ek)是是G的一个最佳的一个最佳k边着色。如边着色。如果有一个顶果有一个顶v0，又存在两种颜色，又存在两种颜色i与与j，使得，使得i色在色在v0顶关顶关联的边中不出现，而联的边中不出现，而j色在色在v0顶关联的边中至少出现两次，顶关联的边中至少出现两次，则由则由EiEj导出的子图中含导出的子图中含v0的连通分支是一个奇圈。的连通分支是一个奇圈。证证明明设设GEiEj中中包包含含v0的的连连通通分分支支为为H.假假设设H不不是是奇奇圈圈，由由引引理理1，则则H存存在在一一个个二二边边着着色色，使使两两种种颜颜色色在在每
8、每个个度度数数不不小小于于2的的顶顶点点上上表表现现。以以这这种种方方式式用用颜颜色色i与与j重重新给新给H着色，得到一个着色，得到一个G的一个新的的一个新的k边着色边着色用用c(v)表示顶点表示顶点v关联的边中的颜色数关联的边中的颜色数,则有则有第10页，本讲稿共100页由于两种颜色由于两种颜色i和和j都都在在u上表现，且有上表现，且有于是，于是，这与这与C的选择矛盾。由此推出的选择矛盾。由此推出H是奇圈是奇圈。第11页，本讲稿共100页定理定理若若G是二分图，则是二分图，则证明：设证明：设G是具有是具有的图，且的图，且C=(E1,E2,E)是是G的一个最佳的一个最佳k边着色，并边着色，并设
9、设u是满足是满足c(u)N,则存在则存在无公共边的匹配无公共边的匹配M1和和N1，使得，使得证明证明令令H=GM N，则则H中每个顶点至多与一条中每个顶点至多与一条M的边及一条的边及一条N的边相的边相关联，因此关联，因此dH(v)=1or2 v V(H)第15页，本讲稿共100页从而从而H的每个分支都是一个圈或一条路，由的每个分支都是一个圈或一条路，由M及及N中的边交错组成。但中的边交错组成。但 M M，H中一定存中一定存在一个分支是一条路在一个分支是一条路P，且其起点和终点都是，且其起点和终点都是M饱饱和的。令和的。令P=v0e1v1,e2n+1v2n+1,v0e1v1,e2v2e2n+1v
10、2n+1取取M1=(M-e1,e3,e2n+1)e2,e4,e2n N1=(N-e2,e4,e2n)e1,e3,e2n+1.第16页，本讲稿共100页定理定理G是二分图，是二分图，G的最大度数的最大度数p，则，则G内存在内存在p个个无公共边的匹配无公共边的匹配M1,M2,Mp,使得使得且对且对1 i p,证明证明由于由于G是二分图，是二分图，E(G)可以划分成可以划分成(G)个匹配个匹配第17页，本讲稿共100页故对于故对于p,存在存在p个无公共边的匹配个无公共边的匹配使得使得对边数之差大于对边数之差大于1的匹配反复应用上述引理，可得的匹配反复应用上述引理，可得p个两两个两两无无公共边的匹配公
11、共边的匹配M1,M2,Mp,满足定理的条件满足定理的条件.第18页，本讲稿共100页例例4名教师，名教师，5个班级，教学要求如下：个班级，教学要求如下：试排出试排出4间教室，间教室，3间教室和间教室和2间教室的课程表。间教室的课程表。解解以以X=x1,x2,x3,x4,Y=y1,y2,y3,y4,y5,做一二分图做一二分图G,xi与与yj之间连之间连aij条边相连条边相连.于是于是(G)=4,E(G)=11.第19页，本讲稿共100页x1x2x3x4y1y2y3y4y5安排安排4个节课，个节课，可安排可安排4个教室个教室4个节课的课表。个节课的课表。红线：第红线：第1节节兰线：第兰线：第2节节
12、绿线：第绿线：第3节节黑线：第黑线：第4节节第20页，本讲稿共100页x1x2x3x4y1y2y3y4y5红线：第红线：第1节节兰线：第兰线：第2节节绿线：第绿线：第3节节黑线：第黑线：第4节节123456x1y1y1y3y4x2y2y4x3y3y4y2x4y4y5第21页，本讲稿共100页x1x2x3x4y1y2y3y4y5红线：第红线：第1节节兰线：第兰线：第2节节绿线：第绿线：第3节节黑线：第黑线：第4节节123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43个教室个教室第22页，本讲稿共100页x1x2x3x4y1y2y3y4y5可安排可安排2个教室个教室6个节课的
13、课表。个节课的课表。第23页，本讲稿共100页x1x2x3x4y1y2y3y4y5红线：第红线：第1节节兰线：第兰线：第2节节绿线：第绿线：第3节节黑线：第黑线：第4节节123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43个教室个教室第24页，本讲稿共100页x1x2x3x4y1y2y3y4y5红线：第红线：第1节节兰线：第兰线：第2节节绿线：第绿线：第3节节黑线：第黑线：第4节节123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y42个教室？个教室？第25页，本讲稿共100页2.点着色点着色 着色着色:如果使用如果使用n种颜色把图种颜色把图G的每个顶点
14、都分的每个顶点都分配一种颜色，且使得相邻顶点异色，则称此为配一种颜色，且使得相邻顶点异色，则称此为对对G的顶点正常的顶点正常n着色。着色。G的顶点正常着色中所的顶点正常着色中所需颜色数的最小值称为需颜色数的最小值称为G的的顶色数顶色数，简称，简称色数色数。用用(G)表示，色数为表示，色数为k的图称为的图称为k色图色图。第26页，本讲稿共100页第27页，本讲稿共100页点色数的简单性质点色数的简单性质l(G)=1 G是零图是零图 l(Kn)=nl(G)=2G是非零图二部图是非零图二部图l(Cn)=2,n偶数偶数(Wn)=3,n奇奇数数3,n奇数奇数4,n偶偶数数第28页，本讲稿共100页(G)
15、上界上界定理定理1(G)(G)+1证明证明 v V(G),G(v)=u|(u,v)E(G),|G(v)|(G),给给 G(v)中顶点着色至多需要中顶点着色至多需要(G)种颜色种颜色,所以至少还剩一种颜色可用来给所以至少还剩一种颜色可用来给v着色着色.定理定理2(Brooks):若若G连通、非完全图连通、非完全图Kn(n 3)、非非奇圈奇圈,则则(G)(G).说明说明:n=1G=K1,n=2:连通连通G=K2 第29页，本讲稿共100页l例例 Petersen图图=3.l解解1:由由Brooks定理定理,=3.又图中有奇圈又图中有奇圈,3.所所以以=3.l解解2:存在如下存在如下3-着色着色,=
16、3.又图中有奇圈又图中有奇圈,3.所所以以=3.第30页，本讲稿共100页例例(K6)=6(W6)=4(W5)=3(S6)=2(C6)=2(C5)=3第31页，本讲稿共100页应用：安全装箱问题，考试安排问题，信道分配问题应用：安全装箱问题，考试安排问题，信道分配问题等。等。以每种货物为一顶点，仅当两种货物放在一个箱子以每种货物为一顶点，仅当两种货物放在一个箱子里不安全时，在两种货物对应的顶点之间连一边，构成里不安全时，在两种货物对应的顶点之间连一边，构成图图G。如果求得如果求得(G),对对G用用(G)种颜色着色，同色种颜色着色，同色的顶点对应的货物放在同一箱子中，所需箱子的的顶点对应的货物放
17、在同一箱子中，所需箱子的最小数目为最小数目为(G)。第32页，本讲稿共100页下面给下面给出一种近似算法出一种近似算法-最大度数优先最大度数优先的的Welsh-Powell算法算法.这个算法给出了一个较好的着色方法这个算法给出了一个较好的着色方法,但不是最有但不是最有效的方法效的方法,即所用的颜色数不一定是最少的即所用的颜色数不一定是最少的.第33页，本讲稿共100页最大度数优先最大度数优先的的Welsh-Powell算法算法 设设G=(V,E),),V=v1,v2,vn,且不妨假设且不妨假设d(v1)d(v2)d(vn).).c1,c2,cn为为n种不同的颜色种不同的颜色.令有序集令有序集C
18、i=c1,c2,ci,i=1,2,n.j=1.转向转向.给给vj 着着Cj 的第一个颜色的第一个颜色Cj 1.若若j=n 时时,停停;否则否则,转向转向.kj,若若vk 和和vj 相邻相邻,令令Ck=CkCj 1.j=j+1,转向转向.第34页，本讲稿共100页信道分配问题：信道分配问题：在无线传输中，发射台所用频率从小到大编号，在无线传输中，发射台所用频率从小到大编号，称为信道。用同一信号的两个台的距离不得小于一称为信道。用同一信号的两个台的距离不得小于一个常数个常数d，问各台至少需要几个不同的信道？，问各台至少需要几个不同的信道？以发射台为顶点，仅当发射台间的距离小于以发射台为顶点，仅当发
19、射台间的距离小于d时，在两发射台对应的顶点之间连一边，构成图时，在两发射台对应的顶点之间连一边，构成图G。(G)为所求为所求。第35页，本讲稿共100页 应用：药品存储问题，考试安排问题，信道应用：药品存储问题，考试安排问题，信道分配问题等。分配问题等。以每种药品为一顶点，仅当两种药品放在一间房以每种药品为一顶点，仅当两种药品放在一间房子里不安全时，在两种药品对应的顶点之间连一边，子里不安全时，在两种药品对应的顶点之间连一边，构成图构成图G。如果求得如果求得(G),对对G用用(G)种颜色着色，种颜色着色，同色的顶点对应的药品放在同一间房子中，所需房同色的顶点对应的药品放在同一间房子中，所需房间
20、的最小数目为间的最小数目为(G)。第36页，本讲稿共100页信道分配问题：信道分配问题：在无线传输中，发射台所用频率从小到大编在无线传输中，发射台所用频率从小到大编号，称为信道。用同一信号的两个台的距离不得号，称为信道。用同一信号的两个台的距离不得小于一个常数小于一个常数d，问各台至少需要几个不同的信道？，问各台至少需要几个不同的信道？以发射台为顶点，仅当发射台间的距离小于以发射台为顶点，仅当发射台间的距离小于d时时，在两发射台对应的顶点之间连一边，构成，在两发射台对应的顶点之间连一边，构成图图G。(G)为所求为所求。第37页，本讲稿共100页特殊图的色数特殊图的色数零图：零图：(G)=1完全
21、图完全图Kn：(G)=nG是一条回路：是一条回路：(G)=2若若|V|是偶数是偶数(G)=3若若|V|是奇数是奇数G是一棵非平凡树：是一棵非平凡树：(G)=2(G)=2的充要条件是的充要条件是:(a)|E|1；(b)G中不存中不存在边数为奇数的回路。（此时在边数为奇数的回路。（此时G为二部图）为二部图）若若G1、G2为为G的两个连通分支，则的两个连通分支，则(G)=max(G1),(G2)第38页，本讲稿共100页定理定理1对对G=(V,E)，=maxdeg(vi)|vi V，则，则(G)+1。定理定理2(Brooks)设设G=(V,E)是简单连通图，但不是完全图，是简单连通图，但不是完全图，
22、不是奇数长度圈，不是奇数长度圈，=maxdeg(vi)|vi V 3，则，则(G),即即G是是-可着色的可着色的。l定理给出了色数的一个上限，但很不精确。定理给出了色数的一个上限，但很不精确。Brooks定定理也说明只存在两类满足理也说明只存在两类满足(G)=+1的的图。图。例例二部图可二部图可2着色，但是着色，但是 可以相当大。可以相当大。第39页，本讲稿共100页Hajs猜想猜想若若G是是n色图，则色图，则G包含包含Kn的一个同胚的一个同胚图。图。n=1,2显然，显然，n=3,4已证，其他未决已证，其他未决。四色猜想四色猜想任何平面图都是任何平面图都是4-可着色的。可着色的。由于存在着不可
23、由于存在着不可3-着色的平面图着色的平面图K4，4色问题若可色问题若可证明，将是平面图色数问题的最佳结果。证明，将是平面图色数问题的最佳结果。五色定理五色定理任何简单平面图都是任何简单平面图都是5-可着色的可着色的。第40页，本讲稿共100页色数色数G=(V,E)为简单图，为简单图，vi,vj为其中不相邻顶点。为其中不相邻顶点。为在为在G中添加边中添加边(vi,vj)得到的图，得到的图，为在为在G中合中合并并vi,vj，其他顶点与其关系不变，并合并多重边，其他顶点与其关系不变，并合并多重边（称为收缩（称为收缩vi,vj）得到的图。则有：）得到的图。则有：(G)=min(),()例例ijijij
24、G第41页，本讲稿共100页例例如图，如图，求求(G)。(K5)=5(K4)=4(K4)=4(K3)=3第42页，本讲稿共100页定义定义:对给定的图对给定的图G=(V,E)，PG(k)表示以表示以k种颜给种颜给G进行进行正常着色的方案数目正常着色的方案数目。两种方案相同：同一个结点着同一种颜色。两种方案相同：同一个结点着同一种颜色。可以用结点集到颜色集的函数表述。可以用结点集到颜色集的函数表述。当当k0。4色猜想：对平面图色猜想：对平面图G,PG(4)0（存在（存在4-着色方案着色方案）.例如，例如，PK3(3)=6色多项式色多项式第43页，本讲稿共100页PK3(3)=6abcabcabc
25、abcabcabc第44页，本讲稿共100页若干特殊图的若干特殊图的PG(k)1）零图：）零图：G=(V,E)，n=|V|，|E|=0，PG(k)=kn2）树：根节点在）树：根节点在k种颜色中任取，非根节点选取与其种颜色中任取，非根节点选取与其父亲节点不同的颜色。父亲节点不同的颜色。PG(k)=k(k-1)n-1图图G的色多项式为的色多项式为k(k-1)n-1，当且仅当，当且仅当G是具有是具有n个个顶点的树。顶点的树。3）完全图：）完全图：PG(k)=k(k-1)(k-2)(k-n+1)第45页，本讲稿共100页定理定理3设简单图设简单图G，e=vivj为为G的一条边，记的一条边，记G-e为从
26、为从G中去掉中去掉e后得到的图；后得到的图；G*e为从收缩边为从收缩边e后得到的后得到的图，并记图，并记PG*e(k)和和PG-e(k)分别为分别为G*e和和G-e的的k染色方染色方案数，则案数，则PG(k)=PG-e(k)-PG*e(k)。(1)vivj同色；同色；(2)vivj异色异色第46页，本讲稿共100页推论推论1对任何图对任何图G=(V,E)，n n=|V|，e e=|E|，PG(k)都是都是k的整系数的整系数n n次多项式，且：次多项式，且：首项为首项为kn n；次项为次项为-e ekn n-1；常数项为常数项为0；各项系数的符号正各项系数的符号正-负交替。负交替。证明证明 对图
27、对图G的边数的边数e e进行归纳法证明进行归纳法证明.约定重边变成单边，约定重边变成单边，不影响顶点的正常着色。不影响顶点的正常着色。e e=0时，有时，有PG(k)=kn n,成立。成立。假设假设e e n-1时，成立。考虑时，成立。考虑e e=n的情形的情形.则则G-e的边数为的边数为n-1,G*e等于或小于等于或小于n-1，由归纳法假设，由归纳法假设，PG-e(k)=kn n-(e e-1)kn n-1+an n-2kn n-2-an n-3kn n-3+(-1)n n-1a1k第47页，本讲稿共100页PG*e(k)=kn-1n-1-e ekn n-2+bn n-3kn n-3-bn
28、n-4kn n-4+(-1)n n-2b1k其中其中e e是简单图是简单图G*e的边数，的边数，ai,bi 0.由公式由公式PG(k)=PG-e(k)-PG*e(k)PG(k)=kn n-(e e-1)kn n-1+an n-2kn n-2-an n-3kn n-3+(-1)n n-1a1k-kn-1n-1-e ekn n-2+bn n-3kn n-3-bn n-4kn n-4+(-1)n n-2b1k=kn n-e ekn n-1+(an n-2+e e)kn n-2-(an n-3+bn n-3)kn n-3+(-1)n n-1(a1+b1)k推论推论1证明了函数证明了函数PG(k)具有多
29、项式形式。具有多项式形式。色数多项式色数多项式:上述函数上述函数PG(k)称为图称为图G的色数多项式。的色数多项式。第48页，本讲稿共100页减边法减边法:求给定图求给定图G的色数多项式的色数多项式原理：原理：定理定理3，PG(k)=PG-e(k)-PG*e(k)在图在图G中任取一边中任取一边e；在图在图G中去掉中去掉e，得新图，得新图G-e在图在图G中收缩中收缩e的两端点，得新图的两端点，得新图G*e，由上述公式有，由上述公式有PG(k)=PG-e(k)-PG*e(k)继续分解继续分解G-e和和G*e，直到最后全部为零图。，直到最后全部为零图。利用利用n阶零图的阶零图的P(k)=kn构造图构
30、造图G的色数多项式。的色数多项式。第49页，本讲稿共100页例例 如图，求其色数多项式。如图，求其色数多项式。减边法比较适合于求稀疏图的色数多项式。减边法比较适合于求稀疏图的色数多项式。P（,k）=P（,k）-P（,k）=P(,k）-P（,k）-P(,k）-P（,k）=(k3-k2)-(k2-k)=k3-2k2+k第50页，本讲稿共100页加边法加边法:求给定图求给定图G的色数多项式的色数多项式原理：定理原理：定理3，PG(k)=PG-e(k)-PG*e(k)在图在图G中任取两个不相邻顶点中任取两个不相邻顶点u,v；在图在图G中加上中加上(u,v)，得新图，得新图G+e，在图在图G中收缩中收缩
31、(u,v)，得新图，得新图G*e，由上述讨论有，由上述讨论有PG(k)=PG+e(k)+PG*e(k)继续分解继续分解G+e和和G*e，直到最后全部为完全图。，直到最后全部为完全图。利用利用n阶完全图的阶完全图的P(k)=k(k-1)(k-2)(k-n+1)构造图构造图G的色数多项式的色数多项式。加边法比较适合于求稠密图的色数多项式。加边法比较适合于求稠密图的色数多项式。第51页，本讲稿共100页G的的色数多项式是色数多项式是k(k-1)n-1G是是n个顶点的树个顶点的树.顶点顶点是是n n的树的树T的的色数多项式是色数多项式是k(k-1)n n-1.对顶点数对顶点数n n进行归纳证明。进行归
32、纳证明。当当n n=1,2时，成立。假设时，成立。假设n n n-1时，成立，考虑时，成立，考虑n n=n的情的情形。此时，考虑形。此时，考虑T的一个叶点的一个叶点v0,记记T1=T-v0,则由归纳假则由归纳假设，设，PT1(k)=k(k-1)n n-2对于对于T1的每一种正常的每一种正常k着色，着色，v0在在T中着色时有中着色时有k-1种种选择，因此选择，因此PT(k)=(k-1)k(k-1)n n-2=k(k-1)n n-1.第52页，本讲稿共100页能否判断一个多项式为某一个图的色数多项式？能否判断一个多项式为某一个图的色数多项式？说明说明k4-3k3+k2不是色数多项式。不是色数多项式
33、。该多项式满足推论的条件，设它是图该多项式满足推论的条件，设它是图G的色多项式。的色多项式。则则V(G)=4,E(G)=3.若若G是连通的，是连通的，G是树，于是是树，于是PG(k)=k(k-1)3=k4-3k3+k2-k.若若G不连通，则不连通，则G只能如图所示，于是只能如图所示，于是PG(k)=kk(k-1)(k-2)=k4-3k3+2k2.第53页，本讲稿共100页例例如图，求其色数多项式。如图，求其色数多项式。32=k(k-1)(k-2)(k-3)(k-4)+3k(k-1)(k-2)(k-3)+2k(k-1)(k-2)=k(k-1)(k-2)(k2-4k+5)第54页，本讲稿共100页
34、4 4 独立集、支配集和覆盖集独立集、支配集和覆盖集同同色色顶顶点点构构成成的的顶顶点点集集：顶顶点互不相邻点互不相邻红色顶点集构成一个独立集。红色顶点集构成一个独立集。第55页，本讲稿共100页独立集：独立集：图图G=(V,E)，I V，若，若I中中任意两个顶点任意两个顶点都不相邻，则称都不相邻，则称I为为G的一个独立集的一个独立集.例例独立集：独立集：b,d,b,f,a,c,b,d,f,acbdef4.1独立集独立集第56页，本讲稿共100页极大独立集：如果极大独立集：如果I为为G的一个独立集的一个独立集，且，且 u V-I,I u不不是是G的的独独立立集集，则则称称I为为G的的一一个个极
35、极大大独独立立集集。设设G的所有独立集为的所有独立集为I1、I2、Ik，记，记称为称为G的的独立数独立数。最大独立集：最大独立集：G的一个独立集的一个独立集Ii称为称为G的一个最大的一个最大独立集若独立集若|Ii|=。第57页，本讲稿共100页例例求最大独立集问题是求最大独立集问题是NP完全的。完全的。独立集：独立集：b,d,b,f,a,c,b,d,f,极大独立集：极大独立集：a,c,b,e,b,d,f 最大独立集：最大独立集：b,d,f =3acbdef第58页，本讲稿共100页定义定义设设G=(V,E)是简单无向图，同时将是简单无向图，同时将G的邻接矩阵的邻接矩阵的第的第i行与第行与第j行
36、，第行，第i列与第列与第j列互换，称为一次列互换，称为一次平平移变换移变换。平移变换不影响图的结点之间的连接关系，仅仅改变平移变换不影响图的结点之间的连接关系，仅仅改变了了i,j 编号。也就是说，邻接矩阵的平移变换对应于编号。也就是说，邻接矩阵的平移变换对应于图中结点的一个重新编号。图中结点的一个重新编号。定理定理1设设G=(V,E)是具有是具有n个结点的简单无向图，个结点的简单无向图，A是是其邻接矩阵，且其邻接矩阵，且A具有如下形式：具有如下形式：(1)极大独立集的求法：极大独立集的求法：第59页，本讲稿共100页其中其中令令若若，则其已确定一极，则其已确定一极大独立集大独立集其中其中vt(
37、1 t i)与下三与下三角矩阵的第角矩阵的第t行对应。行对应。第60页，本讲稿共100页证明证明则则必有一个元素为必有一个元素为1，不妨设，不妨设由矩阵由矩阵A可知，可知，akj=0,1 k,j i，即结点即结点考虑考虑A21,因因互不相邻。互不相邻。说明说明vj与与vk相邻。即相邻。即中任何一个结点都与中任何一个结点都与I=v1,v2,vi相邻。相邻。I=v1,v2,vi是极大一独立集是极大一独立集.第61页，本讲稿共100页形如形如(1)，满足定理条件的邻接矩阵称为，满足定理条件的邻接矩阵称为标准型标准型.定理定理2 A是简单无向图是简单无向图G=(V,E)的的邻接矩阵，则总可以经邻接矩阵
38、，则总可以经过若干次平移变换，将过若干次平移变换，将A化为标准型，从而得到化为标准型，从而得到G的一的一个极大独立集个极大独立集.acbdef第62页，本讲稿共100页acbdef第63页，本讲稿共100页acbdef第64页，本讲稿共100页G的所有极大独立集的求法：的所有极大独立集的求法：借助布尔变量的运算求借助布尔变量的运算求G的所有极大独立集。的所有极大独立集。已知简单无向图已知简单无向图G=(V,E),V=v1,v2,vn,约定：约定：(1)G的每个点的每个点vi作为一个布尔变量；作为一个布尔变量；(2)“”,“”表示表示“与与”运算和运算和“或或”运算，即布运算，即布尔尔积与布尔和
39、。积与布尔和。布尔运算性质与集合的运算性质类似。布尔运算性质与集合的运算性质类似。图图G的过点的过点vi,vj的边对应一布尔积的边对应一布尔积vi vj.做布尔表达做布尔表达式：式：第65页，本讲稿共100页中每一项中每一项vi vj对应对应G的一条边，的一条边，表示对所有边求布尔和。利用德摩根定律有，表示对所有边求布尔和。利用德摩根定律有，设设与与都是都是v1,v2,vn的表达式。的表达式。因独立集不包含任何一边的两个端点，因独立集不包含任何一边的两个端点，在独立集上取值为在独立集上取值为0；反之若；反之若 =0，则对应的点集为独，则对应的点集为独立集。立集。在独立集上取值为在独立集上取值为
40、1；反之若；反之若点集为独立集。点集为独立集。则对应的则对应的考虑所有考虑所有的点集合，即为的点集合，即为第66页，本讲稿共100页所有的极大独立集。所有的极大独立集。v6v5v4v1v2v3第67页，本讲稿共100页v6v5v4v1v2v3极大独立集极大独立集第68页，本讲稿共100页利用极大独立集可以得到一个正常点着色的算法：利用极大独立集可以得到一个正常点着色的算法：定义定义 若将图若将图G=(V,E)的顶点集合的顶点集合V划分成划分成k个子集个子集合：合：V1,V2,Vk，即即且且，Vi是是的极大独立的极大独立集，集，i=1,2,k.其中其中V0=,将将Vi中的顶点染上中的顶点染上i色
41、，则称这种色，则称这种上色是对图上色是对图G的一种的一种k点点规范着色规范着色。规范着色是正常着色。下面证明图规范着色是正常着色。下面证明图G可以可以k点点正正常点着色则存在常点着色则存在k点点规范着色规范着色。第69页，本讲稿共100页证明证明 设设G有正常着色有正常着色C=(V1,V2,Vk),即即且且C是是k点规范着色点规范着色.若若V1是极大独立，则将是极大独立，则将V1中的点上中的点上1色。不然，色。不然，V1是是G的一个独立集，从的一个独立集，从V-V1中调一些点放入中调一些点放入V1中，总可以将中，总可以将V1扩成扩成G的极大独立集的极大独立集,这是这是 定理定理 如果图如果图G
42、是可以是可以k点点正常点着色的，则正常点着色的，则G存在存在k点点规范着色规范着色。,Vi中的顶点染上中的顶点染上i色色,调整调整Vi，分别变为分别变为第70页，本讲稿共100页对图对图G-V1重复上面的过程，最后便得到规范重复上面的过程，最后便得到规范k点着色。点着色。v1v3v2v4v5V1=v5是是G的极大独立集的极大独立集.V2=v2,v4是是G-V1的极大的极大独立集独立集.V3=v1,v3是是G-V1-V2的极大的极大独立集独立集.V=V1V2V3,得到一规范着色。得到一规范着色。用第一种颜色为图上色时，尽可能多的将一些无色顶上用第一种颜色为图上色时，尽可能多的将一些无色顶上色，直
43、至不能再多为止，一直保持邻顶不同色；接着色，直至不能再多为止，一直保持邻顶不同色；接着第71页，本讲稿共100页点覆盖点覆盖:图图G=(V,E)，K V，若若G的任何一条边都与的任何一条边都与K中顶点关联，则称中顶点关联，则称K为为G的一个点覆盖（集）。的一个点覆盖（集）。例例acbdef点覆盖：点覆盖：a,b,c,e,a,b,c,d,e,a,c,e,极小点覆盖、点覆盖数、最小点覆盖。极小点覆盖、点覆盖数、最小点覆盖。4.2点覆盖点覆盖第72页，本讲稿共100页极小点覆盖：极小点覆盖：K是是G的一个极小点覆盖的一个极小点覆盖K为为G的一的一个点覆盖且个点覆盖且 K1 K，K1不是不是G的点覆盖
44、。的点覆盖。点覆盖数：点覆盖数：设设G的所有点覆盖为的所有点覆盖为C1、C2、Cl，记，记称为称为G的点覆盖数。的点覆盖数。最小点覆盖：最小点覆盖：G的一个点覆盖的一个点覆盖Ci称为称为G的一个最小点的一个最小点覆盖若覆盖若|Ci|=。第73页，本讲稿共100页例例点覆盖：点覆盖：a,b,c,d,e,a,b,c,e,a,c,e,极小点覆盖：极小点覆盖：a,c,e,b,d,e,f,a,c,d,f最小点覆盖：最小点覆盖：a,c,e=3acbdef第74页，本讲稿共100页4.3独立集与覆盖集的关系独立集与覆盖集的关系独立集与覆盖集在一个图中具有独立集与覆盖集在一个图中具有互补性互补性。(1)I为为
45、G=(V,E)的独立集的独立集V-I是是G的覆盖集。的覆盖集。(2)I为为G=(V,E)的极大独立集的极大独立集V-I是是G的极小覆盖集。的极小覆盖集。(3)+=V.若若I是是G的独立集，即的独立集，即I中任何两个顶点在中任何两个顶点在G中都不相中都不相邻，因此邻，因此E中每条边至少有一个端点在中每条边至少有一个端点在V-I中，即中，即V-I是是G的覆盖集；反之，若的覆盖集；反之，若V-I是是G的一个覆盖，即每条边的一个覆盖，即每条边至少在至少在V-I中，则中，则I中没有相邻的顶点，中没有相邻的顶点，I是是G的独立的独立集。集。第75页，本讲稿共100页极小覆盖一种求法极小覆盖一种求法求覆盖集
46、：求覆盖集：v V，或者，或者v盖住与盖住与v关联的所有边，关联的所有边，或者是其邻点盖住与或者是其邻点盖住与v关联的边，可以写成关联的边，可以写成第76页，本讲稿共100页极小覆盖集可由下面的式子给出：极小覆盖集可由下面的式子给出：展开式中每一项是一个极小覆盖集。展开式中每一项是一个极小覆盖集。acbdef极小覆盖集：极小覆盖集：a,c,e,b,d,e,f,a,c,d,f。求极大独立集或极小覆盖集是求极大独立集或极小覆盖集是NP难的。难的。第77页，本讲稿共100页acbdef极小覆盖集还可以利用前面求极大独立集的方法求；极小覆盖集还可以利用前面求极大独立集的方法求；同样求极大独立集也可以用
47、上面的方法求得同样求极大独立集也可以用上面的方法求得。极小覆盖集：极小覆盖集：a,c,e,b,d,e,f,a,c,d,f。极大独立集：极大独立集：b,d,f,a,c,b,e。第78页，本讲稿共100页支配集：支配集：图图G=(V,E)，K V，若若G的任何顶点或的任何顶点或属于属于K，或至少与，或至少与K中一点邻接，则称中一点邻接，则称K为为G的一的一个支配集。个支配集。例例支配集：支配集：a,c,b,e,b,d,f,a,b,c,a,b,c,d,e,f,acbdef4.4支配集支配集第79页，本讲稿共100页极小支配集：极小支配集：K为为G的一个极小支配集的一个极小支配集K为为G的一的一个支配
48、集且个支配集且 K1 K，K1不是不是G的支配集。的支配集。支配数：支配数：设设G的所有支配集为的所有支配集为A1、A2、Ak，记，记称为称为G的支配数。的支配数。最小支配集：最小支配集：G的一个支配集的一个支配集Ai称为称为G的一个最小支的一个最小支配集若配集若|Ai|=。acbdef如图如图,极小支配集：极小支配集：a,c,b,e,c,f,b,d,f。最小支配集：最小支配集：a,c,b,e,c,f。=2第80页，本讲稿共100页上式展开，每一项是一个极小支配集。上式展开，每一项是一个极小支配集。baedfc第81页，本讲稿共100页高斯提出高斯提出5皇后和皇后和8皇后问题皇后问题最少几个最
49、少几个“后后”放在哪些方格中，才能吃掉对方任何一个放在哪些方格中，才能吃掉对方任何一个格子上的子儿？格子上的子儿？最多几个最多几个“后后”放在哪些方格中，使得任意放在哪些方格中，使得任意“后后”吃不掉其吃不掉其他的他的“后后”？第82页，本讲稿共100页4.5独立集、支配集和点覆盖的关系独立集、支配集和点覆盖的关系定理定理1设设G=(V,E)无孤立点，则：无孤立点，则：G的一个极大独立集必是的一个极大独立集必是G的一个极小支配集；的一个极小支配集；若若S为为G的一个独立集，则的一个独立集，则V-S为为G的一个支配的一个支配集。集。第83页，本讲稿共100页定理定理2设图设图G=(V,E)无孤立
50、点，无孤立点，C V，则，则C为为G的一个点覆的一个点覆盖盖V-C为为G的一个独立集。的一个独立集。推论推论1G如上所述，如上所述，C V，则，则C为为G的一个极小覆盖的一个极小覆盖V-C是是G的一个极大独立集。的一个极大独立集。推论推论2G如上所述，如上所述，n=|V|，则，则+=n。第84页，本讲稿共100页支配集与独立集的应用支配集与独立集的应用（1）中心台站的选址）中心台站的选址在在v1,v2,.,vn这这n个城镇之间建立一个通信网络。现从个城镇之间建立一个通信网络。现从这几个城镇中选定几座城镇，在那里建立中心台站，这几个城镇中选定几座城镇，在那里建立中心台站，要求它们与其它各城镇相邻