第4,5章E,H图,匹配103.ppt

第四章第四章 欧拉图与哈密尔顿图欧拉图与哈密尔顿图§ 4.1 欧拉图欧拉图 定义定义1 设设G 是无孤立点的图经过是无孤立点的图经过G的每条边的每条边的的(闭闭)迹被称为迹被称为 Euler(闭闭)迹迹，存在，存在Euler闭迹闭迹的图称为的图称为欧拉图欧拉图,简称简称E 图Euler闭迹又称为闭迹又称为Euler环游 上图中，（上图中，（a））,（（f））是欧拉图；（是欧拉图；（b））, (d) 有欧拉迹但有欧拉迹但不是欧拉图不是欧拉图;（（c））和（和（e））无欧拉迹无欧拉迹a）（f）（e）（d）（c）（b）例例1 定理定理1 1 下列陈述对于一个连通图下列陈述对于一个连通图G是等价的：是等价的： (1) G是欧拉图是欧拉图 (2) G的每个点的度是偶数的每个点的度是偶数3) G的边集能划分为圈的边集能划分为圈 令令C是是G中的一条欧拉闭迹中的一条欧拉闭迹C中任一个给定的中任一个给定的点在点在C中每出现一次恰关联两条边，因为中每出现一次恰关联两条边，因为G的每条的每条边在边在C中仅出现一次，所以该点的度应为该点在中仅出现一次，所以该点的度应为该点在C中出现的次数乘以中出现的次数乘以2, 是一个偶数。

是一个偶数证明证明 (1) (2) 因为因为G连通非平凡，故每个点的度至少是连通非平凡，故每个点的度至少是2，，所以所以G含有一个圈含有一个圈Z (见习题见习题1,12)移去Z的各条边产生一个的各条边产生一个生成子图生成子图G1，，其中每个点的度仍然是偶数若其中每个点的度仍然是偶数若G1没有边，则没有边，则（（3）已经成立；否则，重复应用这种论证于）已经成立；否则，重复应用这种论证于G1，，产生一个产生一个图图G2，，其中所有的点的度仍然是偶数，等等当该过程终止其中所有的点的度仍然是偶数，等等当该过程终止于空图于空图Gn时，我们就得到了将时，我们就得到了将G的边分成若干圈的一个划分的边分成若干圈的一个划分2) (3): (3) (1) : 令令Z1是这个划分的一个圈若是这个划分的一个圈若G仅由仅由Z1组组成，则成，则G显然是欧拉图否则，有另外一个圈显然是欧拉图否则，有另外一个圈Z2与与Z1有一有一个公共点个公共点v，，从从v开始并且由开始并且由Z1和和Z2相连组成的通道是含有相连组成的通道是含有这两个圈中各条边的一条闭迹。

继续这个过程，我们可以这两个圈中各条边的一条闭迹继续这个过程，我们可以构成一条含有构成一条含有G的所有边的闭迹；从而的所有边的闭迹；从而G是欧拉图是欧拉图推论推论 连通图连通图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 中奇点数不超过中奇点数不超过22. 若奇点数为若奇点数为0, 则一笔画与起点无关则一笔画与起点无关; 若奇点若奇点 数为数为2, 则一笔画的起点与终点均为奇点则一笔画的起点与终点均为奇点.3. 在有向图（即每条边均为有向边的图，其系在有向图（即每条边均为有向边的图，其系统讨论将在第九章进行）中有类似结论统讨论将在第九章进行）中有类似结论. 有向图有向图D中，以一点中，以一点u为起点的弧（即有向边）的数为起点的弧（即有向边）的数目称为目称为u的出度，记为的出度，记为 dD+(u)；；以一点以一点u为终点的弧的为终点的弧的数目称为数目称为u的入度，记为的入度，记为dD - (u)。

