离散考前预习

我想及格啊╥﹏╥

一、命题逻辑

1-1 命题逻辑及其表示法

只有确定真值的陈述句才是命题。

1-2 联结词

真值的确定方法：
合取：$\land$ ，同真则真。
析取：$\lor$ ，同假则假。
条件：$\rarr$，前真后假则假。
双条件：$\leftrightarrow$，同真异假。

1-3 命题公式与翻译

略

1-4 真值表与等价公式

枚举所有情况，通过运算，即可得到所需式子的真值。

命题定律：

满足结合律，交换律，吸收率。
德摩根率：$\neg(P \lor Q)\iff \neg P \land \neg Q$
$\neg (P \land Q) \iff \neg P \lor \neg Q$

1-5 重言式与蕴含式

重言式：永真式。
矛盾式：永假式。

定理

$A\iff B$ 当且仅当$A \leftrightarrow B$为重言式。
当且仅当$P\to Q$是一个永真式时，我们称$P$蕴含$Q$，记作$P\Rarr Q$。

1-6 其他联结词

应该不考

1-7 对偶与范式

对偶：式子中$\land$与$\lor$相互取代，$T$与$F$相互取代。

合取范式

具有如下型式：
$A_1\land A_2\land .....\land A_n(n>=1)$

析取范式

具有如下型式：
$A_1\lor A_2\lor .....\lor A_n(n>=1)$

求一个命题公式的合取范式或者析取范式

将其他联结词化为$\land$，$\lor$，$\neg$，运算。

求主析取范式与主合取范式

真值表中该式子为真的所有命题变元合取的析取为主析取范式。
真值表中该式子为假的所有命题变元取反后析取的合取为主合取范式。
例如：

所有$(P\land Q)\lor (\neg P \land R)$为$T$的命题变元为
1、$P,Q,R$
2、$P,Q,\neg R$
3、$\neg P,Q,R$
4、$\neg P,\neg Q,R$
则$(P\land Q)\lor (\neg P \land R)$的主析取范式为$(P\land Q\land R ) \lor (P\land Q \land \neg R)\lor(\neg P \land Q \land R)\lor (\neg P \land \neg Q \land R)$。
所有$(P\land Q)\lor (\neg P \land R)$为$F$的命题变元为
1、$P,\neg Q , R$
2、$P, \neg Q, \neg R$
3、$\neg P, Q , \neg R$
4、$\neg P,\neg Q,\neg R$
则$(P\land Q)\lor (\neg P \land R)$的主合取范式为$(\neg P\lor Q\lor\neg R ) \land (\neg P\lor Q \lor R)\land( P \lor \neg Q \lor R)\land (P \lor Q \lor R)$。
注意主合取范式要取反。

1-8 推理理论

1、$P\to Q\iff\neg P\lor Q$
2、$\neg(P\to Q)\iff P\land \neg Q$
3、$P\to Q\iff\neg Q\to \neg P$
4、$P\to (Q \to R)\iff (P \land Q)\to R$
5、 $P\leftrightarrow Q \iff (P \to Q)\land(Q \to P)$

三、集合与关系

3-1 集合的概念和表示法

幂集

给定集合$A$，由集合$A$的所有子集为元素组成的集合，称为集合$A$的幂集，记作$\Phi(A)$。

如果$A$有$n$个元素，其幂集有$2^n$个元素。

证明：对于集合中的每个，有选与不选两种选法，由乘法原理，得幂集中元素个数为$2*2*2...*2(n个2)$。

那么在写幂集所有元素时，可根据此证明来写。

幂集的嵌套

例：$\Phi(\Phi(\varnothing))$

设$A=\Phi(\varnothing)$，对于$\Phi(A)$，有$\Phi(A)=\{\varnothing,\{\ A\}\}$；对于$A$，有$A=\Phi(\varnothing)=\{\varnothing\}$，则有$\Phi(\Phi(\varnothing)) =\Phi(A)=\{\varnothing,\{\varnothing\}\}$。

3-2 集合的运算

集合的补

设$A,B$为任意两个集合，所有属于$A$而不属于$B$的元素组成的集合$S$称为$B$对于$A$的补集，或相对补，记作$A-B$。

设$E$为全集，则$E-A$为$A$的绝对补，记作~$A$（补集）。

性质

显然

~（ ~A）= A。

~$E= \varnothing$。

~$\varnothing=E$。

$A\cap$~$A= \varnothing$。

$A \cup$~$A=E$。

~$(A\cup B) =$~$A \cap$~$B$。

~$(A\cap B) =$~$A \cup$~$B$。

定理

不知道考不考，先抄上

$A-B=A \cap$~$B$。

$A-B=A-(A \cap B)$。

$A \cap (B-C)=(A \cap B)-(A \cap C)$。

集合的对称差

设$A$和$B$的对称差为$S$，$S$中的元素属于$AorB$，且不能即属于$A$又属于$B$。

性质

不写了，我赌他不考

3-3 包含排斥原理

容斥原理居然不学，这河里吗

3-4 序偶与笛卡尔积

序偶

确定次序的两个元素的集合，可推展为$n$元组（套娃）

直接看作pair（bushi

笛卡尔积

序偶的运算

长这样

