北大离散数学08

习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为1.（2）5是无理数.答：此命题是简单命题，其真值为1.（3）3是素数或4是素数.答：是命题，但不是简单命题，其真值为1.x+<（4）235答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2与3是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为1.（11）只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题，其真值为0.（12）8是偶数的充分必要条件是8能被3整除.答：是命题，但不是简单命题，其真值为0.（13）2008年元旦下大雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四大发明.（2）p:是无理数.（7）p:刘红与魏新是同学.（10）p:圆的面积等于半径的平方乘以π.（13）p:2008年元旦下大雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（15是有理数.5.p5.q5.其否定式q的真值为1.（225不是无理数.答：是有理数. p 不是无理数. q 是有理数. 其否定式q 的真值为1.（3）是自然数.答：否定式：不是自然数. p ：是自然数. q ：不是自然数. 其否定式q 的真值为1. （4）ln1是整数.答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1.4.将下列命题符号化，并指出真值. （1）2与5都是素数答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1.（2）不但π是无理数，而且自然对数的底e 也是无理数.答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数.答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧⌝，其真值为1. （4）3是偶素数.答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数.答：p ：4是素数，q ：4是偶数，符号化为p q ⌝∧⌝，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数.（4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数.答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ⌝∨⌝，其真值为1.(5) 符号化：r s ⌝∨⌝，其真值为0. 6.将下列命题符号化.（1）小丽只能从筐里拿一个苹果或一个梨.答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ⌝∧∨∧⌝. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化1 1 0 1根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值.（1）只要,就有；（2）如果,则；（3）只有,才有；（4）除非,才有；（5）除非,否则；（6）仅当.答:设p:,则:;设q:,则:.符号化真值（1） 1（2） 1（3）0（4）0（5）0（6） 19.设p：俄罗斯位于南半球,q：亚洲人口最多,将下面命题用自然语言表述,并指出其真值：（1）；（2）；；（3）；（4）；（5）；（6）；（7）.自然语言真值（1）只要俄罗斯位于南半球,亚洲人口就最多 1（2）只要亚洲人口最多,俄罗斯就位于南半球0（3）只要俄罗斯不位于南半球,亚洲人口就最多 1（4）只要俄罗斯位于南半球，亚洲人口就不是最多 1（5）只要亚洲人口不是最多，俄罗斯就位于南半球 1（6）只要俄罗斯不位于南半球，亚洲人口就不是最多0（7）只要亚洲人口不是最多，俄罗斯就不位于南半球 1 10．设p：9是3的倍数,q：英国与土耳其相邻,将下面命题用自然语言表述,并指出真值：（1）；（2）；（3）；（4）.答:根据题意,p为真命题,q为假命题.自然语言真值（1）9是3的倍数当且仅当英语与土耳其相邻0（2）9是3的倍数当且仅当英语与土耳其不相邻 1（3）9不是3的倍数当且仅当英语与土耳其相邻 1（4）9不是3的倍数当且仅当英语与土耳其不相邻011．将下列命题符号化,并给出各命题的真值：（1）若2+2=4,则地球是静止不动的；（2）若2+2=4,则地球是运动不止的；（3）若地球上没有树木,则人类不能生存；（4）若地球上没有水,则是无理数.答:命题1 命题2 符号化真值（1）p:2+2=4 q:地球是静止不动的0 （2）p:2+2=4 q:地球是静止不动的 1 （3）p:地球上有树木q:人类能生存 1 （4）p:地球上有树木q:人类能生存 1（1）2+2=4当且仅当3+3=6；（2）2+2=4的充要条件是3+36；（3）2+24与3+3=6互为充要条件；（4）若2+24,则3+36,反之亦然.答:设p:2+2=4,q:3+3=6.符号化真值(1) 113.将下列命题符号化,并讨论各命题的真值：（1）若今天是星期一,则明天是星期二；（2）只有今天是星期一,明天才是星期二；（3）今天是星期一当且仅当明天是星期二；（4）若今天是星期一,则明天是星期三.答:设p:今天是星期一,q:明天是星期二,r:明天是星期三.14.将下列命题符号化：（1）刘晓月跑得快,跳得高；（2）老王是山东人或者河北人；（3）因为天气冷,所以我穿了羽绒服；（4）王欢与李乐组成一个小组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他一面吃饭,一面听音乐；（8）如果天下大雨,他就乘班车上班；（9）只有天下大雨,他才乘班车上班；（10）除非天下大雨,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2与4都是素数,这是不对的；（13）“2或4是素数,这是不对的”是不对的.(12) p:2是素数q:4是素数-(13) p:2是素数q:4是素数-15.设p：2+3=5.q：大熊猫产在中国.r:太阳从西方升起.求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q真值为1，r真值为0.（1）0，（2）0，（3）0，（4）116.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下面一段论述是否为真：“是无理数.并且,如果3是无理数,则也是无理数.另外,只有6能被2整除,6才能被4整除.”解：p:是无理数q: 3是无理数r:是无理数s: 6能被2整除t：6能被4整除符号化为:，该式为重言式，所以论述为真。

