离散课件 18支配集覆盖集独立集

第十八章

支配集、覆盖集、独立集、匹配与着色18.1支配集、点覆盖集与独立集18.2边覆盖集与匹配18.3着色例：一座监狱有5间牢房,牢房之间有通道连接,其示意图如下图所示,图中点表示牢房,边表示通道.监狱看守位置要设在能通过通道直接监视所有牢房的地方,假定看守站岗时不得走动．问：至少需要几名看守才能完成监视任务．

2名定义1.设无向简单图G=<V,E>,VV,若viV-V,vjV

*使得vivjE,则称V*是G的一个支配集,并称vj支配vi.G的顶点数最少的支配集V称为G的最小支配集,记0(G)=|V|.最小支配集极小支配集

18.1支配集、点覆盖集与点独立集v1v2v3v4v5{v1,v2,v3,v4},{v1,v5},{v5}都是支配集;{v1,v2,v3,v4}是极小支配集;{v5}是最小支配集;{v1,v5}既不是极小支配集,也不是最小支配集.0(G)=1定义2.

设无向简单图G=<V,E>,V*V,若eE,vV

*,使得v与e关联,则称V*是G的点覆盖集,简称点覆盖,并称v覆盖e.G的顶点数最少的点覆盖V称为G的最小点覆盖,记0(G)=|V|.最小点覆盖极小点覆盖v1v2v3v4v5{v1,v2,v3,v4},{v5},{v1,v5}都是点覆盖;{v1,v2,v3,v4}是极小点覆盖;{v5}是最小点覆盖;{v1,v5}既不是极小点覆盖,也不是最小点覆盖.0(G)=1定义3.

设无向简单图G=<V,E>,V*中任何两个顶点均不相邻,则称V*是G的点独立集,简称独立集.G的顶点数最多的独立集V称为G的最大独立集,记0(G)=|V|.最大独立集极大独立集v1v2v3v4v5{v1,v2,v3,v4},{v5},{v1,v2}都是独立集;{v1,v2,v3,v4}是最大独立集;{v5}是极大独立集;{v1,v2}既不是最大独立集,也不是极大独立集.0(G)=4定理1.

无向简单图的极大独立集是极小支配集.推论:0(G)≥

0(G)定理2.

设无向简单图G=<V,E>,V*V,V*为G的点覆盖当且仅当V-V*为G的独立集.推论:设G是n阶无向图,则0(G)+0(G)=n.18.2边覆盖集与匹配定义1.设无向简单图G=<V,E>无孤立点,E*E,若vV,eE*使得v与e关联,则称E*为边覆盖集,简称边覆盖,并称e覆盖v.G的边数最少的边覆盖E称为G的最小边覆盖,记1(G)=|E|.最小边覆盖极小边覆盖e1v1v2v3v4e2e3e4e5{e1,e2,e3},{e1,e3,e5},{e1,e5}都是边覆盖;{e1,e2,e3}是极小边覆盖;{e1,e5}是最小边覆盖;{e1,e3,e5}既不是极小边覆盖,也不是最小边覆盖.1(G)=2定义2.设无向简单图G=<V,E>,E*E,若E*中任何两条边均不相邻,则称E*为G的边独立集,也称为G的匹配.G的边数最多的匹配E称为最大匹配,记1(G)=|E|.最大匹配极大匹配e1v1v2v3v4e2e3e4e5{e2},{e1,e5}都是匹配;{e2}是极大匹配;{e1,e5}是最大匹配.1(G)=2定义3.设M是G的一个匹配,(1)M中的边称为匹配边,不在M中的边称为非匹配边;(2)与匹配边关联的顶点称为饱和点,不与匹配边关联的顶点称为非饱和点;(3)若G中每个顶点都是饱和点,称M为完美匹配;(4)G中由匹配边和非匹配边交替构成的路称为交错路,起点和终点都是非饱和点的交错路称为可增广的交错路.e1v1v2v3v4e2e3e4e5M={e2}是G的匹配,e2是匹配边,e1,e3,e4,e5是非匹配边;{v1,v3}是饱和点,{v2,v4}是非饱和点;M不是完美匹配;e1e2e5是可增广的交错路;{e1,e5}是完美匹配定理1.

设M是G的一个匹配,则M为G的最大匹配当且仅当G中不含关于M的可增广的交错路.定理2.(Hall定理)设偶图G=<X,Y,E>,则G包含饱和X的每个顶点的匹配当且仅当|N(S)||S|,对所有SX成立.例1.某中学有3个课外小组:物理组、化学组、生物组.今有张、王、李、赵、陈5名同学.若已知:(1)张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员;(2)张为物理组成员,王、李、赵为化学组成员,王、李、赵、陈为生物组成员;(3)张为物理组和化学组成员,王、李、赵、陈为生物组成员.问:能否选出3名不兼职的组长？解:设v1,v2,v3,v4,v5分别表示张、王、李、赵、陈.u1,u2,u3分别表示物理组、化学组、生物组.在3种情况下作二部图分别记为G1,G2,G3,求饱和u1,u2,u3的匹配.图中粗边所示的匹配就是其中的一个(1)选张为物理组组长、李为化学组组长、赵为生物组组长;(2)选张为物理组组长、李为化学组组长、陈为生物组组长;(3)选不出3名不兼职的组长.18.3着色定义1.给图的某类元素(点、边、面)中的每一个指定一种颜色,使得相邻元素有不同颜色,称为图的(点、边、面)着色.若颜色集C有|C|=k,则称k-着色.点着色(2-着色)边着色(4-着色)面着色(3-着色)定义2.着色所需的最少颜色数,称为色数.点色数记为(G),边色数记为(G),面色数记为*(G).G(G)=2,

(G)=4,*(G)=3.例：某单位存储8种化学药品，其中某些药品之间会发生化学反应，他们之间的关系如下图所示.问：至少需要几个库房存储这些化学药品？v1v2v4v3v5v6v7v8解：(G)=4,

{v1,v4}{v2,v7}{v5,v3}{v8,v6}各存放在一个库房里.

定理1.

对于任意无环图G,(G)(G)+1.定理2.(Brooks定理)设无环连通图G不是完全图,也不是奇圈,则(G)(G).定理3.(Vizing定理)若G是简单图,则(G)=(G)或(G)+1.定理4.

G是偶图当且仅当(G)=2.定理5.

若G是偶图,则(G)=(G).定理6.

平面图G是k-可面着色的当且仅当其对偶图G*是k-可着色的.定理7.(四色定理)任何平面图都是4-可着色的.例1.

求Petersen图G的点色数.解:根据Brooks定理,(G)(G)=3.由于Petersen图中含奇圈,故(G)3.综上知:

(G)=3.例2.某一天内有n个教师给m个班级上课,每个教师在一个课时只能给一个班级上课.(1)这一天内至少排多少节课?(2)不增加节数的情况下至少需要几个教室?(3)若教师是t1,t2,t3,t4,班级是c1,c2,c3,c4,c5.已知t1给c1,c2,c3上2节,1节,1节课,t2给c2,c3各上1节课,t3给c2,c3,c4各上1节课,t4给c4,c5上1节,2节课.求最省教室的课表.解:令G=<T,C,E>,T={教师},C={班级},E={教师给班级上课}.给G进行边着色,同色边代表教学可以同时进行,所以色数就是节数,同色边数就是教室数.(1)至少排(G)=(G)节课;(2)至