定理定理3 下列陈述对于一个连通有向图下列陈述对于一个连通有向图D是等价的：是等价的：（（1）） D是欧拉有向图是欧拉有向图2））D的每个点的入度等于出度的每个点的入度等于出度 （（3））D的弧集可划分为有向圈的弧集可划分为有向圈 例例 欧拉有向图欧拉有向图:§ 4.2 高效率计算机鼓轮的设计高效率计算机鼓轮的设计 计算机中旋转鼓轮的位置是借助于鼓轮表面上的一计算机中旋转鼓轮的位置是借助于鼓轮表面上的一系列电触点所产生的二元信号来识别的这个表面分系列电触点所产生的二元信号来识别的这个表面分为为m段，每段由绝缘体或导体材料组成绝缘段给出段，每段由绝缘体或导体材料组成绝缘段给出信号信号0（没有电流），导通段给出信号（没有电流），导通段给出信号1（有电流）有电流）0010010触点触点例如，例如，图中，鼓轮的位置图中，鼓轮的位置由四个触点给出读数由四个触点给出读数（（0010）如果鼓轮沿顺）如果鼓轮沿顺时针方向旋转一段，读数时针方向旋转一段，读数将是（将是（1001） 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的具有最大的具有最大τ的一个（的一个（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位排成一个圆圈，与所求的鼓轮相对位排成一个圆圈，与所求的鼓轮相对应，就得到下图的鼓轮设计应，就得到下图的鼓轮设计0 11 01 100德德 · 布鲁因序列的构造布鲁因序列的构造: 步骤步骤1 构造一个有向图构造一个有向图H: 它的点是它的点是2k-1个不同的有序个不同的有序 (k-1)-元组对点元组对点 v = (b1,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的欧拉有向闭迹的欧拉有向闭迹, 由此得由此得k-部分序列部分序列 S1,S2,…,Sτ 和相应的德和相应的德 · 布鲁因序列布鲁因序列S. 例例 下图为下图为k = 4 (τ=24=16) 的的德德 · 布鲁因图布鲁因图, 相应的欧拉相应的欧拉有向闭迹及相应的德有向闭迹及相应的德 · 布鲁因序列布鲁因序列. 000100010001101110011111abcdefgjklmnipqh弧弧a = (0000)b = (0001)c = (0010)d = (0101)e = (1010)f = (0100)g = (1001)h = (0011)i = (0110)j = (1101)k = (1011)l = (0111)m = (1111)n = (1110)p = (1100)q = (1000)(abcdefghijklmnpq……) = (0000101001101111……)欧拉闭迹和相应的欧拉闭迹和相应的德德 · 布鲁因序列布鲁因序列该例有16个解，其中的一些为 (abcdkijefjhlmnpq……) = (0000101101001111……)(abcdkipghlmjefq……) = (0000101100111101……)(abcfgijedklmnpq……) = (0000100110101111……)(abhijklmnpgcdefq……) = (0000110111100101……)(abhijedklmnpgcfq……) = (0000110101111001……)(abhijefgcdklmnpq……) = (0000110100101111……)(abhipgcdklmnjefq……) = (0000110010111101……)§ 4.3中国邮路问题中国邮路问题 问题问题：邮递员从邮局出发，递送邮件，然后返回邮邮递员从邮局出发，递送邮件，然后返回邮局，要求辖区每条街至少走一遍且走过的总路程最局，要求辖区每条街至少走一遍且走过的总路程最短，应如何选择路线？短，应如何选择路线？ 图论模型：图论模型：在一个连通的具有非负权的赋权图在一个连通的具有非负权的赋权图G中找中找一条包含每条边（允许重复）且边权之和最小的闭途径一条包含每条边（允许重复）且边权之和最小的闭途径.称之为称之为最优环游最优环游。

对该问题对该问题 (1) 若图若图G是一个欧拉图，则找出是一个欧拉图，则找出G的欧拉回路即可的欧拉回路即可 (2) 对一般图，其解法为：添加重复边以使对一般图，其解法为：添加重复边以使G成为欧拉成为欧拉图图G*，，并使添加的重复边的边权之和为最小，再求并使添加的重复边的边权之和为最小，再求G*的的欧拉回路欧拉回路 (3) 对恰有两个度数为奇的点的图对恰有两个度数为奇的点的图G，，可证：需要重可证：需要重复的边正好是从一个奇度点到另一个奇度点的最短路复的边正好是从一个奇度点到另一个奇度点的最短路上的边，即问题为欧拉问题与最短路问题的综合上的边，即问题为欧拉问题与最短路问题的综合说明说明: (1) 若若G是是Euler图，则图，则G的任何的任何Euler环游都是最优环游环游都是最优环游.(2) 若若G 不是不是Euler图，用添加重复边以使图，用添加重复边以使G成为欧拉图成为欧拉图G* 的方法时，添加的重复边具有的特征由定理的方法时，添加的重复边具有的特征由定理3给出给出. 定理定理3 若若W是图是图G中一条包含所有边的闭通道，则中一条包含所有边的闭通道，则W在在这样的闭通道中具有最短的长度的充要条件是：这样的闭通道中具有最短的长度的充要条件是： (1) 每一条边最多重复经过一次；每一条边最多重复经过一次；(2) 在在G的每一个圈上，重复经过的边的数目不超过的每一个圈上，重复经过的边的数目不超过圈的长度的一半圈的长度的一半算法的思想算法的思想 从任一点出发按下法来描画一条边不重复从任一点出发按下法来描画一条边不重复的迹，使在每一步中未描画的子图的割边仅当没有别的迹，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。

的边可选择时才被描画Euler图中确定图中确定Euler环游的环游的Fleury算法算法Fleury算法算法1. 任意选取一个顶点任意选取一个顶点v0，置，置w0= v02. 假设迹假设迹wi=v0e1v1…eivi已经选定，那么按下述方法从已经选定，那么按下述方法从 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处离开处离开的路线afedcbihgj 解：解：图中只有两个奇度顶点图中只有两个奇度顶点e和和g,因此存在起点为因此存在起点为e,终终点为点为g的欧拉迹。

的欧拉迹 为了在为了在G中求出一条起点为中求出一条起点为e,终点为终点为g的欧拉迹，在的欧拉迹，在e和和g间添加一条平行边间添加一条平行边mafedcbihgjm 用用Fleury算法求出欧拉环游为：算法求出欧拉环游为： emgcfabchbdhgdjiejge 所以：解为：所以：解为：egjeijdghdbhcbafcg 设设G=(n, m)是欧拉图是欧拉图 由由Fleury算法知：算法需要算法知：算法需要m次循环；次循环； 算法中主要运算是判断：算法中主要运算是判断： ，，该判断的时间复杂性是该判断的时间复杂性是n2数量级的数量级的 所以所以Fleury算法时间复杂性是：算法时间复杂性是：O(n2m), 是好是好算法算法复杂性分析算法复杂性分析(2) 考查考查G’的圈的圈, 若存在圈若存在圈C,其中重复边的总长大于圈其中重复边的总长大于圈长的一半，则在圈长的一半，则在圈C上交换重复边和不重复边得图上交换重复边和不重复边得图G”.重复这个过程重复这个过程,直到得到一个图直到得到一个图G*,在在G*中没有重复边中没有重复边的总长大于圈长的一半的圈的总长大于圈长的一半的圈. 不是不是Euler图求最优环游的方法图求最优环游的方法(1) 用每条边最多添一条边的方法任意添一些重复边使用每条边最多添一条边的方法任意添一些重复边使图图G 成为一个欧拉多重图成为一个欧拉多重图G’.(3) 用用Fleury算法求算法求G*的的Euler环游环游.例例 图图G如图如图(a)所示所示(各边权为各边权为1),它有它有10个奇度点。

任意个奇度点任意添一些边得到一个欧拉多重图添一些边得到一个欧拉多重图(b) (b)中有色圈中重复边的数目为中有色圈中重复边的数目为5，大于圈长，大于圈长8的一半，的一半，在这个圈上交换重复边和不重复边，得到在这个圈上交换重复边和不重复边，得到(c) (c)中每一个圈中重复边中每一个圈中重复边的数目均不大于圈长的一的数目均不大于圈长的一半半.从而，由从而，由(c)中每条欧拉中每条欧拉闭迹对应原图一条闭通道，闭迹对应原图一条闭通道，它含有所有的边且具有最它含有所有的边且具有最短的长度短的长度a)(b)(c)§4.4 哈密哈密尔尔顿图顿图 经过图中每个点仅一次的路（圈）称经过图中每个点仅一次的路（圈）称为的为的Hamilton路路 (圈圈)，存在，存在Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图，简称，简称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 = | S |（（a））v 可验证彼得森图（上图（可验证彼得森图（上图（b b））所示）不是哈所示）不是哈密尔顿图，但满足式（密尔顿图，但满足式（* *）式。