定理

证明

我赌他不考

3-5 关系及其表示

二元关系

任一序偶的集合，确定了一个二元关系$R$。

若有$<x,y>$在$R$中，记作$<x,y> \in R$或$xRy$。

X到Y的关系

$X×Y$的任何字集，都定义一种关系$R$，称作$X$到$Y$的关系。

空关系与全域关系

其中$X×Y$的子集$\varnothing$为空关系；
$X×Y$的子集$X×Y$为全域关系

恒等关系

设$I_X$是$X$上的恒等关系，则$I_X内的元素均为<x,x>$。
例：
$A=\{1,2,3\}$，那么其恒等关系$I_A=\{<1,1>,<2,2>,<3,3>\}$

例：

$n$个元素的集合上，可以定义$2^{n^2}$种关系。

前域、值域

若有$<x,y>\in R$，则所有$x$组成的集合称为前域（定义域），所有$y$组成的集合称为值域。

相关定理不抄了，我赌他不考

关系的表示

关系矩阵（邻接矩阵）

关系图（有向图）

根据图画矩阵或者根据矩阵画图。

3-6 关系的性质

自反性

对于集合$X$中的所有元素x，都存在$<x,x>$。

在关系矩阵中，表现为对角线上所有元素都为1；在关系图中，表现为每个结点都有自回路。

例题：

反自反性

对于集合$X$中的所有元素x，都不存在$<x,x>$。

在关系矩阵中，表现为对角线上所有元素都为0；在关系图中，表现为每个结点都没有自回路。

例题：

对称性

在关系矩阵中，关于主对角线对称；在关系图中，若两结点有边，必是往返两条。

反对称性

在关系矩阵中，关于主对角线对称的元素不能同时为1（可以同时为0）；在关系图中，若两结点有边，只有一条单向边。

传递性

如果$x,y,z\in X$，且$<x,y>\in R,<y,z>\in R$，那么有$<x,z>\in R$。
在关系矩阵中，如果$M[i,j]=1$且$M[j,k]=1$，则$M[i,k]=1$。

在关…关系图被我吃了

直接两重循环枚举所有情况，这样不会漏。

例题：

3-7 复合关系和逆关系

复合关系

设$R$是$X$到$Y$的关系，$S$是 从$Y$到$Z$的关系，则$R\circ S$称为$R$和$S$的复合关系。表示为$R\circ S=\{x \in X\land z \in Z \land (\exists y)(y \in Y \land <x,y> \in R \land <y,z> \in S)\}$
显然$R\circ S$是$X$到$Z$的关系。
合成运算是对关系的二元运算，它能够由两个关系生成一个新的关系。

例题：

已知$X=\{1,2,3,4\},Y=\{2,3,4\},Z=\{1,2,3\}$。
$R=\{<x,y> \mid x\in X \land y \in Y \land x + y=6\}$；
$S=\{<y,z> \mid y\in Y \land z \in Z \land y -z = 1\}$。
求$R \circ S, S \circ R$。
先写出$R$和$S$。
$R=\{<2,4>,<3,3>,<4,1>\}$,$S=\{<2,1>,<3,2>,<4,3>\}$。
$R\circ S$中的元素，即在$R$中如果有$<x,y>$，在$S$中如果有$<y,z>$，那么$R \circ S$就是元素$<x,z>$的集合。
$S\circ R$同理。注意顺序关系。
$R\circ S=\{<2,3>,<3,2>,<4,2>\}$。
$S\circ R=\{<3,4>,<4,3>\}$。

定理1：

$(R_1\circ R_2)\circ R_3=R_1\circ (R_2\circ R_3)$

关系的幂运算

自己与自己运算。

定理

对于有穷集$A$和$A$上的关系$R$，$R$的不同次幂只有有限个。

矩阵运算不学了

逆关系

设$R$为$X$到$Y$的二元关系，如将$R$中每一序偶的元素顺序互换，所得的集合称为$R$的逆关系，记作$R^c$。
如有$R=\{<1,a>,<2,b>,<3,c>\}$,那么$R_c=\{<a,1>,<b,2>,<c,3>\}$

定理

1、$(R_1 \cup R_2)^c=R_1^c \cup R_2^c$
2、$(R_1 \cap R_2)^c=R_1^c\cap R_2^c$
3、$(A×B)^c=B×A$
4、$(R_1-R_2)^c=R_1^c-R_2^c$
5、$(T\circ S)^c=S^c \circ T^c$
6、设$R$为$X$上的二元关系，则
$a)R$是对称的，当且仅当$R=R^c$。
$b)R$是反对称的，当且仅当$R \cap R^c \subseteq I_X$。
7、$(\bar{R})^c=\bar{R^c}$，其中$\bar{R}=A×B-R$。

例题

$\bar{R}$是属于$A×A$但不属于$R$的。

3-8 关系的闭包运算

闭包

$R$的自反，对称，传递闭包，记作$r(R),s(R),t(R)$。

定理

设$R$是$X$上的二元关系，那么
$a)R$是自反的，当且仅当$r(R)=R$。
$b)R$是对称的，当且仅当$s(R)=R$。
$c)R$是传递的，当且仅当$t(R)=R$。

闭包的求法

