第9章 习题解答
26
第9章 习题解答
习题 9.7
1.当n和m满足什么条件时，完全二部图Kn,m是欧拉图?
解：当n与m都为偶数时，Kn,m中每个结点都是偶数度的，这时Kn,m为欧拉图。 2.当n和m满足什么条件时，完全二部图Kn,m是汉密尔顿图?
解：当n=m时，Kn,m任何一对结点的度数之和大于等于结点数n＋m，根据定理9.5.5的推论，在G中存在一条汉密尔顿回路。所以，Kn,m是汉密尔顿图。
3.图9.66是二部图，M= ?(a1,b5),(a3,b1),(a4,b3)?是一个匹配。求图中的最大匹配。
解：图9.66的匹配M=?(a1,b5),(a3,b1),(a4,b3)?。用(*)标记V1中所有M的非饱和点a2。 ①选V1的新标记过的结点a2，用(a2)标记不通过M的边与a2邻接且尚未标记过的V2
的结点b1，b3。
②选V2的新标记过的结点b1，用(b1)标记通过M的边与b1邻接且尚未标记过的V1的结点a3；类似地用(b3)标记a4。
③选V1的新标记过的结点a3，用(a3)标记不通过M的边与a3邻接且尚未标记过的V2
的结点b4。也可以选V1的新标记过的结点a4，用(a4)标记不通过M的边与a4邻接且尚未标记过的V2的结点b4。
b4是M的非饱和点，标记结束。如图9.96所示。
从b4倒向追踪到标记有(*)的结点，就得到了M可扩路：a2b1a3b4或a2b3a4b4，取前者。 把M可扩路a2b1a3b4中的边(a3,b1)从M中去掉，而把(a2,b1)和(a3,b4) 添到M中得到新的匹配M′=?(a1,b5), (a2,b1),(a3,b4),(a4,b3)?，如图9.97所示。
因为V1中已无M′的非饱和点，即图中已无M′可扩路，所以M′=?(a1,b5), (a2,b1),(a3,b4), (a4,b3)?就是最大匹配
27
第9章 习题解答
4.某单位按编制有7个工作空缺：p1，p2，…，p7，有10个申请者：a1，a2，…，a10。它们能胜任的工作集合依次是?p1, p5, p6?，?p2, p6, p7?，?p3, p4?，?p1, p5?，?p6, p7?，?p3?，?p2, p3?，?p1, p3?，?p1?，?p5?。如果规定每个申请者最多只能安排一个工作。试给出一种方案使分配到工作的申请者最多。
解：按题意构造一个二部图G=
在图9.98中可以求得一个最大匹配： M=?(p1,a9),(p2,a2),(p3,a6), (p4,a3),(p5,a4),(p6,a1),(p7,a5)?
5.设G=?V1,V2,E?是二部图，|V1|＞|V2|，证明如果V1的每个结点的度数不小于δ，那么V2中必有一个结点的度数大于δ。
证明：令|V1|=n1，?v?V1，deg(v)≥δ，则|E|≥n1δ，
再令|V2|=n2，设?v?V2，deg(v)≤δ，则|E|≤n2δ，从而n1δ≤|E|≤n2δ，于是n1≤n2，即|V1|≤|V2|，与条件矛盾。
6.证明：树是二部图。 证明：设G是树，以下证明G是二部图。?v0?V，令
X={v|从v0到v的距离是偶数} Y=V－X
显然X∩Y=?，X∪Y=V，?(vi,vj)?E，由于树中无回路和X、Y的定义，则必有vi?X，vj?Y或vi? Y，vj?X，由二部图的定义知，G=?V,E?=
n27.如果G是具有n个结点，m条边的二部图，证明m≤。
4证明：设G=
－(nn1－n1)=－2··n1＋ n1=(－n1)2≥0
2244 28
第9章 习题解答
n2n22
所以，≥nn1－ n1≥m，即m≤。
44
29
第9章 习题解答
习题 9.8
1.设G是至少有11个结点的无向简单连通平面图，证明G的补图G一定是非平面图。 证明：反证法。
设G是平面图，G的结点数为v，边数为e，G的结点数为v′，边数为e′。
1由补图的定义知v=v′，e＋e′=v(v?1)，由不等式e≤3v–6，e′≤3v′–6=3v–6，相加得
2122
v(v?1)= e＋e′≤6v－12，v－v≤12v－24， v－13v＋24≤0，即(v－11)( v－2)＋2≤0。 2另一方面，当v≥11时，(v－11)( v－2)v＋2＞0，矛盾。 所以，补图G一定是非平面图。
2.证明：每个面至少有4条边围成的任何简单连通平面图中，m≤2n－4，其中n为结点数，m为边数。
证明：设该图有r个面，所有面次数之和大于等于4r，另一方面，所有面次数之和等111于边数的2倍。所以2m≥4r，即r≤m，代入欧拉公式2=n－m＋r≤n－m＋m= n－m，
222化简后得m≤2n－4。
3.证明：在6个结点12条边的简单连通平面图中，每个面用3条边围成。 证明：设v和e分别为该图的结点数和边数，则v=6，e=12，由欧拉公式r=2＋e－v=8，
即图中有8个面，又因为?deg(ri)=2e=24，而每个面的次数deg(ri)≥3，故必有deg(ri)=3，
i?18i=1…8。即个面用3条边围成。
4.证明：小于30条边的平面简单图有一个结点度数小于等于4。 证明：反证法。
假设每个结点的度大于4，即deg(ri)≥5，因为2e=?deg(vi)≥5v，即v≤
i?1n2e。由于e5≤3v－6，代入后得到e≤
6e－6，即有e≥30，与边数小于等于30向矛盾。 55.设G是简单平面图，面数r＜12，?(G)≥3，证明G中存在次数小于等于4的面。 证明：不妨设G是连通的，否则对它的每个连通分支进行讨论(因为每个连通分支都满足条件)。
设n，m，r分别为G的结点数，边数和面数。则G中欧拉公式2=n－m＋r成立，又2由?(G)≥3可以推出3n≤2m，即n≤m。将上述结论和已知条件r＜12代入欧拉公式得2
32＜m－m＋12，化简后得m＜30， 32另一方面，若所有的面均至少由5条边围成，则5r≤2m，即r≤m，代入欧拉公式
5
30