四川大学离散数学(冯伟森版)课后习题答案习题参考解答(图论部分)
习题十
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= { v 1,v 2,v 3,v 4,v 5}
每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
v 1
v 5
v 3
v 4
v 2
将奇数3，3 对应的结点v 2,v 3一组，画一条连线
其他序列可以类式作图，当然大家也可以画图其它不同的图形。■
4．证明：在（n ，m ）图中。
证明：图的点度数是一组非负整数{d(v 1),d(v 2)…d(v n )}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为δ，平均值 = (d(v 1)+d(v 2)…+d(v n ))/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), ■
v 1 v 5
v 3
v 4
v 2
v 1
v 5
v 3
v 4
v 2
7. 无向图G 有21条边，12个3度数结点，其余结点的度数均为2，求G 的阶数n 。
解：根据握手定理有： 21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■
8．证明：完全图的点诱导子图也是完全图。
证明：方法1
为证明此结论，我们先证两个引论：
引论1：设G(V,E)为母图，,则G 的任意子图G'(V ’,E ’)是G 关于V ’的点诱导子图G''(V ’,E ’’)的子图。
引论2：引论1中G ’’(V ’,E ’’)的任意点诱导子图，也是G 图的点诱导子图。 证明：略，请读者证明。
设有完全图Kn( n ≥1),现根据其p 阶点诱导子图作归纳证明。
Kn 的1阶点诱导子图，显然是完全图，且都是K1图。当n ≥2，Kn 的2阶点诱导子图，显然是完全图，且都是K2图
假设Kn 的p(n >p >2)阶点诱导子图，为Kp 图，那么对任意的p+1阶点诱导子图G ，根据引理2结论，G 的任意p 阶点诱导子图G ’为Kn 的p 阶点诱导子图，且为Kp 图。因此，G 必为Kp+1图。
根据以上论证可得原命题成立■ 方法2
因为完全图的任意两个顶点均邻接，所以点导出子图任意两个顶点也邻接，为完全图。■ 9．若，称G 是自补图。确定一个图为自补图的最低条件；画出一个自补图来。
解：设G 为(n,m)图，为(n,m`)图， 根据补图的定义有，至少应该满足 m+m`=n(n-1)/2 (1) 根据同构的定义有，至少应该满足 m=m` (2)
(1),(2)联立求解得：m=n(n-1)/4, 及一个图为自补图，最低条件为结点数为4的倍数或为4的倍数加1。 图示略■
10．判断图10.29中的两个图是否同构，并说明理由。
图9-1.15
解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构■
11．证明： 图10.30中的两个图是同构的。
图
10.29
解：略■
12. 求具有4个结点完全图K 4的所有非同构的生成子图。
解：我们可以把生成子图按总度数不同进行分类，不同总度数的子图类决不同构。总度数相同的子图类中，再去找出不同购的子图。因此求解如下： Σd(v) = 0: (0,0,0,0) =2: (1,1,0,0)
=4: (2,1,1,0) (1,1,1,1)
=6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3)
总共10个不同构生成子图■
13. 设有向图D=
(1) 在图中找出所有长度分别为1，2，3，4的圈 (至少用一种表示法写出它们，并以子图形式画出它们)。
(2) 在图中找出所有长度分别为3，4，5，6
的回路，并以子图形式画出它们。
解：(1)
图10.30
(2)子图略
长度为三的回路：Ae 1Ae 1Ae 1A,Ae 1Ae 3De 2A,Ae 4Be 7Ce 5A,Ae 4Be 8Ce 5A
长度为四的回路：AAAAA ，AAADA ，AABe 7CA,AABe 8CA,ABe 7CDA,ABe 8CDA
长度为五的回路：AAAAAA,AAAADA,AAABe 7CA,AAABe 8CA,AABe 7CDA,AABe 8CDA, AADADA,AAAe 4Be 7Ce 5A,AAAe 4Be 8Ce 5A, ADAe 4Be 7Ce 5A,ADAe 4Be 8Ce 5A ■
14. 试证明在任意6个人的组里，存在3个人相互认识，或者存在3个人相互不认识。
证明：设A 为6人中的任一人，那么A 要么至少与3人认识，要么至少与3人不认识，二者必居其一。
假设A 与B ，C ，D 三人认识，如果B ，C ，D 三人互不认识，结论成立
如果B ，C ，D 三人中，至少有两人相互认识，则它们和A 一起，构成相互认识的3人，结论成立。
同理，A 至少与3人不认识，结论也成立。因此，题设结论成立■
15. 若u 和v 是图G 中仅有的两个奇数度结点,证明u 和v 必是连通的。
证明：反证法，假设u 和v 不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立■
16. 证明:G 是二部图当且仅当G 的回路都是偶长回路。
证明：设二部图G ，顶点分为两个集合V1 ，V2 充分性：
先证明在二部图中，奇长路的道路的两个端节点一定分别在两个顶点集合中，对道路长度使用归纳法，
（1） 当道路长度为1是，根据二部图的定义，每条边的两个顶点分别在两个点集合中，
结论成立
（2） 假设道路长度为2n-1 ( n ≥2)时结论成立
（3） 当道路长度为2n+1时，设P=v 1v 2…v 2n-1v 2n v 2n+1,在此路径上删除最后两个结点，那
C=AA
C=ADA C=Ae 4Be 7Ce 5A
C=Ae 4Be 8Ce 5A C=Ae 4Be 7Ce 6De 2A
C=Ae 4Be 8Ce 6De 2A
么道路P将变为长度为2n-1的奇长道路，根据假设，v1,v2n-1分别在两个顶点集合中，那么v2n和v1在同一顶点集合中，而v2n+1和v1在不同顶点集合，结论成立
因为G中的任何回路，写成道路的形式，起点和终点时一个结点，当然在同一个顶点集合中，因此长度必为偶数；
必要性：（仅对连通分支证明）
在图中任意取一点着色为白色，将和此点最短距离为奇数的点着色为黑点，为偶数的着色为白点，那么将结点分为白色和黑色连个点集，任何同色点之间没有边相连。否则将形成奇数长度的回路，例如同色结点v1，v2 相邻，那么从初始着色点v开始通过最短路径可以形成如下回路v…v1v2…v,因为v…v1,v2…v长度和为偶数，那么回路v…v1v2…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是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边■
19. 设G=(V,E)是点度均为偶数的连通图。证明:对任何。
证明：G-v最多产生d(v)个奇数度点，又因为每个连通分支中奇数度点的个数是偶数，即G-v的连通分支最少有两条边和v相连，所以总连通分支数小于等于d(v)/2■
20. 证明:图中距离满足欧几里德距离的三条公理。
证明：（1）d(u,v)≥0,即任何两个结点之间的最短路长度大于等于0
显然，结点ｕ与自己之间的距离为０，而和其他结点之间的最短距离不为０。
（２）ｄ（ｕ，ｖ）＝ｄ（ｖ，ｕ），两个结点之间的最短距离相等
显然，如果长度为ｋ的最短道路p=u…v ，即使u到v的最短道路，也是v到u的最短道路。（3）d(u,v)+d(v,w)≥d(u,w)
假设d(u,v)+d(v,w)≤d(u,w)，那么最短道路P=u…w ,就不是最短道路，因为另一条道路p’=u…v…w其长度小于Ｐ，与最短道路相矛盾，因此原结论存立■
21. 证明:在非平凡连通图G中,e为割边的充要条件是它不包含于G的任何圈中。
证明：1）e为割边 =〉e不包含于G的任何圈中
假设e包含在某一圈Ci中，那么删除此边，但边关联的两个邻接点依然连通，所以没有破坏原图的连通性。因此不是割边，矛盾。所以假设不成立，既e不包含于G的任何圈中；
2）e不包含于G的任何圈中 =〉e为割边
假设e为割边，那么删除此边，生成子图依然连通。e关联的两个邻接点有基本道路存在，此基本道路连同e构成一个圈。与题设矛盾。所以假设不成立，既e为割边。
根据1），2)可知，题设结论成立■
22. 证明:若G是3度正则的简单图,则。（请冯老师帮助解答下）
证明：
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中全部结点的有向道路。
证明：假设不存在包含全部结点的有向道路，那么设ｐ＝ｖ１ｖ２．．．ｖｋ是Ｇ中最长的有向道路，且ｕ结点不包含在此有向道路中。ｕ和此道路中任何中间结点都不可能双向可达，且ｕ不能到达ｖ１，且ｖｋ也不能到达ｕ，否则，此最长路可扩充。那么由于道路上的每个结点和ｕ都单向可达，所以此最长路和ｕ之间的可达关系必然如下图所示：
ｖｋ／２＋１
ｖｋ／２
ｋ为偶数ｕ
ｖｋ＋１／２
ｖｋ＋１／２－１
ｋ为奇数
ｕ
ｖｋ＋１／２＋１
当ｋ为偶数时，道路可扩充为v 1…v k/2…u …v k/2+1…v k ,而当ｋ为奇数时，不管ｖｋ＋１／２与ｕ之间是如何单向可达的，都可以构造出更长的有向道路，矛盾，所以Ｇ中一定存在包含所有结点的有向道路■
26. 无向图G 如图10.32所示，先将此图顶点和边标出，然后求图中的全部割点和割边。
图10.32
解：标注如下所示：
根据标记后的图，可求得割点分别为：ｕ４，ｕ７，ｕ８，割边分别为：ｕ４ｕ５，ｕ７ｕ８，ｕ８ｕ９■
27. 求图10.33的全部强分图和单向分图。
图10.33
解：将图重新标记如下：
ｕ６
ｕ５
ｕ４
ｕ３
ｕ２
ｕ１
ｕ７
ｕ８
ｕ９
那么此图的邻接矩阵为，通过计算可求得其强分图矩阵为：
因此，此图有两个强分图，一个包含一个结点Ｖ９ ，一个包含其它的８个节点。由于两个强分图之间存在有向道路，因此全部９个结点，构成了单向分图■
28. 证明：一个连同无向简单图中，任意两条最长路至少有一个公共顶点。
证明：假设两条最长路ｐ１＝ｖ１ｖ２．．．ｖｋ，ｐ２＝ｕ１ｕ２．．．ｕｋ没有公共点，那么两条道路上的点集之间就有道路相连，否则就不是连通图了。设此道路起点是ｐ１上ｍ点，终点是ｐ２上的ｗ点．可根据如下情况进行调论：（１）ｍ，ｗ是ｐ１，ｐ２的中间结点，那么可构成新道路 Ｐ＝ｖ１ｖ２．．．ｍ．．．ｗ．．．ｕｋ，此路至少比Ｐ１长1，矛盾。（2）假设m 和w 不能均分p1,p2,那么可以将两个长路段和m,w 之间的道路进行拼接，那么可得到比p1长的道路，与ｐ１，ｐ２是最长路矛盾。因此任意两条最长路至少有一个公共顶点■
29. 证明：若G 是n 阶无向简单图，G 中每一对不相邻的顶点的度数之和至少是n -1，则G 是连通图。
证明：假设G 不是连通图，G1，G2 是G 的两个连通分支，分别为n1,n2阶连通无向简单子图，则n1+n2≤n 。对G1中任意结点v1,和G2中任意结点v2而言，v1的最大点度为n1-1,v2的最大结点度为n2-1;则v1,v2的点度之和，最大为n1+n2-2≤n-2 30. 求出图10.34的邻接矩阵、可达性矩阵、强分图和关联矩阵。 图10.34 ｖ４ ｖ１ ｖ９ ｖ２ ｖ３ ｖ５ ｖ６ ｖ７ ｖ８ 解：对图的结点和边进行编号如下： 邻接矩阵： 因此可达矩阵为： 强分图矩阵为： 关联矩阵为： ■ 31. 设P= (p ij ) n×n 是可达性矩阵。证明:P 错误！未找到引用源。P T 中第i 行中非零元素所在列号给出了包含结点v i 的强分图的全部结点编号。 证明：根据强分矩阵的计算过程可知，其包含的含义是结点间双向可达信息。根据有向图的双向可达关系是一个等价关系，因此P 错误！未找到引用源。P T 中第i 行中非零元素所在列号既是一个等价类，所以包含了一个强分图的所有结点■ 已完成[1，2，3，4，5，6，7，8，9，10，11，12，13,14，15，16，17，18，19，２０,21，２３，２４，２５，２６，２７，２８，29，３０，31] 第２２题未证明 ｅ１２ ｅ１１ ｅ１０ ｅ９ ｅ８ ｅ７ ｅ６ ｅ５ ｅ３ ｅ２ ｅ１ ｅ４ ｖ７ ｖ１ ｖ３ ｖ６ ｖ５ ｖ４ ｖ２ 习题十一 1. 设一个树中度为k的结点数是n k（2≤k），求它的叶的数目。 解：设T的节点总数为n，叶节点数目为t ，根据题意及握手定理有： t + n2 + n3 + …+ n k = n (1) t + 2n2 + 3n3 + …k(n k) = 2(n-1) (2) 握手定理 (1),(2)联立求解得： t = n3 + 2n4+ … (k-2)n k + 2■ 2. 证明：树T中最长道路的起点和终点必都是T的叶。 证明：假设T中最长道路P=v i1v i2…v ik的起点或终点不是T的叶结点，设d(v i1)>1,则v i1的所有邻接点(v‘1,v’2…,v’l)都在P中，那么在T 中可以找到一个回路,那么截取道路P, 得到回路C= v i1…v’l v i1 .与T中无回路矛盾。对于d(v ik)>1时同理。因此，假设不成立，即最长道路P的起点和终点都是T的叶节点■ 3. n（n≥3）阶无向树T的最大度Δ至少为几？最多为几？ 解：当T中只有一个枝点时，Δ = n-1,为最大值。当T构成一条链时，只有两个叶结点，其余结点都为2度点，此时Δ = 2，为最小值，因此Δ至少为2 ，最大为n-1■ 4.n（n≥3）阶无向树T的最大度Δ=2，则T中最长的简单道路为几？ 解：根据第3题结论，当无向树T的最大度Δ=2时，T构成一条链，以此最长的简单道路包含所有的节点，道路长度L=n-1■ 5. 证明：任何无向树都是二部图。 证明：以树Ｔ中任意结点ｕ为起点，将与ｕ最短距离为偶数的结点放入ｖ１结点集合，将与ｕ最短距离为奇数的结点放入ｖ２结点集合，那么这两个结点集合中，显然不存在公共点，同时两个结点集合组成了树的全部结点，因此是数Ｔ的结点集合的一个分化。假设在Ｖｉ集合中存在两个结点ｕ１，ｕ２是邻结点，那么就存在如下道路：ｐ＝ｕ．．．ｕ１ｕ２．．．．ｕ， 其中ｐ１＝ｕ．．．ｕ１代表ｕ到ｕ１的最短路径，ｐ２＝ｕ２．．．ｕ代表ｕ到ｕ２的最短路径，且ｕ１ｕ２边不在最短路径上，否则他们的最短路径不是同奇偶的；因此，Ｐ中包含圈，这与树中无圈相矛盾，所以Ｔ中的边，只能存在于两个点集合之间，所以是二部图■ 6. 证明：如果T是树且Δ≥k，则T中至少有k个叶结点。 证明：当T为非平凡树时，根据T的定义，T中每个枝点都是割点，当删除d(v)=Δ的节点时，ω（T-v）=Δ，每个分支都是数，如果分支都是平凡树，则这些节点都是T的叶，叶节点数为Δ。如果分支有非平凡数，那么至少有两个叶节点，其中至少一个是删除v时就存在的，因此总的叶节点个数≥Δ≥k。因此Ｔ中至少有ｋ个叶结点■ 7. 设G为n（n≥3）阶简单图，证明G或中必含圈。（有误，>4,p223） 证明：反证法，假设G和中都不含圈，那么G和的所有分支都是树。则G所包含的最大边数|E(G)|=n-1, 则所包含的最大边数|E()|=n-1. 因为G及的边数总和|E(G)|+ |E()| = n(n-1)/2, 但根据假设条件，max|E(G)|+max |E()|=2(n-1) < n(n-1)/2, 矛盾.因此，G或中必含圈■ 8．证明：恰好有两个顶点的度为1的树必为一道路P。 证明：因为此树仅有2个叶结点，因此Δ<3。那么枝点的度只能为2。所以此树为一条链，及一条道路■ 9. 设T是一个n+1阶树，G是最小点度的简单图。证明：Ｇ必含有与Ｔ同构的子图。 证明：采用归纳法证明，对ｎ进行归纳 （１）当ｎ＝１时，Ｔ为２阶树，因为Ｇ是最小点度的简单图，所以任意意个结点与其邻结点都构成一颗２阶树，成立 （２）假设ｎ＝ｋ，ｋ≥２时，结论成立，即T是一个ｋ+1阶树，G是最小点度的简单图。 Ｇ必含有与Ｔ同构的子图 （３）当ｎ＝ｋ＋１时，G是最小点度的简单图，Ｔ是任意一棵ｋ＋２阶树，在Ｔ中删除一个叶结点ｔ，那么Ｔ－｛ｔ｝是一棵ｋ＋１阶树，利用归纳假设，G中必存在与Ｔ－｛ｔ｝同构的子图T’，T’中最大的点度不超过k，所以每个T’中的结点都有邻结点不包含在T’中，所以T’可在某个结点上增加一个额外的结点u，使T’+{u} 与T 同构 综上所述，结论成立■ 10.设e是连通图G的一条边。证明：e是G的割边当且仅当e含于G的每个生成树中。 证明： 1）充分性：e是G的割边则e含于G的每个生成树中 假设e不包含在某棵生成树T中，那么e一定在T的树补边集中，那么G-{e }中依然包含树T,因此G-{e }连通，与e是割边矛盾，因此e含于G的每个生成树中； 2)必要性：e含于G的每个生成树中则e是G的割边 假设ｅ不是Ｇ的割边，那么Ｇ－｛ｅ｝依然连通，具有生成树，这些生成树也是Ｇ的生成树， 且不包含ｅ，与e含于G的每个生成树中前提矛盾，因此e是G的割边。 综上所述，题设结论：e是G的割边当且仅当e含于G的每个生成树中成立■ 11.设T1和T2是连通图G的两个不同的生成树，a是在T1中但不在T2中的一条边。证明：T2中存在一条边b，使得（T1-a）+b和（T2-b）+a也是G的两个不同的生成树。 证明：从T1中删除边ａ，得树T1－１和T1－２，分别用Ｖ１，Ｖ２表示这两棵子树的结点集合，设Ea＝｛ｅ｜ｅ的两个端点分别属于Ｖ１，Ｖ２｝，显然，ａ∈Ea．因为ａ不在T2中，所以ａ是T2的树补边。设C（a）为在中T2增加边a后所得到的圈，则C(a)中必然存在T2 的树边b不在T1中但在Ea中。否则，C(a)上的T2的所有树边均在T1中或均不在Ea中。如果C(a)上的T2的所有树边均在T1中，则C(a)上的所有边都在T1中，与T1是树矛盾。如果C(a)上的T2的所有树边均不在Ea中，则C(a)中除ａ外所有的边的端点均在Ｖ１或Ｖ２中，与C(a)是基本回路矛盾。所以C(a)中必然存在不在T1中但在T2中的的树边，设ｂ是其中的一条。则（T1-a）+b连通且无回路是Ｇ的生成子图，它是Ｇ的生成树。同理（T2-b）+a也是Ｇ的生成树■ 12.用Kruskal算法求图11.13的一个最小生成树。 解：略，请参考书中算法计算■ 13. 设简单连通图G=（V，E）的边集E恰好可以划分为G的两个生成树的边集。证明：如果G中恰有两个4度以下结点u和v，则uv E。（请冯老师帮助证明下） 14. 已知n阶m条边的无向简单图是由k（k≥2）棵树组成的森林，证明：m = n–k。 证明：设ｋ棵树分别为ｎ１，ｎ２，．．．ｎｋ，根据树的性质有如下公式成立：n 1+n2…n k = n (1) (n 1-1)+(n2-1)…(n k-1) = m (2) (1)-(2) 得：n – m = k => m = n-k■ 15. 证明: 简单连通无向图G的任何一条边，都是G的某一棵生成树的边。 证明：简单连通无向图G的任何一条边，要么是割边，要么是非割边。如果是割边，那么此边是所有生成树的树边；如果不是割边，设边为ｅ，那么G-{e}连通，可以求出生存树Ｔ，此Ｔ也是Ｇ的生存数，且不包含ｅ，那么ｅ是Ｔ的树补边。则Ｔ+{e},有唯一一个圈Ｃ，删除圈上任意一条非ｅ边，便得到一颗包含ｅ边的树■ 16. 证明:在完全二又树中,边的数目等于2(t -1)，式中t是叶的数目。 证明：设Ｔ中的结点数为ｎ，枝点数为ｉ；根据完全二叉树的定义，有下面的等式成立。n=i+t,m=2i,m=n-1.解方程组，得到m=2(t-1)■ 17. 决定一个m叉树中内部道路长度之和与外部道路长度之和的关系。 解：根据完全二叉树的内部道路长度之和与外部道路长度之和的关系猜测m 叉树中内部道路长度之和与外部道路长度之和的关系为：Ｊ＝（ｍ－１）Ｉ＋ｍｉ．其中Ｊ表示各叶结点的道路长度之和，Ｉ表示各分支点道路长度之和，ｉ表示分支结点数。下面对分支结点数ｉ进行归纳： ｉ＝１时，Ｉ＝０，Ｊ＝ｍ，故Ｊ＝（ｍ－１）Ｉ＋ｍｉ成立． 假设ｉ＝ｋ是结论成立． 当ｉ＝ｋ＋１是，设在完全ｍ叉树Ｔ中，ｖ是一个道路长度为ｌ的分支点且其ｍ个儿子ｖ１，ｖ２．．．ｖｋ都为叶结点，那么Ｔ－｛ｖ１，ｖ２．．．ｖｋ｝是含ｋ个分支点的完全ｍ叉树。由归纳假设有Ｊ｀＝（ｍ－１）Ｉ｀＋ｍｋ，比较Ｔ和 Ｔ－｛ｖ１，ｖ２．．．ｖｋ｝，Ｊ＝Ｊ｀＋ｍ（ｌ＋１）－ｌ＝Ｊ｀＋（ｍ－１）ｌ ＋ｍ ，Ｉ＝Ｉ｀＋ｌ，所以Ｊ＝（ｍ－１）Ｉ｀＋ｍｋ＋（ｍ－１）ｌ ＋ ｍ ＝（ｍ－１）Ｉ＋ｍ（ｋ＋１）■ 18. 给出公式的根树表示。 解：将标示符号看成叶结点，逻辑连接词作为分支结点，按公式的先后顺序构造根树如下： ■ ■ 19. 给定权1,4,9,1,2,6,4,6,8,10,构造一个最优二叉树。 解：根据带权最优二叉树定理构造过程如下： ? ` P Q P R P Q ? ? ? ? Λ Λ Λ ■ 20. 把图11.14的有序林变换成一个二叉树。 解：STEP1: 将每棵有序树采用中间格式表达出来 SETP2： 再用一条有向道路把各分支的根从左到右连接起来 1 4 9 1 2 6 4 6 8 10 1 1 2 4 4 6 6 8 9 10 重新排序 ==== 2 2 4 4 6 6 8 9 10 ==== 4 4 4 6 6 8 9 10 ====== 8 4 6 6 8 9 10 ==== 8 10 6 8 9 10 ==== 8 10 14 9 10 8 9 14 10 10 交换10，9 ======== 17 14 10 10 ==== 17 14 20 ============= 31 20 ============= 51 1 1 10 2 4 9 8 6 6 4 SETP3：转换为二叉树。 具体过程略■ 21. 证明:正则二叉树必有奇数个结点，且树叶数t与结点数n之间有：t=（n-1）/2。 证明：因为正则二叉树的边数ｍ与分支点数ｉ的关系为：ｍ＝２ｉ，又因为是树，因此结点数ｎ满足：ｎ＝ｍ－１＝２ｉ－１，必为奇数。叶结点数ｔ和枝点数之和为ｎ，即：ｔ＋ｉ＝ｎ，因此t=（n-1）/2■ 22. 遍历一棵树是指访问这个树的每个结点一次且仅一次。遍历二叉树有如下三种方式: (1)前序遍历:访问根, 遍历左子树,然后遍历右子树。 （2)中序遍历: 遍历左子树,访问根,然后遍历左子树。 （3)后序遍历: 遍历左子树, 遍历右子树,然后访问根。 根据三种不同遍历形式,分别写出图11.15中各结点被访问的顺序。 图11.15 解： （１）前序遍历结果：abdfjglmcehi （２）中序遍历结果：jfdlgmbachei （３）后序遍历结果：jflmgdbhieca■ 23. 设英文字母b，d，g，o，y，e出现的频率分别是0.014，0.038，0.02，0.08，0.131,构造一个与它们对应的前缀码,并写出符号串dogbybed对应的编码。 解：构造最优树如下： 因此获得相应的前缀码：b=00000,g=00001,y=0001,d=001,o=01,e=1 所以dogbybed 的编码为：0010100001000000001000001001■ 完成题目 [1，2，3,4，５，6，7，8，１０，１１，１２,14，１５,16，１７,18，19，20，２１，22,23] 勘误： １．２３题，［频率分别是0.014，0.038，0.02，0.08，0.131］改为［频率分别是0.014，0.038，0.02，0.08，0.02，0.131］ｐ２２３ ２．7题，［ 设G 为n （n ≥3）阶简单图，证明G 或中必含圈］改为［设G 为n （n ≥５）阶简单图，证明G 或中必含圈］p223 第十三题未证明 0.038 (d) 0.014，0.038，0.02，0.08，0.02，0.131 0.014，0.02， 0.02，0.038，0.08，0.131 ＝＝＝＝＝＝ 0.034 0.02，0.038，0.08，0.131 ＝＝＝＝＝＝＝＝ 0.0５2 0.038，0.08，0.131 ＝＝＝＝＝＝＝＝ 0.０９ 0.08，0.131 ＝＝＝＝＝＝＝＝ 0.283 0.131 ＝＝＝＝＝＝＝＝＝ ０．４１４ 1 1 1 0.08 (o) 0.131 (e) 0.014 (b) 0.02 (g) 0 1 1 0.0２ (y) 习题十二 1．证明下面3个图都是平面图。 证明：因为所给图都可以平面图的方式画出来，如下： ■ 2．下面3个图都是平面图，先给图中各边标定顺序，然后求出图中各面的边界和面度。解：略■ 3. 设G是阶数不小于11的图。证明：G或中至少有一个是非平面图。 证明：假设G和都是平面图，因为，所以至少有一个图的边数，设，有因为是平面图，所以有，求解得ｎ≤１０．与题设G是阶数不小于11的图矛盾，因此G或中至少有一个是非平面图■ 4. 证明：具有6个结点、12条边的简单连通平面图，它的面的度数都是3。 证明：因为是简单连通平面图，因此根据欧拉公式有６－１２＋ｆ＝２，所以有８个面。根据面度和与边的关系有，Σｄ（ｆｉ）＝２ｍ＝２４；因为要在平面上围成一个面，至少需要３边，所以８个面，Σｄ（ｆｉ）≥２４。因此，不存在面度大于３的面，所有面的度数都是３■ 5. 证明：少于30条边的简单平面图至少有一个顶点的度不大于4。 证明：假设图Ｇ（ｎ，ｍ）的每个结点的点度都大于等于５，根据握手定理及平面图的判定定理有： ５ｎ≤２ｍ＜６０（１）握手定理 ｍ≤３ｎ－６（２） 根据（１）得到：ｎ<１２ 结合（１）（２）得到：５ｎ／２≤３ｎ－６，所以ｎ≥１２，矛盾。因此假设不成立，题设结论成立■ 6. 设G是具有k（k≥2）个连通分支的平面图，则n–m+f=k+1。 证明：针对每个连通分支而言，满足欧拉公式及：n i-m i+f i = 2,因此Σni –Σmi + Σfi = 2k.因为对G图而言只有一个外部面，但在针对每个连通分支引用欧拉欧式的时候都计算了一次外部面，因此外部面多计数k-1次，所以总面数比求和公式少k-1个面，因此有Σni –Σmi + Σfi-(k-1) = 2k-(k-1) 得n–m+f=k+1■ 7. 证明：对K3.3的任何一边e，K3,3-e是平面图。同样，对K5的任何边e，K5-e也是平面图。 证明：因为K3,3-e，K5-e可以画成平面图的形式，如下： ■ 8. 当m和n取什么值时K m,n是平面图？证明你的结论。 解：当m≤2，n≥1, 或n≤2，m≥1时，K m,n是平面图。因为： 当m≤2，n≥1时，如果m = 1 , 那么此图是一颗树，因此是平面图 如果ｍ＝２，那么可以将此图案如下方式图示： 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) xG ?，在（a）(b)中均为真命题。 (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ?? x ? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ , ( )) ( H ) x ((y ( (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))),()(()((y x H x F x y G y →?∧?? 9.给定解释I 如下: (a) 个体域D 为实数集合R. (b) D 中特定元素=0. (c) 特定函数(x,y)=xy,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 图论复习题答案 一、判断题，对打，错打 1．无向完全图是正则图。 () 2．零图是平凡图。() 3．连通图的补图是连通图.() 4．非连通图的补图是非连通图。() 5．若连通无向简单图G中无圈，则每条边都是割边。() 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。() 7．任何树都至少有2片树叶。() 8．任何无向图G都至少有一个生成树。() 9．非平凡树是二分图。() 10．所有树叶的级均相同的二元树是完全二元树。() 11．任何一个位置二元树的树叶都对应唯一一个前缀码。() 12． K是欧拉图也是哈密顿图。() 3,3 13．二分图的对偶图是欧拉图。() 14．平面图的对偶图是连通图。() 页脚内容1 15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。() 二、填空题 1．无向完全图K6有15条边。 2．有三个顶点的所有互不同构的简单无向图有4个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有10片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集有n-1个，基本圈有m-n+1个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2个面。 三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算 求解下列问题： （1）D中长度等于3的通路和回路各有多少条。 （2）求D的可达性矩阵。 （3）求D的强分图。 解：（1） a b c d e 图1 页脚内容2 页脚内容3 M=????????????????000101000000001 010*******M 2=?? ? ? ??????? ?????010******* 000101000001000 M 3=????????????????10000 01000010000001010000M 4=??? ???? ? ??? ?????00010 01000 100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4=????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??????????? ?? ???010000001000010 1000001000 +??? ???? ? ??? ?? ???100000100001000 0001010000 + ????????????????00010 01000100000100000010 =??? ???? ???? ?? ???21020 1301011111 020******* D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4）=??? ???? ? ????? ???110101********* 1101011011 b c d e 图1 离散数学图论与系中有图题目 ————————————————————————————————作者：————————————————————————————————日期： 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1) 习题6 1.设A={1，2，3，4}，B=A×A。确定下述集合是否为A到B的全函 数或部分函数。 (1) {(1,(2,3)),(2,(2,2)),(3,(1,3)),(4,(4,3))}. (2) {(1,(1,2)),(1,(2,3)),(3,(2,4))}. (3){(1,(3,3)),(2,(3,3)),(3,(2,1)),(4,(4,1))}. 解： （1）、全函数 （2）、不符合单值 （3）、全函数 要点：根据全函数定义，X中每个元素x都在Y中有唯一元素y 与之对应。 2.判别以下关系中那些是全函数。 (1){(n1,n2)|n1,n2∈N,0<2n1-n2<5}。 (2){(n1,n2)|n1,n2∈N,n2是n1的正因子个数}。 (3){(S1,S2)|S1,S2?{a,b,c,d}且S1 S2=?}。 (4){(a,b)|a,b∈N,gcd(a,b)=3}. (5){(x,y)|x,y∈Z,y=x2}. 解： (1) {(n1,n2)|n1, n2∈N, 0<2 n1-n2<5} 不是函数，n1=0时无定义，且(3,4),(3,5)在其中。 (2) {(n1,n2)|n1, n2∈N, n2是n1的正因子个数} 部分函数，n1=0时无定义 (3) {(S1,S2)|S1, S2?{a,b,c,d}且 S1? S2= ?} 不是函数，因为({a},{b}) ,({a},{c})均在其中。 (4) {(a, b)|a, b ∈N, gcd(a,b)=3} 不是函数，因为(3, 3) ,(3, 6), (3, 9)均在其中。 (5) {(x, y)|x, y ∈Z, y=x2} 全函数 3.在§3.1中已经定义了集合的特征函数。请利用集合A和B的特征函数χA（x）和χB（x）表示出A B，A B，A-B，A以及A○+B对应的特征函数。 解：（略） 4.试确定在含n个元素的集合上可以定义多少个二元关系，其中有多少个是全函数。 解: 可以定义n n个二元关系，n！个全函数 5.设，证明：。 证明：b∈f(A)-f(C)?b∈f(A)∧ b?f(C) ?(?x)[x∈A ∧ x?C ∧ f(x)=b] ?(?x)[x∈A-C ∧ f(x)=b] ?b∈f(A-C) 所以f(A)-f(C)?f(A-C) 习题一 作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。 证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。 当n=2时，结论显然；设结论对n=k 时成立。 当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。 证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u 1 v 1 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 (a) v 2 v 3 u 4 u (b) 离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝ 第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每 一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故 G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G 学号：0441 姓名：张倩 习题1 4．证明图1-28中的两图是同构的 证明：将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )?u i (1? i ? 10) 容易证明，对?v i v j ?E((a)),有f(v i v j )?u i u j ?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： (a) v 1 v 2 v 3 v v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b) m=4： m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 ()1 1 123121,1,,1,,,=d d n d d d d d π++---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于?? 2，因此，对vin ，存在点vik 与之邻接，则vik?vinvik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题十 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= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) 离散数学模拟试题1 一.单项选择题(每小题1.5分,共30分) 1. 永真命题公式( ) ①只存在主析取范式;②只存在主合取范式; ③既存在主析取范式也存在主合取范式;④都不对. 2. 下列代数系统中消去侓不成立的是( ) ①.群;②含幺半群;③整环;④分配格. 3.在4个元素的集合上可定义的满射有( )个 ①4;②12; ③16 ④24 4. 在整环和格的定义中对运算都要求满足的性质是( ) ①及收律; ②幂等律; ③交换律; ④分配律. 5. 下面说法中正确的是( ) ①半群都有幂等元;②.剩余类环 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 习题十 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= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) 1-1，1-2 （1）解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P：a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨Q）→R (6) 解： a)P:天气炎热。Q:正在下雨。P∧Q b)P:天气炎热。R:湿度较低。P∧R c)R:天正在下雨。S:湿度很高。R∨S d)A:刘英上山。B:李进上山。A∧B e)M:老王是革新者。N:小李是革新者。M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。R:我在睡觉。P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式） b)是合式公式 c)不是合式公式（括弧不配对） d)不是合式公式（R和S之间缺少联结词） e)是合式公式。 （2）解： a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。这个过程可以简记为：A；(A∨B)；(A→(A∨B)) 同理可记 b）A；┓A ；(┓A∧B) ；((┓A∧B)∧A) c）A；┓A ；B；(┓A→B) ；(B→A) ；((┓A→B)→(B→A)) d）A；B；(A→B) ；(B→A) ；((A→B)∨(B→A)) （3）解： a）((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b）((B→A)∨(A→B))。 （4）解： a) 是由c) 式进行代换得到，在c) 中用Q代换P, (P→P)代换Q. 二、应用题 题0：（1996年全国数学联赛） 有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。 注：[n /2]表示不超过n /2的最大整数。 证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有 （1）对每个顶点x ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , 习题十 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= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 图论复习题答案 一、 判断题，对打√，错打 1．无向完全图是正则图。( √ ) 2．零图是平凡图。( ) 3．连通图的补图是连通图. ( ) 4．非连通图的补图是非连通图。( ) 5．若连通无向简单图G中无圈，则每条边都是割边。( √ ) 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。( ) 7．任何树都至少有2片树叶。( ) 8．任何无向图G都至少有一个生成树。( ) 9．非平凡树是二分图。( √ ) 10．所有树叶的级均相同的二元树是完全二元树。( ) 11．任何一个位置二元树的树叶都对应唯一一个前缀码。( √ ) 12．3,3 K是欧拉图也是哈密顿图。( ) 13．二分图的对偶图是欧拉图。( ) 14．平面图的对偶图是连通图。( √ ) 15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。( )二、填空题 1．无向完全图K6有 15 条边。 2．有三个顶点的所有互不同构的简单无向图有 4 个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有 10 片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集 有 n-1 个，基本圈有 m-n+1 个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要 加k / 2 条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2 个面。 三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算 求解下列问题： （1）D中长度等于3的通路和回路各有多少条。（2）求D的可达性矩阵。 （3）求D的强分图。 a b e 图1 解： （1） M=????????????????00010 1000000001 010******* M 2 =?? ?? ??? ? ??? ?????010******* 00010 1000001000 M 3=????????????????1000001000010000001010000 M 4=??????? ?????????0001001000100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4 =????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??? ???? ? ??? ?? ???010000001000010 1000001000 + ????????????????1000001000010000001010000 +??? ?? ???????????0001001000100000100000010 = ??? ???? ? ????????21020 13010111110202011021 D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4 ）=??? ???? ? ????? ???110101********* 1101011011 （3）R T =????????????????11111 1111100100 1111100101 R×R T =??? ???? ? ??? ?????11010 11010 001001101000001 由矩阵R×R T 可知，该有向图的强分图有：{a}，{ b ，d ，e}， { c} a b e 图1屈婉玲版离散数学课后习题答案【3】
2004图论复习题答案
离散数学图论与系中有图题目
川大离散数学习题6
图论 张先迪 李正良 课后习题答案
离散数学测验题--图论部分(优选.)
吉林大学离散数学课后习题答案
图论1-3藏习题解答
习题参考解答图论部分
四川大学离散数学试题
离散数学课后习题答案(左孝凌版)
离散数学图论练习题
习题参考解答(图论部分)
离散数学课后习题答案_(左孝凌版)
图论习题参考答案
习题参考解答(图论部分)Word版
离散数学答案 第二版 课后答案--
2004图论复习题答案
相关文档
- 离散数学课后习题答案(第一章)
- 离散数学课后习题答案(左孝凌版)
- 离散数学课后习题答案
- 离散数学课后习题答案-(左孝凌版)
- 离散数学课后习题答案
- 屈婉玲版离散数学课后习题答案【3】
- 离散数学课后习题答案_(左孝凌版)
- 离散数学(左孝凌)课后习题解答(详细)
- 离散数学课后习题答案-(左孝凌版)
- 离散数学课后习题答案(左孝凌版)
- 离散数学课后习题答案(第三章)
- 离散数学课后习题答案_(左孝
- 离散数学课后习题答案
- 离散数学答案屈婉玲版第二版课后答案
- 离散数学课后习题答案(左孝凌版)
- 离散数学课后习题答案第二章
- 离散数学课后习题答案.pdf
- 离散数学课后习题答案_(左孝凌版)
- 离散数学课后习题答案第一章
- 离散数学课后习题答案第三章