自反闭包的求法

$r(R)=R \cup I_X$。

对称闭包的求法

$s(R)=R\cup R^c$。

传递闭包的求法

Warshall算法

矩阵运算

三重循环

对于每一列i，遍历所有行，如果当前行$A[j,i]$为1，对当前行所有元素与第$i$行进行逻辑加。

//对每一列
for(int i = 1; i <= n; i++ ){
	//遍历每一行
	for(int j = 1; j <= n; j ++ ) if (A[j,i] == 1) {
		for (int k = 1; k <= n; k ++ )
		A[j,k] = A[j,k] 逻辑加 A[i,k];//逻辑加:有1则1
	}
}

例题

设$A=\{a,b,c,d\}$，给定$A$上的关系$R$为$R=\{<a,b>,<b,a>,<b,c>,<c,d>\}$，求$t(R)$。
得关系矩阵$M_R$如下：

$$\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0&1&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$$

按照$Warshall$算法的步骤来求解：

首先看第一列，此时$i=1$：
扫描第1列的每一行，其中$M[2,1]$为1，那么第$i(1)$行与第$j(2)$行进行逻辑加运算，结果赋到第$j$行，得：

$$\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 1&1&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$$

第一列扫描完成，扫描第二列，此时$i=2$：
扫描第二列的每一行，其中$M[1,2],M[2,2]$为1。
第$i(2)$行与$j(1)$行进行逻辑加操作，结果赋到第$j$行，得：

$$\begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1&1&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$$

第$i(2)$行与第$j(2)$行进行逻辑加操作，$M_R$不变。
第二列扫描完成，扫描第三列，此时$i=3$：
扫描第三列的每一行，其中$M[1,3],M[2,3]$为1.
第$i(3)$行与第$j(1)$进行逻辑加操作，结果赋到第$j$行，得：

$$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1&1&0\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$$

第$i(3)$行与第$j(2)$进行逻辑加操作，结果赋到第$j$行，得：

$$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$$

第三列扫描完成，扫描第四列，此时$i=4$:
扫描第四列的每一行，其中$M[1,4],M[2,4],M[3,4],M[4,4]$为1，
第$i(4)$行与第$j(1,2,3,4)$行进行逻辑加操作，结果赋到第$j$行，第四行全为$0$，$M_R$不变。
$t(R)$的最终结果为：

$$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1&1&1\\ 0&0&0&1\\ 0&0&0&0 \end{bmatrix}$$

3-9 集合的划分与覆盖

划分与覆盖

设有：$A=\{1,2,3\}$。

覆盖：集合的所有元素等于$A$。

划分：集合的所有元素等于$A$，但子集相交为空集。

最大划分与最小划分

交叉划分

定义：若$A=\{ A_1,A_2... A_m\}$与$B=\{B_1,B_2,...B_m\}$都是集合$X$的划分，则其中所有的$A_i\cap B_i$组成的集合$C$，则$C$是$A$与$B$两种划分的交叉划分。

$A$和$B$为同一集合$X$的两种不同划分。

例如：$X$表示所有学生。

$A=\{男生，女生\}$，$B=\{山东籍学生，非山东籍学生\}$

$C=\{山东籍男生，山东籍女生，非山东籍男生，非山东籍女生\}$

交叉划分中所有元素的并为 $X$。

交叉划分是原来各划分的加细。(字面意思)

4个元素的集合有15种不同的划分。

3-10等价关系与等价类

等价关系

在集合上满足自反，传递，对称。

完全关系（全域关系）：集合$A$上的完全关系是$A×A$。

等价类

定义：

$R$是$A$上的等价关系，$a\in A$，由$a$确定的集合$[a]_R:$

$[a]_R = \{x\mid x\in A\land<a,x>\in R\}$

则 $x \in[a]_R\iff<a,x>\in R$

例：$A = \{1,2,3,4,5,6,7\}$，$R$是$A$上的模3同余关系。

$[1]_R = \{1,4,7\} = [4]_R = [7]_R$ 余数为1的等价类。

$[2]_R = \{2,5\} = [5]_R$，余数为2的等价类。

$[3]_R = \{3,6\} = [6]_R$，余数为0的等价类。

等价类性质

1、$R$是$A$上等价关系，任意$a \in A$，若$x,y \in [a]_R$,必有$<x,y> \in R$。

2、$a,b \in A$，$[a]_R \cap [b]_R =\varnothing$，当且仅当$<a,b>!\in R$

3、若$aRb$，即$<a,b> \in R$ ，则$[a]_R =[b]_R$。

4、$R$的所有等价类构成的集合是$A$的一个划分。

这个划分即商集。

由等价关系图求等价类

独立子图个数 等于 不同的等价类个数

等价关系R1有三个独立子图，即有三个等价类。

R2有两个独立子图，即有两个等价类。

商集

定义： $R$的所有等价类构成的集合称之为$A$关于$R$的商集。记作$A/R$。即$A/R=\{[a]_R\mid a \in A\}$。

集合$A$上的一个等价关系$R$，决定了$A$的一个划分，该划分就是商集$A/R$

秩

商集中的元素个数（即等价类个数）称为等价关系R的秩。

求出所有的等价关系

所有划分并上$I$。

