数学建模之着色

数学建模之着色第1页，共100页，2023年，2月20日，星期六记为

正常着色就是相邻的边用不同的颜色着，所用的最少颜色数就是边色数。目前为止，还没有一个好的算法求一般图的边色数。第2页，共100页，2023年，2月20日，星期六例设n个人中有些要进行俩俩会谈，每次会谈需要一个单元时间。问最少要用多少单元时间才能安排完所有会谈？第3页，共100页，2023年，2月20日，星期六例设n是正整数，且Ai(i=1,2,…,2n+1)是某集合B的子集,且设∣Ai∣=2n;(b)∣Ai∩Aj∣=1,1≤i<j≤2n+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页，2023年，2月20日，星期六得到了一个完全图K2n+1,由已知，B中每个元素都对应K2n+1中的一条边。约定标0的元素着红色，标1的元素着绿色，连接两红元素的边着红色，连接两绿元素的边着绿色。问题转化为完全图K2n+1，的边用红、绿两种颜色着色，使得每个顶Ai皆与n条红边相关联。K2n+1共有n(2n+1)条边，当n为奇数时，无解.对于n为偶数时，用数学归纳法证明问题有解。假设n=2时，K2n+1=5,每个Ai有4个元素，这时有解。第5页，共100页，2023年，2月20日，星期六证明n=2(k+1)时成立.假设n=2k时问题有解。第6页，共100页，2023年，2月20日，星期六引理1

设G不是奇圈的连通图，则G存在一个二边着色，使两种颜色在每个度数不小于2的顶点上表现。若与顶点v关联的某边染有颜色i，则称颜色i在顶点v上表现。证明假设G是非平凡图。G是Euler图时。若G是偶圈，则G的正常2边着色具有所要求的性质。否则，G必有一个度数至少为4的点v0.设v0e1v1e2…env0是G的Euler环游，并且设E1={ei∣i是奇数}，E2={ei∣i是偶数}第7页，共100页，2023年，2月20日，星期六则G的二边着色(E1，E2)具有所要求的性质，因为G的每个顶点都是v0e1v1e2…env0的内点。(2)G不是Euler图时，则添加一个新的顶点v0,并将它和G的每个奇数度的点连接起来，构成一个新图G*。显然G*是Euler图。设v0e1v1e2…en*v0是G*的Euler环游，并且类似地构造E1,E2,易证二边着色(E1∩E，E2∩E)具有所要求的性质.第8页，共100页，2023年，2月20日，星期六定义若C1,C2是对G的两种k边着色，且满足其中c1(v)是C1着色时，顶点v关联的边中的颜色数，其中c2(v)是C2着色时，顶点v关联的边中的颜色数,则称C2是对C1的一种改善，不能改善的k边着色称为最佳k边着色。第9页，共100页，2023年，2月20日，星期六引理2设C=(E1,E2,…,Ek)是G的一个最佳k边着色。如果有一个顶v0，又存在两种颜色i与j，使得i色在v0顶关联的边中不出现，而j色在v0顶关联的边中至少出现两次，则由Ei∪Ej导出的子图中含v0的连通分支是一个奇圈。证明设G[Ei∪Ej]中包含v0的连通分支为H.假设H不是奇圈，由引理1，则H存在一个二边着色，使两种颜色在每个度数不小于2的顶点上表现。以这种方式用颜色i与j重新给H着色，得到一个G的一个新的k边着色用c‘(v)表示顶点v关联的边中的颜色数,则有第10页，共100页，2023年，2月20日，星期六由于两种颜色i和j都在u上表现，且有于是，这与C的选择矛盾。由此推出H是奇圈。第11页，共100页，2023年，2月20日，星期六定理若G是二分图，则证明：设G是具有的图，且C=(E1,E2,…,E)是G的一个最佳k边着色，并设u是满足c(u)<d(u)的一个顶点。显然u满足引理2的假设。所以G包含一个奇圈，因而不是偶图，矛盾。第12页，共100页，2023年，2月20日，星期六定理(Vizing1964)若G是简单图，则G的边色数第13页，共100页，2023年，2月20日，星期六“课程表问题”：有m位教师x1,x2,…，xm和n个班级y1,y2,…，yn,老师xi为班级yj日授课pij学时，试按排一个授课表使学校上课的时间最少。令X={x1,x2,…，xm},Y={y1,y2,…，yn},顶xi与yj之间有pij条边相连，形成一个有重边的二分图G.每一学时，每位老师最多为一个班级上课，每个班至多接受一个老师的授课，于是问题就是求又，可见，若没有上课多于p节的老师，也没有上课多于p节的班级，则可编出至多p节的课程表；如果只有指定的几间教室可以用，全校一天最少只排几节课？第14页，共100页，2023年，2月20日，星期六设共计l门课，编成每天p节课的课表，每节课平均要开l/p门课，至少用{l/p}间教室。定理设M与N是图G的无公共边的匹配，且∣M∣>∣N∣,则存在无公共边的匹配M1和N1，使得证明令H=G[M△N]，则H中每个顶点至多与一条M的边及一条N的边相关联，因此