这表明定理）式这表明定理5 5给出给出的条件只是图的条件只是图 G 是哈密尔顿图的是哈密尔顿图的必要条件而不必要条件而不是充分条件是充分条件 (b)引理引理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 = uvv3v4…vnu当当G1= G + uv时，有时，有故有　　故有　　 若有若有i (3≤i≤n-1) 使使u adj vi，，v adj vi+1 (如图如图)，，则则 G 中有一个中有一个H圈圈 C1 = uvivi-1…v3 v vi+1vi+2…vn u即即G是是H 图图 vi-1 vi-2 v3 vivi+1 vi+2 vi+3vu vn 若不存在这样的若不存在这样的i ，，因因 v3, v4,…, vn-1中有中有 -2 个个点与点与u邻接，故邻接，故v4, v5, …,vn中就有中就有 -2 个点不能个点不能与与v 邻接。

从而邻接从而这与已知条件相矛盾故在假设的这与已知条件相矛盾故在假设的 dG(u) + dG(v) ≥ n的的条件下，一定存在上述图示那样的条件下，一定存在上述图示那样的i ，，使使G中存在一个中存在一个H 圈，所以圈，所以G为为H图 (v) ≤ (n-1) – ( -2) = n - dG(u)dG(v)

图 图的闭包的构造方法图的闭包的构造方法: 将图中度数之和至少是图的顶点个将图中度数之和至少是图的顶点个数的非邻接顶点对数的非邻接顶点对递归地递归地连接起来，直到不再有这样的连接起来，直到不再有这样的顶点对存在时为止顶点对存在时为止例例 下图给出了下图给出了6个顶点的图的闭包的构造过程个顶点的图的闭包的构造过程 故唯一 引理引理3 图图G的闭包是唯一的的闭包是唯一的 G  ∩证明证明 如果如果 和和 是是G 的两个闭包则由的两个闭包则由 G  G  ,得得而而 ∩ 是闭图是闭图(引理引理2) , 且且 ∩   ,∩   , 故由故由闭包的定义闭包的定义∩证明证明 如果如果G是是H图，显然，图，显然， 是是H图 定理定理7 (Bondy 1969) 一个简单图一个简单图G是是H图的充要条件为图的充要条件为它的闭包它的闭包 是是H图 如果如果 是是H图，当图，当G= 时，结论成立；当时，结论成立；当G≠ 时，时，必相继存在若干条边，使得必相继存在若干条边，使得 G + e1 + e2 + … + ek = 其中其中ei G，，(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））两个均不是完全图，但它们却是自己的闭包两个均不是完全图，但它们却是自己的闭包 （（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) ≥ n则则G是是H图653 4 2 9 7 8 1例例 右图的闭包是完全图。

右图的闭包是完全图因此，由推论因此，由推论1，它是，它是H图，图，其其H圈为圈为C =1234567891而仅仅改动一条边的一个端点所而仅仅改动一条边的一个端点所得之图得之图P.79则不是则不是H图 说明：说明：判断一个图是否哈密尔顿图，往往要结合定义进行判断一个图是否哈密尔顿图，往往要结合定义进行由定义知：一个图若有度为由定义知：一个图若有度为1 1的顶点，一定不是哈密尔顿图，的顶点，一定不是哈密尔顿图，只可能有哈密尔顿路；若图是哈密尔顿图，则图中只可能有哈密尔顿路；若图是哈密尔顿图，则图中2 2度顶点度顶点关联的边必属于所有哈密尔顿圈；一个顶点关联的边再多，关联的边必属于所有哈密尔顿圈；一个顶点关联的边再多，一个哈密尔顿圈只能用其两条边一个哈密尔顿圈只能用其两条边不是哈密尔顿图，不是哈密尔顿图，因图中二度顶点所因图中二度顶点所关联的关联的8 8条边（红边）条边（红边）已构成圈，而此圈不是已构成圈，而此圈不是哈密尔顿圈哈密尔顿圈问题问题：一个旅行售货员想访问若干城市（假定各城镇之间一个旅行售货员想访问若干城市（假定各城镇之间均有路可通），然后返回问如何安排路线使其能恰好访均有路可通），然后返回。