3-11 相容关系

不作要求

3-12 序关系

偏序关系和偏序集

设$R$为定义在集合$A$上的一个关系，若$R$是：
$a)$自反的
$b)$反对称的
$c)$传递性
则$R$称为偏序关系，记为$≼$。序偶$<A,≼>$称作偏序集。

例题

验证偏序关系：
可以用关系图或者关系矩阵：

y盖住x

$COV A=\{<x,y>\mid x,y\in A;y盖住x\}$。

哈斯图

如果$y$盖住$x$那么在哈斯图中，$y$在$x$上面。

正整数$m=12$的因子的整除关系的哈斯图：

哈斯图的一种简单画法

不难发现，哈斯图的画法麻烦在于确定层次，只要确定了层次，就能根据盖住关系连上线。

第一步：找出元素集合值域中没出现的放在顶层。
第二步：去掉顶层中所有元素前域的所有关系。

举例：

$<\{2,3,6,12,24,36\},整除>$,画出哈斯图。
下面列举出所有步骤：
当前所有关系为$<2,6>,<2,12>,<2,24>,<2,36>,<6,12>,<6,24><6,36>,<3,6>,<3,12>,<3,24>,<3,36>,<12,24>,<12,36>$。
值域中没出现的元素为$2,3$。
我们把$2,3$放在顶层，并删去所有以$2,3$为前域的所有关系。
此时哈斯图为

剩余关系为：
$<6,12>,<6,24><6,36>,<12,24>,<12,36>$
此时值域为$12,24,36$，其中$6$是没出现过的。
把6放在顶层，此时哈斯图为：

删去顶层元素$6$为前域的所有关系，此时剩余关系为：
$<12,24>,<12,36>$
当前值域为$24,36$，其中$12$是没有出现过的。
把$12$放在顶层，此时哈斯图为：

删去顶层元素$12$为前域的所有关系，此时剩余关系为（这时候不用删了，直接放最顶层）。
得到哈斯图：

哈斯图是简化的关系图
（1）自反性：每个顶点都有自回路，省去自回路。
（2）反对称性：从小到大安置顶点，可省略箭头。
（3）传递性：如果有$(a,c),(b,c),(a,c)$，只画$(a,b),(b,c)$，省略$(a,c)$。

链（反链）

在偏序集$<A,≼>$的一个子集中，如果每两个元素都是有关系的，则这个子集为链；
如果每两个元素都是无关的，称这个子集为反链。

全序关系（线序关系）

如果是一个链，则为全序关系（线序关系）。

极大元（极小元）

$<A,≼>$是一个偏序集合，$B$是$A$的子集，存在元素$b$，x≼$B$中所有元素，则称$b$是$B$的极大元。

理解：

$a)$极大元必须来自集合$B$。
$b)$极大元不必与集合中所有元素都有关系。
$c)$哈斯图中，$B$的元素没有比极大元更靠上的。

重点是不必与所有元素都有关系。
极小元同理。

最大元（最小元）

理解：

$a)$最大元必须来自集合$B$。
$b)$最大元必须与集合中所有元素都有关系。
$c)$哈斯图中，$B$的元素没有比极大元更靠上的。

最大元和最小元不一定存在，但如果存在，那么肯定是唯一的。

上界（下界）

上界：与最大元定义类似，不同的是不限制在$B$中，而是在$A$中。

理解：

$a)$不一定要来自集合B
$b)$上界要和$B$中所有元素可比。
$c)$上界在哈斯图中比$B$中所有元素都靠上。
下界同理。

上确界（下确界）

上确界是最小的的上界，下确界是最大的下界。
上确界（下确界）有且只有一个。
上确界是上界中的最小元，下确界同理。

找上下（确）界的方法

通过定义不难发现，只要找到与$B$中所有元素有关系的元素，就能解决问题。那么问题就转化为从$A$中找出与$B$中所有元素都有关系的元素。
找最大元同样需要判断是否都有关系。
在哈斯图中，如果两个结点之间连通，并且是逐级递增（递减），即不能回溯，那么这两个元素就有关系。
下面举例说明：

在上图中，我们称$a,j$是有关系的，一条可行的路线是$a,c,f,h,j$、
而$a,b$是没有关系的，因为如果要到达，只能$a,c,f,b$，但是在这个过程中出现了回溯$f->b$，所以$a,b$是没有关系的。

例题：

对于$B$：在全局中查找与$B$有关系的，分别是$h,i,j,k$，显然他们都是上界，无上确界，因为没有最小元。
对于$B'$：全局查找与$B'$有关系的，分别是$a,b,c,d,e,f,g$，显然他们都是下界，无下确界，因为没有最大元。
对于$B''$：有关系的是$k,a$，其中$k$是上界，同时也是上确界；$a$是下界，同时也是下确界。

练习题：

良序

任一偏序集合，假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。

定理：

每一个良序集合，一定是全序集合。
每一个有限的全序集合，一定是良序集合。
良序集合是全序集合的子集。

五、代数系统

5-1 代数系统的引入

n元运算

集合上n个元素的运算。
对于集合$A$，一个从$A^n$到$B$的映射，称为集合$A$上的一个$n$元运算，若$B\subseteq A$则称该$n$元有运算是封闭的。

