集合论

第一课

overview， 离散数学研究的领域：

  1. 集合论， 图论
  2. 代数结构 - 研究各种代数的定律，交换律等等 组合数学-研究排列组合
  3. 数理逻辑-使用数理推理逻辑，

集合论包括： 集合、二元关系、函数、自然数、基数（势）

图论包括： 图、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配/覆盖/独立/匹配、带权图

逻辑演算： 命题逻辑演算，谓词逻辑演算

p q r 代表命题， 为真或者为假

  • $\lnot$ 否

  • $\lor$ 或者

  • $\land$ 并且 合取式

  • $\to$ 蕴含 implies

  • $\leftrightarrow$ 等价

以上存在优先级,从上至下.

  • 可满足
  • 矛盾式 永假
  • 重言式 永假

等值演算

$A \Leftrightarrow B$: $A \leftrightarrow B$ 是永真式

公式之间可以进行演算。

16 组等值演算律

  1. 幂等律 $A \Leftrightarrow A \land A $ , $A \Leftrightarrow A \lor A$ ;
  2. 交换律 $A \land B \Leftrightarrow B \land A, A \lor B \Leftrightarrow B \lor A$;
  3. 结合律 $(A \lor B) \lor C \Leftrightarrow A \lor (B \lor C), (A \land B) \land C \Leftrightarrow A \land (B \land C)$
  4. 分配律
    1. $A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C) $;
    2. $A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)$;
  5. 德摩根定律
    1. $\lnot(A \land B) \Leftrightarrow \lnot A \lor \lnot B$;
    2. $\lnot(A \lor B) \Leftrightarrow \lnot A \land \lnot B$;
  6. 吸收率
    1. $A \land ( A \lor B) \Leftrightarrow A$；
    2. $A \lor (A \land B) \Leftrightarrow A$;
  7. 零律（相当实数的 0）
    1. $A \land 0 \Leftrightarrow 0$;
    2. $A \lor 1 \Leftrightarrow 1$;
  8. 同一律（相当于实数的 1）
    1. $A \land 1 \Leftrightarrow A$;
    2. $A \lor 0 \Leftrightarrow A$;
  9. 排中律 $A \lor \lnot A \Leftrightarrow 1$; 单独提到这个排中律是存在争议的，比如说，“我说的这句话是假的” 这句话本身是真是假？就不符合排中律。
  10. 矛盾律 $A \land \lnot A \Leftrightarrow 0$;

第二课

  1. 双重否定律 $\lnot \lnot A \Leftrightarrow A$;
  2. 蕴含等值 $A \to B \Leftrightarrow \lnot A \lor B$;
  3. 等价等值式$A \leftrightarrow B \Leftrightarrow (A \to B) \land (B \to A)$;
  4. 假言易位 $A \to B \Leftrightarrow \lnot B \to \lnot A$;
  5. 归谬论 $(A \to B) \land (A \to =\lnot B) \Leftrightarrow \lnot A$;（或者说，反证法经常用)

根据上面的等值式， 可以开始进行等值演算。

例子： 证明 $p \to (q \to r)$ 等价 $(p \land q) \to r$;

$\Leftrightarrow p \to (\lnot q \lor r)$;

$\Leftrightarrow \lnot p \lor (\lnot q \lor r)$;

$\Leftrightarrow \lnot p \lor \lnot q \lor r$;

$\Leftrightarrow \lnot(p \land q) \lor r$;

$\Leftrightarrow (p \land q) \to r$;

重要的推理定律 9:00

若 A 和 B 是两个命题，其中 $A \to B$ 是永真式(重言式)， 则 $A \Rightarrow B$，简称 A 推出 B；

上面是等值演算，接下来的部分根据等值演算，来进行推理，以及其中的一些推理定律。

  1. 附加律 $A \Rightarrow A \lor B$ .这个的意思也就是 $A \to (A \lor B)$ 是永真式, 人话就是如果 A 成立，则 A 或 B一定成立;
  2. 化简律 $A \land B \Rightarrow A$. $A \land B \to A$ 如果 A 与 B 成立，则 A 一定成立;
  3. 假言推理 $(A \to B) \land A \Rightarrow B$ .
    1. 因为 A 所以 B，A 成立，所以 B 也成立。
  4. 拒取式 $(A \to B) \land \lnot B \Rightarrow \lnot A$ .
    1. 因为 A 所以 B，B 不成立，所以 A 不成立。
  5. 析取三段论 $(A \lor B) \land \lnot A \Rightarrow B$ .
    1. 要么 A，要么B， A不成立，只有 B 成立
  6. 假言三段论$(A \to B) \land (B \to C) \Rightarrow (A \to C)$ .
  7. 等价三段论$(A \leftrightarrow B) \land (B \leftrightarrow C) \Leftrightarrow A \leftrightarrow C$.
  8. 构造性两难 $(A \to B) \lor (C \to D) \lor (A \lor B) \Rightarrow (C \lor D)$ 自然语言描述：
    1. 如果发展经济 -> 造成污染
    2. 不发展经济 -> 贫穷
    3. 发展经济 v 不发展经济
    4. 只能要么污染要么贫穷