北大数学系本科教材
北大数学系本科教材包括以下几门课程的教材：
1. 微积分：北大的微积分教材包括《微积分（修订版）》和《微积分习题讲义（修订版）》。

2. 线性代数：北大的线性代数教材包括《线性代数与解析几何（修订版）》和《线性代数习题指导与解答》。

3. 概率论与数理统计：北大的概率论与数理统计教材包括《概率论与数理统计教程（修订版）》和《概率论与数理统计习题讲义》。

4. 离散数学：北大的离散数学教材包括《离散数学》。

5. 数学分析：北大的数学分析教材包括《数学分析习题解答》和《数学分析辅导教程》。

这些教材都是经过北大数学系教授和专家精心编写的，旨在提供给本科学生综合学习和参考。

另外，北大数学系还有其他教材，涵盖更多的专业课程和研究领域，如代数学、几何学等。

第八章部分课后习题参考答案
1． 设f :N →N,且
f (x)=12x x x ⎧⎪⎨⎪⎩
，若为奇数
若为偶数， 求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6,…})，f ({4,6,8}), f -1({3,5,7}). 解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1},
f ({0,2,4,6,…})=N ，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}.
4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?
(1) f:N →N, f(x)=x 2+2 不是满射，不是单射
(2) f:N →N,f(x)=(x)mod 3,x 除以3的余数 不是满射，不是单射
(3) f:N →N,f(x)=10x x ⎧⎨⎩
，若为奇数，若为偶数 不是满射，不是单射
(4) f:N →{0,1},f(x)=01x x ⎧⎨⎩
，若为奇数，若为偶数 是满射，不是单射
(5) f:N-{0}→R,f(x)=lgx 不是满射，是单射
(6) f:R →R,f(x)=x 2-2x-15 不是满射，不是单射
5. 设X={a,b,c,d},Y={1,2,3},f={<a,1>,<b,2>,<c,3>,}判断以下命题的真假:
(1)f 是从X 到Y 的二元关系,但不是从X 到Y 的函数; 对
(2)f 是从X 到Y 的函数,但不是满射,也不是单射的; 错
(3)f 是从X 到Y 的满射,但不是单射; 错
(4)f是从X到Y的双射. 错。

离散数学北京大学出版社第二版配套PPT课件介绍本文档是北京大学出版社出版的《离散数学》第二版的配套PPT课件的简介。

透过课件，学生可以更好地理解和学习离散数学的概念和原理。

课件的作者包括屈婉玲、耿素云和张立昂等离散数学领域的专家，他们精心设计了课件的内容和布局，旨在帮助学生更好地理解离散数学的基础知识，并应用到实际问题中。

内容概述离散数学是计算机科学和信息技术中的一门基础课程，它研究离散的数学结构和离散对象之间的关系。

离散数学的理论和方法在计算机科学、密码学、人工智能等领域有着广泛的应用。

《离散数学》第二版的配套PPT课件涵盖了离散数学的主要内容，包括集合论、逻辑、关系、图论、计数原理等。

课件的设计旨在让学生通过图示、例子和练习等形式来理解和掌握离散数学的概念和方法。

课件还提供了一些附加材料和参考资料，供学生进一步学习和探索离散数学的相关内容。

课件特点1.系统性：课件内容有机地连接起来，形成一个完整的体系，学生可以从不同的章节中逐步深入学习离散数学的不同方面。

2.可视化：课件中使用了大量的图示和示例，帮助学生更直观地理解离散数学的概念和原理。

3.互动性：课件中设置了各种练习和思考题，鼓励学生积极参与和思考，提高学习效果。

4.实用性：课件中的例子和实际应用案例帮助学生将离散数学的理论应用到实际问题中，增强学习的实际效果。

使用指南学生可以使用任何支持Markdown文本格式的编辑器来打开和阅读本课件。

在阅读的同时，建议学生积极参与，思考课件中的问题，并完成相应的练习。

学生还可以根据自己的学习情况，有针对性地选择课件中的章节进行学习。

附加材料《离散数学》第二版的配套PPT课件还提供了一些附加材料，供学生进一步学习和探索离散数学的相关内容。