dH(v)=1or2vV(H)第15页，共100页，2023年，2月20日，星期六从而H的每个分支都是一个圈或一条路，由M及N中的边交错组成。但∣M∣>∣M∣，H中一定存在一个分支是一条路P，且其起点和终点都是M饱和的。令

P=v0e1v1,…e2n+1v2n+1,v0

e1

v1,e2

v2…e2n+1

v2n+1取M1=(M-{e1,e3,…,e2n+1})∪

{e2,e4,…,e2n}

N1=(N-

{e2,e4,…,e2n})∪{e1,e3,…,e2n+1}.第16页，共100页，2023年，2月20日，星期六定理G是二分图，G的最大度数p，则G内存在p个无公共边的匹配M1,M2,…,Mp,使得

且对1ip,证明由于G是二分图，E(G)可以划分成(G)个匹配第17页，共100页，2023年，2月20日，星期六故对于p,存在p个无公共边的匹配使得对边数之差大于1的匹配反复应用上述引理，可得p个两两无公共边的匹配M1,M2,…,Mp,满足定理的条件.第18页，共100页，2023年，2月20日，星期六例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页，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5安排4个节课，可安排4个教室4个节课的课表。红线：第1节兰线：第2节绿线：第3节黑线：第4节第20页，共100页，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5红线：第1节兰线：第2节绿线：第3节黑线：第4节123456x1y1y1y3y4x2y2y4x3y3y4y2x4y4y5第21页，共100页，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5红线：第1节兰线：第2节绿线：第3节黑线：第4节123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43个教室第22页，共100页，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5可安排2个教室6个节课的课表。第23页，共100页，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5红线：第1节兰线：第2节绿线：第3节黑线：第4节123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y43个教室第24页，共100页，2023年，2月20日，星期六x1x2x3x4y1y2y3y4y5红线：第1节兰线：第2节绿线：第3节黑线：第4节123456x1y4y1y3y1x2y2y4x3y3y4y2x4y5y42个教室？？？第25页，共100页，2023年，2月20日，星期六2.点着色

着色:如果使用n种颜色把图G的每个顶点都分配一种颜色，且使得相邻顶点异色，则称此为对G的顶点正常n着色。G的顶点正常着色中所需颜色数的最小值称为G的顶色数，简称色数。用c(G)

表示，色数为k的图称为k色图。第26页，共100页，2023年，2月20日，星期六第27页，共100页，2023年，2月20日，星期六点色数的简单性质(G)=1G是零图(Kn)=n(G)=2G是非零图二部图(Cn)=2,n偶数(Wn)=3,n奇数