一阶谓词逻辑基本概念与命题符号化

全总个体域: 限定范围内所有的东西

  • 量词：

    • 所有的 $\forall$

    • 存在 $\exists$

  • 辖域

    • 例如，在命题“对于任意 $x\in\mathbb{R}$，存在 $y\in\mathbb{R}$，使得 $y>x$”中，“对于任意 $x\in\mathbb{R}$”是全称量词的辖域，而“存在 $y\in\mathbb{R}$，使得 $y>x$”是存在量词的辖域。

  • 指导变元 guide variable

  • 自由变元 free variable

  • 约束变元 bound variable

例子：

$\forall x(F(x) \to G(x))$ ，对于所有的，$F(x)$ x 是人，那么 $G(x)$—-只要是人,都会死的.

$\exists x(F(x) \land G(x))$ , there exists $F(x)$ x is a person. and $G(x)$ – X is smorking. some people smoke.

$F(x)$: x 是火车, $G(x)$: x 是汽车, $H(x,y)$: x 比 y 快

$\forall x(F(x)\to \forall y(G(y)\to H(x,y)))$ ; 对于所有的是火车的,比所有的是汽车的都要快.

$\exists x(G(x) \land \exists y(F(y) \to H(x,y)))$; 有的汽车比火车要快;

  • 解释 $\forall x(F(x) \to \exists y(G(y) \land H(x,y,z)))$;

    • 在上述的例子当中, 给每一个命题提供一个解释

      • $F(x)$ x 是实数

      • $G(x)$ x 是整数

      • $H(x,y,z) ;x+y = z$.

      • 公式作用域是全总个体域

    • 紧跟着量词的是指导变元(上例中 x,y 都是指导变元)

    • 量词后面紧跟的括号就是这个量词的辖域, 而在括号里面的指导变元就是约束出现.

    • 在指导变元的辖域当中,但是不是指导变元,则称之为自由出现. (z 就是自由出现)

    • 上面的例子可以理解为: 对于所有的实数 x, 存在整数 y,使的 x + y = z

一阶谓词逻辑等值式与基本等值

等值式的定义: $A \Leftrightarrow B$ : $A \leftrightarrow B$ 为用真式, 以下四种情况满足用真式.

  • 有限个体域可以消去量词

    • 如果是有限的个体域,$\forall$ 可以转换为每个个体相与

    • $\exists$ 可以转换为每个个体相或

  • 量词可以进行否定

    • 全称量词的否定：$\neg\forall x, P(x) \Leftrightarrow \exists x, P(x) $ 不是所有的都满足,同时也表示存在某个 $x$，使得 $P(x)$ 不成立。

    • 存在量词的否定： $\neg\exists x, P(x) \Leftrightarrow \forall x, \lnot P(x)$ 不存在满足, 表示所有 $x$ 都不满足 $P(x)$。

第三课

  • 量词管辖域的收缩与扩张

    • $\forall x(A(x) \lor B) \Leftrightarrow \forall x(A(x)) \lor B$;

    • $\forall x(A(x) \land B) \Leftrightarrow \forall x(A(x)) \land B$;

    • $\forall x(A(x) \to B) \Leftrightarrow \exists x A(x) \to B$;

      • 解释一下: 前面的公式是对于任何的 x, 如果 A(x) 为真, 则 B 为真

      • 后面的公式, 存在 x, 使得 A(x)为真, 则 B 为真.

      • 自然语言不太好描述.

      • $\forall x(A(x) \to B)$

      • $\Leftrightarrow \forall x(\lnot A(x)\lor B)$

      • $\Leftrightarrow \forall x \lnot A(x) \lor B$

      • $\Leftrightarrow \lnot\exists xA(x) \lor B$

      • $\Leftrightarrow \exists xA(x) \to B$

  • $\forall x(B \to A(x)) \Leftrightarrow B \to \forall xA(x)$;

  • 量词分配 10:30

    • 分配1 $\forall(A(x)\land B(x)) \Leftrightarrow \forall A(x) \land \forall B(x)$;

    • 分配2 $\exists (A(x) \lor B(x)) \Leftrightarrow \exists A(x) \lor \exists B(x)$;

  • 前束范式：谓词存在量词在最前面, 且作用到公式尾部.下面的例子就是如何重构成一个前束范式.

    • $\forall xF(x) \lor \lnot\exists xG(x,y)$

    • $\Leftrightarrow \forall xF(x) \lor \forall x\lnot G(x,y)$

    • $\Leftrightarrow \forall xF(x) \lor \forall z\lnot G(z,y))$

    • $\Leftrightarrow \forall x(F(x) \lor \forall z\lnot G(z,y))$

    • $\Leftrightarrow \forall x\forall z(F(x) \lor\lnot G(z,y))$

    • $\Leftrightarrow \forall x\forall z(G(z,y) \to F(x))$

  