代数系统

一个非空集合$A$连同若干个定义在该集合上的运算$f_1,f_2....f_k$所组成的系统就称为一个代数系统，记作$<A,f_1,f_2...f_k>$。
例如整数集合上的加法运算和乘法运算组成的代数系统：$<I,+,*>$。

5-2 运算及其性质

*对$\Delta$可分配

设$*$和$\Delta$是定义在集合$A$上的两个二元运算，如果对于任意的$x,y,z\in A$，都有
$x*(y\Delta z)=(x*y)\Delta (x*z)$；
$(y \Delta z)*x=(y*z)\Delta (z*x)$，那么称运算$*$对于$\Delta$是可分配的。
$*$对于$\Delta$可分配不代表$\Delta$对于$*$是可分配的。

幺元

任何元素与它运算都为这个元素本身。
设集合中有元素$x$，$*$是集合上的一个二元 运算，若有$e_l*x=x$，则称$e_l$为集合中关于运算$*$的左幺元；若有$x*e_r=x$，则称$e_R$为集合中关于运算$*$的右幺元。如果一个元素$e$既是左幺元又是右幺元，则称$e$为集合中关于运算$*$的幺元。

定理

设$*$是定义在集合上$A$的一个二元运算，且在$A$中有关于运算$*$的左幺元$e_l$和右幺元$e_r$，则$e_l=e_r=e$，且幺元唯一。

零元

类似幺元。
不同处在于任何元素与它运算都等与零元。
零元是唯一的

逆元

设集合$A$上存在二元运算为$*$，幺元为$e$。如果对于$A$中的一个元素$a$存在着$A$中的某个元素$b$，使得$b*a=e$，那么称$b$为$a$的左逆元；如果$a*b=e$，那么称$b$为$a$的右逆元。如果$b$既是$a$的左逆元与右逆元，那么$b$就是$a$的一个逆元。
如果$a$是$b$的逆元，那么$b$也是$a$的逆元，即$a$与$b$互为逆元。元素$x$的逆元记作$x^{-1}$。
每个元素的逆元是唯一的。

5-3 半群

广群

封闭

半群

封闭
可结合

定理

$<S,*>$是一个半群，$B\subseteq S$且$*$在$S$上是封闭的，那么$<B,*>$也是一个半群。

定理

设$<S,*>$是一个半群，如果$S$是一个有限集，则必有$a\in S$，使得$a*a=a$。

独异点

含有幺元的半群称为独异点。

定理

设$<S,*>$是一个独异点，则在关于运算$*$的运算表里任何两行或两列都是不相同的。

定理

设$<S,*>$是独异点，对于任意$a,b\in S$，且$a,b$均有逆元，则
$1) (a^{-1})^{-1}=a$
$2)a*b$有逆元，且$(a*b)^{-1}=b^{-1}*a^{-1}$。

5-4 群与子群

群

1、封闭
2、可结合的
3、存在幺元
4、每个元素都有逆元

阶数、有限群、无限群

设$<G,*>$是 一个群，如果$G$是有限集，那么$<G,*>$为有限群，$G$中元素个数称为该有限集的阶数，记作$\mid G\mid$，如果$G$是无限集，那么$<G,*>$为无限群。

群之间的关系

群$\subset$独异点$\subset$半群$\subset$广群。

群：

1、封闭
2、可结合
3、有幺元
4、每个元素有逆元

独异点

1、封闭
2、可结合
3、有幺元

半群

1、封闭
2、可结合

广群

封闭

定理

群中不可能有零元。

定理

设$<G,*>$是一个群，对于$a,b\in G$，必存在唯一的$x \in G$，使得$a*x=b$。

定理（消去律）

$a*b=a*c$，则$b=c$。

置换

从集合$S$到$S$的一个双射称为$S$的一个置换。

定理

运算表中的每一行或者每一列都是$G$的一个置换。

定理

在群$<A,*>$中，除幺元外，不可能有别的等幂元。

子群与平凡子群

子群

群$<G,*>$，$S$是$G$的非空子集，如果$<S,*>$也构成群，则称$<S,*>$是$<G,*>$的子群。

平凡子群

子群的基础上，如果$S=\{e\}$或者$S=G$，则是平凡子群。

定理

设有群$<G,*>$，该群的幺元必定是其子群的幺元。

定理

$<G,*>$是一个群，$B$是$G$的非空子集，如果$B$是一个有限集，只要$*$在$B$上封闭，那么$<B,*>$必定是$<G,*>$的子群。

5-5 阿贝尔群和循环群

阿贝尔群

可交换

群是阿贝尔群的充要条件

对任意的$a,b\in G$，有$(a*b)*(a*b)=(a*a)*(b*b)$

循环群

群中任意元素都由$a$的幂组成，该群为循环群，$a$称为生成元。

定理

循环群必定是阿贝尔群。
证明：幂运算满足可交换性。

定理

对于有限循环群：
设$<G,*>$由$a$生成，阶数是$n$,即$\mid G\mid=n$，则$a^n=e$，且$G=\{a,a^2,a^3,,,a^n=e\}$,$e$是幺元，$n$是使$a^n=e$的最小正整数，$n$为元素$a$的阶。
循环群的生成元可以是不唯一的。