问如何安排路线使其能恰好访问每个城镇一次且走过的总路程最短？这个问题称为旅行问每个城镇一次且走过的总路程最短？这个问题称为旅行售货员问题售货员问题.求最优圈，目前还没有一个理想的算法求最优圈，目前还没有一个理想的算法§4.6 旅行售货员问题旅行售货员问题 图论模型图论模型：在赋权完全图：在赋权完全图G中求具有最小权的哈中求具有最小权的哈密尔顿圈，这个圈称为密尔顿圈，这个圈称为最优圈最优圈一个可行解法：一个可行解法： （（1）任取）任取G 的一个哈密尔顿圈的一个哈密尔顿圈C （（2））修改修改 C 为为 Cij 使使Cij 比比 C 优，优，其方法为：设其方法为：设 C = v1 v2…vn v1，，若若存在整数存在整数 i，，j，，满足满足0 < i+1

示VjV2V1VnVj+1Vj-1ViVi+1例例3 求图中（求图中（a））所示图的最优圈所示图的最优圈解解 任取一个哈密尔顿圈任取一个哈密尔顿圈C = bcadb，，如图（如图（b） ∵ ∵ w (ca) + w (db) = 18+7 = 25 > 23 = w (cd) + w(ab) ∴ ∴ 取取 C ‘ = b c d a ba) bacd10181171412(b) abdc10111214187第五章第五章 匹配与因子分解匹配与因子分解§5.1 匹配匹配 定义定义 设设M是图是图G的边子集，若任意的的边子集，若任意的 e∈∈M，，e 都不是都不是环，且属于环，且属于M 的边互不相邻，则称的边互不相邻，则称 M 为为 G的一个的一个匹配匹配设 M 为为 G 的一个匹配，对的一个匹配，对 v∈∈V(G)，，若若 v 是是 M 中某边的一个中某边的一个端点，则称端点，则称 v 为为 M 饱和点饱和点，否则称为，否则称为 M 非饱和点非饱和点 匹配还可分为匹配还可分为最大匹配最大匹配（含边数最多的匹配）和（含边数最多的匹配）和完完美匹配美匹配（（ 图中的点均为图中的点均为 M 饱和点的匹配饱和点的匹配 M ））等类型。

