《离散数学》刘任任版第九章

1、 习 题 九1证明：任何树最多只有一个完美匹配分析：树是连通没有回路的图；树的完美匹配是树存在一个匹配M，满足树的所有顶点v都是M-饱和点。而两个完美匹配中不同的边所关联的顶点的度至少为2，否则如果等于1的话，则该顶点关联的边只有一条，在构造完美匹配的时候为了使得这个点成饱和点，只有一种选择。证明：设树有两个或两个以上的完美匹配，任取完美匹配和，。于是。易知边导出子图中的每个顶点满足。于是中存在回路，从而中有回路。此与是树矛盾，故结论成立。2证明：树有完美匹配当且仅当对任意，均有分析：一方面，由定理9.1.3 图G存在完美匹配当且仅当对任意SV(G)，有，所以如果树G有完美匹配，则；而G有完美

2、匹配，说明偶数，所以；从而有。 另一方面，如果对任意，均有，则对v而言，可利用这个这个奇分支找到v关联的唯一边，从而构造出G的一个完美匹配。证明：必要性 设有完美匹配。由定理9.1.3，取，则 又 有完美匹配，偶数。于是=奇数。故 . 从而 .充分性 设对任意，有.即恰有一个奇分支，因是树，故只能与中的一个顶点邻接。设v与的关联边为。显然v确定以后，uv是唯一确定的，且易知。因为G-v只有一个奇分支，则G-u以后，v应该与G-v的其他偶分支在一个连通分支中，而这个分支的顶点数显然是奇数，从而构成G-u的唯一一个奇分支，而u与这个奇分支中的顶点显然也只有与v邻接，所以。于是对任意，按这样的方法构

3、造其关联边，所的的匹配 就是G的一个完美匹配3设是奇数。举出没有完美匹配的-正则简单图的例子。 分析：作G如下：取2k-1个顶点，在奇足标顶点和偶足标顶点间两两连以边外，再连以边，所得图记为G0，显然G0除外其余顶点的度均为k，而的度为k-1，取k个两两不相交的G0的拷贝和一个新顶点v0，并把每个G0拷贝中对应于的顶点与v0相连以边。最后所得的图记为G，显然G是k-正则的简单图。又由于G0含2k-1个顶点，则G的顶点数为：k*(2k-1)+1。所以如果G有一个完美匹配M的话，则|M|=。假设M是G的一个完美匹配，则其边应来自k个独立的G0，和跟v0相关联的一条边。而每个G0，其包含的顶点数为2

4、k-1，所以G0能提供给M的边最多为k-1条，k个这样的G0能提供给M的边最多为k*(k-1)，因此M最多包含的边为k*(k-1)+1=k2-(k-1)< ，因此G不可能有完美匹配。解：令k=3，得到的图G0及G如下：V0V1V2V3V5V4V1V2V3V5V4V1V2V3V5V44设为偶数，举出没有完美匹配的-正则简单图的例子. 分析：当k为偶数时，取G=Kk+1，则G的顶点数为k+1，显然G的顶点数为奇数，所以G无完美匹配。解：令k=2时，可构造出无完美匹配的2-正则图。5两人在图上进行对奕双方分别执黑子和白子，轮流向G的不同顶点下子，要求当i >0时，邻接，并规定最后可下子的

5、一方获胜。若规定执黑子者先下子，试证明执黑子的一方有取胜的策略当且仅当G无完美匹配。分析：假设G有完美匹配，则G的每个顶点都是M-饱和点，这样先下者无论取哪个顶点，后下者都可取其相邻的M-饱和点，这样先下的人必输；因此先下的人如要赢的话，G中肯定无完美匹配。 反过来，如果G中无完美匹配，由于任何图都有最大匹配，则可找到G的一个最大匹配M，由于M不是完美匹配，因此G中存在M-非饱和点v，先下的黑方就可找到这个点下，则与v相邻的下一个点必是M-饱和点，不然，Muv就是一个更大的匹配，与M是最大匹配矛盾。同理中不存在可增广路，故黑方所选必是饱和点，如此下去，最后必是白方无子可下，故黑方必胜。 证明：

6、必要性（反证法） 若中存在一个完美匹配，则中任何点都是饱和点。故不论执黑子（先下者）一方如何取，白方总可以取中和关联边的另一端点作为，于是，黑方必输。 充分性. 设中不存在完美匹配，令是的最大匹配，而是非饱和点。于是，黑方可先取点，白方所选必是饱和点（因是最大的匹配）由的最大性可知中不存在可增广路，故黑方所选必是饱和点，如此下去，最后必是白方无子可下，故黑方必胜。6证明：二分图有完美匹配当且仅当对任何，有 成立 举例说明若不是二分图，则上述条件未必充分。分析：由定理9.1.2Hall定理，对于具有二划分（X,Y）的二分图，G有饱和X中每个顶点的匹配当且仅当对任意的,有，显然如果G有完美匹配M的