5-7 陪集与拉格朗日定理

$A,B$的积、$A$的逆

设$<G,*>$是一个群，$A,B\in G$的幂集且$A,B$不为空集，记
$AB=\{a*b\mid a\in A,b\in B\}$.
$A^{-1}=\{a^{-1} \mid a \in A\}$.

运算查表即可。

陪集

设$<H,*>$是群$<G,*>$的一个子群，$a\in G$，则集合$\{a\}H(H\{a\})$称为由$a$确定的$H$在$G$中的左陪集（右陪集），简称为$H$关于$a$的左陪集（右陪集），记为$aH(Ha)$，$a$称为陪集的代表元素。

解释

左陪集是指的$a$从左边与$H$中的元素作运算得到的集合，右陪集是指$a$从右边与$H$中的元素运算得到的集合。
$aH=\{a*h\mid h\in H\}$;$Ha=\{h*a\mid h\in H\}$.

例：

假设运算为$x*x-y*y$，那么左陪集中$aH$的元素为$a*a-h*h$，右陪集$Ha$中的元素为$h*h-a*a$。

$H$是直线$y=2*x$，其左陪集为$<x_0,y_0>$与其运算，易知陪集$<x_0,y_0>H$是通过点$<x_0,y_0$且平行于$y=2*x$的直线。

考察$<N_6,+_6>$的子群$<H_2,+_6>$,$H_2=\{0,2,4\}$。
求出$H_2$的所有左陪集。
$0H_2=\{0+_60,0+_62,0+_64\}=\{0,2,4\}$;
$1H_2=\{1+_60,1+_62,1+_64\}=\{1,3,5\}$;
$2H_2=\{2+_60,2+_62,2+_64\}=\{2,4,0\}$;
$3H_2=\{3+_60,3+_62,3+_64\}=\{3,5,1\}$;
$4H_2=\{4+_60,4+_62,4+_64\}=\{4,0,2\}$;
$5H_2=\{5+_60,5+_62,5+_64\}=\{5,1,3\}$;
可以发现$0H_2=2H_2=4H_2=\{0,2,4\}$;
$1H_2=3H_2=5H_2=\{1,3,5\}$.

定理：

任意两个左陪集要么相等，要么不相交。
这定理好像没讲？

拉格朗日定理

设$<G,*>$是有限群，$\mid G\mid =n$，$<H,*>$是$<G,*>$的子群，且$\mid H\mid = m$，则$n=k*m。$

推论

任何质数阶的群不可能有非平凡子群。
因为质数因子只有$1$和其本身，如果有非平凡子群，与之矛盾。

5-8 同态与同构

同态

设$<X,*>,<Y,\circ >$是两个代数系统，$*,\circ$都是二元运算，如果存在映射$f: X \to Y$，使得对任何$x_1,x_2\in X$，有$f(x_1*x_2)=f(x_1)\circ f(x_2)$，则称$f$是从$<X,*>$到$<Y,\circ>$的同态映射，简称这两个系统同态，记作$X\sim Y$。并称$<f(X),\circ>$为$<X,*>$的同态像。
$f(X)=\{a\mid a=f(x),x\in X\}\subseteq Y$.即将$X$中的元素映射后的集合属于$Y$。

例：

对于乘法运算，可以通过取对数映射为 加法
$ln(x_1*x_2)=lnx_1+lnx_2$

同态的类型

$f$是从$A$到$B$的一个满射，则称$f$为满同态；

$f$是从$A$到$B$的一个入射，则称$f$为单同态；
$f$是从$A$到$B$的一个双射，则称$f$为同构映射,并称$<A,\Delta>,<B,*>$是同构的，记作$A\cong B$。

5-9 环与域

不学了

七、图论

7-1 图的基本概念

图

有结点，有边。（大雾

有向边、无向边

有方向的边、无方向的边

有向图、无向图、混合图

无向图：每条边都是无向边的图。
有向图：每条边都是有向边的图。
混合图：显然。

邻接和关联

邻接点：有边相连的两个结点。
邻接边：关联于同一结点的两条边。
孤立点：没有边与它相连。
零图：全部是孤立点。
平凡图：仅有一个孤立点的图。
自回路（环）：顾名思义。

度数

结点的度数为其边的数量。
最大度：该图结点中最大度数。
最小图同理。

例图中：最大度为3，最小度为2.

定理：

1、图中度数总和为边数两倍（每条边连接两个结点，对总和贡献为2）。
2、在任何图中，度数为奇数的结点必定是偶数个。

例题

度数总和为$2×12$，剩余结点为$(x-6)$，要使剩余结点尽量少，则剩余结点度数要尽量大，最大为$2$（题目要求），有$2*(x-6)$。

入度、出度

有向图中，从一个结点出发的边，对该结点出度贡献为1；到达一个结点的边，对该结点入度的贡献为1.

多重图、简单图

平行边：连于同一结点的多条边。
多重图：含有平行边的图。

$(a)(b)$都是多重图，有向图中平边边必须同一方向。$(b)$中，$<v_1,v_2>,<v_1,v_2>$为平行边。
不含有平行边和环的图称为简单图。

完全图

