北大离散数学07

2017秋课件作业第一部分集合论第一章集合的基本概念和运算1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}⊆A。

1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．Ø。

1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题）（1）N⊆Q，Q∈S，则N⊆S，［错］（2）-1∈Z，Z∈S，则-1∈S。

［错］1-4设集合B={4，3}∩Ø，C={4，3}∩{Ø}，D={3，4，Ø}，E={x│x∈R并且x2-7x+12=0}，F={4，Ø，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A]A.C;B.D;C.E;D. F.1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D]A.N;B.Z;C.Q;D.Z+1-6为何说集合的确定具有任意性?(简答题)答：按研究的问题来确定集合的元素。

我们所要研究的问题当然是随意的呗。

之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。

第二章二元关系2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA，试求：（综合题）(1)domR=?;(2)ranR=?;(3)R的性质。

（4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。

R）=？答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}；(1)DomR={R中所有有序对的x}={3,2,1};(2)RanR={R中所有有序对的y}={2,1,3}；(3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。

（4）商集A/R={{1，2，3}，{2，3}，{3}}。

由于R不是等价关系，所以，等价类之间出现交集。

另外一个版本：北大数学科学学院本科生课程课程号 00130011 课程名数学分析(一)课程号 00130012 课程名数学分析(二)课程号 00130013 课程名数学分析(三)课程号 00130031 课程名高等代数(上)课程号 00130032 课程名高等代数(下)课程号 00130051 课程名解析几何课程号 00130061 课程名解析几何习题课课程号 00130072 课程名初等数论课程号 00130081 课程名常微分方程课程号 00130091 课程名计算机原理与算法语言课程号 0013010. 课程名计算机实习课程号 00130110 课程名复变函数课程号 00130120 课程名微分几何学课程号 00130130 课程名抽象代数(A)课程号 00130140 课程名实变函数论课程号 00130150 课程名偏微分方程课程号 00130161 课程名拓朴学(一)课程号 00130162 课程名拓朴学(二)课程号 00130170 课程名泛函分析课程号 00130180 课程名数学模型学课程号 00130190 课程名微分流形课程号 00130201 课程名高等数学(B)(一)课程号 00130202 课程名高等数学(B)(二)课程号 00130203 课程名高等数学(B)(三)课程号 00130221 课程名高等数学(C)(一)课程号 00130222 课程名高等数学(C)(二)课程号 00130241 课程名高等数学(D)(一)课程号 00130242 课程名高等数学(D)(二)课程号 00130250 课程名高等数学(E)课程号 00130260 课程名线性代数(B)课程号 00130270 课程名线性代数(C)课程号 00130280 课程名计算方法课程号 00130290 课程名汇编语言课程号 00130300 课程名数理逻辑及其在人工智能中的应用课程号 00130310 课程名数据结构课程号 00130320 课程名计算机图形学课程号 00130330 课程名数字信号处理课程号 00130340 课程名编译原理课程号 00130350 课程名抽象代数(B)课程号 00130360 课程名代数数论基础课程号 00130370 课程名有限群课程号 00130380 课程名代数选讲课程号 00130390 课程名图论课程号 00230010 课程名概率统计(A)课程号 00230020 课程名概率统计(B)课程号 00230030 课程名概率统计(C)课程号 00230040 课程名普通统计学课程号 00230050 课程名概率论课程号 00230060 课程名数理统计课程号 00230070 课程名测度论和概率论基础课程号 00230080 课程名应用多元统计分析课程号 00230090 课程名应用随机过程课程号 00230100 课程名应用时间序列分析课程号 00230110 课程名保险统计学课程号 00230120 课程名决策分析课程号 00230130 课程名抽样调查课程号 00230140 课程名试验设计课程号 00230150 课程名统计计算课程号 00230160 课程名算法分析与数据结构课程号 00230170 课程名图论( 离散数学 ) 课程号 00230180 课程名保险风险模型课程号 00230190 课程名运筹学课程号 00230200 课程名复变函数课程号 00230210 课程名 FORTRAN课程号 00230220 课程名热力学与统计物理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

内容简介本书共分五编。

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

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

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

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

第五编为数理逻辑，其中包括命题逻辑、一阶谓词逻辑、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大部分，数理逻辑部分包括命题逻辑的基本概念、等值演算、范式与推理理论，一阶逻辑的基本概念、前束范式以及推理理论。

离散数学作业7离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。

并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题1．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100，则G 的边数为( D )．A ．5B ．6C ．3D ．4 2．设图G ＝<V ,E >，则下列结论成立的是 ( C )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(3．设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( D )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的 4．给定无向图G 如右图所示，下面给出的结 点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }姓 名： 学 号： 得 分： 教师签名：a b dc eο ο ο ο ο 4题图C ．{a , c }D ．{b , e }5．图G 如右图所示，以下说法正确的是 ( C ) ． A ．{(a , c )}是割边 B ．{(a , c )}是边割集 C ．{(b , c )}是边割集 D ．{(a, c ) ,(b, c )}是边割集6．无向图G 存在欧拉通路，当且仅当(D )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点7．若G 是一个欧拉图，则G 一定是( C )．A ．平面图B ．汉密尔顿图C ．连通图D ．对偶图8．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( A )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋29．设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n -+B ．m n -C ．1m n ++D ．1n m -+ 10．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（D ）．A ．8B ．5C ．4D ．3二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是 {f,c} ．3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数 等于边数的两倍．4．设有向图D 为欧拉图，则图D 中每个结点的入度 等于出度 ． 5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．设无向图G ＝<V ，E >是汉密尔顿图，则V 的任意非空子集V 1，都有 W(G-V1) ≤∣V 1∣．7．设完全图K n 有n 个结点(n ≥2)，m 条边，当 当m=2n 时，K n 中存在欧拉回路．ο a οο οο b cde 5题图8．设图G=<V,E>，其中|V|=n，|E|=m．则图G是树当且仅当G是连通的，且m=2V-2 ．9．连通无向图G有6个顶点9条边，从G中删去4 条边才有可能得到G的一棵生成树T．10．设正则5叉树的树叶数为17，则分支数为i = 4 ．三、判断说明题（判断下列各题，并说明理由．）1．(1) 如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(2) 图G1，(如下图所示) 是欧拉图．解：(1)错，图G是无向图，当且仅当G是连通的，且所有结点度数均为偶数，这里不能确定G图是否是连通的。