7、话，则M既饱和X，也饱和Y。但当G不是二分图时，这个结论不一定成立，如K2n+1对任意的满足，但它无完美匹配。 证明：必要性. 设有完美匹配，则饱和及，由定理和对任何或，有今任取，有于是有 充分性：设对任何，有.即任取，有，于是由定理，存在饱和的匹配，同理，存在饱和的匹配，从而，易知和都是完美匹配。当不是二分图时，条件不充分，如。7个学生做化学实验，每两个人一组，如果每对学生只在一起互作一次实验，试作出一个安排，使任意两个学生都在一起做过实验。分析：该题可转化为对具有2n个顶点（可分别记为0，1，2，2n-1）的完全图构造其不同的2n-1个完美匹配，使得（0，1）（0，2）（0，2n-1），（

8、1，2）（1，3），（1，2n-1），（2n-2,2n-1）在这2n-1个匹配中出现且仅出现一次。 解： 共安排2n-1次实验，可使任意两个学生都在一起做过实验。安排如下： 第1次：(0, 1), (2, 2n-1), (3, 2n-2), , (x, y)。 其中， x+y=2n+1; 第2次：(0, 2), (3, 1), (4, 2n-1), , (x, y) 。 其中， x+y=2n+3; 第2n-1次：(0, 2n-1), (1, 2n-2), (2, 2n-3), , (x, y) 。 其中， x+y=2n-1;8试证明：任何一个（0,1）矩阵中，包含元素1的行或列的最小数目，等于

9、位于不同行不同列的1的最大数目。分析：由定理9.2.2，对二分图G，均成立（其中为G的最大匹配数，为G的点覆盖数）。将给定的（0，1）矩阵表示成一个二分图，.其中当且仅当该题转化为了判断G的和的关系。 证明： 设是一个（0,1）矩阵.将表示成一个二分图，.其中当且仅当于是，的（最小）点覆盖数等于含中元素1的行（第行元素1的数目表示顶点覆盖的边之数目）或列（第列元素1的数目表示顶点覆盖的边数目）的数目。而的最大匹配数等于中位于不同行不同列的1的最大数目.由定理9.2.2知，若为二分图，则。故结论成立.9能否用5个的长方表将图9-13中的10个正方形完全遮盖住？图9-13分析：按如下方法作出图：在

10、图9-13的每个正方形格子中放一个顶点，与邻接当且仅当与所在的方格有公共边。则该问题等价于判断相应图是否有完美匹配，解：按照分析，构造图如下：则有，由定理9.1.3可判断它没有完美匹配。因此不能用5个的长方表将图9-13中的10个正方形完全遮盖住。u10试证明：是二分图当且仅当对的每个子图均有。分析：若G=（X，Y）是二分图，显然X和Y都构成G的点独立集，所以G的最大独立数，且；而二分图的每个子图显然也是二分图。证明：必要性.设是二分图，于是的任何子图也是二分图，设，。不妨设。显然 ， 因此，。于是，。充分性. 若不是二分图，则中含奇回路。令。显然，。 矛盾。故是二分图。11试证明：是二分图当

11、且仅当对的每个适合的子图，均有.分析：是指G的最大独立集，是指G的边覆盖数。 如果G是不含孤立点的二分图（X，Y），显然=max(|X|,|Y|)，因此如果能证明=max(|X|,|Y|)，则对不含孤立点的二分图G，有证明： 必要性. 设是二分图。 ，即无孤立点。显然也是二分图，设，且。于是，。而一条边最多覆盖一个顶点，故。但由于无孤立点，因此，故。充分性. 若不是二分图，则含奇回路。设。于是 ，而。矛盾。故必为二分图。12设是具有划分（X，Y）的二分图。证明：若对于任何.均有，则有饱和中每一顶点的匹配。分析：根据定理9.1.2，二分图G有饱和X中每个点的匹配当且仅当对任何，有根据这个结论，如

12、果能说明满足条件的二分图G中不存在任何，有，则题目得证。证明： 由题意知，对。若中不存在饱和的匹配，则由Hall定理，存在，使。设，其中。由对任何，得，但由于S中的点关联的边都是的点关联的边，因此，因此有，但，因此在中总存在一点，有。矛盾。故中存在饱和的匹配。13证明（Hall定理的推广）：在以为二划分的二分图G中，最大匹配数为 分析：由定理9.2.2有：如果一个图G是二分图，则，是G的最大匹配数，是G的最小覆盖。因此如果能说明等于的话，则本题得以证明。证明：由于，所以=显然是G的一个覆盖，而G的任意一个覆盖都可以写成的形式，所以=因此有=14证明：在无孤立点的二分图G中，最大独立集的顶点集(

13、G)等于最小边覆盖数。证明：参见题1115在9个人的人群中，假设有一个人认识另外两个人，有两个人每人认识另外4个人，有4个人认识另外5个人，余下的两个人每人认识另外的6个人。证明：有3个人，他们全部互相认识。分析：将该题中的人用图中的节点表示，两个节点有连线当且仅当两个人认识，则该题转化为求证满足上述条件的图G含有一个K3。 要判断一个图是否含有K3，我们先要了解以下概念和定理：T2，p：具有p个顶点的完全2分图，如果p是偶数，则该图的每一部分顶点数为p/2；如果p为奇数，则该图的其中一部分顶点数为(p-1)/2，另一部分顶点数为(p+1)/2。Turan定理（托兰定理）的推论：若简单图G不含