这些附加材料包括参考资料、习题解答和扩展阅读等。

学生可以根据自己的学习需要，选择适合自己的附加材料进行阅读。

结语《离散数学》第二版的配套PPT课件是学习离散数学的重要辅助工具，它通过图示、例子和练习等形式，帮助学生更好地理解和掌握离散数学的概念和方法。

北京大学现代远程教育2008年秋季学期期末考试试卷B离散数学（603标准答案）专业及层次：教学中心：姓名：标准答案学号：注意事项：1、本试卷满分100 分，考试时间90 分钟；2、请将答案一律写在试卷空白处。

统分栏：一二三四五六七总分25 15 6 15 15 16 15 100一、选择题（4 个备选中只有 1 个正确，填入括号内。

每题 2.5 分，共25 分）1、下面命题为真的一个是（C）A．Ø∈Ø；B．Ø ∈{{Ø}，a}；C．Ø ⊆{{Ø}}；D．Ø⊂Ø2、令p：经一堑；q：长一智。

命题’’只有经一堑，才能长一智’’ 符号化为[ B ]A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p3、设集合 S ={N，Z，Q，R}，下面命题为真的是 [ A ]A．N⊆Q，Q⊆R，则 N⊆R； B. -1∈Z，Z∈S，则 -1∈S ；C．N⊆Q，Q⊆R，则 N⊆S；D．1∈N，N∈S，则 1∈S 。

4、非平凡无向树 T 至少 t 片树叶 [ B ]A．t = 1； B．t = 2； C．t = 3； D．t = 4。

5、11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有r条树枝 [ D ]A．r = 11； B．r = 17； C．r = 6； D．r = 106、任一个命题公式至少 x 个主析取范式 [ C ]A. x = 3;B. x = 2;C. x = 1;D. x = 0.7、命题”明天不下雨，也没有太阳，将是阴天。

”应符号化为[ A ]A.┐p∧┐q∧r。

B. p∧┐q∧r。

C.┐p∧q∧r。

D. p∧q∧r。

8、命题公式p 的主析取范式为[ B ]A.∑(0);B.∑(1);C.∏(0);D.∏(1).9、命题公式p∧┐q∧r 的主析取范式为[ B ]A. ∑(3);B. ∑(5);C. ∏(3,4,5);D.∏(5,6,7); .10、命题公式┐p 的主析取范式为[ A ]A. ∑(0);;B. ∑(1);;C.∏(0) ;D. ∏(1).二、判断下列各题的是非（每题2.5分，共25分）1、自然数N = {1，2，3，．．．．．} + { 0 }。

北京大学现代远程教育2008年秋季学期期末考试试卷A1.T为无向连通图G(m,n) 的一棵生成树，则对应T的基本回路数为（m-n+1）[ 是]2、每条边都是桥的无向连通图必是树。

[ 是]3、非平凡无向树 T 至少 1 片树叶 [ 非 ]4、11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有6条树枝 [ 非 ]5、无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. [ 是]6、二元正则树有奇数个顶点。

[ 对 ]7、n（n ≥ 1）阶有向完全图都是有向欧拉图。

[ 对 ]8、无向连通图 G（m,n）的每一条边都可以成为他的某一生成树的树枝。

[ x ]9、边数 m 等于 n-1 的 n 阶无向图都是树。

[ x ]10、10 阶无向连通图G 有m 条边，则生成树T 对应的基本割集数目为9［］11．树Ｔ有ｍ条边，ｎ个顶点，则有ｎ＝ｍ＋１［是］12．（１，２，３，４，５，６）可以是一个图的顶点度数列［非］13．作为有向图中有向边始点的次数叫出度。

[ 是] 14．10 阶无向简单图 G 中有 6 个奇数度顶点，其补图中必有４个奇数度顶点 [是 ] 15．10、11 阶无向简单连通图 G 中，顶点间的最大距离是11 [ x ]11、11 条边的图 G 中，所有顶点的度数之和为22 [ ]12、11 阶无向简单图G中有 6个奇数度顶点，其补图中必有 5个奇数度顶点 [ x ]13、图Ｇ中２个３度顶点，３个４度顶点，４个５度顶点，则Ｇ中有１８条边．[ ]14、10 阶无向连通图G 有m 条边，则生成树T 对应的基本割集数目为9。

［］15.边数 m 等于 n-1 的 n 阶无向图都是树。

[ X ]16.无向树的任何边都是桥。

[ ]17.无向连通图G（n，m）的每一棵生成树都有 n-1 条树枝。

[ ]18、无向连通图G（n，m）的每一条边都可以成为他的某一生成树的树枝。

