《第4,5章E,H图,匹配103.ppt》由会员分享，可在线阅读，更多相关《第4,5章E,H图,匹配103.ppt（92页珍藏版）》请在三一办公上搜索。
1、第四章 欧拉图与哈密尔顿图,4.1 欧拉图,定义1 设G 是无孤立点的图。经过G的每条边的(闭)迹被称为 Euler(闭)迹，存在Euler闭迹的图称为欧拉图,简称E 图。Euler闭迹又称为Euler环游。,上图中，（a）,（f）是欧拉图；（b）,(d)有欧拉迹但不是欧拉图;（c）和（e）无欧拉迹。,例1,定理1 下列陈述对于一个连通图G是等价的：,(1)G是欧拉图。,(2)G的每个点的度是偶数。,(3)G的边集能划分为圈。,令C是G中的一条欧拉闭迹。C中任一个给定的点在C中每出现一次恰关联两条边，因为G的每条边在C中仅出现一次，所以该点的度应为该点在C中出现的次数乘以2,是一个偶数。,推论
2、 连通图G 有Euler迹当且仅当G最多有两个奇点。,证明 定理1表明：G有Euler闭迹当且仅当G有零个奇点。,若连通图G有Euler非闭迹C,并设点u和v分别是C的起点和终点.记在C中添加一条连接u和v的新边e后所得到的图为C+e。显然，C+e是一条Euler闭迹,则由已证结论，C+e有零个奇点,从而C,即G有两个奇点。,反之，设G是恰有两个奇点 u 和 v 的连通图。在 u和v间添加新边 e 得图G+e,则 G+e 没有奇点。由已证结论,G+e有Euler闭迹,从而G 有Euler迹。,综上,推论结论成立.,由以上讨论我们还有：,1.图 G 有欧拉迹,G 能“一笔画”,G 连通且 G 中
3、奇点数不超过2,2.若奇点数为0,则一笔画与起点无关;若奇点 数为2,则一笔画的起点与终点均为奇点.,3.在有向图（即每条边均为有向边的图，其系统讨论将在第九章进行）中有类似结论.,有向图D中，以一点u为起点的弧（即有向边）的数目称为u的出度，记为 dD+(u)；以一点u为终点的弧的数目称为u的入度，记为dD-(u)。,定理3 下列陈述对于一个连通有向图D是等价的：,（1）D是欧拉有向图。,（2）D的每个点的入度等于出度。,（3）D的弧集可划分为有向圈。,4.2 高效率计算机鼓轮的设计,计算机中旋转鼓轮的位置是借助于鼓轮表面上的一系列电触点所产生的二元信号来识别的。这个表面分为m段，每段由绝缘
4、体或导体材料组成。绝缘段给出信号0（没有电流），导通段给出信号1（有电流）。,1.S的周期:S中对任何正整数n,具有 an+=an的最小的正整数.,问题 为提高效率,我们期望鼓轮每旋转一周(m段)读出的由k位组成的m个数应是互不相同的.进一步,对故定的k,最大的m应是多少?如何构造这样的鼓轮?,涉及该问题的数学模型的几个概念:,设 S=(a1,a2,a n,)为（0,1）无限序列.,2.S的k-部分序列S1,S2,:是由S中相继k个元素组成的k元组作为元素组成的序列,即 S1=(a1,a2,ak),S2=(a2,a3,ak+1),3.德 布鲁因（De，Bruijn）序列:指对于固定的正整数k的
5、具有最大的一个（0,1）周期序列S，它使得S 的k-部分序列 S1,S2,S 均不相同。,易知,不同的 k 元(0,1)序列 Si 恰有2k 个，即=2k,上问题的数学模型:对于固定的k，求德 布鲁因序列S.,例1 设k=3，则=23=8，这 8个不同的3-部分序列为:（000）(001)(010)(101)(011)(111)(110)(100),相应的德布鲁因序列是 S=(0001011100010111)把这个序列的前8位排成一个圆圈，与所求的鼓轮相对应，就得到下图的鼓轮设计。,德 布鲁因序列的构造:,步骤1 构造一个有向图H:它的点是2k-1个不同的有序(k-1)-元组。对点 v=(b
6、1,b2,bk-1)，用两条弧分别将v联到点v1=(b2,b3,bk-1,0)和v2.=(b2,b3,bk-1,1),得有向边v,v1和v,v2。当然，上述的点v=(b1,b2,bk-1)也有两条由点u1和u2的指向v的边联接，其中 u1=(0,b1,b2,bk-2)，u2=(1,b1,b2,bk-2)。,说明：(1)H 的每一点v，有 d+(v)=d-(v)=2，且是连通的从而H是欧拉有向图,称为德 布鲁因图。(2)H有2k条弧，若以每一条由点（b1,b2,bk-1）到点（b2,b3,bk）的弧a代表一个k-元组（b1,b2,bk），便可得2k个不同的k-元组。,步骤2 求H的欧拉有向闭迹,
7、由此得k-部分序列 S1,S2,S 和相应的德 布鲁因序列S.,例 下图为k=4(=24=16)的德 布鲁因图,相应的欧拉有向闭迹及相应的德 布鲁因序列.,该例有16个解，其中的一些为,(abcdkijefjhlmnpq)=(0000101101001111)(abcdkipghlmjefq)=(0000101100111101)(abcfgijedklmnpq)=(0000100110101111)(abhijklmnpgcdefq)=(0000110111100101)(abhijedklmnpgcfq)=(0000110101111001)(abhijefgcdklmnpq)=(0000
8、110100101111)(abhipgcdklmnjefq)=(0000110010111101),4.3中国邮路问题,问题：邮递员从邮局出发，递送邮件，然后返回邮局，要求辖区每条街至少走一遍且走过的总路程最短，应如何选择路线？,图论模型：在一个连通的具有非负权的赋权图G中找一条包含每条边（允许重复）且边权之和最小的闭途径.称之为最优环游。,对该问题(1)若图G是一个欧拉图，则找出G的欧拉回路即可。,(2)对一般图，其解法为：添加重复边以使G成为欧拉图G*，并使添加的重复边的边权之和为最小，再求G*的欧拉回路。,(3)对恰有两个度数为奇的点的图G，可证：需要重复的边正好是从一个奇度点到另一个
9、奇度点的最短路上的边，即问题为欧拉问题与最短路问题的综合。,说明:(1)若G是Euler图，则G的任何Euler环游都是最优环游.,(2)若G 不是Euler图，用添加重复边以使G成为欧拉图G*的方法时，添加的重复边具有的特征由定理3给出.,定理3 若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短的长度的充要条件是：,(1)每一条边最多重复经过一次；,(2)在G的每一个圈上，重复经过的边的数目不超过圈的长度的一半,算法的思想 从任一点出发按下法来描画一条边不重复的迹，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。,Euler图中确定Euler环游的Fleury算
10、法,Fleury算法,1.任意选取一个顶点v0，置w0=v0。,2.假设迹wi=v0e1v1eivi已经选定，那么按下述方法从 E e1,e2,ei中选取边ei+1：使(1)ei+1和vi相关联；(2)除非没有别的边可选择，否则ei+1 不是 G=G-e1,e2,ei的割边。,3.当第2步不能再执行时，算法停止。,例,可证，Fleury算法是一个好算法。,例：某博物馆的一层布置如下图，其中边代表走廊，结点e是入口，结点g是礼品店，通过g我们可以离开博物馆。请找出从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的路线。,解：图中只有两个奇度顶点e和g,因此存在起点为e,终点为g的欧拉迹。,为
11、了在G中求出一条起点为e,终点为g的欧拉迹，在e和g间添加一条平行边m,用Fleury算法求出欧拉环游为：,emgcfabchbdhgdjiejge,所以：解为：egjeijdghdbhcbafcg,设G=(n,m)是欧拉图,由Fleury算法知：算法需要m次循环；,算法中主要运算是判断：，该判断的时间复杂性是n2数量级的。,所以Fleury算法时间复杂性是：O(n2m),是好算法。,算法复杂性分析,(2)考查G的圈,若存在圈C,其中重复边的总长大于圈长的一半，则在圈C上交换重复边和不重复边得图G”.重复这个过程,直到得到一个图G*,在G*中没有重复边的总长大于圈长的一半的圈.,不是Euler
12、图求最优环游的方法,(1)用每条边最多添一条边的方法任意添一些重复边使图G 成为一个欧拉多重图G.,(3)用Fleury算法求G*的Euler环游.,例 图G如图(a)所示(各边权为1),它有10个奇度点。任意添一些边得到一个欧拉多重图(b)。,(b)中有色圈中重复边的数目为5，大于圈长8的一半，在这个圈上交换重复边和不重复边，得到(c)。,(c)中每一个圈中重复边的数目均不大于圈长的一半.从而，由(c)中每条欧拉闭迹对应原图一条闭通道，它含有所有的边且具有最短的长度。,(a),(b),4.4 哈密尔顿图,经过图中每个点仅一次的路（圈）称为的Hamilton路(圈)，存在Hamilton圈的图
13、称为哈密尔顿图，简称H图。Hamilton路也简称H路。,只有哈密尔顿路，但不是哈密尔顿图,哈密尔顿图,无哈密尔顿路,例如,证明 设C 是G 中一条哈密尔顿圈。任取 V 中非空子集S，因 C 是G 的哈密尔顿圈含G 的所有点，故S 也是子图 C 的非空子集。由点不重复的圈的特性知任意删去C 中|S|个点，最多将C 分为|S|“段”，即(C-S)|S|（*）,而 C 是 G 的生成子图，又有(G-S)(C-S)所以(G-S)|S|,定理5 若G是H图，则对于V的每个非空真子集S，均有(G-S)|S|(4.1),依据定理4可判断下图（a）不是哈密尔顿图，这是因若取 S=v，有(G-S)=2 1=|
14、S|,可验证彼得森图（上图（b）所示）不是哈密尔顿图，但满足式（*）式。这表明定理5给出的条件只是图 G 是哈密尔顿图的必要条件而不是充分条件。,引理1设G是简单图，u和v是G中不邻接的顶点，且适合 d(u)+d(v)n 则G是H图的充要条件是G+uv为H图。,证明必要性：若G是H图，则显然G+uv也是H图。,充分性：设G+uv是H图。如果G+uv的H圈不含边uv，则由 G=(G+uv)-uv知G中有一个H圈。,如果G+uv的H 圈中含有 uv 边，不妨设H圈为 C=uvv3v4vnu。当G1=G+uv时，有,故有,若有i(3in-1)使u adj vi，v adj vi+1(如图)，则 G
15、中有一个H圈 C1=uvivi-1v3 v vi+1vi+2vn u即G是H 图,若不存在这样的i，因 v3,v4,vn-1中有-2 个点与u邻接，故v4,v5,vn中就有-2 个点不能与v 邻接。从而,这与已知条件相矛盾。故在假设的 dG(u)+dG(v)n的条件下，一定存在上述图示那样的i，使G中存在一个H 圈，所以G为H图。,定义1 在n阶简单图G中，若对d(u)+d(v)n的任何一对点u和v均有u adj v，则称G是闭图。,引理2 若G1和G2是同一个点集V 的两个闭图，则G=G1G2是闭图。,由G1和G2是闭图，u和v在G1和G2中都邻接，故u和v在G中也邻接，从而G是闭图。,证明
16、 因对任何wV，有 dG(w),dG(w),注:闭图的并不一定是闭图。例如,定义2 若一个与G 有相同点集的闭图，使G，且对异于 的任何图H，若有G H，则H不是闭图，则称 是G的闭包，即G的闭包是包含G的极小闭图。,图的闭包的构造方法:将图中度数之和至少是图的顶点个数的非邻接顶点对递归地连接起来，直到不再有这样的顶点对存在时为止。,例 下图给出了6个顶点的图的闭包的构造过程。,故唯一。,引理3 图G的闭包是唯一的。,G,证明 如果 和 是G 的两个闭包。则由 G G,得,证明 如果G是H图，显然，是H图。,定理7(Bondy 1969)一个简单图G是H图的充要条件为它的闭包 是H图。,如果
17、是H图，当G=时，结论成立；当G 时，必相继存在若干条边，使得,G+e1+e2+ek=,其中eiG，(i=1,2,k)。根据闭包的定义，对 中边ek的端点u和v有,因为G+e1+e2+ek是H图，由引理1知 G+e1+e2+ek-1是H图，反复应用引理1可知G是H图。,注:一个图G的闭包不一定是完全图。比如下图中（a）、（b）两个均不是完全图，但它们却是自己的闭包。,推论1 设是n 3的简单图。若 是完全图，则G是H图。,推论2（1）设G是n 3的简单图。若G中每个点的度d(v)n/2，则G是H图。(由此得定理6)（2）设G是n 3的简单图，若G中任何两个不邻接的点u和v均有 d(u)+d(v
18、)n则G是H图。,说明：判断一个图是否哈密尔顿图，往往要结合定义进行。由定义知：一个图若有度为1的顶点，一定不是哈密尔顿图，只可能有哈密尔顿路；若图是哈密尔顿图，则图中2度顶点关联的边必属于所有哈密尔顿圈；一个顶点关联的边再多，一个哈密尔顿圈只能用其两条边。,不是哈密尔顿图，因图中二度顶点所关联的8条边（红边）已构成圈，而此圈不是哈密尔顿圈。,问题：一个旅行售货员想访问若干城市（假定各城镇之间均有路可通），然后返回。问如何安排路线使其能恰好访问每个城镇一次且走过的总路程最短？这个问题称为旅行售货员问题.,求最优圈，目前还没有一个理想的算法。,4.6 旅行售货员问题,图论模型：在赋权完全图G中求
19、具有最小权的哈密尔顿圈，这个圈称为最优圈。,一个可行解法：,（1）任取G 的一个哈密尔顿圈C。,（2）修改 C 为 Cij 使Cij 比 C 优，其方法为：设 C=v1 v2vn v1，若存在整数 i，j，满足0 i+1j n，且 w(vivj)+w(v i+1v j+1)w(vi vi+1)+w(vj vj+1)则 Cij=v1 v2 vi vj vj-1 v i+1 v j+1 vj+2 vnv1 比 C 优。其中C与Cij的关系如图所示。,例3 求图中（a）所示图的最优圈。,解 任取一个哈密尔顿圈C=bcadb，如图（b）。,w(ca)+w(db)=18+7=25 23=w(cd)+w(
20、ab)取 C=b c d a b。,第五章 匹配与因子分解,5.1 匹配,定义 设M是图G的边子集，若任意的 eM，e 都不是环，且属于M 的边互不相邻，则称 M 为 G的一个匹配。设 M 为 G 的一个匹配，对 vV(G)，若 v 是 M 中某边的一个端点，则称 v 为 M 饱和点，否则称为 M 非饱和点。,匹配还可分为最大匹配（含边数最多的匹配）和完美匹配（图中的点均为 M 饱和点的匹配 M）等类型。,对 M2，点v1是的饱和点，点v2是非饱和点。,例1中的M1 和M2既不是最大匹配，也不是完美匹配，而M3是最大匹配，也是完美匹配。,例1 设图G 为:,G的匹配有：,M1=v1v8,M2=
21、v1v3，v8v4，v7v5,M3=v1v2，v8v3，v7v4，v6v5 等等,关系：(1)完美匹配必是最大匹配，而最大匹 配不一定是完美匹配。,(2)一个图的最大匹配必存在，但完美匹配不一定存在。,(3)图G 存在完美匹配的一个必要条件 是 G 的点数为偶。,设M 为图G的一个匹配,可看出：对3，若取3中非 M 的边再连同 M 的不在3中的边组成 M，则 M 的边数比 M的边数多，这表明 M 不是该图的最大匹配。,M 交错路：G 中由M中的边与非M 中的边交替组成的路。,M 可扩路：起点与终点均为M 非饱和点的M交错路。,定理1（Berge，贝尔热，1957）G 的匹配 M是最大匹配当且仅
22、当 G 不含 M 可扩路.（等价于：M不是最大匹配当且仅当 G 含 M 可扩路）,证明 设M是G的匹配，并假设G 包 含M可扩充路 v0v1v2m+1,定义M E 为M=(M v1v2,v3v4,v2m-1 v2m)v0v1,v2v3,v2m v2m+1,则M是G的匹配，且|M|=|M|+1，因而M就不是最大匹配。,反之，假设M不是最大匹配，且令M是G的最大匹配，则|M|M|(1.1)置H=GMM，这里MM表示M和M的对称差。,贝尔热(1926-2002)法国著名数学家。他的无限图理论及其应用(1958)是继哥尼之后的图论历史上的第二本图论专著。他不仅在图论领域做出了许多贡献，而且四处奔波传播
23、图论，推动了图论的普及和发展。1993年，他获得组合与图论领域颁发的欧拉奖章。贝尔热在博弈论、拓扑学领域里也有杰出贡献。在博弈领域，他引入了Nash均衡之外的另一种均衡系统。Nash的生活被改编成电影美丽的心灵，获02年奥斯卡金像奖。贝尔热对中国的手工艺很感兴趣。他也是一位象棋高手，还创作过小说谁杀害了Densmore公爵。,H 的每个顶点在H中具有的度是1或2。因为它最多只能和M的一条边以及 M的一条边相关联，因此 H 的每个分支或是由M和M中的边交错组成的偶圈，或是由M和M中的边交错组成的路。由（1.1）式，M包含的边多于M的边，因而H中必定有的一条路P,其边始于M且终止于M，因此P的起点
24、和终点在H中被M所饱和，在图G中就是M非饱和的。于是P是G的一条M可扩路。,5.2 偶图的匹配与覆盖,取图 G 的一个顶点子集S，令 N(S)=v|存在 uS，且v与u 相邻称 N(S)为 S 的邻集。,取 S=v1,v2，则 N(S)=v8,v3,v1,v2,定理2（Hall，1935）设G为具有二分类（X,Y）的偶图，则G包含饱和X的每个顶点的匹配当且仅当|N(S)|S|（2.1）对所有 S X 成立.,证明 假设G包含匹配M，它饱和X的每个顶点，并设S是X的子集。由于S的顶点在 M 下和N(S)中的相异顶点配对，显然有|N(S)|S|。,反之，假设G是满足（2.1）式的偶图，M*是G的最
25、大匹配。若M*不饱和X的所有顶点，我们则将有如下矛盾。,设 u 是X的一个M*非饱和点，并设 Z=v|vV，且v通过M*交错路与u连接,置 S=ZX 和 T=ZY（见图）,由于M*是最大匹配，从上节定理1可知：u为Z中唯一的M*非饱和点(否则将含 M*可扩路)。且任意一对配对点v和w,若vS,则必wT,反之亦然.因此,|T|=|S|-1（2.2）而且 T N(S)。,又因N(S)中每个顶点v 均由一个M*交错路连接于u，故vZ,从而vT,这表明N(S)T,于是有 T=N(S)(2.3),由（2.2）式和（2.3）式推出|N(S)|=|T|=|S|-1|S|这与假定（2.1）式矛盾。所以M*饱和
26、X的所有顶点.,推论 若G是k正则偶图（k0），则G有完美匹配。,证明 设G是具有二分类（X,Y）的k正则偶图（k0）。首先有|X|=|Y|(习题1的9).,任取X的一个子集S，令 E1=e|eE,并且 e 与 S 中的顶点关联 E2=e|eE,并且 e 与 N(S)中的顶点关联,因与 S 中的顶点关联的边必与 N(S)中的顶点关联，所以E1 E2,再根据定理2，可知G有一个饱和X的每个顶点的匹配M，由于|X|=|Y|，所以M是完美匹配。,图G的一个覆盖:指V(G)的一个子集 K，使得G的每条边都至少有一个端点在 K 中。,G的最小覆盖:G中点数最少的覆盖,匹配与覆盖的关系:设K是G的覆盖，M
27、是G的匹配,则有,理由:K至少包含M中每条边的一个端点。,(2)定理4 设M是匹配，K是覆盖，若|M|K|，则M是最大匹配，且K是最小覆盖。,证明 设M*是最大匹配,是最小覆盖，则由（2.4）式，|M|M*|K|由于|M|K|，所以|M|=|M*|,|=|K|。,(3)定理5（Knig，哥尼，1931）偶图中，最大匹配的边数等于最小覆盖的顶点数。,证明 设G 是具有二分类（X,Y）的偶图，M*是G的最大匹配，用U 表示 X 中的 M*非饱和顶点的集，用 Z 表示由 M 交错路连接到 U 中顶点的所有顶点的集。置 S=ZX,T=ZY。,类似于定理2的证明，可知T中的每个顶点都是M*饱和的，并且N
28、(S)T。定义=(XS)T（见图）。,哥尼(Knig，1884-1944)第一本图论教材有限图与无限图理论（1936年）的撰写者。该书对青年学者产生了很大影响，推动了图论的进一步发展。在20多年时间里，它都是世界上唯一一本图论著作。直到1958年，法国数学家贝尔热(Berge）才出版专著无限图理论及其应用。哥尼早期学习拓扑学，但对图论兴趣特别大。他一直工作在布达佩斯工业大学。讲课很有激情，吸引了很多优秀学生转向图论研究。特别是，他把一起获得匈牙利国家高中数学竞赛一等奖的3个学生都吸引来研究图论，这3个学生是：Erds,Gallai,Turan.都是伟大的数学家。哥尼1944年为免遭纳碎迫害，选
29、择了自杀。,则G的每条边必然至少有一个端点在 中，因为否则就存在一条边，其一个端点在S中，而另一个端点在YT中，这与N(S)T相矛盾。于是 是G的覆盖。并且显然有,|M*|=,由定理4，是 最小覆盖。,例1 矩阵的一行或一列统称为一条线。证明：包含了一个（0,1）矩阵中所有1的线的最小条数，等于具有性质任意两个1都不在同一条线上的1的最大个数。,这样,此矩阵的第 i 行线包含1的个数就是 G 中点 xi 关联的边数，而第 j 列线包含1的个数就是G中点 yj 关联的边数，故包含了（0,1）矩阵中所有1的线的最小条数就是偶图G中的最小覆盖的点数。,证明 将（0,1）矩阵 对应一个具有二分类(X,
30、Y)的偶图G,使其行代表X 中的元素,列代表Y 中的元素,且满足,（注:对应后,1则代表边,G含有饱和X的每个点的匹配当且仅当Q中存在|X|个不同行不同列的1),而（0,1）矩阵中任意两个都不在相同线上的若干个1，就是偶图G中的一个匹配。而具有上述性质的1的最大个数，就是偶图G中最大匹配的边数，由定理5，问题得证.,5.3 Tutte定理与完美匹配,奇(偶)分支:图的有奇(偶)数个顶点的分支,我们用o(G)表示图G的奇分支的个数。,定理5（Tutte）G有完美匹配当且仅当 o(GS)|S|,对所有SV成立（3.1）证明冗长，从略。,推论 每个没有割边的3正则图都有完美匹配。,5.4 因子分解,
31、一.1因子分解,图G的因子:G的一个至少有一条边的生成子图；,G的因子分解:将G分解为一些边不相交的因子,使这些因子的并即为G；,n-因子：指n度正则的因子。,n-因子分解：每个因子均为n-因子的因子分解，此时称G本身是n-可因子化的。,若G有一个1-因子（即完美匹配），则显然G是偶阶图。所以,奇阶图不能有1-因子。,定理6-8 完全图K2n,k-正则偶图(k0),具有Hamilton圈的3-正则图是1-可因子化的。,例1 求K6的1-因子分解。,解 可由下法来确定K2n的1分解:将K2n中的点以数字来标记;如图1,除2n外，它们中的每一个数，按箭头方向移动一个位置；在每个位置中，同一行的两点
32、邻接就得到一个1-因子，共有2n-1个不同的位置就产生了2n-1个不同的1-因子，从而完成了的1-因子分解。沿此方法，可得K6到的1-因子分解（见图2）。,例2 将K3,3作1-因子分解,解 我们将X的点用数字1，2，3标记，而Y的点用1，2，3来标记，用置换G来表示K3,3中X的点与Y的点间之匹配关系，则,定理9 若3-正则图有割边，则不可1-因子分解。,证明 若3-正则图G可1-因子分解，因去掉G的不含割边的1-因子后，图中每个点均为2度从而每条边均在圈中，特别地割边也在圈中，矛盾。,二.2因子分解,由定义有:(1)若一个图是2-可因子化，则每个因子一定是不相交圈的一个并。,(2)2-可因
33、子化的图的所有点的度一定是偶数，所以 完全图K2n不是2-可因子化的。,(3)若一个2-因子是连通的，则它是一个H圈。,定理10 图K2n+1 是n个H圈的和。,证明 为了在 K2n+1 中构成n个边不相交的生成圈，先标定它的点v1,v2,v2n+1。然后，在点v1,v2,v2n上构成 n 条路Pi 如下：Pi=vivi+1vi-1vi+2vi-(n-1)vi+n。,其中Pi 的第j 点是vk，k=i+(-1)j，并且所有下标取为整数1，2，2n（mod 2n）。生成圈Hi 是由v2n+1联接于Pi 的两个端点构成。,例3 将K7分解成3个生成圈的和。,解 将K7的顶点用数码i表示，而1,2,
34、3；4,5,6为正六边形的顶点，7是中心（下图（a）。其实线就是一个2因子，它是一个Hamilton圈 H1=v7v1v2v6v3v5v4v7，若将1,2,3,4,5,6绕中心按顺时间方向移动一个位置（下图（b），则得另一个H 圈H2=v7v2v3v1v4v6v5v7，第三个H 圈必然是 H3=v7v3v4v2v5v1v6v7，则 K7=H1H2H3。,P1=1(1+1)(1-1)(1+2)(1-2)(1+3)=126354(mod 6),Pi=vivi+1vi-1vi+2vi-(n-1)vi+n;Pi 的第 j 点是vk，其中 k=i+(-1)j,P2=2(2+1)(2-1)(2+2)(2-
35、2)(2+3)=231465(mod 6),定理11 完全图K2n是一个1-因子和n-1个H圈的和。,定理12 每一个没有割边的3度正则图是一个1-因子和一个2-因子的和。(由定理5的推论可证),注 若没有割边的3度正则图中的2-因子是一些偶圈,则该图也是1-可因子化的.,定理13 一个连通图是2-可因子化的当且仅当它是偶数度正则的。,三、荫度,荫度 图G分解为边不相交的生成林的最少数目,记为(G)。,定理14 令G是一个非平凡图，又令ms是G的任何一个有s个点的子图中边的最多数目，则,(G)的证明 因为若G有n个点，则在任何一个生成林中边的最多数目是n1。从而G的边不相交的生成林至少有 m/
36、(n-1)个.但G的荫度是一个整数，所以(G)。对于子图H，显然有(G)(H)，故(G)。,对于Kn，ms 的最大值显然在 s=n 时出现，所以(Kn)=,类似地，对完全偶图Kr,p，ms 的最大值在 s=n=r+p 时取到。所以有,推论 完全图和完全偶图的荫度为,例4 分K7为生成林的最小分解如下图所示。,说明 这种构造是由K7的一个点v7为心的星形图与相应的K6的上述三条生成路形成的生成子林所组成。,人员分派问题：n 个工人 x1,x2,xn，n 件工作 y1,y2,yn。已知 xi 能胜任 ki 件工作，i=1，2，,n。问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作
37、。假定每件工作只能一人做，若能，又如何安排？,建模：以工人和工作为点，当且仅当 xi 能胜任工作 yj 时则连线，得偶图 G.于是一种符合要求的安排对应 G 中一个完美匹配。所以此问题实际上是求偶图的完美匹配问题.,进一步：若不要求人数与工作数相等，则问题是求偶图的饱和V1的每个点的匹配问题，其中V1是工人的集合；进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为求偶图的最大匹配问题。,5.5 最优匹配与匈牙利算法,一、匈牙利算法,算法思想：先任取一个匹配 M，然后寻找M 可扩路。若不存在 M 可扩路，则 M 为最大匹配；若存在，则将可扩路中 M
38、 与非 M 的边互换，得到一个比 M 多一条边的匹配 M，再对 M 重复上面过程。,算法是从V1 的每个非饱和点出发寻找 M 可扩路的。若从V1 的每个非饱和点出发都无 M 可扩路，则 M 必无可扩路，从而 M 是最大匹配。这是因偶图中不可能存在两个端点均在 V 2 中的 M 可扩路。,定义1 设M是G中的匹配，u是X的M非饱和点，若树HG 满足（）vV(H)；（）对H的每个顶点v，H中唯一的（u,v）路是一条M交错路，则称树H是一棵扎根于u的M交错树（如下图）,算法中,寻找以u为起点的一条M可扩路，其过程包含了“生长”一棵扎根于u的M交错树H。开始时，H仅由单一顶点u组成，而在以后的步骤中若
39、始终是下图(a)的情况,则无M可扩路：若出现下图(b)的情况,则找到了M可扩路：,匈牙利算法(求饱和X中每个点的或最大匹配),给定具有二分类(X,Y)。的偶图.,(1)任取一个匹配M。,(3)取X 的非饱和点 u，令 S=u，T=。（有|T|=|S|-1）,(2)若 X 中每个点均为 M 饱和点，则停（输出M）；否 则继续（3）。,(4)若N(S)=T，则-（此时由于|T|=|S|-1，所以|N(S)|S|,若求饱和X中每个点的匹配则停(问题无解);若求最大匹配则将u也作为M 饱和点对待，转(2)；否则取 yN(S)T。,(5)若y 为饱和点，则转（6）；否则转（7）。,(6)存在 zX，有
40、yzM，令 S=Sz，T=Ty，转（4）。（注意，这样替换后，|T|=|S|-1依然成立）,(7)存在 u 到 y 的 M 可扩路，令 M=(ME()(ME()，M=M，转（2）。,例1 求图G（如图（a）所示）的最大匹配，其中 X=v1,v2,v3,v4,v5。,（1）任取一个匹配 M=v1u1，v3 u3，v5u5，如图（a）的红边所示。,(2)显然X中存在非饱和点，取其中一个 v2，令S=v2，T=。,因N(S)=u1,u3T，故取 u1N(S)T=N(S)=u1,u3。,u1为饱和点，且 v1u1 M，令 S=S v1=v1,v2，T=T u1=u1。,因N(S)=u1,u2,u3T，
41、故取 u2N(S)T=u2,u3。,u2 为非饱和点，得M可扩路=v2u1v1u2,取M=(ME()(ME()=v2u1,v1u2,v3u3,v5u5，如图（b）中的红边。,(3)取X的非饱和点 v4。从v4出发重复（2）的过程得M可扩路=v4u5v5u4,(4)X已无非饱和点，故结束。,取M=v1u2，v2u1，v3u3，v4u5，v5u4，如图（c）中红边。,二、最优匹配,工作安排问题未考虑每人做某项工作的效率。若要求考虑效率，并问“如何安排使效率最大”，这称为最优安排问题。最优安排的图论模型是在赋权偶图中寻找具有最大权的匹配，称为最优匹配。,5.6 匹配在矩阵理论中的应用,定理16 v阶
42、方阵 M=(aij)的行列式展开式中每一项均为零的充要条件是存在nv，使 M 有一个 n(v-n+1)阶的子矩阵，它的所有的元素均为零。,证明 作一个具有二分类(X,Y)的偶图G，其中X=x1,x2,xv，Y=y1,y2,yv，xi 与 yj 邻接当且仅当在 M 中aij0。,因(j1,j2,jv)是(1,2,v)的一个排列，故E1是一个完美匹配。,Hall定理表明不存在这样的完美匹配当且仅当存在X的一个子集S，使|N(S)|S|-1,设|S|=n。这对应M中有n行，这n行中至多只有n1列中有非零元，而在其余的(v-n+1)列中每个元均为零。于是M有一个n(v-n+1)阶的零子矩阵。,例1 在
43、5阶方阵,中，第2,3,5行和第1,2,5列导出了一个3阶零矩阵。取n=3，v-n+1=3，故由定理16知 det M 的每一项均为零。,事实上，从矩阵M对应的偶图G中（右图），若取S=x2,x3,x5，则 N(S)=y3,y4，显然|S|N(S)|，故G没有完美匹配，因而 det M 的展式中每项均为0。,章4习8，证明：若G有2k0个奇数顶点，则存在k条边不重的迹Q1,Q2,Qk，使得：,证明：不失一般性，只就G是连通图进行证明。,设G=(n,m)是连通图。令vl，v2，,vk,vk+1,v2k是G的所有奇度点。,在vi与vi+k间连新边ei得图G*（1ik).则G*是欧拉图，因此，由Fl
44、eury算法得欧拉环游C.,在C中删去ei（1ik).得k条边不重的迹Qi（1ik):,章4习9，设G是非平凡的欧拉图，且v V(G)。证明：G的每条具有起点v的迹都能扩展成G的欧拉环游当且仅当G-v是森林。,证明：“必要性”,若不然，则G-v有圈C。,考虑G1=G-E(G)的含有顶点v的分支H。,由于G是非平凡欧拉图，所以G1的每个顶点度数为偶数，从而，H是欧拉图。,H是欧拉图，所以存在欧拉环游T.对于T，把它看成v为起点和终点的一条欧拉迹，显然不能扩充为G的欧拉环游。这与条件矛盾！,“充分性”,若不然，设Q=(v,w)是G的一条不能扩充为G的欧拉环游的最长迹，显然v=w,且Q包含了与v关联
45、的所有边。即Q是一条闭迹。,于是，G-v包含G-Q且G-Q的每个顶点度数为偶数.,于是，G-Q的非平凡分支是欧拉图，说明有圈，即G-v有圈，这与条件矛盾.,章5习2(1)证明：每个k方体都有完美匹配(k大于等于2),(2)求K2n和Kn,n中不同的完美匹配的个数。,(1)证明一：证明每个k方体都是k正则偶图。,事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。,如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。,又不难知
46、道k方体的每个顶点度数为k,所以k方体是k正则偶图。,由推论：k方体存在完美匹配。,证明二：直接在k方体中找出完美匹配。,设k方体顶点二进制码为(x1,x2,xn),我们取(x1,x2,xn-1,0),和(x1,x2,xn-1,1)之间的全体边所成之集为M.,显然，M中的边均不相邻接，所以作成k方体的匹配，又容易知道：|M|=2k-1.所以M是完美匹配。,(2)我们用归纳法求K2n和Kn,n中不同的完美匹配的个数。,K2n的任意一个顶点有2n-1中不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出K2n的不同完美匹配个数为：(2n-1)!,同样的推导方法可归纳出K n,n的不同完美匹配个数为：(n)!,章5习3，证明树至多存在一个完美匹配。,证明：若不然，设M1与M2是树T的两个不同的完美匹配，那么M1M2,且TM1M2每个顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。,
