离散数学课堂笔记
离散数学课堂上的知识总结
介绍
离散数学课程由计算机系段建勇教授讲授。本文对课程内知识点进行了总结和提炼。
数理逻辑
命题
定义：唯一确定真值的陈述句
逻辑连接词
条件：与日常用语中的 如果…则,必须…以便,等含义相当。
双条件：与日常用语中的当且仅当,充分必要,只有且仅有…才能等含义相当。
命题公式与赋值
错误的命题：
- $(P)$ × (多括号)
- $(P \rightarrow Q),(P\wedge Q)\rightarrow Q)$ × (非法字符)
含有n个不同变元的公式有$2^n$个不同赋值。
含有n个分量$P_1,P_2,…,P_n$的命题公式可有无穷多个, 但互不等价的公式只有$2^{2^{n}}$个。
对偶与范式
在给定的命题公式中,将联结词$\vee$换成$\wedge$,将$\wedge$换成$\vee$,若有特殊变元F和T亦相互取代,所得公式A称为A的对偶式。
范式
合取范式：
项之间用析取号连接
析取范式同理
主析取范式
由小项组成，小项由合取号构成。小项中包含所有的变元。小项用m表示。
主合取范式同理
谓词逻辑
谓词的概念与表示
定义:一个 n 元谓词记作: $A(x_1 , x_2, … x_n)$
例:
令 A(x) : x 是大学生; a:张华 , b:李明 D:人类 则 A (a) 表示命题: 张华是大学生,A (b) 表示命题: 李明是大学生。
在谓词逻辑中,重言式不等于永真式。
量词
特性谓词:当在全总个体域中讨论命题时,需在命题表示中增加一个特性谓词,以给出个体变元的个体域。
例:
全称量词用条件
任何人都是要死的
H(x):x是要死的 M(x):x是人
则命题表示为:$( \forall x)(M(x)\rightarrow H(x))$
存在量词用合取
有些人是聪明的
A(x)：x是聪明的 M(x):x是人
则命题表示为:$( \forall x)(M(x)\wedge A(x))$
谓词公式
闭式:不含自由变元的公式 开式:含有自由变元的公式
0元谓词为闭式
-
如果公式A在任何解释下均为真,称A为永真式
-
如果 A在某个解释I和I的一个赋值下为真,称A可满足
-
如果公式在任何解释下均为假,称A为永假式
$( \forall x) A(x)\rightarrow B \Leftrightarrow ( \exists x) (A(x)\rightarrow B)$
$( \exists x) A(x)\rightarrow B \Leftrightarrow ( \forall x) (A(x)\rightarrow B)$
$B \rightarrow (\forall x) A(x) \Leftrightarrow (B \rightarrow (\forall x)A(x))$
$B \rightarrow (\exists x) A(x) \Leftrightarrow (B \rightarrow (\exists x)A(x))$
$(\forall x)(A(x) \wedge B(x)) \Leftrightarrow (\forall x)A(x) \wedge (\forall x)B(x)$
$(\exists x)(A(x) \vee B(x)) \Leftrightarrow (\exists x)A(x) \vee (\exists x)B(x)$
$( \forall x)A(x) \vee ( \forall x)B(x) \Rightarrow (\forall x)(A(x) \vee B(x))$
$(\exists x)(A(x)\wedge B(x)) \Rightarrow ((\exists x)A(x) \wedge (\exists x)B(x)$
前束范式
定义:一个公式,如果量词均在全式的开头,它们的作用域,延伸到整个公式的末尾,则该公式叫做前束范式。
集合
概念和表示法
集合相等:$A = B \Leftrightarrow A \subseteq B and A \supseteq B$
空集:$ \emptyset \subseteq A$
子集:
对于含有n个元素的集合A,它的子集个数为$2^{n}$
幂集:
由集合A的所有子集为元素组成的集合称为集合A的幂集,记为 $P(A)$
$P(\emptyset) = { \emptyset }$
$P(P(\emptyset)) = { { \emptyset },\emptyset }$
$P(\emptyset,{\emptyset }) = { \emptyset,{\emptyset },{{\emptyset }},{\emptyset, {\emptyset }}}$
集合运算
对称差:$A \oplus B = (A \cup B) - (A \cap B) = (A - B) \cup (B - A) $
$(A \oplus B) \oplus C = A \oplus (B \oplus C) $
关系
序偶
$<x,y,z> = «x,y>,z>$
笛卡尔积:
$A = { a,b} ,B = {1,2} ,A \times B = {<a,1>,<a,2>,<b,1>,<b,2>}$
关系及其表示
$|A| = n,|B| = m,则A到B的不同的关系有: 2^{| A \times B|} = 2 ^{n \times m}$
domR:前域
ramR:值域
FLDR:前域+值域
关系的性质
自反:对任意元素x,都有<x,x>
对称:关系矩阵是对称的
反自反:所有的元素x都没有<x,x>
反对称:关系矩阵中,除了自己和自己,没有对称的1
反对称例:
对称和反对称是可以同时存在的。例如:
复合关系和逆关系
复合关系:
$R={<a,b>},S = {<b,c>} ,R \circ S = {<a,c>}$
$R^{0} = I_x$
逆关系:
$R={<a,b>},R^c = {<b,a>}$
闭包
t:传递
r:自反
s:对称
划分
$A=\lbrace a,b,c\rbrace$
最大划分$\lbrace\lbrace a \rbrace,\lbrace b\rbrace,\lbrace c\rbrace\rbrace$,最小划分$\lbrace \lbrace a,b,c\rbrace \rbrace$
等价关系和等价类
R是自反,对称,传递的,则R为等价关系
序关系
哈斯图:
-
以集合A中的全部元素为结点,
-
若x < y, 则结点y在x的上方,
-
若y为x的盖住,则x,y之间有一边
偏序:自反,传递,反对称
等价:自反,对称,传递
相容:自反,对称
拟序:反自反,传递
图
图的基本概念
握手定理:任一图的结点度数之和=边数的二倍
即 $\sum_{v\in V} d(v) = 2 |E|$
推论:任何图中度数为奇数的结点个数为偶数
因为结点度数之和一定是偶数，且度数为偶数的结点的度数之和一定是偶数，故度数为奇数的结点的度数之和也需要是偶数。若度数为奇数的结点的数量为奇数，则度数为奇数的结点的度数之和一定是奇数。因此只能当度数为奇数的结点的数量为偶数时才能满足握手定理。
定理:在有向图中，入度之和=出度之和
多重图:含有平行边(联结同一对结点的多条边)的图称为多重图
简单图:不含平行边和环的图称为简单图
无向完全图:无向简单图G=<V,E>中,若每一对不同结点间都有一边相连,则该图称为无向完全图
含有$n$个结点的无向完全图记为$K_n$
其边数为 $\frac{1}{2} n(n-1)$
有向完全图:无向简单图G=<V,E>中,若每一对不同结点间都有一边相连,则该图称为无向完全图
补图:给定一个图G,由G中所有结点和所有能使G成为完全图的添加边组成的图,称为G的相对于完全图的补图 (G的补图),记作$\overline{G}$
子图:设图G=<V,E>,如果有图 G‘=<V’,E‘>,使得E’$\in$E, V‘$\in$V, 则称G’为G的子图。记作G‘$\in$G。
拥有原图的一些点和一些边
生成子图:若G’是G的子图,且V’=V,称G’为G的生成子图。
拥有原图的所有点和一些边
相对补:设G’=<V’,E’>是图G=<V,E>的子图,若有另一图G”=<V”, E” >, 使得 E”=E - E‘, 且V”中仅包含E”的边所关联的结点。则称G”是子图G’的相对于图G的补图(G的相对补)。记作G”= G- G'.
同构:若两图同构则它们的结点数相同,边数相同,且度数相同的结点数相同。
路与回路
路:边与点交替的序列称为路
路的长度:路中边的数量
回路(闭路):起点和终点一样
迹(链):路的各边不相同
通路:路的各点不相同
圈:闭的通路
推论:在n阶图中，如果从u到v存在通路，则从u到v存在长度小于等于n-1
联通分支:极大联通子图
联通分支数:联通分支的数量
点割集:设G=<V,E>为无向连通图,若有点集V1$\in$V, 使G删除V1所有点后,所得的子图不连通; 而删除V1的任何真子集后仍连通, 则称V1是G的一个点割集。若点割集只含有一个结点,则该结点称为割点。
点连通度:连通图的最小点割集的阶
不连通图: k(G)=0 存在割点的连通图: k(G)=1 平凡图: k(G)=0 (可视为连通或不连通) 完全图: k(Kn)=n-1
在此图中，点割集为{b,d,e}，{b,d}，{c}，{a,c}。点连通度为1。
边割集:设G=<V,E>为无向连通图,若有边集E1$\in$E, 使图G删除E1中所有边后得到的子图不连通; 而删除E1的任何真子集后仍连通, 则称E1是G的一个边割集。若边割集只含一边,则称该边称为割边(桥)。
边连通度:连通图的最小边割集的阶
不连通图: $\lambda$(G)=0
存在割边的连通图: $\lambda$(G)=1
平凡图:$\lambda$(G)=0 (可视为连通或不连通)
完全图: $\lambda$($K_n$)=n-1;
在此图中，边割集为{$e_1,e_3$}，{$e_2,e_4$}，{$e_5$}，{$e_3,e_4$}，{$e_1,e_2$}，{$e_2,e_4,e_5$}，{$e_1,e_3,e_5$}等。边连通度为1。
求图的点连通度和边连通度：
点连通度：2
删除u,v
边连通度：3
删除中间的三条边
定理:对于任何图G,有$k(G) \leqslant \lambda(G) \leqslant \delta(G)$
点连通度:$k(G)$
边连通度:$\lambda(G)$
点的最小度:$\delta(G)$
定理:一个连通无向图G中的结点v是割点,当且仅当存在结点u和w,使得u,w之间的每条路都通过v。
可达性:
- 在无向图中,若从u到v可达, 则从v到u必可达。
- 在有向图中,若从u到v可达, 则从v到u未必可达。
- G是单侧连通的,若$\forall$u,v$\in$V,必有u可达v或 v可达u。
- G是强连通的,若$\forall$u,v$\in$V,u,v都互相可达。
- G为弱连通的,若略去边的方向,作为无向图是连通的。
- 有向图是强连通的,当且仅当G中有一个回路,它至少包含每个结点一次。
定理:在简单有向图中
- 具有强连通性的最大子图,称为强分图;
- 具有单侧连通性的最大子图,称为单侧分图;
- 具有弱连通性的最大子图,称为弱分图。
定理:有向图的每个结点位于且只位于一个强分图中。
欧拉图(E图)
欧拉路:设G是无孤立结点的图,若存在一条经过图中每边一次且仅一次的路,该路称为欧拉路
欧拉回路:若欧拉路是闭的,称为欧拉回路
欧拉图:具有欧拉回路的图称为欧拉图
无向图存在欧拉路的充要条件:无向图G具有一条欧拉路,当且仅当G是连通的且有零个或两个奇数度结点。
无向图存在欧拉回路的充要条件:无向图G具有一条欧拉回路,当且仅当G是连通的且有零个奇数度结点。
一笔划问题的判别:一张图能由一笔划出, 当且仅当每个交点处的线条数均为偶数或恰有两个交点的线条数为奇数
有向图存在欧拉路的充要条件:有向图G具有一条从v$\rightarrow$u单向欧拉路, 当且仅 当G是连通的, 且$d^+ (v)= d^-(v)+1$, $d^+ (u)= d^- (u)-1$, 其他结点入度=出度。
有向图存在欧拉回路的充要条件:有向图G具有一条单向欧拉回路, 当且仅当G是弱连通的,且每个结点入度等于出度。
汉密尔顿图(H图)
汉密尔顿路:给定图G,若存在一条路经过G中每个结点恰好一次, 这条路称为汉密顿路
汉密尔顿回路:若汉密尔顿图是闭得，称为哈密尔顿回路
汉密尔顿图:存在汉密尔顿回路的图称为汉密尔顿图
定理:若图G=<V,E>是H图,则对$\forall$S$\in$ V且 S$\neq$$\Phi$,均有W(G-S)≤|S| , 其中W(G-S)是G-S的连通分支数。
存在汉密尔顿图的充分条件:如果G中每一对(不相邻)结点度数之和大于等于n-1,则在G中存在一条汉密尔顿路。
存在汉密尔顿回图的充分条件:如果G中每一对(不相邻)结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。
例题:七天内安排七门考试使得同一教师所任的两门课不得安排在接连的两天内。
证明:若没有教师担任多于四门课,则符合上述要求的安排总是可行的。
解:将考试抽象为一个点,若两个考试不是同一个老师则连一条线。此时,我们需要证明一条汉密尔顿路。而考试顺序，就是汉密尔顿路经过节点的路径。
why?因为一门课不能重复考且必须考，因此每个点必须且只能经过一次。 $\rightarrow$ 汉密尔顿图
每个点的度数范围为[3,6] (这个老师上四门课，则这个点可以连3个其他的考试)。且最多只有一个点的度数为3 (如果有两个老师都上了四门课，则总考试数为8，故不存在这种情况。因此最多只有一个老师上四门课，因此最多只有一个点的度数为3)。故任意不相交两点的度数之和一定大于等于7。因此存在汉密尔顿路。
平面图
平面图:无向图G,所有结点和边画在平面上 且 任何两条边除了端点外没有其他的交点 G是一个连通平面图
面的次数:面的边界回路长度称为面的次数.记作deg(r)。
如果面的面积有限,称为有限面,否则为无限面
r1: （A,B,D,A） deg(r1) : 3
r2: （B,C,D,B） deg(r2): 3
r3: （C,D,E,F,C） deg(r3)：5 （E,F走了两次）
r4: （A,B,C,E,A） deg(r4): 4
r5: （A,D,E,A）外面的区域 deg (r5): 3
定理:有限平面图中, 面的次数之和 = 边数的两倍。
欧拉定理:设G为连通平面图,共有v个结点e条边和r个面,则欧拉公式成立:v-e+r=2
定理:设G是有v个结点e条边的简单连通平面图,若v≥3则e≤3v-6
