离散数学第9章习题答案

习题9

1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。

证明：（1）先证结论：

因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。■

2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。

证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤ 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■

3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）

解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明：

(6 , 3, 3, 2, 2 ) 对应图G的点集合V= { v1,v2,v3,v4,v5}

v1 v2 v3v5 v4

每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)

1

v1 v2 v3v5 v4

将奇数3，3 对应的结点v2,v3一组，画一条连线 v1 v2 v3v5 v4

其他序列可以类式作图，当然大家也可以画图其它不同的图形。■

4．证明：在（n，m）图中。

证明：图的点度数是一组非负整数{d(v1),d(v2)…d(vn)}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为δ，平均值 = (d(v1)+d(v2)…+d(vn))/n = 2m/n,所以。■

5．证明定理10.2。

【定理10.2】 对于任何（n,m）有向图G =（V，E），

证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。因此，上述关系等式成立。■

6．设G是（n，m）简单二部图，证明：。

证明：本题目，我们只需要说明n阶的简单二部图的边数的最大值 = 即可。

设n阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n。此种情况下，当G为完全二部图时，有最多的边数，即max(m) = |V1||V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。及max(max(m)) = ,所以n阶二部图(n,m), ■

2

7. 无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。

解：根据握手定理有： 21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■

10．判断图10.29中的两个图是否同构，并说明理由。

???????图10.29 9-1.15图

?????

解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构■

13. 设有向图D=如下图10.31所示。

(1) 在图中找出所有长度分别为1，2，3，4的圈 (至少用一种表示法写出它们，并以子图形式画出它们)。

(2) 在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。

解：(1)

C=AA C=Ae4Be8Ce5A C=Ae4Be7Ce6De2A C=ADA (2)子图略

C=Ae4Be7Ce5A C=Ae4Be8Ce6De2A

3

长度为三的回路：Ae1Ae1Ae1A,Ae1Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A

长度为四的回路：AAAAA，AAADA，AABe7CA,AABe8CA,ABe7CDA,ABe8CDA

长度为五的回路：AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7CDA,AABe8CDA, AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A, ADAe4Be7Ce5A,ADAe4Be8Ce5A■

15. 若u和v是图G中仅有的两个奇数度结点,证明u和v必是连通的。

证明：反证法，假设u和v不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立■

17.设(n, m)简单图G满足,证明G必是连通图。构造一个的非连通简单图。

证明：假设G不连通，分支G1，G2．．Ｇｋ，那么他们的边数的最大值ｍａｘ（ｍ）＝Σ（ｎ

（ｎ－１）／２＝（ｎ－１）／２Σ（ｎｉ－１）＝（ｎ－ｉ－１）ｎｉ／２≤Σ（ｎｉ－１）

１）（ｎ－ｋ）／２，所以，只有当k=1时，才能满足题设要求，G是连通图。如果将顶点集合分成两个点集，|V1|=1，|V2|=n-1,构成如下的有两个分支的非连通简单图，G1=（1，0），G2=Kn-1,满足题设条件■

18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价: (1）G无割边；

(2) G中任何两个结点位于同一回路中；

(3) G中任何一结点和任何一边都位于同一回路中； (4) G中任何两边都在同一回路中。

证明：（1）=〉（2）

因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p’,以此类推，可以找到一条核p每条边都不相同的p’’=v…u,这样p和p’’就构成了一条回路。 （2）=〉（3）

因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=u…v1…v2…u,那么将回路中v1…v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1≠C2，C1=u…v1…u,C2=u…v2…u,那么构成新的道路P=u…v1…u…v2…u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1…v2用v1v2=e替换，就得到新的新的回路，并满足要求. （3）=〉（4）

对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（3）存在回路C1 = u1…v1v2…u1,C2=u2…v1v2…u2。那么可以形成新的闭道路P=u1…v1v2…u2…v1v2…u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1…u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求. (4)=>(1)

因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不

4

连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边■

19. 设G=(V,E)是点度均为偶数的连通图。证明:对任何。

证明：G-v最多产生d(v)个奇数度点，又因为每个连通分支中奇数度点的个数是偶数，即G-v的连通分支最少有两条边和v相连，所以总连通分支数小于等于d(v)/2■

21. 证明:在非平凡连通图G中,e为割边的充要条件是它不包含于G的任何圈中。

证明： 1） e为割边 =〉e不包含于G的任何圈中

假设e包含在某一圈Ci中，那么删除此边，但边关联的两个邻接点依然连通，所以没有破坏原图的连通性。因此不是割边，矛盾。所以假设不成立，既e不包含于G的任何圈中；

2）e不包含于G的任何圈中 =〉e为割边

假设e为割边，那么删除此边，生成子图依然连通。e关联的两个邻接点有基本道路存在，此基本道路连同e构成一个圈。与题设矛盾。所以假设不成立，既e为割边。 根据1），2)可知，题设结论成立■

23. 证明:在具有n（n≥2）个结点的简单无向图G中，至少有两个结点的度数相同。

证明：此题可用鸽笼原理，因为n个结点的简单无向图G中，结点的度数只可能是0，1，2…n-1这n个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1，反之也然。所以n 个结点，最多有n-1种度数，其中必有至少两个结点的度数相同■

24. 设G是的简单图。证明:G中必有长度至少为的圈。

