离散数学图论知识点总结

总结 离散数学知识点

第二章 命题逻辑

1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；

5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项；

7.n个变元共有2n个极小项或极大项，这2n为(0~2n-1)刚好为化简完后的主析取加主合取；

8.永真式没有主合取范式，永假式没有主析取范式；

9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则

①真值表法；②直接证法；③归谬法；④附加前提法；

第三章 谓词逻辑

1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^;

3.既有存在又有全称量词时，先消存在量词，再消全称量词；

第六章 图论基础

图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。

6.1 图的基本概念

我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。 任意两个元素a,b构成的无序对（Unordered pair）记作(a,b)，这里总有(a,b)?(b,a)。 设A,B为两个集合，无序对的集合{(a,b)a?A?b?B}称为集合A与B的无序积（Unordered Product），记作A&B。无序积与有序积的不同在于A&B?B&A。

例如，设A??a,b?，B??0,1,2?，则A&B?{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)} ?B&A,A&A?{(a,a),(a,b),(b,b)}。 为了引出图的定义，我们先介绍如下的例子。

B start s=0,i =1 i=1 S i=11? Y N s

第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)

离散数学课程作业（图论）

一、 填空题 1. 2. 3. 4.

任意两点之间都有边相连的无向简单图称为 ；只有点，没有边的图称为 ；只有一个点的图称为 。 有n个顶点的连通无向图中至少有 条边。

无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G的阶数n至少为 。（答案：11） 写出如下无向图的关联矩阵：

5. 对任何连通平面图恒有：顶点数－边数＋面数＝ 。 6. 一个连通的无向图G是欧拉图当且仅当G中有 个奇度点。 7. 任意一棵非平凡的无向树都恰有 片叶子。 8. 判断如下哪些说法是正确的？

（1） 无向简单图中，无向完全图是边数最多的简单图。 （2） 哈密顿图一定是连通图。 （3） 欧拉图中只有2个奇度点。 （4） 在简单图中，连通但删去一条边后就不连通的图一定是树。

8. 设Ｇ是一个有n个结点的有向完全简单图，则Ｇ的边数为 。 9. 设T为一棵树，边数为m ，顶

离散数学第一章知识点总结（仅供参考）

1.判断给定的句子是否为命题的基本步骤：首先应是陈述句；其次要有唯一的真值。 例：（1）我正在说谎。

不是命题。因为无法判定其真假值，若假设它为假即我正在说谎，则意味着它的反为真，即我正在说实话，二者相矛盾；若假定它为真即我正在说实话，则意味着它的反为假，我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题 （2）x-y ＞2。

不是命题。因为x, y的值不确定，某些x, y使x?y＞2为真，某些x, y使x?y＞2为假，即x?y＞2的真假随x, y的值的变化而变化。因此x?y＞2的真假无法确定，所以x?y＞2不是命题。

2.命题可以分为两种类型：原子命题（不能再分解为更简单命题，又可称为简单命题）； 复合命题(通过联结词、标点符号将原子命题联结而成的命题） 3.命题常元：一个命题标识符如果表示确定的简单命题，就称为命题常元

命题变元：如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元 注：当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派

4.联接词：（1）否定联

离散数学图论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。

一、单项选择题

1．设图G的邻接矩阵为

??01100?011?

?10??10000??

?01001????01010??则G的边数为( )．

A．6 B．5 C．4

2．已知图G的邻接矩阵为

，

则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．V?deg(v)?E

v?v?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割

离散数学图论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。

一、单项选择题

1．设图G的邻接矩阵为

??01100?011?

?10??10000??

?01001????01010??则G的边数为( )．

A．6 B．5 C．4

2．已知图G的邻接矩阵为

，

则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．V?deg(v)?E

v?v?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割

离散数学图论部分综合练习

1．设图G＝，则下列结论成立的是 ( )． A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．?deg(v)?E

v?Vv?Va ? d? ? c

图一

b ? ? f

?e

2．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集

3．如图二所示，以下说法正确的是 ( )． A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集

4．如图三所示，以下说法正确的是 ( ) ．

图二 A．{(a, e)}是割边 B．{(a, e)} 是边割集

C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集

图三

5．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( )．

数理逻辑部分

第1章 命题逻辑 1.1 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题

注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化

用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1）表示 简单命题

用“1”表示真，用“0”表示假

例如，令 p： 是有理数，则 p 的真值为 0

q：2 + 5 = 7，则 q 的真值为 1

联结词与复合命题 1.否定式与否定联结词“?”

定义 设p为命题，复合命题 “非p”（或 “p的否定”）称

为p的否定式，记作?p. 符号?称作否定联结词，并规定?p 为真当且仅当p为假.

2.合取式与合取联结词“∧”

定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真

注意：描述合取

离散数学图论单元测验题

一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G＝中，结点总度数与边数的关系是( )

(A) deg(vi)=2?E? (B) deg(vi)=?E? (C)

?deg(v)?2E (D) ?deg(v)?E

v?Vv?V2、设D是n个结点的无向简单完全图，则图D的边数为( ) (A) n(n－1) (B) n(n+1) (C) n(n－1)/2 (D) n(n+1)/2

3、 设G＝为无向简单图，?V?=n，?(G)为G的最大度数，则有

(A) ?(G)n (D) ?(G)?n

4、图G与G?的结点和边分别存在一一对应关系，是G≌G?(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 5、设V?{a,b,c,d}，则与V能构成强连通图的边集合是( )

(A) E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} (B) E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?} (C) E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?}

6、有向