等类型对对 M2，，点点v1是的饱和点，点是的饱和点，点v2是非饱和点是非饱和点v1v2v3v4v8v5v7v6 例例1中的中的M1 和和M2既不是最大匹配，也不是完美匹配，既不是最大匹配，也不是完美匹配，而而M3是最大匹配，也是完美匹配是最大匹配，也是完美匹配例例1 设图设图G 为为:G的匹配有：的匹配有：M1 = {v1v8}M2 = {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交交错错路路例如，例如，取取M = {红边红边}Г1Г2Г3M交交错错路路M 可扩路可扩路定理定理1（（Berge，，贝尔热，贝尔热，1957）） G 的匹配的匹配 M是最大匹配当且是最大匹配当且仅当仅当 G 不含不含 M 可扩路可扩路 . （（等价于：等价于： M不不是最大匹配当且仅当是最大匹配当且仅当 G 含含 M 可扩路可扩路 ））证明证明 设设M是是G的匹配，并假设的匹配，并假设G 包包 含含M可扩充路可扩充路 v0v1…v2m+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 = G[M△△M′]，这里，这里M△△M′表示表示M和和M′的对称差。

的对称差 贝尔热贝尔热(1926---2002) 法国著名数学家他的法国著名数学家他的《《无限图理论及其应无限图理论及其应用用》》(1958) 是继哥尼之后的图论历史上的第二本图论专著他不仅是继哥尼之后的图论历史上的第二本图论专著他不仅在图论领域做出了许多贡献，而且四处奔波传播图论，推动了图在图论领域做出了许多贡献，而且四处奔波传播图论，推动了图论的普及和发展论的普及和发展 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的起点和终点在的起点和终点在H中被中被M′所饱和，在图所饱和，在图G中就是中就是M非饱和的于是非饱和的于是P是是G的一条的一条M可扩路可扩路 §5.2 偶图的匹配与覆盖偶图的匹配与覆盖 取图取图 G 的一个顶点子集的一个顶点子集S，，令令 N (S) = { v | 存在存在 u∈∈S，，且且v与与u 相邻相邻}称称 N (S) 为为 S 的的邻集邻集取取 S = {v1, v2}，，则则 N (S) = {v8, v3,v1, v2}v1v2v3v4v8v5v7v6例如图例如图中中定理定理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的最大匹的最大匹配若M*不饱和不饱和X的所有顶点，我们则将有如下矛盾的所有顶点，我们则将有如下矛盾 设设 u 是是X的一个的一个M* 非饱和点，并设非饱和点，并设 Z={ v | v∈∈V，且，且v通过通过M*交错路与交错路与u连接连接 }置置 S = Z∩X 和和 T = Z∩Y （见图）（见图）由于由于M*是最大匹配，从上节定理是最大匹配，从上节定理1可知：可知：u为为Z中唯一的中唯一的M*非饱和点非饱和点 (否则将含否则将含 M * 可扩路可扩路) 且任意一对配对点且任意一对配对点v和和w,若若v∈∈S,则必则必w∈∈T, 反之亦然反之亦然. 因此因此SuT=N (S) | T |= |S |-1 （（2.2）） 而且而且 T   N(S ) 。

又因又因N(S)中每个顶点中每个顶点v 均由一个均由一个M*交错路连接于交错路连接于u，，故故v∈∈Z, 从而从而v∈∈T, 这表明这表明N(S )   T , 于是于是有有 T = N(S ) (2.3) 由（由（2.2）式和（）式和（2.3）式推出）式推出 |N(S )| = | T |= |S |-1< |S | 这与假定（这与假定（2.1）式矛盾 所以所以M*饱和饱和X的所有顶点的所有顶点. 推论推论 若若G是是k正则偶图（正则偶图（k>0），则），则G有完美匹配有完美匹配证证明明 设设G是是具具有有二二分分类类（（X, Y））的的k正正则则偶偶图图 （（k>0）首先有）首先有 |X| = |Y| (习题习题1的的9). 任取任取X的一个子集的一个子集S ，令，令 E1={e | e∈∈E,并且并且 e 与与 S 中的顶点关联中的顶点关联} E2={e | e∈∈E,并且并且 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是是G的匹配的匹配, 则有则有 理由理由: K至少包含至少包含M中每条边的一个端点中每条边的一个端点 (1) |M|≤| K |, 特别地特别地,若若M*是最大匹配，且是最大匹配，且 是最小覆盖是最小覆盖, 则则|M*|≤ (2.4)(2) 定理定理4 设设M是匹配，是匹配，K是覆盖，若是覆盖，若|M|＝＝|K|，则，则M是最大是最大匹配，且匹配，且K是最小覆盖是最小覆盖证明证明 设设M*是最大匹配是最大匹配 , 是最小覆盖，则由（是最小覆盖，则由（2.4）式，）式， |M|≤|M*|≤| |≤|K|由于由于|M|＝＝|K |，所以，所以 |M| = |M*|, | | = |K|。

(3) 定理定理5（（Kǒnig，，哥尼，哥尼，1931）） 偶图中，最大匹配的边偶图中，最大匹配的边数等于最小覆盖的顶点数数等于最小覆盖的顶点数证明证明 设设G 是具有二分类（是具有二分类（X, Y）的偶图，）的偶图，M*是是G的最大的最大匹配，用匹配，用U 表示表示 X 中的中的 M* 非饱和顶点的集，用非饱和顶点的集，用 Z 表示表示由由 M 交错路连接到交错路连接到 U 中顶点的所有顶点的集置中顶点的所有顶点的集置 S = Z∩X , T = Z∩Y类似于定理类似于定理2的证明，可知的证明，可知T中的每个顶点都是中的每个顶点都是M*饱和的，饱和的，并且并且N(S)＝＝T定义 = (X\S)∪∪T（见图）SUT=N (S)X \S 哥尼哥尼(KÖnig ，，1884----1944))——第一本图论教材第一本图论教材《《有限有限图与无限图理论图与无限图理论》》（（1936年）的撰写者年）的撰写者 该书对青年学者产生了很大影响，推动了图论的进一步发该书对青年学者产生了很大影响，推动了图论的进一步发展。

在展在20多年时间里，它都是世界上唯一一本图论著作直多年时间里，它都是世界上唯一一本图论著作直到到1958年，法国数学家贝尔热年，法国数学家贝尔热(Berge）才出版专著）才出版专著《《无限图无限图理论及其应用理论及其应用》》 哥尼早期学习拓扑学，但对图论兴趣特别大他一直工作哥尼早期学习拓扑学，但对图论兴趣特别大他一直工作在布达佩斯工业大学讲课很有激情，吸引了很多优秀学生在布达佩斯工业大学讲课很有激情，吸引了很多优秀学生转向图论研究特别是，他把一起获得匈牙利国家高中数学转向图论研究特别是，他把一起获得匈牙利国家高中数学竞赛一等奖的竞赛一等奖的3个学生都吸引来研究图论，这个学生都吸引来研究图论，这3个学生是：个学生是：ErdÖs ,Gallai, Turan.都是伟大的数学家都是伟大的数学家 哥尼哥尼1944年为免遭纳碎迫害，选择了自杀年为免遭纳碎迫害，选择了自杀则则G的每条边必然至少有一个端点在的每条边必然至少有一个端点在 中，因为否则就中，因为否则就存在一条边，其一个端点在存在一条边，其一个端点在S中，而另一个端点在中，而另一个端点在Y\T中，中，这与这与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, Y)的偶图的偶图G, 使其行代表使其行代表X 中的元素中的元素, 列代表列代表Y 中的元素中的元素, 且满足且满足（（注注: 对应后对应后, 1则代表边则代表边, G含有饱和含有饱和X的每个点的匹配当且仅当的每个点的匹配当且仅当Q中存中存在在 |X| 个不同行不同列的个不同行不同列的1) 而（而（0,1）矩阵中任意两个都不在相同线上的若干个）矩阵中任意两个都不在相同线上的若干个1 ，，就是偶图就是偶图G中的一个匹配。