重要的推理定律：

  1. ”$\forall xA(x) \lor \forall xB(x) \Rightarrow \forall x(A(x) \lor B(x)$”
  2. ”$\exists xA(x)\land B(x) \Rightarrow \exists xA(x) \land \exists B(x)$”
  3. ”$\forall xA(x) \to B(x) \Rightarrow \forall xA(x) \to \forall xB(x)$”
  4. ”$\forall x(A(x) \to B(x)) \Rightarrow \exists xA(x) \to \exists xB(x)$”

集合论 28:50

  1. 集合的概念
  2. 集合之间的关系
  3. 集合的运算
  4. 文氏图，容斥原理

谈到罗素悖论

集合的表示方法有哪些？ 列举法/描述法/特征函数法/文氏图

谈到集合的概念， 集合用来定义数学基础。但是因为如果没有公理定义，则存在悖论。引出罗素悖论。所以谈到公理集合论，和朴素集合论。本课程是朴素集合论。

第四课

集合的简介

  1. 集合是一种描述工具

  2. 集合一种通用的语言

  3. 集合可以进行思维训练

德国数学家康托 contor 发明了集合论(朴素集合论). 集合论的目的是为了给数学确定基础.集合论是数学当中最基本的概念. 朴素集合论是存在矛盾的.所以引出了公理集合论. 用公理来保证集合的准确性.

其中一个典型的例子就是罗素悖论.

罗素悖论定义如下:

  • $X={x\mid x\ne \emptyset}, {a}\ne \emptyset, {a}\in X, X\notin \emptyset, X\in X$; x 包含自己,

  • $\emptyset \notin \emptyset, {a}\notin{a},\exists x(x\notin x)$; x 不包含自己.

  • $S = { x \mid x\notin x}$ ; x 不属于自己的集合构成的集合.

问:

  • $S \in S ?$

  • $S \in S \Rightarrow S \notin S$

  • $S \notin S \Rightarrow S \in S$

上面罗素悖论的公式用自然语言描述:

  • 有的集合自己是自己的元素(所有包含十个元素以上的集合)

  • 有的集合自己不是自己的元素(某公司5月1号上班的人)

  • 不属于自己的集合构成一个集合 S.

  • 集合 S 本身是否属于 S 集合?

  • 如果 S 属于 S, 则 S 不满足集合的 S 的性质.它不属于自己.

  • 如果 S 不属于 S, 则 S 满足集合 S 的性质, 它属于自己. 得出矛盾.

集合的表示方法

  • 列举法 ,就是全部列出来, 不讲究顺序,允许重复

  • 描述法, x 是人, x 是整数 ${x\mid P(x)}$ 可以与列举法转换.

  • 特征函数法

  • 文氏图

  • 常用的数的集合

    • N: 自然数 ${0,1,2,3…}$

    • Z: 整数 ${0,\pm1,\pm2,\pm3…}$

    • Q: 有理数

    • R: 实数

    • C: 复数

集合的类型以及运算方式

  • 集合 set

  • 子集 $A\subset B$

  • 真子集 $A\subseteq B$

  • 空集(0元集) $\empty$

  • 全集 $E$

  • 幂集 $P(A)={x\mid x\subseteq A}, P(A) =2^n$

  • n元集: 含有 n 个元素的集合.

  • $ A $ 表示集合 A 中元素的个数.

  • 指标集 就是集合 index 的集合

  • 交并补

  • 相对补集

  • 对称差

  • 绝对补

  • 广义并

  • 广义交

容斥原理， principle of inclusion/exclusion
主要是用于 counting， 可以说是用数论来计数，但是计算的是集合交集的运算方式。

AuB = A + A - A^B

第五课

集合恒等式，与等值演算类似。

11:00 提到对偶原理，用于讲解公式的对称性。

集合可以通过形式化的证明， 也就是讲集合转换成逻辑语句，然后进行等值演算。

28:00 讲解对称差的性质。也是对称差存在的一些定律。

43:00 特征函数与集合运算。

第六课

集族的一些性质,以及其证明

第七课 第二章

二元关系

有序对与笛卡尔集
有序三元祖， 有序 n 元组
笛卡尔集
笛卡尔集性质

36:00 开始讲解二元关系

A 上的二元关系。 举例来说， 三个元素存在多少种不同的二元关系。 512 种。 为啥？ 3x3 ,然后从当中取出两个元素，也就是 2^9，512 种不同的取法。

第八课

一些特殊关系。

  • 空关系，
  • 恒等关系，
  • 全域关系，
  • 整除关系，
  • 小于等于，
  • 包含关系，
  • 真包含

二元关系有关的一些概念

  • 定义域(domain)，值域(range)，域(domain)
  • 逆(inverse)，合成(compose)
  • 限制(restriction) 象（image）
  • 单根，单值

comments： 感觉这个部分，mit 的课程更加清晰一些。
injection, surjection, bijection, total, function

第九课

关系的表示/性质/闭包

关系的表示方法

集合，关系矩阵，关系图

关系矩阵在效率上存在一定的优势，关系图对理解层面，存在优势。

关系

自反，反自反，对称，反对称，传递

闭包

自反闭包，对称闭包，传递闭包

第十课

继续讲解关系当中，传递性

30:00 开始讲解闭包

一个对象刚开始不具备自反性，添加最小集合的元素，从而使对象具有自反性。
则，增加的这些元素的集合，称之为自反闭包。
以此类推。

第十一课

等价关系: 自反，对称，传递的二元关系。
具体实践有： 等价类，商集，划分，块，加细。
第二类， Stirling 数， Bell 数。

偏序关系：自反，反对称，传递的二元关系。

表达偏序关系使用哈斯图
特殊元素，链，反链。
线序，拟序，良序。

等价关系

R 是等价关系 <=> R 是自反的，对称的，传递的

提到 mod 关系。这个关系是等价关系。

A = {a,b,c} 上的全体等价关系有 5 种。

{a,b,c}/ {a},{b},{c},/ {a,b}, {c}/ {a,c},{b}/{b,c}, {a}

划分： partition

stirling 子集数 将 n 个不同的球放到 k 个相同的盒子，要求无空盒，不同放法的总数，称之为 striling 数。

30:00 左右开始讲划分

第十二课 偏序关系

3:00
partial order.
poset ,偏序集

12:00 哈斯图

  1. 用顶点表示 A 中元素。
  2. 当且仅当 y 覆盖(自然数当中，大于关系中，3 覆盖 2) x 时，y 在 x 上方，在 x 与 y 之间画无相边。
  3. 组织架构图可以理解为一种哈斯图

16:00 开始讲各种偏序关系的哈斯图的例子。

21:00 全序关系（线序关系） – 哈斯图是一条直线。

拟序关系： 反自反的，传递的 -> 反对称性

30:00 上确界， 下确界。

33:00 链， 反链 ,哈斯图当中的一个分支，就是一个链。

反链，就是链上元素互相都不可比较。

42:00 良序关系， well ordering principle…，良序集可以做数学归纳法
每一个集合都可以良序化。
良序原理 <=> 选择公理

第十三课 函数

偏函数: A 到 B 的偏函数 partial function – domF 属于 A ^ ranF 属于 B

全函数 total function： bijection + function

13:00 真偏函数
真偏函数，就是偏函数减去全函数

本节只讨论全函数。
单射： injection ， F 是单根的。
满射： surjection， ran F = B
双射： bijection ， 一一对应

函数的计数

33:00 image ，象与原象

特殊函数：

  • 常数函数 对于所有的 input， 输出均为常数
  • 恒等函数 对于所有的 input， 输出也为 x
  • 特征函数 对于所有的 input， 如果 x 属于 A， 则 output 为1， 否则为 0.
  • 单调函数 单调增， 单调减， input & output 是偏序集。
  • 自然映射/典型映射 一个元素对应到等价类，或者说等价关系。例如，所有男人都是渣男，看看谁谁谁都那么渣。

A = {a,b,c,d,}
A/R={{a,b},{c},{d}}
F:A -> A/R, F(x) = [x]
F(a) = {a,b},
F(b) = {a,b},
F(c) = {c},
F(d) = {d},

函数合成 fOg:A -> C; fOg(x) = f(g(x))

第十四课

反函数 f: A -> B f^-1: B -> A 是其反函数。

构造双射， 这个对应 mit 当中的 counting。这个很适合用来证明 countable and uncountable

19:00 单边逆，左逆， 右逆。

21:00 使用集合论定义自然数。

封闭性， A 在 F 函数下封闭，F(A) 属于 A , F: A -> A <=> F 是一元运算
例如： f： N -> N ， f(x) = x+1

对于偶数不封闭， 对于 {2,3,4…} 封闭。

使用三元组定义自然数 <M,F,e> ， F: M -> M ; Peano 系统

  1. e 属于 M( e for element)
  2. M 在 F 下封闭
  3. e 不属于 ranF
  4. F 是单射 injection
  5. A 属于 M ^ e 属于 A ^ A 在 F 下封闭 => A = M 极小性公理。

第五条： 如果 A 是 M 的子集， e 也属于 A， 并且 A 也在 F 下封闭， 那么 A 就是 M。
保证 M 是最小的， 或者说只有一个 M。

上面提出需求， 如何使用集合来实现上面的 peano 系统 ？

35:00 提到后继， A+ = A U {A} , 拥有 A 属于 A+， 并且 A 是 A+ 的子集

37:00 归纳集，空属于 A， 所有的 x， x 属于 A ，则 x+ 属于 A
A 是归纳集，A 含有空，且对后继封闭。

自然数是什么呢: 属于于每个归纳集的集合。 自然数集： 是包含于每个归纳集的集合.

问，所以自然数是有归纳集所拥有的性质吗？

所以，自然数的各种运算方式， 可以转换成集合的运算。

D = {v | v 是归纳集}
D 不是集合， 否则导致悖论！ D 是类

自然数集 N = 广义交 D

N 是归纳集需要被证明

第十五课

5:00 证明 N 是归纳集

后继函数： 西格玛： N -> N, ForA n 属于 N，西格玛（n） = n+

自然数的定义是： <N, 西格玛， 0> 是 Peano 系统

28:00 传递集: 广义并属于其本身, 与之相对应的是归纳集。

42:00 开始用基本内容定义自然数的各种基本定律,或者说运算。

第十六课

基数

无穷集合如何比较大小？

A 与 B 等势。A 与 B 无穷集形成双射。

(0,1) 与 R 可以构造 bijection。

(0,1) 与 [0,1] 也可以构造双射。

hilbert 旅馆

6:40 讲如何让 0，1 开/闭区间建立一一映射。很有趣，值得一看。

x = 0, 对应 1/2
x = n, 对应 1/(n+2)
其他一一对应。

等势关系是一个等价关系。

12:00 N 与 R 不能等势
A 与 P(A) 不能等势。
28: 00 康托定理的证明
证明不可等势的一些方式方法。 uncountable 的一些方式方法。
对角化证明

公元前5世纪: 这句话是假的，悖论
公元13世纪: 我是说谎者。
1874: cantor 实数不可数。
1901: 罗素悖论 , 不以自身作为元素的集合的全体。
1931: 哥德尔不完全定理, 这句话没有证明。
哥德尔想表达的是，不是所有的东西都是有证明的。

1936: 图灵 停机问题是不可判定的。p np
任何东西都是一个字符串在计算机当中。所以计算机程序可以和自然数建立双射。
所以，实数比自然数多，所以存在一些 np 问题。
可能判定一个程序是否有 bug。也是使用对角线法证明。

对于所有的输入，形成矩阵，因为输入是无穷的，所以也就是一个无穷的矩阵。 这个时候，沿着对角线取反，形成新的输入，这个输入与任何的输入都不同， 所以输入是不可数的， 也就是说，停机问题不可解决。
证明了通用机的存在性。

第十七课

基数的定义 card A = card B， <=> A 与 B 可以建立双射。
有穷集 A card A = n <=> A 与 n 可以建立双射。
N card N = 阿列夫
实数集R， card R= 阿利夫1 = 阿列夫 0, 1, 2 … 阿列夫0， 阿利夫 都称作基数。

B 比 A 优势 <=> A 比 B 劣势 <=> 存在 f：A -> B 单射。
绝对优势， 绝对劣势。

第十八课

基数运算的定义。
10: 00 基数运算的一些性质。

17:00 连续统假设 CH
19:00 ZF系统
20:00 ZFC 系统
选择公理的等价形式。
25:00 well ordering principle 良序

序数

38:00 3n+1 猜想。

图论

第十九课

无序积，对应的概念是笛卡尔集（卡氏积)
(a,b)

