发布时间 : 星期四 文章湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第二学期--图论与组合数学更新完毕开始阅读84a394ba84254b35effd341c
5．两人在图G上进行对奕双方分别执黑子和白子，轮流向G的不同顶点v0,v1,v2,?下子，要求当i >0时，vi与vi?1邻接，并规定最后可下子的一方获胜。若规定执黑子者先下子，试证明执黑子的一方有取胜的策略当且仅当G无完美匹配。
分析：假设G有完美匹配，则G的每个顶点都是M-饱和点，这样先下者无论取哪个顶点，后下者都可取其相邻的M-饱和点，这样先下的人必输；因此先下的人如要赢的话，G中肯定无完美匹配。
反过来，如果G中无完美匹配，由于任何图都有最大匹配，则可找到G的一个最大匹配M，由于M不是完美匹配，因此G中存在M-非饱和点v，先下的黑方就可找到这个点下，则与v相邻的下一个点必是M-饱和点，不然，M∪{uv}就是一个更大的匹配，与M是最大匹配矛盾。同理G中不存在M可增广路，故黑方所选vi必是M饱和点，如此下去，最后必是白方无子可下，故黑方必胜。
证明：必要性（反证法） 若G中存在一个完美匹配M，则G中任何点v都是M饱和点。故不论执黑子（先下者）一方如何取vi?1，白方总可以取M中和vi?1关联边的另一端点作为vi，于是，黑方必输。
充分性. 设G中不存在完美匹配，令M是G的最大匹配，而v0是非M饱和点。于是，黑方可先取v0点，白方所选v1必是M饱和点（因M是最大的匹配）由M的最大性可知G中不存在M可增广路，故黑方所选vi必是M饱和点，如此下去，最后必是白方无子可下，故黑方必胜。
6．证明：二分图G有完美匹配当且仅当对任何S?v(G)，有
|S|?NG(S) 成立
举例说明若G不是二分图，则上述条件未必充分。
分析：由定理9.1.2Hall定理，对于具有二划分（X,Y）的二分图，G有饱和X中每个顶点的匹配当且仅当对任意的S?X,有|S|?NG(S)，显然如果G有完美匹配M的话，则M既饱和X，也饱和Y。但当G不是二分图时，这个结论不一定成立，如K2n+1对任意的S?V(G)满足
|S|?|NG(S)|，但它无完美匹配。
证明：必要性. 设G有完美匹配M，则M饱和X及Y，由Hall定理和对任何S?X或
S?Y，有
|S|?|NG(S)|
今任取S?V(G)，有S?S1?S2,S1?X,S2?Y于是有
|S|?|S1?S2|?|S1|?|S2|?|NG(S1)|?|NG(S2)|
?|NG(S1?S2)|?|NG(S)|
46
充分性：设对任何S?V(G)，有|S|?|NG(S)|.
即任取S?X，有|S|?NG(S)|，于是由Hall定理，存在饱和X的匹配M(X)，同理，存在饱和Y的匹配M(Y)，从而|X|?|Y|，易知M(X)和M(Y)都是完美匹配。
当G不是二分图时，条件不充分，如G?K3。
7．2n个学生做化学实验，每两个人一组，如果每对学生只在一起互作一次实验，试作出一个安排，使任意两个学生都在一起做过实验。
分析：该题可转化为对具有2n个顶点（可分别记为0，1，2，…，2n-1）的完全图构造其不同的2n-1个完美匹配，使得（0，1）（0，2）…（0，2n-1），（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的行或列的最小数目，等于位于不同行不同列
的1的最大数目。
分析：由定理9.2.2，对二分图G，均成立??(G)??(G)（其中??(G)为G的最大匹配数，?(G)为G的点覆盖数）。将给定的（0，1）矩阵表示成一个二分图G(V1,V2,E)
V1?{u1,?,un}，V2?{v1,?,vn}.其中M(i,j)?1当且仅当(ui,vj)?E(G)
该题转化为了判断G的?(G)和??(G)的关系。
证明： 设Mm?n是一个（0,1）矩阵.将Mm?n表示成一个二分图G(V1,V2,E)，
V1?{u1,?,un}，V2?{v1,?,vn}.其中
M(i,j)?1当且仅当(ui,vj)?E(G)
于是，G的（最小）点覆盖数?(G)等于含Mm?n中元素1的行（第i行元素1的数目表示顶点ui覆盖的边之数目）或列（第j列元素1的数目表示顶点vj覆盖的边数目）的数目。而G的最大匹配数??(G)等于Mm?n中位于不同行不同列的1的最大数目.
由定理9.2.2知，若G为二分图，则??(G)?
9．能否用5个1?2的长方表将图9-13中的10个1?1正方形完全遮盖住？
47
?(G)。故结论成立.
图9-13
分析：按如下方法作出G?图：在图9-13的每个正方形格子中放一个顶点，u与v邻接当且仅当u与v所在的方格有公共边。则该问题等价于判断相应图G?是否有完美匹配，
解：按照分析，构造图G?如下：则有O(G?{u})?3?1?|{u}|，由定理9.1.3可判断它没有完美匹配。因此不能用5个1?2的长方表将图9-13中的10个1?1正方形完全遮盖住。
10．试证明：G是二分图当且仅当对G的每个子图H均有
u ?(H)?|V(H)|。
12分析：若G=（X，Y）是二分图，显然X和Y都构成G的点独立集，所以G的最大独立数?(G)?|X|， 且?(G)?|Y|；而二分图的每个子图显然也是二分图。
证明：必要性.设G是二分图，于是G的任何子图H也是二分图，设H?(X,Y)，
|X|?|Y|?|V(H)|。不妨设|X|?|Y|。显然 ?(H)?|X|， 因此，
2?(H)?2X?|X|?|Y|?|V(H)|。于是，?(H)?1|V(H)|。 2充分性. 若G不是二分图，则G中含奇回路C。令H?C。显然，
?(H)??V(H)/2??
1|V(H)|。 矛盾。故G是二分图。 248
11．试证明：G是二分图当且仅当对G的每个适合?(H)?0的子图H，均有?(H)???(H). 分析：?(G)是指G的最大独立集，??(G)是指G的边覆盖数。
如果G是不含孤立点的二分图（X，Y），显然?(G)=max(|X|,|Y|)，因此如果能证明
??(H)=max(|X|,|Y|)，则对不含孤立点的二分图G，有?(G)???(G)
证明： 必要性. 设G是二分图。 H?G，?(H)?0，即H无孤立点。显然H也是二分图，设H?(X,Y)，且|X|?|Y|。于是，?(H)?|X|。而一条边最多覆盖一个顶点，故
??(H)?|X|。但由于H无孤立点，因此，??(H)?X，故??(H)?|X|??(H)。
充分性. 若G不是二分图，则G含奇回路C?H。设|V(H)|?2n?1,n?1。于是
?(H)?n，而??(H)?n?1??(H)。矛盾。故G必为二分图。
12．设G是具有划分（X，Y）的二分图。证明：若对于任何u?X,v?Y.均有d(u)?d(v)，
则G有饱和X中每一顶点的匹配。
分析：根据定理9.1.2，二分图G有饱和X中每个点的匹配当且仅当对任何S?X，有|S|?|NG(S)|根据这个结论，如果能说明满足条件的二分图G中不存在任何S?X，有|S|?|NG(S)|，则题目得证。
证明： 由题意知，对?u?X,d(u)?1。
若G中不存在饱和X的匹配，则由Hall定理，存在S?X，使|S|?|NG(S)|。
设S?{u1,?,um}，NG(S)?{vj1,?,vjn}，其中m?n。 由对任何u?X,v?Y，d(u)?d(v)，得都是NG(S)的点关联的边，因此
?d(u)?u?S因此在NG(S)中总存在一点，有d(vjr)?d(ut)。矛盾。故G中存在饱和X的匹配。
13．证明（Hall定理的推广）：在以G(X,Y)为二划分的二分图G中，最大匹配数??(G)为 ??(G)?v?NG(S)?d(u)??d(v)，但由于S中的点关联的边
?d(v)，因此有?d(u)??d(v)，但m?n，
u?Sv?NG(S)u?Sv?NG(S)min{|X?S|?|Ns?xG(S)|}
分析：由定理9.2.2有：如果一个图G是二分图，则??(G)??(G)，??(G)是G的最大匹配数，
?(G)是G的最小覆盖。因此如果能说明min{|X?S|?|NG(S)|}等于?(G)的话，则本题得以
证明。
s?x证明：由于{X?S}?NG(S)??，所以|X?S|?|NG(S)|=|{X?S}?{NG??(S)}|
显然{X?S}?{NG而G的任意一个覆盖都可以写成{X?S}?{NG??(S)}是G的一个覆盖，??(S)}的
min{|X?S|?|N(S)|} 因此有??(G)??(G)=min{|X?S|?|N(S)|}
形式，所以?(G)=
Gs?xGs?x49