而具有上述性质的中的一个匹配而具有上述性质的1的最大个的最大个数，就是偶图数，就是偶图G中最大匹配的边数，由定理中最大匹配的边数，由定理5，问题得证，问题得证. 例如例如, 矩阵矩阵 Q 及其对应的偶图如下图其最小覆盖是及其对应的偶图如下图其最小覆盖是 { x1, y2, y4}，故包含，故包含Q中所有中所有1的线是的线是Q的的1行，第行，第2、、4列，列，共共3条 x1 x2 x3 x4y1 y2 y3 y4§5.3 Tutte定理与完美匹配定理与完美匹配奇奇(偶偶)分支分支: 图的有奇图的有奇(偶偶)数个顶点的分支数个顶点的分支, 我们用我们用o(G)表示表示图图G的奇分支的个数的奇分支的个数 定理定理5（（Tutte）） G有完美匹配当且仅当有完美匹配当且仅当 o(G－－S) ≤|S| , 对所有对所有S V成立成立 （（3.1））证明冗长，从略证明冗长，从略推论推论 每个没有割边的每个没有割边的3正则图都有完美匹配正则图都有完美匹配。

例例 彼得森图满足推论的彼得森图满足推论的条件（即没有割边的条件（即没有割边的3正正则图），故它有完美匹则图），故它有完美匹配配. 注注:有割边的有割边的3正则图不一定有完美匹配正则图不一定有完美匹配 没有完美匹配没有完美匹配有完美匹配有完美匹配§5.4 因子分解因子分解一一. 1－因子分解－因子分解图图G的因子的因子: G的一个至少有一条边的生成子图；的一个至少有一条边的生成子图；G的因子分解的因子分解: 将将G分解为一些边不相交的因子分解为一些边不相交的因子, 使这些使这些因子的并即为因子的并即为G；；n-因子：因子：指指n度正则的因子度正则的因子 n-因子分解因子分解：每个因子均为：每个因子均为n-因子的因子分解，此时称因子的因子分解，此时称G本身是本身是n-可因子化的可因子化的 若若G有一个有一个1-因子（即完美匹配），则显然因子（即完美匹配），则显然G是偶阶图是偶阶图所以所以, 奇阶图不能有奇阶图不能有1-因子 定理定理6-8 完全图完全图K2n , k-正则偶图正则偶图(k>0), 具有具有Hamilton圈的圈的3-正则图是正则图是1-可因子化的。

可因子化的例例1 求求K6的的1-因子分解因子分解解解 可由下法来确定可由下法来确定K2n的的1分解分解:将将K2n中的点以数字来标记中的点以数字来标记; 如图如图1, 除除2n外，它们中的每一个数，按箭头方向移动一个外，它们中的每一个数，按箭头方向移动一个位置；在每个位置中，同一行的两点邻接就得到一个位置；在每个位置中，同一行的两点邻接就得到一个1-因子，共有因子，共有2n-1个不同的位置就产生了个不同的位置就产生了2n-1个不同的个不同的1-因子，从而完成了的因子，从而完成了的1-因子分解沿此方法，可得因子分解沿此方法，可得K6到的到的1-因子分解（见图因子分解（见图2）2n232n-22n-1nn+11图图1v1 v2v6v3v5 v4 K6G2G5G1 G4 图图2G3例例2 将将K3,3作作1-因子分解因子分解 解解 我们将我们将X的点用数字的点用数字1，，2，，3标记，而标记，而Y的点用的点用1’，，2’，，3’来标记，用置换来标记，用置换G来表示来表示K3,3中中X的点与的点与Y的点间之匹的点间之匹配关系，则配关系，则 1 2 31’ 2’ 3’ K3,3G1G2G3图为图为定理定理9 若若3-正则图有割边，则不可正则图有割边，则不可1-因子分解。

因子分解证明证明 若若3-正则图正则图G可可1-因子分解，因去掉因子分解，因去掉G的不含割边的的不含割边的1-因子后，图中每个点均为因子后，图中每个点均为2度从而每条边均在圈中，特度从而每条边均在圈中，特别地割边也在圈中，矛盾别地割边也在圈中，矛盾二二. 2－因子分解－因子分解 由定义有由定义有:(1) 若一个图是若一个图是2-可因子化，则每个因子一定是不相交圈可因子化，则每个因子一定是不相交圈的一个并的一个并2) 2-可因子化的图的所有点的度一定是偶数，所以可因子化的图的所有点的度一定是偶数，所以 完全图完全图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+2…vi-(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, 3；；4, 5, 6为正六边为正六边形的顶点，形的顶点，7是中心（下图（是中心（下图（a））其实线就是一个））其实线就是一个2－－因子，它是一个因子，它是一个Hamilton圈圈 H1= v7v1v2v6v3v5v4v7，若将，若将1, 2, 3, 4, 5, 6绕中心按顺时间方向移动一个位置（下图绕中心按顺时间方向移动一个位置（下图（（b）），则得另一个）），则得另一个H 圈圈H2= v7v2v3v1v4v6v5v7，第三个，第三个H 圈必然是圈必然是 H3 = v7v3v4v2v5v1v6v7，则，则 K7 =H1∪∪H2∪∪H312 63 5 4 （（a）） 723 1 74 6 5 （（b））P1=1(1+1)(1-1)(1+2)(1-2)(1+3)=126354 (mod 6)Pi =vivi+1vi-1vi+2…vi-(n-1)vi+n ; Pi 的第的第 j 点是点是vk ，其中，其中 k = i + (-1) jP2=2(2+1)(2-1)(2+2)(2-2)(2+3)=231465 (mod 6)定理定理11 完全图完全图K2n是一个是一个1-因子和因子和n-1个个H圈的和。

圈的和定理定理12 每一个没有割边的每一个没有割边的3度正则图是一个度正则图是一个1-因子和一因子和一个个2-因子的和因子的和由定理由定理5的推论可证的推论可证)例例 彼得森图彼得森图是一个是一个1-因子和一个因子和一个2-因因子的和子的和 注注 若没有割边的若没有割边的3度正则图中的度正则图中的2-因子是一些偶圈因子是一些偶圈 , 则该图也是则该图也是1-可因子化的可因子化的. 定理定理13 一个连通图是一个连通图是2-可因子化的当且仅当它是偶数可因子化的当且仅当它是偶数度正则的度正则的三、荫度三、荫度荫度荫度 图图G分解为边不相交的生成林的最少数目分解为边不相交的生成林的最少数目,记为记为σ(G) 例例 σ(K4)=2σ(K5) =3定理定理14 令令G是一个非平凡图，又令是一个非平凡图，又令ms是是G的任何一个有的任何一个有s个点的子图中边的最多数目，则个点的子图中边的最多数目，则σ(G)≥ 的证明的证明 因因为若若G有有n个点，个点，则在任何在任何一个生成林中一个生成林中边的最多数目是的最多数目是n－－1。

