离散数学导论-学习指导与习题解析
2012-6
朱怀宏、 徐洁磐 高等教育出版社 (2012-06出版)
朱怀宏，徐洁磐 编
178
《离散数学导论（第4版）：学习指导与习题解析》是《离散数学导论（第4版）》（徐洁磐编著，高等教育出版社出版）一书配套的教学辅导用书。全书针对教材各章的教学重点内容对读者进行辅导，除对各章习题进行分析与解答之外，还增加了大量教材中没有的习题，并给出解答。全书包括集合论初步、关系、函数，有限集与无限集、代数系统、图论、数理逻辑、离散建模8章内容，除第八章外，其余各章均由主要内容、复习重点、基本概念及注意事项、典型例题详细分析、相关教材中的习题及解答、另增配套习题及解答等部分组成。 本书除可与《离散数学导论（第4版）》配套使用之外，还可独立作为离散数学课程的教学参考书，供高等学校计算机及相关专业的学生使用。
第一章 集合论初步 1.1 主要内容 1.2 复习重点 1.3 基本概念及注意事项 1.4 典型例题详细分析 1.5 相关教材中的习题及解答 1.6 另增配套习题及解答第二章 关系 2.1 主要内容 2.2 复习重点 2.3 基本概念及注意事项 2.4 典型例题详细分析 2.5 相关教材中的习题及解答 2.6 另增配套习题及解答第三章 函数 3.1 主要内容 3.2 复习重点 3.3 基本概念及注意事项 3.4 典型例题详细分析 3.5 相关教材中的习题及解答 3.6 另增配套习题及解答第四章 有限集与无限集 4.1 主要内容 4.2 复习重点 4.3 基本概念及注意事项 4.4 典型例题详细分析 4.5 相关教材中的习题及解答 4.6 另增配套习题及解答第五章 代数系统 5.1 主要内容 5.2 复习重点 5.3 基本概念及注意事项 5.4 典型例题详细分析 5.5 相关教材中的习题及解答 5.6 另增配套习题及解答第六章 图论 6.1 主要内容 6.2 复习重点 6.3 基本概念及注意事项 6.4 典型例题详细分析 6.5 相关教材中的习题及解答 6.6 另增配套习题及解答第七章 数理逻辑 7.1 主要内容 7.2 复习重点 7.3 基本概念及注意事项 7.4 典型例题详细分析 7.5 相关教材中的习题及解答 7.6 另增配套习题及解答第八章 离散建模 8.1 主要内容 8.2 复习重点 8.3 基本概念及注意事项 8.4 相关教材中的习题及解答参考文献
版权页： 插图： 4设图G有9个结点，每个结点的次数（度数）不是5就是6，试证G中至少有5个6次结点或至少有6个5次结点。 分析：本题条件是图G共有9个结点，每个结点的次数是5或6，而只要证明满足下面两种情况之一即可。①对于5次结点至少为6个，即可以是6个或8个，而如果只有4个5次结点，那么剩下94=5个结点，而这5个结点的次数为6（即至少有5个6次结点），而如果只有0个、2个5次结点，则对应有9个、7个6次结点，也满足至少5个的情况；②同理，从至少5个6次结点出发，分析少于5个或多于5个时的情况也能得出相应结论。 证明：根据图论中的定理，任何图中奇次结点数为偶数，因此5次结点的个数只能为0，2，4，6，8，此时对应6次结点的个数则为9，7，5，3，1。对这五种情况都满足至少有5个6次或6个5次结点，故结论成立。 5设G为无向连通图，有n个结点，那么G中至少有几条边？为什么？若是有向图又如何？ 解：至少有n,1条边，因为G为无向连通图，设有n个结点v1，v2，，vn，由连通性知，G中每对结点之间都有通路，每个结点都有与其相邻的结点，因此，每个结点至少关联一条边，不妨设按给定结点的顺序相邻（或重新按序编号），则v2与v1相邻有边e1，v3与V2或v1相邻有边e2vn必与v1，v2，，vn1，中某结点相邻有边en1。故G中至少有n1条边。 若G为有向图，则将方向略去，对相应的无向图讨论，结果相同。（因为只是讨论有多少条边，并未要求边的方向。） 7证明每个结点的次数至少为2的图必包含一个回路。 分析：本题证明时所设L是考虑了能否构成环的最坏情况，除两头外，其他结点的次数为2（满足至少为2的最少次数情况），如果不按L来安排结点在图中位置的话，则可出现回路。 由于条件给出每个结点的次数至少为2，那么结点a及L中的另一端点的次数就不会是1，故会有情况，由a引出的另一条边e的另一头必会去与另一结点相连（如结点b，因为按最差情形所有点均放到了L上），此时已出现了回路。 证明：设L是图G最长路中的一条，设其长度为m，这条路的一个端点设为a，考察图G中与a关联的那些边，这些边中任何一条边的另一个端点必在L上，否则，将这个结点加进L中就可得到一条更长的路。 如果G中每个结点的次数至少为2，那么a也要关联一条不在L上的边e。若e是环，则e本身就是回路；否则，边e的另一个端点b（与a不同的点）在L上，而连通L中a到b的子通路与边e就组成一个回路。 8证明：如果n个电话局中的任何两个电话局总是可以通话的，那么至少存在n,1条直通线路。 证明：设n个电话局为n个结点，两个结点之间有连线，当且仅当对应的这两个电话局可直通电话因为任何两个电话局总可以通话（可能中途要通过其他电话局），因此就可构成一个简单的连通图。 现证明，对于具有n个结点的简单连通图G至少存在n1条边。用数学归纳法，有： 当n=2时，有一条边； 当n=3时，至少有两条边； 设当n=k时，G至少有k1条边当再增加一个结点r时，r必与G中的某个结点邻接，因此，具有k+1个结点的简单连通图至少有k条边。 说明：本题是一道应用题，要善于设法将其转换为图论中的问题来进行研究本题中的所有结点均可有通路达到，用数学归纳法证出的是n个结点至少有n1条边将其连通，但一般情况下可以超过n1条边。
《高等学校教材•离散数学导论:学习指导与习题解析(第4版)》由高等教育出版社出版。《高等学校教材•离散数学导论:学习指导与习题解析(第4版)》除可与《离散数学导论（第4版）》配套使用之外，还可独立作为离散数学课程的教学参考书，供高等学校计算机及相关专业的学生使用。
去年买的了，忘评论了，感觉书还可以，就是答案不全啊
用的很不错 期末复习就靠他了