第 1 页/共 9 页
离散数学知识点总结
总结离散数学知识点
第二章命题逻辑
1.→，前键为真，后键为假才为假；，相同为真，别同为假；
2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；
3.求极小项时，命题变元的确信为1，否定为0，求极大项时相反；
4.求极大极小项时，每个变元或变元的否定只能浮现一次，求极小项时变元别够合取真，求极大项时变元别够析取假；
5.求范式时，为保证编码别错，命题变元最好按P,Q,R的顺序依次写；
6.真值表中值为1的项为极小项，值为0的项为极大项；
7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取；
8.永真式没有主合取范式，永假式没有主析取范式；
9.推证蕴含式的办法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)
10.命题逻辑的推理演算办法：P规则，T规则
①真值表法；②直截了当证法；③归谬法；④附加前提法；
第三章谓词逻辑
1.一元谓词：谓词惟独一具个体，一元谓词描述命题的性质；
多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^;
3.既有存在又有全称量词时，先消存在量词，再消全称量词；
第四章集合
1.N，表示自然数集，1,2,3……，别包括0；
2.基：集合A中别同元素的个数，|A|；
3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；
4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2；
5.集合的分划：(等价关系)
第 2 页/共 9 页
第4章 图论
综合练习
一、 单项选择题
1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )．
(A) L可以不是简单路径，而是基本路径
(B) L可以既是简单路径,又是基本路径
(C) L可以既不是简单路径，又不是基本路径
(D) L可以是简单路径，而不是基本路径
答案：A
2．下列定义正确的是( )．
(A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图
(C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图
答案：D
3．以下结论正确是 ( )．
(A) 仅有一个孤立结点构成的图是零图
(B) 无向完全图Kn每个结点的度数是n
(C) 有n(n>1)个孤立结点构成的图是平凡图
(D) 图中的基本回路都是简单回路
答案：D
4．下列数组中，不能构成无向图的度数列的数组是( )．
(A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)
答案：B
5．下列数组能构成简单图的是( )．
(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)
答案：C
6．无向完全图K3的不同构的生成子图的个数为（ ）．
(A) 6 (B) 5 (C) 4 (D) 3
答案：C
7．n阶无向完全图Kn中的边数为（ ）．
(A) 2)1(nn (B) 2)1(nn (C) n (D)n(n+1)
答案：B
8．以下命题正确的是( )．
(A) n(n1)阶完全图Kn都是欧拉图
(B) n(n1)阶完全图Kn都是哈密顿图
离散数学是一门研究离散的数学结构的学科，其中图论是离散数学中的重要分支。图论研究的是图的性质及其应用，而平面图是图论中一个非常重要的概念。在离散数学中，平面图的概念以及平面图的判断是一个非常有趣且具有实际应用的问题，本文将对平面图的概念以及如何判断图是否为平面图进行探讨。
首先，我们来定义平面图。在离散数学中，平面图是指可以画在平面上并且其中不同边和不同顶点之间没有交叉的图。换句话说，如果将图的各个顶点用点表示，将图的各个边用线段表示，那么这些点和线段在平面上的位置不会相互交叉。
接下来，我们来看一下如何判断一个图是否为平面图。首先，我们需要了解一个重要的定理，即欧拉定理。欧拉定理是由瑞士数学家欧拉在18世纪提出的，它表明对于任何平面图都有一个重要的等式：顶点数减去边数再加上面（连通分量的个数）等于2。这个定理为我们判断一个图是否为平面图提供了一个重要的依据。
根据欧拉定理，我们可以得出一个结论：如果一个图的顶点数大于2且边数大于等于3，并且满足顶点数减去边数再加上面（连通分量的个数）等于2的等式，那么这个图就是一个平面图。但这只是一个判断的充分条件，并不是必要条件。
除了欧拉定理，我们还可以借助其他一些方法来判断图是否为平面图，例如柯尼格斯堡七桥问题和柯辞定理。柯尼格斯堡七桥问题是一个历史上著名的问题，它可以用图论的方式进行描述：在柯尼格斯堡的一座岛屿上有7个桥，这些桥将岛屿分为四个部分。问题是能否依次经过这7个桥恰好一次并且回到原点。通过研究这个问题，柯辞定理得出了一个结论：如果一个图中的所有顶点的度数都是偶数，则该图是一个平面图。
除了欧拉定理和柯辞定理，还有其他许多方法可以用来判断图是否为平面图，例如平面图的化简和平面图的染色等方法。通过这些方法的结合使用，我们可以更加准确地判断一个图是否为平面图。
总结起来，离散数学中的图的平面图与平面图的判断是一个非常有趣且具有实际应用的问题。通过欧拉定理、柯尼格斯堡七桥问题和其他一些方法的运用，我们可以准确地判断一个图是否为平面图。因此，研究图的平面图以及判断方法对于离散数学的发展和实际应用具有重要意义。
湘潭大学计算机科学与技术刘任任版离散数学课后习题答案-第二学期--图论与组合数学
习题六
1．设G是一个无回路的图,求证：若G中任意两个顶点间有惟一的通路,则G是树.证明：由假设知，G是一个无回路的连通图，故G是树。
2．证明：非平凡树的最长通路的起点和终点均为悬挂点.分析：利用最长通路的性质可证。
证明：设P是树T中的极长通路。若P的起点v满足d(v)1，则P不是T中极长的通路。对终点u也可同理讨论。故结论成立。
3．证明：恰有两个悬挂点的树是一条通路.
分析：因为树是连通没有回路的，所以树中至少存在一条通路P。因此只需证明恰有两个悬挂点的树中的所有的点都在这条通路P中即可。
证明：设u,v是树T中的两个悬挂点，即d(u)d(v)1。因T是树，所以存在(u,v)-通路
P：uw1wkv,k0。显然，d(wi)2。若d(wi)2，则由T恰有两个悬挂点的假设，可知T中有回路；若T中还有顶点某不在P中，则存在(u,某)-通路，显然u与某不邻接，且d(某)2。于是，可推得T中有回路，矛盾。故结论成立。
4．设G是树,Gk,求证：G中至少有k个悬挂点.
分析：由于Gk，所以G中至少存在一个顶点v的度≥k，于是至少有k个顶点与邻接，又G是树，所以G中没有回路，因此与v邻接的点往外延伸出去的分支中，每个分支的最后一个顶点必定是一个悬挂点，因此G中至少有k个悬挂点。
证明：设uV(G)，且d(u)mk。于是，存在v1,,vmV(G)，使
(l)uviE(G),i1,,m。若vi不是悬挂点，则有viV(G),使。如此下去，有viV(G)，
满足vi(l)vj,ij,且d(vi(l))1,i1,,m。故G中至少有k个悬挂点。
5．设Gp,q是一个图,求证：若qp,则G中必含回路.
分析：利用树是没有回路且连通的图，且树中的顶点数和边数的关系可证。
证明：设G(p,q)有k个分支：G[V1]G1(p1,q1),,G[Vk]Gk(pk,qk)。显然，