从而从而G的边不相交的的边不相交的生成林至少有生成林至少有 m/(n-1)个个. 但但G的的荫度是一个整数，所以度是一个整数，所以σ(G)≥ 对于子于子图H，，显然有然有σ(G)≥σ(H)，故，故σ(G)≥ 对于对于Kn，，ms 的最大值显然在的最大值显然在 s = n 时出现，所以时出现，所以 σ(Kn)= 类似地，对完全偶图类似地，对完全偶图Kr, p，，ms 的最大值在的最大值在 s = n = r + p 时时取到所以有取到所以有推论推论 完全图和完全偶图的荫度为完全图和完全偶图的荫度为 例例4 分分K7为生成林的最小分解如下图所示为生成林的最小分解如下图所示v7 v1v6 v2 v5 v3 v4 v7 v1v6 v2 v5 v3 v4v7 v7 说明说明 这种构造是由这种构造是由K7的一个点的一个点v7为心的星形图与相应的为心的星形图与相应的K6的上述三条生成路形成的生成子林所组成。

的上述三条生成路形成的生成子林所组成人员分派人员分派问题：问题：n 个工人个工人 x1, x2,…, xn，，n 件工作件工作 y1, y2,…, yn已知已知 xi 能胜任能胜任 ki 件工作，件工作，i =1，，2，，…,n问能否存在一种问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作工作安排方案，使每个人都能分配到他所能胜任的一件工作假定每件工作只能一人做，若能，又如何安排？假定每件工作只能一人做，若能，又如何安排？ 建模：建模：以工人和工作为点，当且仅当以工人和工作为点，当且仅当 xi 能胜任工作能胜任工作 yj 时时则连线，得偶图则连线，得偶图 G .于是一种符合要求的安排对应于是一种符合要求的安排对应 G 中一中一个完美匹配所以此问题实际上是求偶图的完美匹配问题个完美匹配所以此问题实际上是求偶图的完美匹配问题. 进一步：进一步：若不要求人数与工作数相等，则问题是求偶图的饱和若不要求人数与工作数相等，则问题是求偶图的饱和V1的每个点的匹配问题，其中的每个点的匹配问题，其中V1是工人的集合；进一步，若问：能否存是工人的集合；进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为作被分配，则问题为求偶图的最大匹配问题求偶图的最大匹配问题。

§5.5 最优匹配与匈牙利算法最优匹配与匈牙利算法一、匈牙利算法一、匈牙利算法 算法思想：算法思想：先任取一个匹配先任取一个匹配 M，，然后寻找然后寻找M 可扩路若不存在若不存在 M 可扩路，则可扩路，则 M 为最大匹配；若存在，则为最大匹配；若存在，则将可扩路中将可扩路中 M 与非与非 M 的边互换，得到一个比的边互换，得到一个比 M 多多一条边的匹配一条边的匹配 M ’，，再对再对 M ’ 重复上面过程重复上面过程 算法是从算法是从V1 的每个非饱和点出发寻找的每个非饱和点出发寻找 M 可扩路可扩路的若从V1 的每个非饱和点出发都无的每个非饱和点出发都无 M 可扩路，则可扩路，则 M 必无可扩路，从而必无可扩路，从而 M 是最大匹配这是因偶图中是最大匹配这是因偶图中不可能存在两个端点均在不可能存在两个端点均在 V 2 中的中的 M 可扩路定义定义1 设设M是是G中的匹配，中的匹配，u是是X的的M非饱和点，若树非饱和点，若树H G 满足满足（（ⅰ））v∈∈V(H)；；（（ⅱ）对）对H的每个顶点的每个顶点v，，H中唯一的（中唯一的（u, v）路是一条）路是一条M交交错路，错路，则称称树H是一棵是一棵扎根于扎根于u的的M交交错树（如下（如下图）） x1 x2 x3 x4 x5 x6y1 y2 y3 y4 y5 y6 G的一个匹配的一个匹配Mx6y5 y6x3 x2x4 x1= u G的一棵的一棵M交错树交错树 算法中算法中,寻找以寻找以u为起点的一条为起点的一条M可扩路，其过程包含了可扩路，其过程包含了“生长生长”一棵扎根于一棵扎根于u的的M交错树交错树H。