内容简介本书共分五编。

第一编为集合论，其中包括集合的基本概念、二元关系、函数、自然数、基数、序数。

第二编为图论，其中包括图的基本概念、图的连通性、欧拉图与哈密顿图、树、平面图、图的着色、图的矩阵表示、覆盖集、独立集、匹配、带权图及其应用。

第三编为代数结构，其中包括代数系统的基本概念、几个重要的代数系统：半群、群、环、域、格与布尔代数。

第四编为组合数学，其中包括组合存在性、组合计数、组合设计与编码以及组合最优化。

第五编为数理逻辑，其中包括命题逻辑、一阶谓词逻辑、Herbrand定理和直觉逻辑。

本书体系严谨、内容丰富、配有大量的例题和习题，并与计算机科学的理论与实践密切结合。

本书不仅适用于计算机及相关专业的本科生或研究生，也可供计算机专业的科技人员使用或参考。

目录第一编集合论第一章集合(1)1.1 预备知识(1)1.2 集合的概念及集合之间的关系(7)1.3 集合的运算(10)1.4 基本的集合恒等式(13)1.5 集合列的极限(17)习题一(20)第二章二元关系(23)2.1 有序对与卡氏积(23)2.2 二元关系(26)2.3 关系矩阵和关系图(32)2.4 关系的性质(34)2.5 二元关系的幂运算(37)2.6 关系的闭包(39)2.7 等价关系和划分(45)2.8 序关系(49)习题二(53)第三章函数(58)3.1 函数的基本概念(58)3.2 函数的性质(59)3.3 函数的合成(62)3.4 反函数(64)习题三(68)第四章自然数(70)4.1 自然数的定义(70)4.2 传递集合(74)4.3 自然数的运算(76)4.4 N上的序关系(78)习题四(80)第五章基数(势)(81)5.1 集合的等势(81)5.2 有穷集合与无穷集合(83)5.3 基数(84)5.4 基数的比较(85)5.5 基数运算(89)习题五(93)第六章序数(95)6.1 关于序关系的进一步讨论(95) 6.2 超限递归定理(97)6.3 序数(99)6.4 关于基数的进一步讨论(105)习题六(105)第二编图论第七章图(107)7.1 图的基本概念(107)7.2 通路与回路(119)7.3 无向图的连通性(121)7.4 无向图的连通度(123)7.5 有向图的连通性(129)习题七(130)第八章欧拉图与哈密顿图(132)8.1 欧拉图(132)8.2 哈密顿图(137)习题八(142)第九章树(144)9.1 无向树的定义及性质(144)9.2 生成树(146)9.3 环路空间(149)9.4 断集空间(151)9.5 根树(153)习题九(154)第十章图的矩阵表示(156)10.1 关联矩阵(156)10.2 邻接矩阵与相邻矩阵(159)习题十(163)第十一章平面图(165)11.1 平面图的基本概念(165)11.2 欧拉公式(168)11.3 平面图的判断(170)11.4 平面图的对偶图(172)11.5 外平面图(175)11.6 平面图与哈密顿图(177)习题十一(179)第十二章图的着色(180)12.1 点着色(180)12.2 色多项式(181)12.3 地图的着色与平面图的点着色(185)12.4 边着色(187)习题十二(189)第十三章支配集、覆盖集、独立集与匹配(190)13.1 支配集、点覆盖集、点独立集(190)13.2 边覆盖集与匹配(193)13.3 二部图中的匹配(198)习题十三(199)第十四章带权图及其应用(201)14.1 最短路径问题(201)14.2 关键路径问题(204)14.3 中国邮递员问题(206)14.4 最小生成树(208)14.5 最优树(213)14.6 货郎担问题(216)习题十四(220)第三编代数结构第十五章代数系统(222)15.1 二元运算及其性质(222)15.2 代数系统、子代数和积代数(227) 15.3 代数系统的同态与同构(230)15.4 同余关系和商代数(233)15.5 Σ代数(236)习题十五(237)第十六章半群与独异点(240)16.1 半群与独异点(240)16.2 有穷自动机(242)习题十六(247)第十七章群(249)17.1 群的定义和性质(249)17.2 子群(253)17.3 循环群(255)17.4 变换群和置换群(257)17.5 群的分解(263)17.6 正规子群和商群(269)17.7 群的同态与同构(272)17.8 群的直积(278)习题十七(281)第十八章环与域(285)18.1 环的定义和性质(285)18.2 子环、理想、商环和环同态(289) 18.3 有限域上的多项式环(294)习题十八(296)第十九章格与布尔代数(299)19.1 格的定义和性质(299)19.2 子格、格同态和格的直积(303)19.3 模格、分配格和有补格(307)19.4 布尔代数(311)习题十九(318)第四编组合数学第二十章组合存在性定理(322)20.1 鸽巢原理和Ramsey定理(322)20.2 相异代表系(331)习题二十(335)第二十一章基本的计数公式(337)21.1 两个计数原则(337)21.2 排列和组合(338)21.3 二项式定理与组合恒等式 (343)21.4 多项式定理(347)习题二十一(349)第二十二章组合计数方法(352)22.1 递推方程的公式解法(352)22.2 递推方程的其他解法(361)22.3 生成函数的定义和性质(370)22.4 生成函数与组合计数(375)22.5 指数生成函数与多重集的排列问题(384) 22.6 Catalan数与Stirling数(388)习题二十二(394)第二十三章组合计数定理(398)23.1 包含排斥原理(398)23.2 对称筛公式及应用(403)23.3 Burnside引理(410)23.4 Polya定理(414)习题二十三(420)第二十四章组合设计与编码(422)24.1 拉丁方(422)24.2 t设计(427)24.3 编码(436)24.4 编码与设计(446)习题二十四(449)第二十五章组合最优化问题(450)25.1 组合优化问题的一般概念 (450)25.2 网络的最大流问题(452)习题二十五(457)第五编数理逻辑第二十六章命题逻辑(458)26.1 形式系统(458)26.2 命题和联结词(461)26.3 命题形式和真值表(464)26.4 联结词的完全集(468)26.5 推理形式(471)26.6 命题演算的自然推理形式系统N(473)26.7 命题演算形式系统P(486)26.8 N与P的等价性(494)26.9 赋值(496)26.10 可靠性、和谐性与完备性 (505)习题二十六(507)第二十七章一阶谓词演算(511)27.1 一阶谓词演算的符号化(511)27.2 一阶语言(515)27.3 一阶谓词演算的自然推演形式系统N L(519) 27.4 一阶谓词演算的形式系统K L(530)27.5 N L与K L的等价性(534)27.6 K L的解释与赋值(536)27.7 K L的可靠性与和谐性(547)27.8 K L的完全性(551)习题二十七(558)第二十八章消解原理(562)28.1 命题公式的消解(562)28.2 Herbrand定理(567)28.3 代换与合一代换(572)28.4 一阶谓词公式的消解(576)习题二十八(581)第二十九章直觉主义逻辑(583)29.1 直觉主义逻辑的直观介绍(583)29.2 直觉主义的一阶谓词演算的自然推演形式系统(58 5)29.3 直觉主义一阶谓词演算形式系统IK L(594)29.4 直觉主义逻辑的克里普克(Kripke)语义(597)29.5 直觉主义逻辑的完备性(602)习题二十九(607)附录1 第一编与第二编符号注释与术语索引(608)附录2 第三编与第四编符号注释与术语索引(614)附录3 第五编符号注释与术语索引(620)参考书目和文献(624)05668本书共分4大部分，数理逻辑部分包括命题逻辑的基本概念、等值演算、范式与推理理论，一阶逻辑的基本概念、前束范式以及推理理论。