14、K3，则E(G)E(T2,p)，且当E(G)=E(T2,p)时，有该定理的严格内容为：若简单图G不含Km+1，则E(G)E(Tm，p)，且当E(G)=E(Tm，p)时，有其中Tm，p为具有p个顶点的完全m部图。这里我们令m=2，只说明我们所要的结论。 这个定理的证明请参看Bondy和Murty著的Graph Theory with Applications中的定理7.9及其证明。按照这个定理，我们只需判断E（G）>E(T2，9)=20即可。证明： 方法一：由题意，可作一个9个点的图，各顶点度序列为。于是有> E(T2，9)=4*5=20由托兰定理推论有G含有一个K3，所以9人中的至

15、少有三个相互认识。方法二（反证法）假设9人中的任意三个都互不认识。由题意，设，如图，于是，中的任何两顶点互不邻接，从而。因此，只有或以及。但由题设，至少有8人认识3个以上的人，此与题意不符。16设（）是简单图，且，则中包含三角形，请证明此结论。分析：该题也可利用托兰定理的推论，如果能证明q>E（T2，p），则可判断G中包含三角形。证明：当p为偶数时，E（T2，p）=由已知条件E（G）= E（T2，p） 当p为奇数时，E（T2，p）=由已知条件E（G）=>=E（T2，p）由以上分析可知，当时，有E（G）> E（T2，p），所以G中包含三角形。17试找出一个简单图，使得，但不包含

16、三角形。分析：由于T2，p不包含三角形，且当p为偶数时，当p为奇数时，所以任意的T2，p都是满足题目条件的不包含三角形的图。解：取p=4，则T2，4右图所示。18将的边着红色或兰色，使其中既无三边红色的，也无10条边全着兰色的。分析：如教材图9-11，将图中不邻接的两顶点之间用兰色的边联结，将邻接的两顶点之间的边着成红色，即满足题要求。解：着色结果如下图。19设，求证分析：是指包含k团或l独立集的顶点数最少的图的顶点数。显然，如果定，的由定理9.3.3当m2时，。证明 , 20证明：当时，分析：此结论的证明可仿照定理9.3.3的方法令，如果能证明Yp中只有不到半数的图含有k团，同时Yp中也只有

17、不到半数的图含有k独立集。于是Yp中必存在某个图它既不含有k团，也不含k独立集，由于这个结论对任意的图都成立，因此有: 证明：在定理9.3.3的证明中，取.于是，有令，则 又，故对于一切，于是，仿定理9.3.3之证明，即得21在匈牙利算法的第3步中，假如y是非M饱和的，如何得到一条从u到y的M可增广路？分析： 由二分图的定义及增广路径的定义，可知二分图中的增广路径具有如下性质：(1) 起点和终点都是非M-饱和点，而其它所有点都是M-饱和点。(2) 整条路径上没有重复的点。(3)路径上总共有奇数条边，且所有第奇数条边都不在M中，所有第偶数条边都在M中。(4)把增广路径上的所有第奇数条边加入到原匹

18、配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。解：根据以上分析，可得到求从u到非M饱和点y的M可增广路径的算法如下：1For i=0 to n 2. pre(vi)=null3 Succ(vi)=null 4 d(u)=0,d(vi)=/初始置每个顶点的前导和后继顶点为null，u与u的距离为0，其他点与u的距离为5 S=u /以u为初始顶点构造所有的M-交错路，直到顶点y在某条交错路上为止4While (y不属于S) 5 任取S中的顶点v，6. if succ(v)=null7 For 每个与v邻接的顶点w 8 If

19、（w是M-饱和点并且 pre(w)null）d(w)=d(v)+1 9. if （(d(w)是奇数并且vw不属于M)或者(d(w)是偶数并且vw属于M)9 succ(v)null，pre(w)=v，S=SW 10 11 /结束while循环找到了一条从u到y的M-可增广路算法结束以后得到一条路径P=ypre(y) pre(pre(y) u则P-即为一条从u到y的M-可增广路径。22说明在匈牙利算法的第3步中，执行 后，所得到的M 仍是G 的一个匹配. 说明：因为P是一条M可增广路，所以可以看作在P上，保留第奇数条边，去掉第偶数条得到的一个边集，显然P的所有偶数条边是没有公共顶点的，所以仍是G的一个匹配。23在图9-12中，将边x3y4去掉，利用匈牙利算法求所得二分图的完美匹配，若不存在，则给出使|NG