开始时，开始时，H仅由单一顶点仅由单一顶点u组成，而在以后的步骤中若始终是下图组成，而在以后的步骤中若始终是下图(a)的情况的情况, 则无则无M可扩可扩路：若出现下图路：若出现下图(b)的情况的情况, 则找到了则找到了M可扩路：可扩路： u（（a）） u（（b））匈牙利算法匈牙利算法 (求饱和求饱和X中每个点的或最大匹配中每个点的或最大匹配)给定具有二分类给定具有二分类( X, Y)的偶图的偶图. (1) 任取一个匹配任取一个匹配M3) 取取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))；否则取；否则取 y∈∈N( S)\ T。

(5) 若若y 为饱和点，则转（为饱和点，则转（6）；否则转（）；否则转（7）6) 存在存在 z∈∈X，，有有 yz∈∈M，，令令 S = S∪∪{z}，，T = T∪∪{y}，， 转（转（4）注意，这样替换后，（注意，这样替换后， |T|=|S|-1依然成立）依然成立） (7) 存在存在 u 到到 y 的的 M 可扩路可扩路Γ，，令令 M’= ( M∪∪E(Γ)) \ ( M∩E(Γ))，， 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, u3}≠T ，，故取故取 u1∈∈N (S) \ T = N (S) = {u1, u3}②② u1为饱和点，且为饱和点，且 v1u1 ∈∈M ，，令令 S = S∪∪{ v1} = {v1,v2}，，T = T∪∪{ u1}= { u1}。

③③ 因因N (S)= {u1, u2, u3}≠T ，，故故取取 u2∈∈N (S) \ T = {u2, u3}④④ u2 为非饱和点，得为非饱和点，得M可扩可扩路路Γ= v2u1v1u2v1u3u4u2u1v3v4v5u5v2(a)⑤ 取取M = ( M∪∪E(Γ))\ ( M∩E(Γ)) = {v2u1, v1u2, v3u3, v5u5}，，如图（如图（b））中的红边中的红边 3 ) 取取X的非饱和点的非饱和点 v4从从v4出发重复（出发重复（2）的过程得）的过程得M可可扩路扩路 Γ= v4u5v5u4 ( 4 ) X已无非饱和点，故结束已无非饱和点，故结束v1u3u4u2u1v3v4v5u5v2(b)v1u3u4u2u1v3v4v5u5v2(c)取取M = {v1u2，，v2u1，，v3u3 ，，v4u5，，v5u4}，，如图（如图（c））中红边二、最优匹配二、最优匹配 工作安排问题未考虑每人做某项工作的效率若要求工作安排问题未考虑每人做某项工作的效率若要求考虑效率，并问考虑效率，并问““如何安排使效率最大如何安排使效率最大””，这称为，这称为最优最优安排问题安排问题。

最优安排的图论模型是在赋权偶图中寻找最优安排的图论模型是在赋权偶图中寻找具具有最大权的匹配有最大权的匹配，，称为称为最优匹配最优匹配 §5.6 §5.6 匹配在矩阵理论中的应用匹配在矩阵理论中的应用定理定理16 v阶方阵阶方阵 M = (aij) 的行列式展开式中每一项均为零的行列式展开式中每一项均为零的充要条件是存在的充要条件是存在n≤v，使，使 M 有一个有一个 n×(v-n+1) 阶的子矩阶的子矩阵，它的所有的元素均为零阵，它的所有的元素均为零证明证明 作一个具有二分类作一个具有二分类 (X , Y) 的偶图的偶图G，其中，其中X = {x1,x2,…,xv} ，，Y = {y1,y2,…,yv}，，xi 与与 yj 邻接当且仅当在邻接当且仅当在 M 中中aij≠0则则 . 这样这样, 若在行列式若在行列式 det M 中有一项中有一项 因因 (j1, j2, …, jv) 是是 (1, 2, …, v) 的一个排列，故的一个排列，故E1是一个是一个完美匹配。

完美匹配 Hall定理表明不存在定理表明不存在这样的完美匹配当且的完美匹配当且仅当存在当存在X的一个子集的一个子集S，使，使 |N(S)|≤|S|-1, 设 |S| = n这对应M中有中有n行，行，这n行中至多只有行中至多只有n－－1列中有非零元，而在其余的列中有非零元，而在其余的 (v-n+1) 列中每个元均列中每个元均为零于是M有一个有一个n×(v-n+1)阶的零子矩的零子矩阵 例例1 在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 的展式中每的展式中每项均为项均为0y1 y2 y3 y4 y5 x1 x2 x3 x4 x5  章章4习习8，证明：若，证明：若G有有2k>0个奇数顶点，则存在个奇数顶点，则存在k条条边不重的迹边不重的迹Q1,Q2,…,Qk，使得：，使得： 证明：不失一般性，只就证明：不失一般性，只就G是连通图进行证明。

是连通图进行证明 设设G=(n, m)是连通图令是连通图令vl，，v2，，…,vk,vk+1,…,v2k是是G的所的所有奇度点有奇度点 在在vi与与vi+k间连新边间连新边ei得图得图G*（（1≦i≦k).≦i≦k).则则G*G*是欧拉图，是欧拉图，因此，由因此，由FleuryFleury算法得欧拉环游算法得欧拉环游C.C. 在在C中删去中删去ei （（1≦≦i≦≦k).得得k条边不重的迹条边不重的迹Qi （（1≦≦i≦≦k):章章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关联的所有边即关联的所有边即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方体是偶图方体是偶图 又不难知道又不难知道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的两个不同的完美匹配，的两个不同的完美匹配，那么那么M1ΔM2≠ΦΦ, ,且且T[T[M1ΔM2]每个顶点度数为每个顶点度数为2，即它存在圈，，即它存在圈，于是推出于是推出T中有圈，矛盾中有圈，矛盾。