每一对结点之间都有边相连。
无向完全图：
$n$个结点中每个结点都与其他$n-1$个结点相连。
有向完全图：
在有向图中每一对结点之间有且只有一对方向相反的有向边。

定理

有$n$个结点的无向完全图有$\frac{1}{2}*n*(n-1)$条边。
证明：组合数。

偶图（二部图）

补图

添加上这个图，能使图$G$变成完全图，这个图称为$G$的补图。

子图

如果$G'$的点集和边集是$G$的子集，那么$G'$是$G$的子图。
如果$G'$包含了$G$的所有结点，则$G'$是$G$的生成子图。

相对补图

$G'=<V',E'>$是$G=<V,E>$的子图，对于另外一个$G''=<V'',E''>$，使得$E''=E-E'$，且$V''$中仅包含$E''$所关联的结点，则称$G''$是$G'$相对于$G$的补图。

同构

充要条件：
结点和边一一对应。
必要条件：
1、结点数目相同
2、边数相等
3、度数相同的结点数目相同

7-2 路与回路

路

。。。

迹

路中所有的边均不相同

通路

路中所有结点均不相同

圈

环

定理

在一个具有$n$个结点的图中，如果从结点$v_j$到结点$v_k$存在一条路，则必存在一条不多于$n-1$条边的路。

无向图的连通性

点连通

两结点存在路，则点联通

连通分支

类似于点连通

连通图

任意两结点都连通的无向图

点割集

设有一个点集$V$，删去这个集合，图变成不连通图，删去这个集合的真子集，不会变成不连通图，这个集合叫做点割集。如果集合中只有一个元素，这个点叫做割点。

边割集

类似点割集。
割边类似割点。

例题

判断是否是点割集

最后一个不是，因为删去其真子集$\{V_4\}$，图变成不连通。

判断是否是边割集

最后一个不是，理由同上例。

连通度

点连通度

在图$G$中为了产生一个不连通图需要删去的结点的最少数目。

边连通度

在图$G$中为了产生一个不连通图需要删去的边的最少数目。

定理

$k(G)<=\lambda(G)<=\delta(G)$
$k(G)$为点连通度
$\lambda(G)$为边连通度
$\delta(G)$为结点最小度

有向图的连通性

单侧连通图

任意两结点，至少有一个结点可达另一个结点的有向图。

强连通图

任意两结点，都互相可达的有向图。

弱连通图

称为无向图后是连通图的有向图。

$(a)$任意两点相互可达，所以是强连通图。
$(b)$任意两点至少有一个结点可以到达另外一个结点，是单侧连通图。
$(c)$在对角线上的两点不连通，但把它看成无向图后可连通，是弱连通图。
如果是强连通图，则必是单侧连通图；如果是单侧连通图，则必是弱连通图。

定理

一个有向图是连通的，当且仅当$G$中有一个回路，它至少包含每个结点一次。

单侧分图

具有单侧连通性质的最大子图，称为单侧分图。

强分图

具有强连通性质的最大子图，称为强分图。

弱分图

具有弱连通性质的最大子图，称为弱分图。

定理

在有向图$G$中，它的每一个结点位于且只位于一个强分图中。
假设位于两个强分图中，则两个强分图$G_1$和$G_2$都有结点$v$，又因为$v$与$G_1$内所有结点都相互可达，$v$与$G_2$内所有结点都相互可达，那么$G_1$和$G_2$就是连通的，与假设矛盾，所以每个结点只能位于一个强分图中。

7-4 欧拉图与汉密尔顿图

欧拉路

给定无孤立结点图$G$，若存在一条路，经过图中每边一次且仅 一次，该路称为欧拉路。如果欧拉路是回路，该欧拉路称为欧拉回路。

欧拉图

存在欧拉回路的图。

欧拉定理

无向图具有一条欧拉路的充要条件：
1、连通
2、奇数度顶点个数是0或者2
如果无奇数度结点，为欧拉图。如果奇数度结点为2，则为半欧拉图（有欧拉通路，无欧拉回路）

一笔画判定问题（欧拉定理的应用）

有欧拉路就能一笔画。

有向图中的欧拉路

通过图中每条边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。

有向图中的欧拉定理

具有欧拉回路的充要条件

1、连通
2、每个结点入度等于出度

具有欧拉路的充要条件

1、连通且只有两个奇数度结点
2、除两个结点外，其他结点入度等于出度
3、这两个结点中，一个结点的入度比其出度大1（欧拉路的结束点），另一个结点入度比出度小1（欧拉路的起始点）。

汉密尔顿路（回路）

经过图中每个结点一次仅一次的通路（回路）。

汉密尔顿图

存在汉密尔顿回路的图。

汉密尔顿图的必要条件

只能用来判断一个图不是汉密尔顿图。
若图$G=<V,E>$具有汉密尔顿回路，则对于结点集$V$的每个非空子集$V_1$均有$W(G-V_1)<=\mid V_1\mid$，其中$W(G-V_1)$是$G-V_1$中连通分支数。

无向图具有汉密尔顿路的充分条件

