下载文档原格式
离散数学复习资料一、考试内容（1）考试内容以课堂上讲的内容为范围；（2）每次课后布置的作业。
二、各章节提要教学目的及要求：教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理理论。
教学重点：命题逻辑中的基本概念和基本推理方法。
教学难点：推理理论小结：学习第一章要注意以下几点：（1）弄清命题与陈述句的关系。
（2）弄清由5种基本联结词联结的复合命题的逻辑关系及其真值。
特别是要弄清蕴含式”P→Q“的逻辑关系及其真值。
（3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。
（4）会准确地求出给定公式的主析取范式和主合取范式。
掌握主析取范式与真值表、成真赋值、主合取范式的关系。
（5）会用多种方法判断公式的类型及判断两个公式是否等价。
（6）会用等价变换法将一个联结词集中的公式等价地化为另一个联结词全功能集中的公式。
（7）掌握推理和判断推理是否正确的方法。
教学目的及要求：深刻理解和掌握谓词逻辑的基本概念和基本推理方法。
教学内容：谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。
教学重点：谓词逻辑中的基本概念和基本推理方法。
教学难点：谓词演算的推理理论。
小结：学习第二章要注意以下几点：(1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。
(2)在将命题符号化时，要特别注意量词与联结词的搭配。
经常的情况是全称量词∀与蕴含词→搭配，存在量词∃与合取词∧搭配。
因此有下面两种形式的公式：（∀x）(A(x) →B(x)) ①（∃x）(A(x) ∧ B(x)) ②而（∀x）(A(x) ∧ B(x)) ③（∃x）(A(x) → B(x)) ④③与①，④与②的含义完全不同。
(3)记住主要的等价式。
会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。
1：什么是欧拉路？如何用欧拉路判定一个图G是否可一笔画出？给定无孤立点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；如果一个图有欧拉路，则这个图能一笔画出。
2：什么是汉密尔顿图？请找出一个无向图具有汉密尔顿路的充分条件。
给定图G，若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作汉密尔顿回路，如果一个图有汉密尔顿回路，则这个图是汉密尔顿图。
一个无向图具有汉密尔顿路的充分条件：设G具有n个结点的简单图，如果G中每一对结点的度数之和大于等于n-1，则在G 中存在一条汉密尔顿路。
3：什么是图的正常着色？简述韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法。
图G的正常着色(或简称为着色)是指对它的每一个结点指定一种颜色，使得没有两个相邻的结点有同一种颜色。
韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法：⑴将图G的结点按照度数的递减次序进行排列。
(这种排列可能并不是唯一的，因为有些点有相同的度数)。
⑵用第一种颜色对第一点进行着色，并且按排列次序，对前面着色点不邻接的每一点着上同样的颜色。
⑶用第二种颜色对尚未着色的点重复⑵，用第三种颜色继续这种做法，直到所有的点全部着上色为止。
4：什么是平面图？平面图的一个重要性质是欧拉定理，请写出欧拉定理。
设G＝〈V，E〉是一个无向图，如果能够把G的所有结点和边画在平面上，且使任何两条边除了端点外没有其它的交点，就称G是一个平面图。
平面图有一个重要性质是欧拉定理：设有一个连通平面图G，共有v个结点e条边r块面，则欧拉公式 v-e+r＝2 成立。
5：请给出树的至少5个等价的定义。
（每个1分，写对5个以上给满分，）给定树T，以下关于树的定义是等价的：⑴无回路的连通图；⑵无回路且e=v-1，其中e为边数，v为结点数；⑶连通且e=v-1；⑷无回路且增加一条新边，得到一个且仅一个回路；⑸连通且删去任何一个边后不连通；⑹每一对结点之间有一条且仅一条路。
《离散数学B》教学大纲Discrete Mathematics B课程代码：课程性质：专业基础理论课/必修适用专业：信息计算、信息安全、信管开课学期：3总学时数：56 总学分数： 3.5编写年月：2005年7月修订年月：2007年7月执笔：魏均斌一、课程的性质与目的离散数学虽然是近几十年来产生出的一门新课，就其数学内容来说却不是新的，有些内容甚至是很古典的。
随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述，从而为研究计算机科学及相关学科提供了有利的理论基础和工具。
1.本课程的教学目的和要求：离散数学是计算机科学及相关学科的一门非常重要的专业基础课。
教学的目的是培养学生的数学思维能力，通过教学，最终使学生能够在众多的概念中要找出最重要的，在众多的定理中找出最根本的，将这些少量的概念和定理能够透彻地理解，自如地运用，就达到了掌握离散数学的教学要求。
2.本课程的主要内容：朴素集合论、古典数理逻辑、图论、抽象代数学（包括群、环、域、格、布尔代数）。
3.教学重点与难点：离散数学包含的数学内容非常多，这些数学内容彼此间的独立性很强，每一个内容都可以做为一门课单独讲授，而在一个学期里讲授离散数学这门课，就只能讲授各个内容的最基本的知识，为学生今后进一步学习打下基础。
因此，教师在认真讲解基本概念和知识外，更重要的是培养学生的数学思维能力，决不能将离散数学讲成数学，这就是离散数学教学的重点，同时也是离散数学教学的难点。
二、教学内容与学时分配（54学时）第一章命题逻辑1.教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、其他联结词、对偶与范式、推理理论。
2.教学目的及要求：深刻理解和掌握命题逻辑中的基本概念和基本方法。
离散数学-图论复习离散数学11春图论部分综合练习辅导大家好！本学期的第二次教学辅导活动现在开始，本次活动主要是针对第二单元图论的重点学习内容进行辅导，方式同样是通过讲解一些典型的综合练习作业题目，帮助大家进一步理解和掌握图论的基本概念和方法．图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法．教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等．本次综合练习主要是复习这一单元的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题．这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习．下面是本学期第4，5次形考作业中的部分题目．一、单项选择题单项选择题主要是第4次形考作业的部分题目．第4次作业同样也是由10个单项选择题组成，每小题10分，满分100分．在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目．1．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 ( ) ．A ．deg(v )=2∣E ∣B ． deg(v )=∣E ∣C ．E v V v 2)deg(=∑∈D ．E v Vv =∑∈)deg(该题主要是检查大家对握手定理掌握的情况．复习握手定理：定理3.1.1 设G 是一个图，其结点集合为V ，边集合为E ，则∑∈=Vv E v ||2)deg(也就是说，无向图G 的结点的度数之和等于边数的两倍．正确答案：C2．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100100110， 则G 的边数为( )．A ．6B ．5C ．4D ．3主要是检查对邻接矩阵的概念理解是否到位．大家要复习邻接矩阵的定义，要记住当给定的简单图是无向图时，邻接矩阵为对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i 与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各有一个1，题中给出的邻接矩阵中共有10个1，故有10÷2=5条边．正确答案：B3．如右图所示，以下说法正确的是 ( ) ．A ．{(a, e )}是割边B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d , e )}是边割集先复习割边、边割集的定义： 定义3.2.9 设无向图G =<V ,E >为连通图，若有边集E 1⊂E ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图是连通图，则称E 1是G 的一个边割集．若某个边构成一个边割集，则称该边为割边（或桥）因为删除答案A 或B 或C 中的边后，得到的图是还是连通图，因此答案A 、B 、C 是错误的．正确答案：D4．图G 如由图所示，以下说法正确的是 ( )．A ．a 是割点B ．{b, c }是点割集C ．{b , d }是点割集D ．{c }是点割集主要是检查对点割集、割点的概念理解的情况．定义3.2.7 设无向图G =<V , E >为连通图，若有点集V 1⊂V ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图是连通图，则称V 1是G 的一个点割集．若某个结点构成一个点割集，则称该结点为割点．从图二中删除结点b, c ，得到的子图是由不连通图，而只删除结点b 或结点c ，得到的子图仍然是连通的，由定义可以知道，{b, c }是点割集．所以正确答案：B5．设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( )．A ．（a ）是强连通的B ．（b ）是强连通的 ο ο ο ο a b cd οe ο ο ο a b c d οC．（c）是强连通的D．（d）是强连通的我们先复习强连通的概念：定义3.2.5 在简单有向图中，若在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G是单向（侧）连通的；若在任何结点偶对中，两结点对互相可达，则称图G是强连通的．正确答案：A问：上面的图中，哪个仅为弱连通的？请大家要复习“弱连通”的概念．6．设完全图Kn 有n个结点(n 2)，m条边，当（）时，Kn中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数我们先复习完全图的概念：定义3.1.6 简单图G=<V，E>中，若每一对结点间都有边相连，则称该图为完全图．有n个结点的无向完全图记为K n．由定义可知，完全图K n中的任一结点v到其它结点都有一条边，共有n-1条边，即每个结点的度数是n-1，当n为奇数时，n-1为偶数．由定理4.1.1的推论一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数．所以，正确答案应该是C．7．若G是一个汉密尔顿图，则G一定是( )．A．平面图B．对偶图C．欧拉图D．连通图我们先复习汉密尔顿图的概念：定义4.2.1 给定图G，若存在一条路经过图G的每个结点一次且仅一次，则该路称为汉密尔顿路；若存在一条回路经过图G的每个结点一次且仅一次，则该回路称为汉密尔顿回路；具有汉密尔顿回路的图称为汉密尔顿图．由定义可知，汉密尔顿图是连通图．所以，正确答案应该是D．问：汉密尔顿图为什么不一定是欧拉图吗？8．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 本题主要检查大家是否掌握了欧拉定理．定理4.3.2（欧拉定理）设连通平面图G的结点数为v，边数为e，面数为r，则欧拉公式v-e+r =2成立．由欧拉公式v-e+r =2，得到r = e- v+2．所以，答案A是正确的．9．无向简单图G是棵树，当且仅当( )．A ．G 连通且边数比结点数少1B ．G 连通且结点数比边数少1C ．G 的边数比结点数少1D ．G 中没有回路．可以运用教材中的定理5.1.1，可以作出正确选择．因为定理5.1.1中给出的图T 为树的等价定义之一是图T 连通且e=v -1，其中e 是边数，v 是结点数．也就是说：无向简单图G 是棵树，当且仅当G 连通且边数比结点数少1． 正确答案：A注：由上面的树的等价定义可知，结点数v 与边数e 满足e=v -1关系的无向连通图就是树．10．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（ ）．A ．8B ．5C ．4D ．3正确答案：B设无向树T 的树叶数为x ，因为树叶是度数为1的结点．那么，由定理3.1.1（握手定理） 设G 是一个图，其结点集合为V ，边集合为E ，则∑∈=Vv E v ||2)deg(得 4+3+2+x =2（8-1），即x =5．应选择B ．下面的内容主要是第5次形考作业的部分题目．二、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．也是检查大家对握手定理掌握的情况．因为图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，即∑∈=⨯+⨯+⨯+⨯=Vv v 3044332211)deg(，根据握手定理，边数有152/30==E ．应该填写：152．设给定图G (如右图所示)，则图G 的点割集是． 本题还是检查大家对点割集、割点的概念理解的情况．点割集、割点的定义前面已经复习了，从图G 中删除结点f ，得到的子图是不连通图，即结点集{f }是点割集；同样，从图G 中删除结点c ，e ，得到的子图也是不连通图，那么结点集{c , e }也是点割集．而删除其他结点集都没有满足点割集、定义的集合，所以应该填写：{f }、{c , e } ο ο ο ο a b cd οe ο f3．无向图G存在欧拉回路，当且仅当G连通且．由定理4.1.1的推论一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数．应该填写：结点度数都是偶数4．设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于，则在G中存在一条汉密尔顿路．定理4.2.2设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路．应该填写：n-15．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．（……边后，可以确定图G的一棵生成树）由握手定理（定理3.1.1）知道图G有18÷2=9 条边，又由定理5.1.1中给出的图T为树的等价定义之一是“图T连通且e=v-1”，可以知道：应该填写：4．6．设正则5叉树的树叶数为17，则分支数为i = ．定理5.2.1 设有正则m叉树，其树叶数为t，分枝数为i，则(m-1)i=t-1．其中m=5，t=17，由(5-1)i=17-1，得i =4．应该填写：4三、判断说明题1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．分析：先复习欧拉图的判别定理：定理4.1.1的推论：一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数．解：不正确．因为题中的图G没有“连通”的条件．2．如下图所示的图G存在一条欧拉回路．解：不正确．因为图G中结点b和c的度数是奇数．注：这是一个汉密尔顿图，但不是欧拉图，它可以作为单向选择题7解答之后提出的问题的一个解答．3．设G是一个有7个结点16条边的连通图，则G为平面图．分析：定理4.3.3 设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．利用该定理判断本题．解：不正确．因为题中的连通简单平面图有v =7个结点，e =16条边，那么16≥3⨯7-6=15，由定理4.3.3知道，图G 不是平面图．4．设G 是一个连通平面图，且有6个结点11条边，则G 有7个面．分析：可以用平面图中的欧拉公式：v-e+r =2来判断，其中v 为结点数，e 为边数，r 为面数．解：正确．因为连通平面图G 有v =6个结点，e =11条边，那么由欧拉公式计算得：r =2+ 11- 6 = 7个面．四、计算题1．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，试(1) 给出G 的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形．解：(1) 因为V ={ v 1，v 2，v 3，v 4，v 5}，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4)，(v 3,v 5)，(v 4,v 5) }，所以G 的图形表示为：(2) 分析：本题给定的简单图是无向图，因此邻接矩阵为对称的．即当结点v i 与v j 相邻时，结点v j 与v i 也相邻，所以连接结点v i与v j 的一条边在邻接矩阵的第i 行第j 列处和第j 行第i 列处各写一个1；当结点v i 与v j 没有边连接时，邻接矩阵的第i 行第j 列处和第j 行第i 列处各写一个0．邻接矩阵： ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0110010110110110110000100 (3) 由G 的图形可知，v 1，v 2，v 3，v 4，v 5结点的度数依次为1，2，4，3，2(4) 由关于补图的定义3.1.9可知，先画出完全图（见图1），然后去掉原图，可得补图（见图2）如下：图 1 ο ο ο ο v ο v v v v ο ο ο ο v ο v v v v ο ο ο ο v ο v v v v图2注意：补图中，如果没有标出结点v 3，则是错的．2．图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形； （2）写出G 的邻接矩阵；（3）求出G 权最小的生成树及其权值．解 （1）因为V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) }，所以G 的图形表示为：（2）由图得图G 的邻接矩阵为：0110110011100110110111110A ⎛⎫ ⎪ ⎪ ⎪= ⎪ ⎪ ⎪⎝⎭（3）图G 有5个结点，其生成树有4条边，用Kruskal 算法（避圈法）求其权最小的生成树T ：第1步，取具最小权1的边(a , c )；第2步，取剩余边中具最小权1的边(c , e )；第3步，取剩余边中不与前2条边构成回路的具最小权2的边(a , b )；第4步，取剩余边中不与前3条边构成回路的具最小权3的边(b , d )．所求最小生成树T 如右下图，其权为()11237W T =+++=．注意：在用避圈法求最小的生成树的关键是：“取图中权数最小的边，且与前面取到的边不构成圈”，很多学生只注意到取权数最小的边了，而忽略了“不构成圈”的要求．如果结点数少一个，边数也少些，大家应该会做了吧．3．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．解：方法（Huffman ）：从2, 3, 5, 7, 17, 31中选2, 3为最低层结点，并从权数中删去，再添上他们的和数，即5, 5, 7, 17, 31；再从5, 5, 7, 17, 31中选5, 5为倒数第2层结点，并从上述数列中删去，再添上他们的和数，即7, 10, 17, 31；然后，从7, 10, 17, 31中选7, 10为倒数第3层结点，并从上述数列中删去，再添上他们的和数，即17, 17, 31；……最优二叉树如右图所示．最优二叉树权值为：2⨯5+3⨯5+5⨯4+7⨯3+17⨯2+31⨯1=10+15+20+21+34+31=131讲评：作业中最优二叉树往往都能画对了，但计算总权值时可能会把有些权的层数计算错了，导致总权值计算错误，大家一定要细心． 注意：这3个计算题大家一定要掌握．五、证明题证明题同学一般都做不好，原因是对证明题方法没有掌握，也是对一些概念不清楚所造成的．因此，希望大家认真学习教材和老师讲课中的证明方法，并通过作业逐步掌握做证明题的方法．1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k 条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加2k 条边到图G 才能使其成为欧拉图． ο ο ο ο ο 3 2 7 5 5 131ο ο ο ο 13ο ο 6。