A & B = {{a,b} | x 属于 A ^ y 属于 B }
(a,b) = (b,a)

使用无序积， 可以定义无向图。

G = <V,E> (Graph)
V != null, 顶点集
E 是 V & V 的子集。

有向边，形成有向边。
V !=- null.
D =- <V,E>
E 是 V x V 的子集。

顶点集 V（）， 边集E（）

V(G) = V, E(G) = E

V(D) = V, E(D) = E

有几个顶点，就是几阶。
有限，就是有限图。
没有边的图， 是零图。Nn (null graph)

一阶零图（平凡图），二阶零图 … n 阶零图

空图代表 V = null， E = null

标定图：各个 V 都有标记。可用于计数。
对应的概念就是非标定图。

基图（低图）由有向图去掉方向得出。

相邻： 有边连接的两个顶点。有公共顶点的两条边。
有向图中，邻接与，邻接到。

关联，以及关联次数。无向图中，两个邻接的顶点，两个顶点的关联次数都是1.
环的关联次数是2.
有向图，出是+1， 入是 -1。

环，只与一个顶点关联的边。
孤立点： 不与任何点产生关联的顶点。

平行边，端点相同的两条无向边，是平行边。
起点与终点相同的两条有向边，是平行边。

邻域，Ng（V) ，就是与 V 相邻的所有的其他的顶点。
闭邻域。 Ng[V]. 与 V 相邻的所有顶点，包括 V 本身。

