Discrete Mathematics (Fourth Edition)
离散数学（第四版）
6000字缩写笔记
1、PERT图与关键路径
2、后续子集算法：找0/1串最右边的0，如果有，把它置为1，后面的都置为0，否则算法终止。
3、Augusta Ada Byron 1815-1852
4、union intersection disjoint difference complement
5、集合S上的关系R可以具备下列特殊性质中的任何一个：
（1）如果对于S中的任意元素x，x R x为真，则称R是自反的（reflexive）
（2）如果只要x R y为真，y R x就为真，则称R是对称的（symmetric）
（3）如果只要x R y和y R z都为真，x R z都为真，则称R是传递的（transitive）
6、自反、对称和传递的关系称为等价关系（equivalence relation）
7、如果R是S上的等价关系，x∈S，则S中与x相关联的元素的集合称为包含x的等价类（equivalence class），记为[x]，所以[x] = {y∈S : y R x}
8、n = q m + r，q为商（quotient），r为余数（remainder）
9、模m的同余关系 congruence modulo m
10、Zm中：[x] + [y] = [x + y]，[x] [y] = [x y]，[x]y = [xy]
11、部分序，极大、极小元
12、哈斯图（Hasse Diagram），由下而上观察，图中所有的线段都看作是指向上方的
13、数学归纳法常用来验证算法
14、循环不变式：loop invariant
15、《算术》（Arithmetica）
16、两图同构，对应顶的度数首先相等
17、Leonhard Euler
18、多重图G中，包含G中所有的边恰好一次，并且第一个顶点和最后一个顶点不相同的通路称为欧拉通路（Euler path），起点和终点相同的称为欧拉回路（Euler circuit）
19、求欧拉回路算法（O(n2)）：算法运行在各顶度数均为偶数的连通多重图G上
（1）令E是G的边集，选一个顶U，令通路C仅由U组成
（2）while E非空（扩充通路）
令V是C中的顶，它与E中某边关联，令通路P恰好包含V
令W = V（扩充P使它成为一条从V到V的通路）
while E中有邻接W的边e
从E中删去e，用邻接e的另一顶替换W
将边e和顶W添加到通路P
endwhile
扩充C：用通路P替换C中出现的任意的某一个V
endwhile
（3）通路C是一条欧拉回路
20、Hamilton path是包含每个顶仅一次的通路，Hamilton cycle是包含每个顶仅一次的回路
21、定理（Ore性质）：n（n>2）阶图G若对任意不相邻顶U、V有deg(U) + deg(V) ≥ n则G有H-回路
22、格雷码（Gray code）应用：确定圆盘旋转的位置（减少错误）
23、BFS算法至多是n2阶的
24、定理（通路的数目）：图G各顶标为V1，V2，…，Vn，邻接矩阵为A，从Vi到Vj的长度为m的通路的数目是Am的(i, j)元素
25、定理24易用数学归纳法证明
26、着色一个图（color a graph）是指给每个顶点指定一种颜色，使得相邻的顶点有不同的颜色
27、当可用n种颜色，但不能用更少的颜色给一个图着色时，称该图具有色数（chromatic number）n
28、Kn的色数是n
29、定理（下界）：图G可用两种颜色着色当且仅当G不包含长度为奇数的回路
30、定理（上界）：图G的色数不会超过G中顶点的最大度数加1
31、【练习】证明：“色数是3”是图的同构不变量
32、每条U-V有向通路都包含一条U-V简单有向通路
33、有向欧拉回路的应用（无线电通信中的旋转磁鼓的位置）：序列01110100
34、有向H-回路（通路）与循环体育比赛
35、竞赛有向图（tournament directed graph）；采用完全图Kn并给每边一个方向
36、寻找一个所有队的排名与为竞赛图寻找一条有向H-通路是等同的
37、欧拉公式（1752）：f – e + v = 2
38、1847年，Gustav Kirchhoff在他的关于电网的工作中首次用到树。后来，Arthur Cayley在化学研究中使用了树
39、设U和V是树中的顶点，那么从U到V恰好有一条简单通路
40、在一棵顶点数超过一的树T中，至少有两个度为1的顶点
41、Prufer算法：
本算法为一棵具有n个有标记的顶点的树构造一个数的序列a1，a2，…，an-2，其中n≥3，且顶点上的标记分别为1，2，…，n
步骤1（初始化）
-
令T是给定的树
-
令k = k + 1
步骤2（选择ak）
while T的顶点多于两个
步骤2.1（寻找一个度为1的顶点）
从T中找出顶点X，其度为1且具有最小的标记
步骤2.2（构造一棵新的树）
-
找出X上的边e，令W表示e的另一个顶点
-
置ak为W上的标记
-
从T中删去边e和顶点X，形成一棵新的树Tʹ
步骤2.3（改变T和k）
-
令T = Tʹ
-
令k = k + 1
endwhile
42、可以如下从n-2个数的序列L构造出一棵树，序列L中的数来自N = {1, 2, …, n}（假定树中顶点标记为1，2，…，n）。
从N中选出不在L中的最小的数k，在这个数和序列L中的第一个数之间构造一条边。
然后从L中删去第一个数，从N中山区k，并重复这个过程。
当L中的数被用完时，构造一条边连接N中剩下的两个数。
43、Prufer算法在有n个标记为1，2，…，n的顶点的树和产生的序列之间建立了一个一一对应。
44、（续43）具有顶点1，2，…，n（n>1）的不同的树有nn-2棵
45、一个图可能会有多棵生成树
46、BFS构造出的生成树称为最短通路树（shortest path tree）
47、Prim算法用来构造一棵最小生成树（minimum spanning tree）：每次选择离已得到的树最近的顶点加入树中并相应地连一条边
48、Kruskal算法每次选择一条权最小的边，如果不构成回路则加入树中，最终也得到一棵最小生成树
49、Prim与Kruskal同样都可以求解最大生成树（maximum spanning tree），只需把“最小”改为“最大”即可
50、DFS构造出的树T称为深度优先搜索树（depth-first search tree）。DFS的阶至多是n2的。
51、（续50）T中的边称为树边（tree edge），其他边称为后向边（back edge）。对顶点所作的标记称为深度优先搜索编码。
52、根树（rooted tree）是一个有向图T，它满足两个条件：
一是当忽略T中的边的方向时，所得到的无向图是一棵树；
二是存在一个惟一的顶点R，R的入度为零，其他任何顶点的入度都为一。顶点R称为根树的根（root）。
53、画根树时将遵循如下惯例：根画在顶端，并省略有向边上的箭头，把边的方向理解为都是向下的。
54、Catalan数：有n个顶点的二叉树的数目是(2n)! / [n! (n+1)!]
55、Fibonacci Tree：T1、T2都只有一个顶点；对于n≥3，Tn是一棵树，其根的左子树是Tn-1，右子树是Tn-2。
56、【练习】（续55）给出Tn的顶点数的公式并证明
57、David A. Huffman最优二叉树（optimal binary tree）算法：每次选标记最小的两个根合并成一棵新的树，新树根的标记为这两个根标记之和
58、（续57）可利用此算法找到合并多个有序列表的最优模式，顶点的权是对应的列表的项数
59、一个列表的二叉搜索树是一棵这样的二叉树：二叉树的每个顶点都被列表的一个元素标记，使得：
（1）没有两个顶点有相同的标记
（2）如果顶点U属于顶点V的左子树，那么U≤V
（3）如果顶点W属于顶点V的右子树，那么V≥W
60、S1，S2，…，Sn的一个相异代表系（system of distinct representatives）是指这样的一个序列：x1，x2，…，xn，其中，xi∈Si（i = 1, 2, …, n），并且各个元素xi都互不相同
61、霍尔定理（Phillip Hall）：有限集合序列S1，S2，…，Sn有相异代表系当且仅当对{1, 2, …, n}的任意子集I，Si（i∈I）的并集所包含的元素至少与集合I所包含的元素个数相同
62、61中所述条件称为霍尔条件（Hall’s condition）
63、【练习】对于r≤n，r×n的拉丁矩形（Latin rectangle）是这样的r×n的矩阵：这个矩阵的元素是数1，2，…，n中的数，而且任何一行或一列中都不会有一个数出现多次。
一个n×n的拉丁矩形称为一个拉丁方（Latin square）。证明：如果r<n，那么一定可以附加n-r行到一个r×n的拉丁矩形，以形成一个拉丁方。（提示：应用霍尔定理）
64、偶图（二分图）：bipartite
65、图的一个匹配（matching）是这样的一个边的集合M，图中没有一个顶点与M中的多条边关联。
66、偶图的0-1矩阵；矩阵的一排（line）是指矩阵的一行或一列。
67、设A是一个矩阵，如果其中没有两个元素在同一排上，则称A的元素的集合是独立的（independent）。
68、A中1的独立集是1的最大独立集（maximum independent set），如果A中没有包含更多1的1的独立集。
69、在偶图中寻找一个最大匹配与在一个0-1矩阵中寻找一个1的最大独立集是等价的。
70、图的一个覆盖（covering）C是指一个顶点的集合，它使每条边至少与C中的一个顶点关联。
71、称C是一个最小覆盖（minimum covering），如果没有包含顶点更少的该图的覆盖。
72、定理：设一个图有一个匹配M和一个覆盖C，那么|M|≤|C|。此外，如果|M|=|C|，那么M是一个最大匹配，C是一个最小覆盖。
73、Dénes König（1931）：在0-1矩阵中，1的最大独立集和最小覆盖包含相同个数的元素。等价地，在偶图中，最大匹配和最小覆盖包含相同个数的元素。
74、（书中关于匹配算法和网络流的内容讲述不清错误连篇所以没有作笔记，以后会单独写相关内容，敬请关注）
75、Pascal’s triangle；西方称为帕斯卡三角形，国内原称杨辉三角形，现多称为贾宪三角形。
76、C(n, r) = C(n-1, r-1) + C(n-1, r)
77、r C(n, r) = n C(n-1, r-1)
78、C(k, 0) + C(k+1, 1) + … + C(k+r, r) = C(k+r+1, r)
79、曲棍球棒公式：C(r, r) + C(r+1, r) + … + C(n, r) = C(n+1, r+1)
80、p为素数，r为整数，1≤r≤p-1，则C(p, r)可以被p整除
81、C(n, m)×C(m, k) = C(n, k)×C(n-k, m-k) (k≤m≤n)
82、有r个对象要选择，每个对象有n种选择方式：
|
条件 |
排列（有序列表）数 |
组合（无序列表）数 |
|
不允许重复 |
P(n, r) |
C(n, r) |
|
允许重复 |
nr |
C(n+r-1, r) |
83、容斥原理：对任意有限集合A1，A2，…，Ar，对1sr，定义ns如下：
从A1，A2，…，Ar中不重复地选择s个集合并计算其交集的大小，对所有可能的选择，定义ns为这些值的和，那么
|A1∪A2∪…∪Ar| = n1 – n2 + n3 – n4 + … + (-1)r-1 nr
84、第二类Stirling数：把n个不同的球放到m个相同的盒中，没有空盒的放法总数记为S2(n, m)
85、S2(n+1, m) = S2(n, m-1) + m×S2(n, m)
86、对于大正整数n有Stirling近似公式：n!～(n/е)n (2πn)1/2
87、错排数递推式：Dn = (n-1) (Dn-2 + Dn-1)，n≥3，D1 = 0，D2 = 1
88、Eugene Charles Catalan (1814 – 1894)
89、在表达式x1x2…xn+1中插入n对圆括号，以把各因子组合成n对数的乘积，插入这n对括号的方法数是Cn，称作Catalan数。
90、（续89）另一种表述基于栈的排列生成。
91、离散动态系统（discrete dynamical systems）是微分方程的离散替代物，微分方程用于研究连续时间框架下的变化。
92、一阶常系数线性差分方程（first-order linear difference equation with constant coefficients）：
初始值为S0的一阶常系数线性差分方程Sn = a Sn-1 + b的通项满足：
Sn = an (S0 + c) – c （当a ≠ 1）
或
Sn = S0 + n b （当a = 1）
其中
c = b / (a – 1)
93、考虑二阶常系数线性齐次差分方程（second-order homogeneous linear difference equation with constant coefficients）：
Sn = a Sn-1 + b Sn-2 (n≥2)
初值为S0和S1。设r1和r2表示方程x2 = a x + b的根，那么，
（1）如果r1 ≠ r2，则存在常数c1和c2，使Sn = c1 r1n + c2 r2n，n = 0, 1, 2, …
（2）如果r1 = r2 = r，则存在常数c1和c2，使Sn = (c1 + n c2) rn，n = 0, 1, 2, …
方程x2 = a x + b称为递推关系Sn = a Sn-1 + b Sn-2的辅助方程（auxiliary equation）。
94、从信息论的观点说明比较排序算法的效率（一个关于下界的说明）：
在任何比较排序算法中都要比较各对元素，有些比较不会提供新的信息（如已知a1≤a2和a2≤a3那么比较a1和a3是没有意义的）。
但不管怎样进行k次比较，可能得到的信息至多有2k种不同的模式。
结论是：通过k次比较，最多能区分2k种不同的顺序。
如果要对列表排序，就必须获得足够的信息，以从其元素n!种可能的不同排列序列中辨别出该列表来。
因此，要对该列表排序，至少要做k次比较，这里，2k≥n!。可以证明n!≥nn/2，于是，
2k≥nn/2
log2(2k)≥log2(nn/2)
k≥(n/2) log2n
由此，任何比较排序算法的复杂性都至少是c n log2n，其中，c为常数。
95、一般地考虑一个无限数列a0，a1，a2，…
其中，对某个整数n，有an+1 = an+2 = … = 0
我们称多项式a0 + a1 x + a2 x2 + a3 x3 + … + an xn是该序列的生成函数（generating function）
96、形如a0 + a1 x + a2 x2 + a3 x3 + …的表达式称为形式幂级数（formal power series）
其中，允许无限多个系数ar不为零。
97、假设G = a0 + a1 x + a2 x2 + a3 x3 + …，这里a0 ≠ 0。则存在惟一的生成函数H，使得G H = 1。
98、卢卡斯序列（Lucas sequence）：Ln = p（n = 1）或Ln = q（n = 2）Ln = Ln-1 + Ln-2（n ≥ 3）。
99、（关于逻辑电路和状态机的内容讲得很烂所以略过，以后有机会给大家写一篇好的~）
100、Collatz序列：根据正整数n是偶数还是奇数，分别用n/2或3n+1替换它，并重复这个过程。
人们猜测但尚未证明：无论从哪个整数n开始，最终都将到达1。
（本文完；未经许可，不得转载）