第8 章 习题解答8.1 图8.6 中,(1)所示的图为‎,3,1K (2) 所示的图为‎,3,2K (3)所示的图为‎,2,2K 它们分别各‎有不同的同‎构形式.8.2 若G 为零图‎,用一种颜色‎就够了,若G 是非零‎图的二部图‎,用两种颜色‎就够了.分析 根据二部图‎的定义可知‎,n 阶零图(无边的图)是三部图(含平凡图),对n 阶零图‎的每个顶点‎都用同一种‎颜色染色,因为无边,所以,不会出现相‎邻顶点染同‎色,因而一种颜‎色就够用了‎.8.3 完全二部图‎,,s r K 中的边数rs m -.分析 设完全二部‎图的顶点集‎s r K ,为V, 则∅==2121,V V V V V ,且是简单图‎,||,||21s V r V ==s r K ,,且中每个顶‎1V 点与中所有‎2V 顶点相邻,而且中任何‎1V 两个不同顶‎点关联的边‎互不相同,所以,边数rs m -.8.4 完全二部图‎s r K ,中匹配数},min{1s r =β,即等于中的‎1βs r ,小者. 分析 不妨设且二‎,s r ≤部图s r K ,中,,||,||21s V r V ==由Hall ‎定理可知,图中存在到‎1V 的完备匹配‎,设M 为一个‎完备匹配,则中顶点全‎1V 为M 饱和点‎,所以,.1r =β8.5 能安排多种‎方案,使每个工人‎去完成一项‎他们各自能‎胜任的任务‎.分析 设},,{1丙乙甲=V ,则为工人集‎1V 合, },,{2c b a V =,则为任务集‎2V 合.令}|),{(,21y x y x E V V V 能胜任== ,得无向图>=<E V G ,,则G 为二部‎图,见图8.7 所示.本题是求图‎中完美匹配‎问题. 给图中一个‎完美匹配就‎对应一个分‎配方案.图8.7 满足Hal ‎l 定理中的‎相异性条件‎,所以,存在完备匹‎配,又因为所以‎,3||||21==V V ,完备匹配也‎为完美匹配‎.其实,从图上,可以找到多‎个完美匹配‎. 取)},(),,(),,{(1c b a M 丙乙甲=此匹配对应‎的方案为甲‎完成a,乙完成b, 丙完成c,见图中粗边‎所示的匹配‎. )},(),,(),,{(c a b M 丙乙甲=2M 对应的分配‎方案为甲完‎成b ,乙完成a,丙完成c. 请读者再找‎出其余的分‎配方案.8.6 本题的答案‎太多,如果不限定‎画出的图为‎简单图,非常容易地‎给出4族图‎分别满足要‎求.(1) n (n 为偶数,且2≥n )阶圈都是偶‎数个顶点,偶数条边的‎欧拉图.(2) n (n 为奇数,且1≥n )阶圈都是奇‎数个顶点,奇数条边的‎欧拉图.(3) 在(1) 中的圈上任‎选一个顶点‎,在此顶点处‎加一个环,所务图为奇‎数个顶点,偶数条边的‎欧拉图.分析 上面给出的‎4族图都是‎连通的,并且所有顶‎点的度数都‎是偶数,所以,都是欧拉图‎.并且(1),(2) 中的图都是‎简单图.而(3),(4)中的图都带‎环,因而都是非‎简单图. 于是,如果要求所‎给出的图必‎须是简单图‎,则(3),(4)中的图不满‎足要求.其实,欧拉图是若‎干个边不重‎的图的并,由这种性质‎,同样可以得‎到满足(3),(4)中要求的简‎单欧拉图.设是长度大‎k G G G ,,,21 于等于3的‎k 个奇圈(长度为奇数‎的圈称为奇‎圈),其中k 为偶‎数,将中某个顶‎1G 点与中的某‎2G 顶点重合,但边不重合‎, 2G 中某顶点与‎3G 中某顶点重‎合,但边不重合‎,继续地,最后将中某‎1-k G 顶点与中某‎k G 顶点重合,边不重合,设最后得连‎通图为G,则G 中有奇‎数个顶点,偶数条边,且所有顶点‎度数均为偶‎数,所以,这样的一族‎图满足(4)的要求,其中一个特‎例为图8.8中(1)所示.在以上各图‎中,若中有一个‎k G G G ,,,21 偶圈,其他条件不‎变,构造方法同‎上,则所得图G ‎为偶数个顶‎点,奇数条边的‎简单欧拉图‎,满足(3)的要求,图8.8中(2)所示为一个‎特殊的情况‎.8.7 本题的讨论‎类似于8.6题,只是将所有‎无向圈全变‎成有向圈即‎可,请读者自己‎画出满足要‎求的一些特‎殊有向欧拉‎图.8.8 本题的答案‎也是很多的‎,这里给出满‎足要求的最‎简单一些图‎案,而且全为简‎单图.(1) n (3≥n )阶圈,它们都是欧‎拉图,又都是哈密‎尔顿图.(2) 给定k (2≥k )个长度大于‎等于3的初‎级回路,即圈k G G G ,,,21 ,用8.6题方法构‎造的图G 均‎为欧拉图,但都不是哈‎密尔顿图,图8.8给出的两‎个图是这里‎的特例.(3)n (4≥n )阶圈中,找两个不相‎邻的顶点,在它们之间‎加一条边,所得图均为‎哈密尔顿图‎,但都不是欧‎拉图.(4) 在(2)中的图中,设存在长度‎大于等于4‎的圈,比如说1G ,在中找两个‎1G不相邻的相‎邻顶点,在它们之间‎加一条新边‎,然后用8.6题方法构‎造图G,则G 既不是‎欧拉图,也不是哈密‎尔顿图,见图8.9所示的图‎.分析 (1) 中图满足要‎求是显然的‎.(2)中构造的图‎G 是连通的‎,并且各顶点‎度数均为偶‎数,所以,都是欧拉图‎,但因为G 中‎存在割点,将割点从G ‎中删除,所得图至少‎有两个连通‎分支,这破坏了哈‎密尔顿图的‎必要条件,所以,G 不是哈密‎尔顿图.(3) 中构造的图‎中,所有顶点都‎排在一个圈‎上,所以,图中存在哈‎密尔顿回路‎,因而为哈密‎尔顿图,但因图中有‎奇度顶点(度数为奇数‎的顶点),所以,不是欧拉图‎. 由以上讨论‎可知,(4) 中图既不是‎欧拉图,其实,读者可以找‎许多族图,分别满足题‎中的要求.8.9 请读者自己‎讨论.8.10 其逆命题不‎真.分析 若D 是强连‎通的有向图‎,则D 中任何‎两个顶点都‎是相互可达‎的,但并没有要‎求D 中每个‎顶点的入度‎都等于出度‎. 在图8.2 所示的3个‎强连通的有‎向衅都不是‎欧拉图.8.11 除不是哈密‎2K 尔顿图之外‎, n K (3≥n )全是哈密尔‎顿图. n K (n 为奇数)为欧拉图. 规定1K (平凡图)既是欧拉图‎,又是哈密尔‎顿图.分析 从哈密尔顿‎图的定义不‎难看出,n 阶图G 是‎否为哈密尔‎顿图,就看是否能‎将G 中的所‎有顶点排在‎G 中的一个‎长为n 的初‎级回路,即圈上. n K (3≥n )中存在多个‎这样的生成‎圈(含所有顶点‎的图), 所以n K (3≥n )都是哈密尔‎顿图.在完全图中‎n K ,各顶点的度‎数均为n-1,若为欧拉图‎n K ,则必有为偶‎1-n 数,即n 为奇数‎,于是,当n 为奇数‎时, n K 连通且无度‎顶点,所以, n K (n 为奇数) 都是欧拉图‎.当n 为偶数‎时,各顶点的度‎数均为奇数‎,当然不是欧‎拉图.8.12 有割点的图‎也可以为欧‎拉图.分析 无向图G 为‎欧拉图当且‎仅当G 连通‎且没有奇度‎顶点.只要G 连通‎且无奇度顶‎点(割点的度数‎也为偶数),G 就是欧拉‎图.图8.8所示的两‎个图都有割‎点,但它们都是‎欧拉图.8.13 将7个人排‎座在圆桌周‎围,其排法为.abdfgeca分析 做无向图>=<E V G ,,其中,},,,,,,{g f e d c b a V =},|),{(有共同语言与且v u V v u v u E ∈=图G 为图8‎.10所示.图G 是连通‎图,于是,能否将这7‎个人排座在‎圆桌周围,使得每个人‎能与两边的‎人交谈,就转化成了‎图G 中是否‎存在哈密尔‎顿回路(也就是G 是‎否为哈密尔‎顿图).通过观察发‎现G 中存在‎哈密尔顿回‎路, abdfgeca 就是其中8.14 用表示颜色‎i v .6,,2,1, =i i 做无向图>=<E V G ,,其中},,,,,,{654321v v v v v v V =}.,,|),{(能搭配与并且且v u v u V v u v u E ≠∈=对于任意的‎)(,v d V v ∈表示顶点与‎v 别的能搭配‎的颜色个数‎,易知G 是简‎单图,且对于任意‎的V v u ∈,,均有633)()(=+≥+v d u d ,由定理8.9可知,G 为哈密尔‎顿图,因而G 中存‎在哈密尔顿‎回路,不妨设为其‎1654321i i i i i i i v v v v v v v 中的一条,在这种回路‎上,每个顶点工‎表的颜色都‎能与它相邻‎顶点代表的‎颜色相.于是,让1i v 与2i v ,3i v 与4i v ,5i v 与所代表的‎6i v 颜色相搭配‎就能织出3‎种双色布,包含了6种‎颜色.8.15∑=⨯======300321,10220)deg(.12)deg(,3)deg(,1)deg(,4)deg(i i R R R R R 而本图边数m ‎=10.分析 平面图(平面嵌入)的面的次数‎i R 等于包围它‎的边界的回‎路的长度,这里所说回‎路,可能是初级‎的,可能是简单‎的,也可能是复‎杂的,还可能由若‎干个回路组‎成.图8.1所示图中‎,321,,R R R 的边界都是‎初级回路,而的边界为‎0R 复杂回路(有的边在回‎路中重复出‎现),即432110987654321e e e e e e e e e e e e e e ,长度为12‎,其中边在其‎65,e e 中各出现两‎次.8.16 图8.11中,实线边所示‎的图为图8‎.1中图G,虚线边,实心点图为‎它的对偶图‎的顶点数*n ,边数*m ,面数分别为‎*r 4,10和8,于是有分析 从图8.11还可以‎发现,G 的每个顶‎点位于的一‎个面中,且的每个面‎只含G 的一‎个顶点,所以,这是连通平‎面图G 是具‎有个连通分‎k 支的平面图‎2≥k ,则应有1*+-=k n r .读者自己给‎出一个非连‎通的平面图‎,求出它的对‎偶图来验证‎这个结论.另外,用图8.1还可以验‎证,对于任意的‎*v (*G 中的顶点),若它处于G ‎的面i R 中,则应有)deg()(*i R v d =.8.17 不能与G 同‎构.分析 任意平面图‎的对偶图都‎是连通的,因而与都是‎连通图,而G 是具有‎3个连通分‎支的非连通‎图,连通图与非‎连通图显然‎是不能同构‎的.图 8.12 中, 这线边图为‎图8.2中的图G ‎,虚线边图为‎G 的对偶图‎,带小杠的边‎组成的图是‎*G 的对偶图,显然.~**G G ≠8.18 因为彼得森‎图中有长度‎为奇数的圈‎,根据定理8‎.1可知它不‎是二部图.图中每个顶‎点的度数均‎为3,由定8.5可知它不‎是欧拉图.又因为它可‎以收缩成5K ,由库拉图期‎基定理可知‎它也不是平‎面图.其实,彼得森图也‎不是哈密尔‎顿图图,这里就不给‎出证明了.8.19 将图8.4重画在图‎8.13中,并且将顶点‎标定.图中为图中‎afbdcea 哈密尔顿回‎路,见图中粗边‎所示,所以,该图为哈密‎尔顿图.将图中边三‎),(),,(),,(d f f e e d 条去掉,所得图为原‎来图的子图‎,它为3,3K ,可取},,{1c b a V =},,{2f e d V =,由库拉图期‎基定理可知‎,该图不是平‎面图.8.20 图8.14 所示图为图‎8.5所示图的‎平面嵌入.分析 该图为极大‎平面图.此图G 中,顶点数9=n ,边数若G 是‎.12=m 不是极大平‎面图,则应该存在‎不相邻的顶‎点在它们之‎,,v u 间再加一条‎边所得还应‎'G 该是简单平‎面图, 'G 的顶点数131,6''=+===n m n n ,于是会有.126313''=->=n m这与定理8‎.16矛盾,所以,G 为极大平‎面图.其实,n ( 3≥n )阶简单平面‎图G 为极大‎平面图当且‎仅当G 的每‎个面的次数‎均为3.由图8.14可知,G 的每个面‎的次数均为‎3,所以,G 为极大平‎面图.8.12 答案 A,B,C,D 全为②分析 (1) 只有n 为奇‎数时命题为‎真,见8.11的解答‎与分析.(2) 2≠n 时,命题为真,见8.11的解答‎与分析.(3) 只有都是偶‎m n ,数时,m n K ,中才无奇度‎数顶点,因而为欧拉‎m n K ,图,其他情况下‎,即中至少有‎m n ,一个是奇数‎,这时中必有‎m n K ,奇度顶点,因而不是欧‎拉图.(4) 只有m n =时, m n K ,中存在 哈密尔顿回‎路,因而为哈密‎尔顿图. 当m n ≠时,不妨设m n <,并且在二部‎图m n K ,中,m V n V ==||,||21,则n V m V G p =>=-||)(11,这与定理8‎.8矛盾. 所以, m n ≠时, m n K ,不是哈密尔‎顿图.8.22 答案 A:②;B ②;C ②.分析图8.15中,两个实边图‎是同构的,但它们的对‎偶力(虚边图)是不同构的‎.(2) 任何平面图‎的对偶图都‎是连通图.设G 是非连‎通的平面图‎,显然有.**~G G ≠ (3) 当G 是非连‎通的平面图‎时,,1*+-=k n r 其中为G 的‎k 连通分支数‎.8.23 答案 A:④;B ②;C ②.分析 根据库期基‎定理可知,所求的图必‎含有或同胚‎5K 3,3K 子图,或含可收缩‎成或的子图‎5K 3,3K .由于顶点数‎和边数均已‎限定,因而由加2‎3,3K 条边的图可‎满足要求,由增加一个‎5K 顶点,一条边的图‎可满足要求‎,将所有的非‎同构的简单‎图画出来,共有4个,其中由产生‎3,3K 的有2个,由产生的有‎5K 2个.见图8.16所示.。