– 相邻表示同类元素之间的关系，关联表示不同元素之间的关系。

关联集： Ig(V) = {e e 与 V 关联}

前驱与后继。和链表类似。

顶点的度: 与顶点 v 关联的边的数量. d()

出度， 入度。

有向图的度，是入度与出度之和。

最大度，就是图里面 V 最大的度。
最大出度，最大入度。最小度。

27:00 图论的基本定理： 握手定理
G=<V,E> 是无向图。 V = {v1,v2,v3…,vn}, |E|=m
则 d(v1) + d(v2) + d(v3) + … + d(vn) = 2m.

对于有向图， 则 d(v1) + d(v2) + d(v3) + … + d(vn) = m.

可以推断出： 奇数度的顶点的个数，一定是偶数

简单图(simple graph)： 既没有环也没有平行边的图。

度数列： 不同顶点的度的数列。

可图化的： 非负整数度数列，如果度数列能够被表示出图，则度数列可图化。

可简单图化：
推断的第一种方法： d1 + d2 + d3 + … + dn = 0(mod2)
n-1 >= d1 >= d2 >= … >= dn >= 0 可简单图化 <=>
d’ = (d2-1, d3-1 … , dd1+1-1, dd1+2, …, dn) 可简单图化。
重复递推到平凡情况，得出是否可简单图化。