3,n奇数4,n偶数第28页，共100页，2023年，2月20日，星期六(G)上界定理1(G)(G)+1证明vV(G),G(v)={u|(u,v)E(G)},

|G(v)|(G),

给G(v)中顶点着色至多需要(G)种颜色,所以至少还剩一种颜色可用来给v着色.定理2(Brooks):若G连通、非完全图Kn

(n3)、非奇圈,则(G)(G).说明:n=1G=K1,n=2:连通G=K2

第29页，共100页，2023年，2月20日，星期六例

Petersen图=3.解1:

由Brooks定理,=3.又图中有奇圈,3.所以=3.解2:

存在如下3-着色,=3.

又图中有奇圈,3.

所以=3.

第30页，共100页，2023年，2月20日，星期六例c(K6)=6c(W6)=4c(W5)=3c(S6)=2c(C6)=2c(C5)=3第31页，共100页，2023年，2月20日，星期六应用：安全装箱问题，考试安排问题，信道分配问题等。以每种货物为一顶点，仅当两种货物放在一个箱子里不安全时，在两种货物对应的顶点之间连一边，构成图G。如果求得(G),对G用(G)种颜色着色，同色的顶点对应的货物放在同一箱子中，所需箱子的最小数目为(G)。第32页，共100页，2023年，2月20日，星期六下面给出一种近似算法--最大度数优先的Welsh-Powell算法.

这个算法给出了一个较好的着色方法,但不是最有效的方法,即所用的颜色数不一定是最少的.第33页，共100页，2023年，2月20日，星期六最大度数优先的Welsh-Powell算法

设G=(V,E),V={v1,v2,…,vn},且不妨假设d(v1)≥d(v2)≥…≥d(vn).c1,c2,…,cn为n种不同的颜色.①令有序集Ci={c1,c2,…,ci},i=1,2,…,n.j=1.转向②.②给vj着Cj的第一个颜色Cj1.若

j=n时,停;

否则,转向③.③k＞j,若vk和vj相邻,令Ck=Ck\{Cj1}.j=j+1,转向②.第34页，共100页，2023年，2月20日，星期六信道分配问题：在无线传输中，发射台所用频率从小到大编号，称为信道。用同一信号的两个台的距离不得小于一个常数d，问各台至少需要几个不同的信道？以发射台为顶点，仅当发射台间的距离小于d时，在两发射台对应的顶点之间连一边，构成图G。(G)为所求。第35页，共100页，2023年，2月20日，星期六应用：药品存储问题，考试安排问题，信道分配问题等。以每种药品为一顶点，仅当两种药品放在一间房子里不安全时，在两种药品对应的顶点之间连一边，构成图G。如果求得(G),对G用(G)种颜色着色，同色的顶点对应的药品放在同一间房子中，所需房间的最小数目为(G)。第36页，共100页，2023年，2月20日，星期六信道分配问题：在无线传输中，发射台所用频率从小到大编号，称为信道。用同一信号的两个台的距离不得小于一个常数d，问各台至少需要几个不同的信道？以发射台为顶点，仅当发射台间的距离小于d时，在两发射台对应的顶点之间连一边，构成图G。(G)