证明：设ｐ＝ｕ．．．ｖ是满足题设要求图Ｇ中的最长基本道路，那么ｄ（ｕ），ｄ（ｖ）都应该大于等于δ。那么，u,v的邻接点都应该在道路p 上，否则此道路可以延长，与其是最长路假设矛盾。如果u，v是邻结点，那么可以构成一个圈c= u…vu，其长度≥δ＋１。如果ｕ，ｖ不是邻结点，那么从ｐ的终点开始删除点，直到其为ｕ的邻结点为止，得到道路ｐ＇,可知道路p’，依然保持ｕ的所有邻结点都在ｐ＇上的性质，所以可构成一个圈ｃ＇＝ｕ．．．ｕ＇ｕ，其长度≥δ＋１，证毕■

25. 证明:G是单向连通图当且仅当存在一条包含G中全部结点的有向道路。

证明：假设不存在包含全部结点的有向道路，那么设ｐ＝ｖ１ｖ２．．．ｖｋ是Ｇ中最长的有向道路，且ｕ结点不包含在此有向道路中。ｕ和此道路中任何中间结点都不可能双向可达，且ｕ不能到达ｖ１，且ｖｋ也不能到达ｕ，否则，此最长路可扩充。那么由于道路上的每个结点和ｕ都单向可达，所以此最长路和ｕ之间的可达关系必然如下图所示：

5

解：n（n≥2）个结点的有向完全图中，每个都是欧拉图，因为每个节点都有相同的入度和出度，可以找到有向欧拉回路■

9. 证明:凡有割点的图都不是哈密顿图。

证明：反证法，假设存在有割点v的图是哈密顿图，那么此图存在哈密顿圈。在此圈中删除割点v，那么剩下的节点依然连通。这和割点的定义相矛盾，所以题设命题成立■

10. 证明: 4k+l阶的所有2k正则简单图都是哈密顿图。

证明：因为图是的正则简单图，因此对任意的u，v∈V, 有d(u) + d(v) = 4k. 根据定理13.4，存在哈密顿道路P= v1v2…v4k+1.

1）如果 v1v4k+1∈E, 则v1v2…v4k+1v1构成一个H圈； 2）如果v1v4k+1E，则是v1的邻接点，那么必为v4k+1的邻接点。否则，v4k+1点度为4k-1-2k=2k-1,与题设矛盾。假设vit-1v4k+1∈E，那么可构造H圈如下：v1…vit-1v4k+1 v4k…vitv1 因此，此图为哈密顿图■

11．在无向完全图Kn中有多少条没有公共边的哈密尔顿回路？

解：1) 设n=2k+1,将节点编号为0,1,2…2k,并作如下图示，

1 2k 2k-1 2k-2 0 2 3 4 K+3 K+2 K+1 k

在上图中先取一条哈密顿回路为0,1,2,2k,3,2k-1,4,…k+3,k,k+2,k+1,0,然后将圆周上的结点按逆时针方向依次转动一个位置，然后可以得到另一条回路为：0,2,3,1,4,2k,5,…k+4,k+1,k+3,k+2,0;显然，这两条回路是没有公共边。继续这样做下去，共可产生条无公共边的哈密顿回路。

若n=2k+2,那么只要在中间增加一个结点ｕ，就可以同样地得到条无公共边的哈密顿回路■

12. 11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生两旁所坐的人都不相同，问11人共进午餐最多能有多少天？

解：将１１个学生分别用结点表示，由于每个同学都可能邻座，因此每两个结点之间都有一条边，因此得到无向完全图Ｋ１１，每次午餐时学生都按照一条哈密顿回路落座，如果两条哈

16

密顿回路有公共边，则公共边端点所代表的学生就是相邻的。因此上述问题转化为求Ｋ１１有多少条无公共边的哈密顿回路问题，利用１１题的结论，共有(11-1)/2=5条无公共边的哈密顿回路，因此这１１个学生共进午餐最多能有５天■

13. 假定在n个人的团体中,任何2人合起来认识其余的n-2个人。证明:

(1)这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；

(2)当月时,这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人。

证明：因为任意两个人加起来认识其余的ｎ－２个人，那么每个人至少认识n-2个人。否则，设ｖ不认识ｕ，ｔ两人，那么ｕ和ｔ两个人将不能认识完剩下的ｎ－２个人，矛盾。当ｎ≥3时，将n个人看成图的结点，相互认识则在相关两个结点间有一条边，构成一个简单无向图G。此图中，任何两个结点的点度之和 d(u)+d(v)≥2(n-2)≥n-1,因此存在哈密顿道路，即这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；

当n≥4, 任何两个结点的点度之和 d(u)+d(v)≥2(n-2)≥n,因此图中存在哈密顿回路，即这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人■

14. 设G是(n, m)简单图。若 ,证明G必是哈密顿图。

证明：假设此图中存在两个点v,u 其点度之和d(v)+d(u)≤n-1,那么剩余n-2个结点的点度之和最大值为(n-2)(n-3) + n-1,那么整个图的最大点度之和为(n-2)(n-3)+n-1+n-1=n2-3n+4,但根据题设条件，点度之和Σd(u) = 2m ≥n2-3n+6.矛盾，因此任意两结点点度之和d(v)+d(u)≥n，因此图G必是哈密顿图■

15. 用两种以上的办法判别图13.11不是哈密顿图。 解：

方法1 ：删点法，如下

由上图可知，删除7个黑色点后，此图变成为具有9个分支的子图，根据哈密顿图的必要性判定定理ω(G-S)≤|S|可知，此图不是哈密顿图。

17

删除任何结点之前的原图 删除黑色结点之后 方法2：根据平面哈密顿图的面度公式：此图只有4度面，因此如果是哈图，则必须满足其中，代表内部面数，代表外部面数。但是，面的总数是13，无论如何不能成立，因此不是哈密顿图■

18

本文来源：https://www.bwwdw.com/article/lggv.html