第二种方法：
d1 + d2 + d3 … + dn = 0(mod2)
并且对 r = 1,2,…,n-1 有
d1+d2+d3+…+dr <= r(r-1) + min{r,dr+2} + … + min{r, dn}.

介绍埃尔特希。

第二十课

图同构: 两个图能够完全重合。形式上讲，顶点可以双射。
~ =

当G1 的两个顶点存在边，那么对应的顶点也有存在边。
如何判定图同构？
NAUTY 算法。
提到零知识证明。

有向图同构。

17:00 图族

完全图， 有向完全图， 竞赛图
柏拉图图，彼得森图，库拉图斯基图
r 部图，二部图（偶图）， 完全 r 部图
路径，圈，轮，超立方体

简单图中，边达到最大，则称之为完全图。
有向完全图，边数是无向的两倍。
无向完全图，给每个边添加上方向，形成竞赛图, 可以用来表达竞赛结果。

柏拉图图： 五种正多面体。

  • 正四面体
  • 正六面体
  • 正八面体
  • 正十二面体
  • 正二十面体

彼得森图： 中间一个五角星，外面套一个五边形。

库拉图斯基图(判定图是否能够被画成平面图）：

  • 完全 2 部图 K3,3。
  • 完全图。

r 部图：
顶点集合可以分为 r 个部分, 每个部分的顶点不能相连。

2 部图：
偶图。

完全 r 部图

路径， paths, P1, 下标指代边数。
圈 ， cycles ， 就是有环路。
轮，wheel 在圈当中多一些轴心。有几个轴就是 W 几
超立方体。两个正方形，形成立方体，两个立方体，内外又可以嵌套。

子图。 G’ 是 G 的子图，就是
V’ 是 V 的子集， E’ 是 E 的子集。
真子图， 生成子图(顶点集和原图一样）。
导出子图，取出一部分的顶点，然后把这些顶点相关的边留下来。

补图： 完全图，拿掉简单图， 就形成了部图。

自补图： 图与其部图同构，则为自补图。

画图，可以先求度数列，然后根据度数列再画图。

图的运算：

  • 删除，收缩，加新边，不交。
  • 并图，交图，差图，环和。
  • 联图，积图。

删除，删除边直接删除，删除顶点需要同时删除其相关的边。
搜索，删除一个边后，两个相连的顶点合并。
加新边
两个图没有公共顶点，图不相交。

联图（join）不交无向图。
就是将两个图连起来。

积图（product）

第二十一课

图的连通性。

通路 walk, 起点，终点，通路长度。
顶点与边的交替序列， 是 walk。
回路。 closed walk, start v = end v.

simple walk: no repeat path.

element walk 初级通路 .没有重复顶点的通路。

element 初级回路。 没有重复顶点的回路。

可以用顶点序列表示通路(walk)。

G 是含圈的图。周长，最长圈的长度，就是图的周长。无圈的，周长要么为零，要么为无穷大。

最短圈的长度是围长。

在 n 阶图G中，若从不同顶点 vi 到 vj 有通路，则最多 n-1 条边。

极大路径法。
在无向简单图中，路径的两个端点不与路径本身以外的顶点相邻，这样的路径称之为极大路径。

扩大路径法。任何一条路径，只要不是，则至少有一个端点可以更大。

扩大路径法证明，如果每个顶点的度>=2. 则存在长度 >= 最小度数 + 1 的圈。

  • 联通 无向图， u v 之间有通路, 联通关系是等价关系。
  • 联通分支, 联通图的等价类。
  • 联通分支数, 等价类的个数。
  • 联通图, p(G) = 1. 就是联通图。
  • 短程线（测底线）, u, v 之间最短距离。
  • 距离(短程线的长度）, 两个点之间的通路长度。
  • 顶点之间的最大距离， 直径。两个点之间的最大距离。

距离函数:
满足两个点距离非负， 两个点对称， d(u,v) + d(v,w) >= d(u,w). 任何函数满足以上性质，那么就是一个距离函数。

G 是一个二部图 <=> G 中无奇圈。
证明： 使用染色法

二部图在资源分配是一个基本模型。
有一些对象，如何分配一些资源。

无向图是联通的， 则 G 的边数 m > n-1

图的联通度。

  1. 如何定量的比较连通性？

中央控制机构的连通性最差。

提到点连通度： 为了破坏连通性，至少需要删除多少个顶点？
边连通度： 至少要删除多少条边？

破坏连通性是什么?
– 联通分支数增加。

点割集, 最小的破坏连通性的集合。
一个点构成的点割集，就是割点。
边割集。

第二十二课

扇形割集。
割边，桥
扇形割集。

点连通度。最小的点割集的数量。
边连通度。同理。

k 连通图。至少要删除 k 个顶点，才能破坏连通性。
k 边连通图。

彼得森图是： 1/2/3-连通图。
但是不是 4 连通图。

1/2/3 边连通图。
边不交路径（edge-disjoint）路径。

K边连通的充分必要条件。
3阶以上的无向图 G 是 k 连通图，当且仅当 G 中 任意 2 低昂定剑佑 k 条以上独立路径。

block 块：极大无割点连通子图。

块的充分必要条件。

可达， reachable: 有向图某两个当中存在通路。
双向可达， 有向图某两个存在双向的通路。

单向连通。

竞赛图一定有初级通路（路径）过每个顶点，恰好一次。可用来排序。

强连通（双向连通），任何一对顶点双向可达。

单向连通，有向图 D 中有通路至少经过每个顶点一次。

强连通分支。单向连通分支，弱连通分支。

第二十三课

欧拉图与哈密顿图

欧拉图： 走过所有边一次，并且恰好一次。

欧拉被称之为有史以来最多产的科学家。

1736 年， 7桥问题，图论与拓扑学诞生。

每一个顶点的度都是偶数度，7 桥问题就被解决了。

经过图中所有的边的简单通路，就被称之为欧拉通路。
有欧拉通路的图，就是半欧拉图
经过图中搜有边的简单回路，就是欧拉回路。
有欧拉回路的图，就是欧拉图。

若欧拉回路总共 k 次经过顶点 v， 则 d（v)= 2k.

无向欧拉图的充要条件：
G是无向连通图，G 是欧拉图 <=> G 中所有的顶点都是偶数度。 <=> G 是若干个边不交的圈的并。

无向半欧拉图的充要条件：

G 中桥好有 2 个奇数度顶点。

有向欧拉图的充要条件：
有向半欧拉图的充要条件：

25:00 Fleury 算法（避桥法）可以得到欧拉回路。

欧拉回路的应用之一： 轮盘设计

41:00 哈密顿图： 走过顶点，并且恰好一次。

哈密顿通路： 经过图中所有顶点的初级通路。
有哈密顿通路的图，就是半哈密顿图
哈密顿回路： 经过所有顶点的回路。
有哈密顿回路的图。

目前没有简单判断是否为哈密顿图的算法。

目前没有充分必要条件。

必要条件：
p(G-V1) <= |v1|

半哈密顿图的必要条件
p(G-V1) <= |v1| + 1

有向哈密顿图充要条件。
有向半哈密顿充要条件。

二十四课 树

代数结构

第三十五课

现代数学的特点

结构与分析
学科的交叉: 运筹学与管理学，离散数学与计算机科学
确定性与非确定性的交叉： 离散概率

CS: computer Science IS: Information System CE: Computer Engineering SE: Software Engineering

研究离散个体以及其结构。

数理逻辑主要研究推理，以及逻辑, 形式化证明。
集合论，主要是表示方法。

组合数学， 是离散结构的存在性。如何计数？如何枚举？如何优化？

28:00 离散数学的知识架构图。

数理逻辑： 人工智能，程序正确性证明及验证。
集合论： 关系数据库模型
图论： 数据结构，数据库模型，网络模型。
代数结构： 软件规约，形式化语义，编译系统，编码理论，密码学，数据仓库
组合数学： 算法设计与分析，编码理论，容错。

30:00 汉诺塔问题。指数爆炸。涉及到组合数学问题。

数据仓库的视图格： OLAP 联机分析处理。如何组织视图，才能够让查询足够快？
每一个聚类就是一个划分，多个维度，再进行笛卡尔积。再形成一个格结构。
引出格的结构。

进程的资源共享模型。命题的迁移，与图有关。

第三十六课

代数系统的基本概念 – 8 学时

  • 二元运算的性质
  • 代数系统的构成
  • 子代数与积代数
  • 代数系统的同态与同构
  • 代数系统上的同余关系与商代数

半群，独异点与群 – 12 学时

  • 半群与独异点的定义与性质
  • 群的定义与分类
  • 群的基本性质
  • 子群
  • 循环群
  • 变换群
  • 置换群
  • 群的分解（陪集分解与 Lagrange 定理，共轭类分解与分类方程）
  • 正规子群
  • 商群及性质
  • 群的同态与同构
  • 群的直积

环与域

  • 环的定义及基本性质
  • 特殊的环
  • 子环
  • 理想
  • 商环及环同态 格与布尔代数
  • 格的定义与性质
  • 子格
  • 格同态与格的直积
  • 特殊的格
  • 布尔代数

代数结构的组成

  1. 载体
  2. 运算
  3. 公理

在以上的基础上，如何构成新的东西。 由已知的代数系统构成新的代数系统。

  1. 子集: 子代数
  2. 不同的代数系统进行笛卡尔积： 积代数
  3. 等价关系： 商代数

通过映射，可以映射到另外一个代数系统。
那么代数系统就是同构的。
通过同态，同构，可以把一些些系统理解为同样的系统。
比如说线性代数系统和自然数可以理解为同构的

对代数系统的典型应用系统研究：

  1. 半群与群，包含一个运算 只有一个二元运算
  2. 环域， 包含两个运算
  3. 格与布尔代数

进一步可以推广至 西格玛代数: 理解下来感觉就是不封闭的。

二元运算以及性质

f:AxA -> A 称之为为 A的二元运算。
0元， 就是选择一个元素。
1元， 针对一个元素的操作， 比如说取反。
2元， 乘法，加法等。

算律

和一个运算相关的

  • 交换律
  • 幂等律
  • 结合律
  • 消去律

和两个及多个元素有关

  • 分配律
  • 吸收率

特异元素

  • 单位元
  • 零元
  • 可逆元素

第三十七课

二元运算的性质体现为两类

  1. 算律
  2. 特异元素

幂等律： a o a = a

特异元素

特异元素名称：

  • 单位元 幺元，e ( eoa = a0e = a, 比如说自然数当中的 + 和 0 )
  • 零元 0 ( aoa = a00 = 0 , 比如说 0 和 x )
  • 幂等元 (aoa = a ,乘法有两个幂等元， 0，1)
  • 可逆元和逆元 (存在单位元的系统， xoy = yoa = e )

打个比方： 加法当中， 单位元是0，没有零元，幂等元也是0，逆元就是正数与负数。
乘法当中，单位元是 1， 零元是 0， 幂等元是 1，0. 逆元就是自然数及其倒数。

特异元素有时候也可以作为算律

  • 同一律（存在单位元）
  • 零律（存在零元）

单位元与零元在整个系统当中具有唯一性。
若存在逆元，针对元素其唯一。

第三十八课

形式化的记法： V = < A, 欧米茄， K >
A: 载体， 比如说集合。
欧米茄： 运算集，非空
K： 代数常数集

V = < A, 欧米茄 >

从高元到低元进行列举
V = < A, o1, o2, o3, … on >

例子

  • < Z, +, * >
  • < Zn, mod+，mod * > …

同类型的： 构成成分相同。
同种的： 构成成分与公理都相同。

22:00 子代数
B 是某代数系统的非空子集。 若 B 对于 A 中所有的运算封闭， 则 B 是 A 的子代数。

子代数与原系统是同种的系统。
子代数一定存在。

29:00 积代数
两个代数系统， 做笛卡尔积。

运算相当于对与对的运算。