为所求。第37页，共100页，2023年，2月20日，星期六特殊图的色数①零图：(G)=1②完全图Kn：(G)=n③G是一条回路：(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页，2023年，2月20日，星期六定理1

对G=(V,E)，=max{deg(vi)|viV}，则

(G)+1。定理2(Brooks)设G=(V,E)是简单连通图，但不是完全图，不是奇数长度圈，=max{deg(vi)|viV}3，则

(G),即G是-可着色的。定理给出了色数的一个上限，但很不精确。Brooks定理也说明只存在两类满足(G)=+1的图。例二部图可2着色，但是可以相当大。第39页，共100页，2023年，2月20日，星期六[Hajós猜想]

若G是n色图，则G包含Kn的一个同胚图。n=1,2显然，n=3,4已证，其他未决。[四色猜想]

任何平面图都是4-可着色的。由于存在着不可3-着色的平面图K4，4色问题若可证明，将是平面图色数问题的最佳结果。[五色定理]

任何简单平面图都是5-可着色的。第40页，共100页，2023年，2月20日，星期六色数

G=(V,E)为简单图，vi,vj

为其中不相邻顶点。为在G中添加边(vi,vj)得到的图，为在G中合并vi,vj

，其他顶点与其关系不变，并合并多重边（称为收缩vi,vj

）得到的图。则有：

c(G)=min(c(),c())例ijijijG第41页，共100页，2023年，2月20日，星期六例

如图，求c(G)。c(K5)=5c(K4)=4c(K4)=4c(K3)=3第42页，共100页，2023年，2月20日，星期六定义:

对给定的图G=(V,E)，PG(k)表示以k种颜给G进行正常着色的方案数目。两种方案相同：同一个结点着同一种颜色。可以用结点集到颜色集的函数表述。当k<

c(G)时,不可能进行正常着色,此时PG(k)=0。当kc(G)时，PG(k)>0。4色猜想：对平面图G,PG(4)>0（存在4-着色方案）.例如，PK3(3)=6色多项式第43页，共100页，2023年，2月20日，星期六PK3(3)=6abcabcabcabcabcabc第44页，共100页，2023年，2月20日，星期六若干特殊图的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页，2023年，2月20日，星期六定理3

设简单图G，e=vivj

为G的一条边，记G-e为从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页，2023年，2月20日，星期六推论1

对任何图G=(V,E)，n=|V|，e=|E|，PG(k)都是k的整系数n次多项式，且：①首项为kn；②次项为-ekn-1；③常数项为0；④各项系数的符号正-负交替。证明对图G的边数e进行归纳法证明.约定重边变成单边，不影响顶点的正常着色。e=0时，有PG(k)=kn,成立。假设en-1时，成立。考虑e=n的情形.则G-e的边数为n-1,G*e等于或小于n-1，由归纳法假设，PG-e(k)=kn-(e-1)kn-1+an-2kn-2-an-3kn-3+…+(-1)n-1a1k第47页，共100页，2023年，2月20日，星期六PG*e(k)=kn-1-e′kn-2+bn-3kn-3-bn-4kn-4+…+(-1)n-2b1k其中e′是简单图G*e的边数，ai,bi0.由公式PG(k)=PG-e(k)-PG*e(k)PG(k)=kn-(e-1)kn-1+an-2kn-2-an-3kn-3+…+(-1)n-1a1k-[kn-1-e′kn-2+bn-3kn-3-bn-4kn-4+…+(-1)n-2b1k]=kn-ekn-1+(an-2+e′)kn-2-(an-3+bn-3)kn-3+…+(-1)n-1(a1+b1)k推论1证明了函数PG(k)具有多项式形式。色数多项式:上述函数PG(k)称为图G的色数多项式。第48页，共100页，2023年，2月20日，星期六减边法:求给定图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构造图G的色数多项式。第49页，共100页，2023年，2月20日，星期六例如图，求其色数多项式。减边法比较适合于求稀疏图的色数多项式。P（,k）=P（,k）-P（,k）=[P(,k）-P（,k）]-[P(,k）-P（,k）]=(k3-k2)-(k2-k)=k3-2k2+k第50页，共100页，2023年，2月20日，星期六加边法:

求给定图G的色数多项式原理：定理3，PG(k)=PG-e(k)-PG*e(k)①在图G中任取两个不相邻顶点u,v；②在图G中加上(u,v)，得新图G+e，在图G中收缩(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页，2023年，2月20日，星期六G的色数多项式是k(k-1)n-1

G是n个顶点的树.顶点是n的树T的色数多项式是k(k-1)n-1.对顶点数n进行归纳证明。当n=1,2时，成立。假设nn-1时，成立，考虑n=n的情形。此时，考虑T的一个叶点v0,记T1=T-{v0},则由归纳假设，

PT1(k)=k(k-1)n-2对于T1的每一种正常k着色，v0在T中着色时有k-1种选择，因此PT(k)=(k-1)k(k-1)n-2=k(k-1)n-1.第52页，共100页，2023年，2月20日，星期六能否判断一个多项式为某一个图的色数多项式？说明k4-3k3+k2不是色数多项式。该多项式满足推论的条件，设它是图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页，2023年，2月20日，星期六例如图，求其色数多项式。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页，2023年，2月20日，星期六4独立集、支配集和覆盖集同色顶点构成的顶点集：顶点互不相邻

红色顶点集构成一个独立集。第55页，共100页，2023年，2月20日，星期六独立集：

图G=(V,E)，IV，若I中任意两个顶点都不相邻，则称I为G的一个独立集.例独立集：

{b,d},{b,f},{a,c},{b,d,f},…acbdef4.1独立集第56页，共100页，2023年，2月20日，星期六

极大独立集：如果I为G的一个独立集，且uV-I,I{u}不是G的独立集，则称I为G的一个极大独立集。设G的所有独立集为I1、I2、…、Ik，记称为G的独立数。最大独立集：

G的一个独立集Ii

称为G的一个最大独立集若|Ii|=

。第57页，共100页，2023年，2月20日，星期六例求最大独立集问题是NP完全的。独立集：{b,d},{b,f},{a,c},{b,d,f},…极大独立集：{a,c},{b,e},{b,d,f}最大独立集：{b,d,f}

=3acbdef第58页，共100页，2023年，2月20日，星期六定义设G=(V,E)是简单无向图，同时将G的邻接矩阵的第i行与第j行，第i列与第j列互换，称为一次平移变换。平移变换不影响图的结点之间的连接关系，仅仅改变了i,j编号。也就是说，邻接矩阵的平移变换对应于图中结点的一个重新编号。定理1

设G=(V,E)是具有n个结点的简单无向图，A是其邻接矩阵，且A具有如下形式：

(1)极大独立集的求法：第59页，共100页，2023年，2月20日，星期六其中令若，则其已确定一极大独立集其中vt(1ti)与下三角矩阵的第t行对应。第60页，共100页，2023年，2月20日，星期六证明则必有一个元素为1，不妨设由矩阵A可知，akj=0,1k,ji，即结点考虑A21,因互不相邻。说明vj与vk相邻。即中任何一个结点都与I={v1,v2,…,vi}相邻。I={v1,v2,…,vi}是极大一独立集.第61页，共100页，2023年，2月20日，星期六形如(1)，满足定理条件的邻接矩阵称为标准型.定理2

A是简单无向图G=(V,E)的邻接矩阵，则总可以经过若干次平移变换，将A化为标准型，从而得到G的一个极大独立集.acbdef第62页，共100页，2023年，2月20日，星期六acbdef第63页，共100页，2023年，2月20日，星期六acbdef第64页，共100页，2023年，2月20日，星期六G的所有极大独立集的求法：借助布尔变量的运算求G的所有极大独立集。已知简单无向图G=(V,E),V={v1,v2,…,vn},约定：

G的每个点vi作为一个布尔变量；“∧”,“∨”表示“与”运算和“或”运算，即布尔积与布尔和。布尔运算性质与集合的运算性质类似。图G的过点vi,vj的边对应一布尔积vi∧

vj.做布尔表达式：第65页，共100页，2023年，2月20日，星期六中每一项vi∧

vj对应G的一条边，表示对所有边求布尔和。利用德摩根定律有，设与都是v1,v2,…,vn的表达式。因独立集不包含任何一边的两个端点，在独立集上取值为0；反之若=0，则对应的点集为独立集。在独立集上取值为1；反之若点集为独立集。则对应的考虑所有的点集合，即为第66页，共100页，2023年，2月20日，星期六所有的极大独立集。v6v5v4v1v2v3第67页，共100页，2023年，2月20日，星期六v6v5v4v1v2v3极大独立集第68页，共100页，2023年，2月20日，星期六利用极大独立集可以得到一个正常点着色的算法：

定义

若将图G=(V,E)的顶点集合V划分成k个子集合：V1,V2,…,Vk，即且，Vi是的极大独立集，i=1,2,…k.其中V0=,将Vi中的顶点染上i色，则称这种上色是对图G的一种k点规范着色。规范着色是正常着色。下面证明图G可以k点正常点着色则存在k点规范着色。第69页，共100页，2023年，2月20日，星期六证明设G有正常着色C=(V1,V2,…,Vk),即且C是k点规范着色.若V1是极大独立，则将V1中的点上1色。不然，V1是G的一个独立集，从V-V1中调一些点放入V1中，总可以将V1扩成G的极大独立集,这是定理如果图G是可以k点正常点着色的，则G存在k点规范着色。,Vi中的顶点染上i色,调整Vi，分别变为第70页，共100页，2023年，2月20日，星期六对图G-V1重复上面的过程，最后便得到规范k点着色。v1v3v2v4v5V1={v5}是G的极大独立集.V2={v2,v4}是G-V1的极大独立集.V3={v1,v3}是G-V1-V2的极大独立集.V=V1∪V2∪V3,得到一规范着色。用第一种颜色为图上色时，尽可能多的将一些无色顶上色，直至不能再多为止，一直保持邻顶不同色；接着…第71页，共100页，2023年，2月20日，星期六点覆盖:

图G=(V,E)，KV，若G的任何一条边都与K中顶点关联，则称K为G的一个点覆盖（集）。例acbdef点覆盖：

{a,b,c,e},{a,b,c,d,e},{a,c,e},…极小点覆盖、点覆盖数、最小点覆盖。4.2点覆盖第72页，共100页，2023年，2月20日，星期六极小点覆盖：

K是G的一个极小点覆盖K为G的一个点覆盖且K1K，K1不是G的点覆盖。点覆盖数：设G的所有点覆盖为C1、C2、…、Cl，记称为G的点覆盖数。最小点覆盖：G的一个点覆盖Ci

称为G的一个最小点覆盖若|Ci|=

。第73页，共100页，2023年，2月20日，星期六例点覆盖：{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页，2023年，2月20日，星期六4.3独立集与覆盖集的关系独立集与覆盖集在一个图中具有互补性。(1)I为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页，2023年，2月20日，星期六极小覆盖一种求法求覆盖集：vV，或者v盖住与v关联的所有边，或者是其邻点盖住与v关联的边，可以写成第76页，共100页，2023年，2月20日，星期六极小覆盖集可由下面的式子给出：展开式中每一项是一个极小覆盖集。acbdef极小覆盖集：{a,c,e},{b,d,e,f},{a,c,d,f}。求极大独立集或极小覆盖集是NP难的。第77页，共100页，2023年，2月20日，星期六acbdef极小覆盖集还可以利用前面求极大独立集的方法求；同样求极大独立集也可以用上面的方法求得。极小覆盖集：{a,c,e},{b,d,e,f},{a,c,d,f}。极大独立集：{b,d,f},{a,c},{b,e}。第78页，共100页，2023年，2月20日，星期六支配集：

图G=(V,E)，KV，若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页，2023年，2月20日，星期六极小支配集：K为G的一个极小支配集K为G的一个支配集且K1K，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页，2023年，2月20日，星期六上式展开，每一项是一个极小支配集。baedfc第81页，共100页，2023年，2月20日，星期六高斯提出5皇后和8皇后问题最少几个“后”放在哪些方格中，才能吃掉对方任何一个格子上的子儿？最多几个“后”放在哪些方格中，使得任意“后”吃不掉其他的“后”？第82页，共100页，2023年，2月20日，星期六4.5独立集、支配集和点覆盖的关系定理1设G=(V,E)无孤立点，则：①G的一个极大独立集必是G的一个极小支配集；②

；③若S为G的一个独立集，则V-S为G的一个支配集。第83页，共100页，2023年，2月20日，星期六定理2设图G=(V,E)无孤立点，CV，则C为G的一个点覆盖

V-C为G的一个独立集。推论1G如上所述，CV，则C为G的一个极小覆盖V-C是G的一个极大独立集。推论2G如上所述，n=|V|，则

+=n。第84页，共100页，2023年，2月20日，星期六支配集与独立集的应用（1）中心台站的选址

在v1,v2,...,vn这n个城镇之间建立一个通信网络。现从这几个城镇中选定几座城镇，在那里建立中心台站，要求它们与其它各城镇相邻，同时，为减少造价，要使中心台站数目最少，有时还会提其它要求，例如在造价最低的条件下，需要造两套（或更多套）的中心台站，以备一套出故障时，可以及时启用另一套台站。第85页，共100页，2023年，2月20日，星期六数学模型：以城镇为顶点，仅当两城之间有直通通信线路时，相应的两顶点连一边形成一个图，此图的最小支配集即为所求。

若建两套，则从所有极小支配集D1,D2,...,Dd中选取Dm与Dn，使得

Dm∩Dn=，

|Dm∪Dn|=min{|Di|+|Dj||1i,jd,Di∩Dj=

｝。baedfc若选一个中心台站，则选{d};若选两个，则选{a,e}或{a,f}.极小支配集：第86页，共100页，2023年，2月20日，星期六（2）独立集在信息论中的应用

设信息传送的基本信号集为S={s1,s2,...sn}。可以把信号si设想成汉字或拉丁字母。统计规律表明哪些信号与哪些信号易于发生错乱是已知的。例如，输入si，i=1,2,...,5,输出应该是si*,i=1,2,...,5,但由于干扰发生了错乱，s1可能和s2错乱，s1还可能和s5错乱等，例如已知错乱可能性如下图所示。

构造一个无向图G,以S为顶点集合，仅当si与sj易于混乱时，在点si与sj之间连一边。求G的最大独立集即可作为无误基本信号集S1。第87页，共100页，2023年，2月20日，星期六s1s2s3s4s5s1*s2*s3*s4*s5*s5s1s2s3s4混乱的可能性图G最大独立集：每一个都可作为无误基本信号集S1。第88页，共100页，2023年，2月20日，星期六作一图G，使得如果用两信号组成一个词向外传输信息，也有一个如何排除干扰的问题，为此，考虑一种图的积的概念。已知两图G1，G2，其顶点集合为：第89页，共100页，2023年，2月20日，星期六在G中顶点的邻集为：则称G为G1与G2之积，记成

G＝G1×G2＝G2×G1。例如，取，则如下图：第90页，共100页，2023年，2月20日，星期六K3K1K6在上面的例子中，若用{s1,s2,...,s5}中的两个信号组成词向外输出，最多能用哪几个词不致于发生错乱呢？这只需考虑圈C=s1s2s3s4s5s1的平方C×C＝C2中的最大独立集中的各顶对应的词。相似地可用Gn=G×G×...×G(n个)中的最大独立集来确定由n个信号组成的词进行信息传送而不致发生错乱。

第91页，共100页，2023年，2月20日，星期六

任给一群人，其中有k个人彼此认识，有l个人彼此不认识，这种人群至少几人？这个答案记成r(k,l)，称为Ramsey(拉姆萨)数。Ramsey证明了r(3,3)=6.4.6团与Ramsey定理人作为顶点，当且仅当两个人认识时连红边，不认识连绿边。r(3,3)>5r(3,3)≤6第92页，共100页，2023年，2月20日，星期六

团：设图G=(V,E)，