是否存在汉密尔顿回路无充要的判别准则，下面给出一个无向图具有汉密尔顿路的充分条件。
设$G$是具有$n（n>=3）$个结点的简单图，如果$G$中每一对结点度数之和大于等于$n-1$，则在$G$中存在一条汉密尔顿路。

推论

设$G$是具有$n（n>=3）$个结点的简单图，如果$G$中每一对结点度数之和大于等于$n$，则在$G$中存在一条汉密尔顿回路。

判断是否是汉密尔顿路

如果不满足必要条件，不是汉密尔顿图。
如果满足必要条件且满足充分条件，是汉密尔顿图。
如果满足必要条件但不满足充分条件，不确定，进一步观察。

定理

设$n$阶有向图$D=<V,E>$中，如果所有的有向边都有无向边代替，所得无向图中含生成子图$K_n$，则有向图$D$中存在汉密尔顿通路。$\mid V\mid >=3$的有向完全图为汉密尔顿图。

7-5 平面图

平面图

在一个平面内，边没有交点。

定理

一个有限平面图，面的次数之和等于其边数的两倍。

欧拉公式

设有一个连通的平面图$G$，共有$v$个结点，$e$条边和$r$个面，则欧拉公式$v-e+r=2$成立。

推论

若$v>=3$，则有$e<=3*v-6$。
以上是平面图的必要条件，用于判断某些图不是平面图。

判断是否为平面图

7-6 对偶图与着色

着色问题

结点着色

邻接的结点着不同颜色。

边着色

相邻的边着不同颜色。

面着色

有公共边界的两个面着不同颜色。
边着色和面着色都能转化为结点着色。

7-7 树与生成树

树

连通且无回路的无向图。

树叶

树中度数为1的点。

分支点

度数大于1的点。

森林

一个无回路的无向图，其每个连通分支是树。

定理

任何一棵树中至少有两片树叶。

$G$的生成树

$G$的生成子图是 一棵树

树枝

生成树$T$中的边。

弦

$G$的不在生成树中的边。

定理

连通图中至少有一颗生成树

连通图的秩

$G$是$n$个结点$m$条边的连通图，则$G$的生成树有$n-1$条边。
要确定一生成树必须删除$m-(n-1)$条边。
$m-n+1$称为连通图$G$的秩。

定理

一条回路和一棵生成树的补至少有一条公共边。
反证：
如果没有公共边，则该回路包含在生成树中。这是不可能的，因为生成树中不能包含回路。

定理

一个边割集和任何生成树至少有一条公共边。
反证：
如果没有，则删去这个边割集后，所得子图必然包含该生成树。，
删去边割集后仍是连通图，矛盾。

带权图

边有权值的图

带权生成树

生成树$T$的权

$T$的所有边权的和

最小生成树

所有生成树中，树权最小的生成树。

Kruskal

每次选边权最小的边，选$n-1$条。只要所选边不构成回路即可。

7-8 根数及其应用

有向树、根数、m叉树

有向树

如果一个有向图在不考虑边的方向时是一棵树，那么这个有向图就称为有向树。

根数

有一个结点入度为0，其余点入度均为1的有向树。

根

根数中入度为0的结点。

叶

根数中出度为0的点。

内点（分支点）

出度不为0的点。树的分支点。

结点$V$的层次

从根到该结点的单向通路长度。

m叉树

每个结点的出度小于等于$m$的根树。

完全m叉树

每个结点的出度恰好等于m或0的根树。

正则m叉树

所有树叶层次相同的完全m叉树。

定理

设有完全$m$叉树，其树叶树为$t$。分枝点数为$i$，则$(m-1)i=t-1$。

需要28片叶子，m为4，计算得出分支点数量。

通路长度

结点的通路长度

从树根到此结点的通路的边数。

内部通路长度

分支点的通路长度。

外部通路长度

树叶的通路长度。

定理

若完全二叉树有$n$个分支点，且内部通路长度的总和为$I$，外部通路长度总和为$E$，则$E=I+2*n$。

带权二叉树、最优树

带权二叉树

每片树叶都带权的二叉树

带权二叉树的权

$\omega(T)=\displaystyle\sum_{i=1}^tw_iL(W_i)$。
其中$L(w_i)$为带权$w_i$的树叶的通路长度。

最优树

在所有带权$w_1,w_2,w_3,,,,,w_t$的二叉树中，$w(T)$最小的那棵树。

定理

设$T$为带权$w_1<=w_2<=....<=w_t$的最优树，则：
带权$w_1,w_2$的树叶$v_{w_1},v_{w_2}$是兄弟。
以树叶$v_{w_1},v_{w_2}$为儿子的分枝点，其内部通路长度最长。

定理

设$T$为带权$w_1<=w_2<=....<=w_t$的最优树，若将$w_1,w_2$的树叶为儿子的分枝点改为带权$w_1+w_2$的树叶，得到一棵新树$T’$，则$T'$也是最优树。

最优二叉树的求法

根据上述定理，每次合并两个最小的权，并把这两个最小的作为它的儿子。

前缀码

互不为前缀

定理

任意一棵二叉树都可以产生一个前缀码

定理

任何一个前缀码都对应一棵二叉树

例题

二叉树遍历

前序遍历

根左右的顺序遍历

中序遍历

左根右的顺序遍历

后序遍历

左右根的顺序遍历