离散数学

课前讯息

• 40%应用题
• 没办法突击考好，有一点难度
• 往年题渗透在教学里了，每年题都不一样
• 没有直接的考勤，但是课堂测验或者巡查什么的被发现也没办法
• TA联系方式：
• 问问题要告诉名字
• 老师喜欢互动
• 小组展示；理论对应可以刻画的生活学习工作中的真实例子 10%
• 全英闭卷笔试的期末考试 70%，作业 15%，出勤 5%
• 各个章节之间看似特别散，其实有很强的内在联系，比如说六个主要内容之间是可以相互表示的。（逻辑，布尔代数，集合，图，树，函数……）

逻辑和证明

1.1命题逻辑

proposition 命题 prop.

条件语句

implication 蕴含 implies
$p → q$是一个单条件语句，一句话概括就是“p能推导出q，q是p的必要条件，p是q的充分条件”

对于这个命题，我们可以用真值表来表示它的真假情况

• 如果 p 为真，能推导出 q 为真，则蕴含式为真；不能推导出 q 为真，则式子为假

• 如果 p 为假，那么 q 可能为真也可能为假，也就是和q无关，蕴含式为真

  | $p$ | $q$ | $p → q$ |
  |:—-: | :—-:|:—-:|
  | T | T | T |
  | T | F | F |
  | F | T | T |
  | F | F | T |

Bicondtion 双向蕴含 IFF 等价于 同或，自然语言中的例子是 “当且仅当”，其实就是pq互为充要条件。
包含双向蕴含的式子也叫双条件语句。双条件语句的真值表如下

$p$	$q$	$p ↔ q$
T	T	T
T	F	F
F	T	F
F	F	T

符号优先级

• $\neg$ 优先级最高
• $\wedge$ 优先级次之
• $\vee$ 优先级次之
• $\rightarrow$ 优先级次之
• $\leftrightarrow$ 优先级最低

1.2命题逻辑的应用（不用看。直接1.3吧）

我们已经知道了6个重要的逻辑连接词：合取（and），析取（or），异或(xor)，蕴含(implication)，双向蕴含(Bicondtion)和否定(NOT)。我们可以用它们来构建复合命题。

自然语言语句翻译

消除自然语言的二义性，翻译成命题逻辑的形式，这样就可以用真值表来判断它的真假了。

最早（2010 年之前）关于人工智能自然语言处理的研究是建立在命题逻辑之上的。

命题逻辑在自然语言处理（NLP）中确实有体现，并且在NLP的早期阶段就起到了一定的作用。然而，在NLP发展的后期阶段，特别是在深度学习和大模型的兴起之后，命题逻辑在主流方法中的应用逐渐减少。

命题逻辑在NLP中的体现主要包括以下方面：

• 语义表示和逻辑推理：在NLP的早期，一些系统尝试使用命题逻辑来表示句子的语义信息，并进行逻辑推理。这种方法通常涉及将自然语言句子转换为逻辑表达式，然后应用逻辑规则进行推理。然而，这种方法在处理复杂的自然语言现象时常常受限，因为自然语言的表达和含义往往不那么规则和明确。

• 语义网络和知识表示：一些NLP系统使用了类似于命题逻辑的语义网络来表示知识，包括实体、关系和事实。这种表示方法可以用于知识图谱构建以及推理任务。然而，随着知识表示方法的发展，基于图谱的方法逐渐被更强大的向量表示方法所取代，例如词嵌入和预训练模型。

尽管命题逻辑在NLP的早期发展阶段起到了一定的作用，但随着神经网络方法的兴起，NLP的主流方法趋向于将大量数据和复杂模型结构纳入考虑，而不太依赖于传统的命题逻辑方法。特别是在预训练模型（如BERT、GPT等）的时代，NLP任务更多地关注语言的统计性质和上下文信息，而不是直接进行严格的逻辑推理。

总体而言，命题逻辑在NLP中的应用逐渐减弱，但在某些特定的任务和研究方向中仍然可能会有所体现。

系统规范说明

在描述硬件或者软件系统的时候，我们经常需要对系统进行规范说明，这些规范说明通常是用命题逻辑来表示的。精确而规范的说明可以帮助我们避免系统设计中的错误。

布尔搜索

在计算机科学中，布尔搜索是一种用于在大型数据库中查找信息的技术。在布尔搜索中，我们使用布尔运算符来组合关键字，以便在数据库中查找特定的信息。
例如知网的高级搜索功能，就是用布尔搜索来实现的。

逻辑电路

谓词命题逻辑可以用来表示逻辑电路。逻辑电路是由逻辑门组成的，逻辑门是用来实现布尔运算的电路。逻辑门有三种基本类型：与门，或门和非门。与门和或门的输入和输出都是布尔值，非门的输入和输出都是布尔值。逻辑门的输出是根据输入的布尔值计算出来的。逻辑门可以用真值表来表示，也可以用逻辑符号来表示。

1.3命题等价式

• tautology 永真命题，也称为重言式
• contradiction 永假命题，矛盾式
• contingency 可能式

逻辑等价 logic equivalence

syntactically 句法地；textually 文本地 semantic 一致的
在所有情况下都具有相同真值的两个复合命题称为是逻辑等价式。

拓展：人工智能其实就是知识的表示。
定理证明和图像识别的技术实现不同。
前者很容易用数学和符号表示，后者例如一只猫的识别，是无法用数字和符号表示的，所以有一种方法就是数据驱动的知识表示。

• 蕴含式可以用门电路表示。
  $p\rightarrow q \leftrightarrow\neg p \vee q$

  1.3.4 De Morgan’ s law

  用取反$\neg$以及合取$\wedge$能表示所有逻辑

$\oplus=\neg (p \leftrightarrow q)$

这一块考3～5 分，hh 应该不会出太难。

逻辑等价式，总结一下

• 分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R),P∨(Q∧R)⇔(P∨Q)∧(P∨R)
• 德摩根律
• 经典蕴含式的置换：$p\rightarrow q \leftrightarrow\neg p \vee q$
• 把等价拆出来：$(p\leftrightarrow q) \leftrightarrow (p\rightarrow q)\wedge(q\rightarrow p)$
• 等价反过来也是等价：$(p\leftrightarrow q) \leftrightarrow (\neg p\leftrightarrow \neg q)$
• 把异或拆出来：$p\oplus q \leftrightarrow (p\vee q)\wedge\neg(p\wedge q)$
• 异或也能表示为等价关系：$p\oplus q \leftrightarrow \neg(p\leftrightarrow q)$
• 等价关系的非：$(\neg(p\leftrightarrow q) )\leftrightarrow (p\leftrightarrow \neg q)$
• 四组
  • 后同变号$(p \rightarrow r) \wedge(q \rightarrow r) \leftrightarrow (p\vee q)\rightarrow r$
  • 后同变号$(p \rightarrow r) \vee(q \rightarrow r) \leftrightarrow (p\wedge r)\rightarrow r$
  • 前同不变号$(p \rightarrow q) \wedge(p \rightarrow r) \leftrightarrow p\rightarrow (q\wedge r)$
  • 前同不变号$(p \rightarrow q) \vee(p \rightarrow r) \leftrightarrow p\rightarrow (q\vee r)$

本节题目小结

• 证明题可以证明两边都为永真，也可以证明两边都为永假
• 两头逼向中间证明
• 涉及蕴含一般就是把蕴含展开

1.4谓词和量词

在逻辑学中，谓词和量词是基本的概念，用于构建命题和表达复杂的逻辑关系。让我为您解释一下这两个概念：

谓词：

谓词是描述某些属性或关系的符号或词语。它可以是一个词、短语或句子，用来表示主语的性质、状态或所具有的关系。在逻辑中，谓词通常用字母或词汇来表示，例如，P(x) 可以表示 “x 是大的”，Q(y) 可以表示 “y 是红色的”。在这里，P 和 Q 就是谓词，x 和 y 是变量，它们可以代表不同的对象或值。

量词：

量词用于指定一个谓词的适用范围，即它们告诉我们谓词适用于多少个元素。有两种常见的量词：全称量词和存在量词。

• 全称量词（∀，读作”对于所有”）：表示一个谓词对于某个特定集合中的所有元素都成立。例如，∀x P(x) 可以解释为 “对于所有 x，P(x) 成立”，表示谓词 P 适用于集合中的每一个元素 x。

• 存在量词（∃，读作”存在”）：表示在某个集合中至少存在一个元素，使得谓词成立。例如，∃x Q(x) 可以解释为 “存在 x，使得 Q(x) 成立”，表示集合中至少有一个元素 x，使得谓词 Q 成立。

习题经验向总结

• 与或等价转换，全称量词对应且；存在量词对应或
• 蕴含式带x的如果是后者，等价式不用变号；如果是前者，等价式要变号。
• 注意题目里的要求 是否实际上答案要写的是negation
• domain

  1.5嵌套量词

  嵌套量词的否定：连续地应用单个量词语句的德摩根定律。
• 一反全反
• 量词和非的前后顺序如果要交换，量词要变号。例如：$\neg(\forall x)(\exists y)P(x,y)\leftrightarrow(\exists x)(\forall y)\neg P(x,y)$

  example

1. Let P(x) be the statements “x is the rational number”. Express the sentence “One rational number is bigger than all other rational numbers” in terms of P(x), quantifiers, and logical connectives:(∃x)(P(x)∧(∀y)(P(y)∧(¬x=y))→x>y)
2. Let C(x): x is a computer. D(x): x is a peripheral equipment. P(x, y): x can communicate with y. Express the sentence “some computers can’t communicate with some peripheral equipment” as a logical expression as : (∃x)(C(x)∧(∃y)(D(y)∧(¬P(x,y))))

1.6推理规则

命题逻辑的推理规则

• theorem 定理
• proof证明
• axioms公理
• postulates假设
• fallacies 谬误
• lemma 引理
• corollary 推论
• conjecture 猜想

永真式是称为 假言推理（modus ponens） 或 分离规则(law of detachment) 的推理规则的基础。

假言推理是一种推理规则，它允许我们从一个条件语句和它的前件推导出结论。

例如，如果我们知道 “如果今天下雨，那么我就不会去公园”，并且我们知道今天下雨了，那么我们就可以推断出 “我今天不会去公园”。这个推理过程可以用下面的推理规则来表示：

有效论证：如果前件为真，那么结论也为真。

推理规则：

• 假言推理（modus ponenes/分离规则the law of detachment）：如果 p → q 为真，p 为真，则 q 为真。
• 敢拒式(rule of modus tollens)：
• 假言三段论(rule of hypothetical syllogism)：如果 p → q 为真，q → r 为真，则 p → r 为真。
• 析取三段论(rule of disjunctive syllogism)：((𝑝∨𝑞)∧¬𝑝)⇒𝑞
• 附加律(rule of addition):𝑝⇒(𝑝∨𝑞)
• 简化律(rule of simplification)：𝑝∧𝑞⇒𝑝
• 合取律(rule of conjunctior)：……
• 消解率(rule of resolution)：……

谬误

• 肯定结论的谬误（fallacy of affirming the conclusion）:
  如果你做过本书的每一道练习题，则你就学习过离散数学。你学习过离散数学。因此，你做过本书的每一道练习题。”这种论证是无效的，称为肯定结论的谬误。((𝑝→𝑞)∧𝑞)→p
• 否定前件的谬误（fallacy of denying the hypothesis）：
  如果你做过本书的每一道练习题，则你就学习过离散数学。你没做过本书的每一道习题。因此，你没学习过离散数学。”该论证为否定假设的谬误，论证无效。((𝑝→𝑞)∧¬𝑝)→¬𝑞

量化命题的推理规则

• 全称实例（Universal instantiation）
• 全称引入（Universal generalization）
• 存在实例（existential instantiation）
• 存在引入（existential generalization）

chapter 2：基本结构：集合、函数、序列、求和与矩阵

2.1 集合

Note that 1 ≠ {1} ≠ 1，Sets Are Objects, Too!

cardinality 基数

|S| (read “the cardinality of S”)基数，大小 is a measure of how many different elements S has.

power set 幂集

所有子集组成的新集合，用P(A)表示一个由集合A的所有子集组成的集合。

Prove that P(A) ⊆ P(B) if and only if A ⊆ B.

Sometimes P(S) is written $2^S$, because |P(S)| = $2^{|S|}$.

tips:

• 证明集合相等的时候，可以证明互为子集。

  cartesian product 笛卡尔积

  $A\times B={(a,b)|a\in A \wedge b\in B}$

也就是说，笛卡尔积是由所有有序对(a,b)组成的集合，其中a来自A，b来自B。

许多离散结构都是基于集合的笛卡尔积概念。例如If R is a relation between A and B then $R \subseteq A\times B$

2.2 函数

• domain 定义域A
• range 值域：所有x对应的y值，值域是陪域的子集
• codomain 陪域：函数的可能值的集合B
• ../image/image 函数值（像）：b is the ../image/image of a under f.

• pre../image/image 原像：a is a pre-../image/image of b under f.

• surjective(Onto) 满射：对于每一个b∈B，都存在a∈A，使得f(a)=b

• injective 单射：一对一的映射关系
• bijective 双射：既满足满射又满足一对一的映射关系
• composition 复合函数：$(f\circ g)(x)=f(g(x))$

$Y^X$

Sometimes we write $Y^X$ to denote the set F of all possible functions $f: X\to Y$.
Thus, $f:\in Y^X$ is another way of saying that $f: X^Y$.

(This notation is especially appropriate, because for finite X, Y, we have |F| = |Y||X|. )

注意。有这样一道题：

• |{f:{0,1}^n->{0,1}^n}|=$2^{n 2^n}$
• 表示从{0,1}^n 到{0,1}^n 的所有函数集的基数 (或大小) 。从{0,1}^n 到{0,1}^n 的函数是一个映射，它为每个0和1的n元组分配另一个0和1的n元组。例如，如果n= 2，则一个可能的函数是f (0,0) = (1,1) 、f (0,1) = (0,0) 、f (1,0) = (1,0) 、f (1,1) = (0,1) 。
  为了找到这个集合的基数，我们需要计算有多少这样的函数存在。对于域中的每个n元组，共域中有 2^n个可能的n元组可以映射到它。由于域中有 2n 个n 元组，因此函数总数为$2^{n 2^n}$

  inverse function 逆函数

  For bijections f:AB, there exists an inverse of f, written $f^{-1}: B\to A$

Intuitively, this is the function that undoes everything that f does.

Formally, it’s the unique function such that $f^{-1} \circ f =I_A$(recall that $I_A$ is the identity function on A)

2.3 序列(不管)

2.4 求和(不管)

2.5 矩阵(不管)

chapter 3：算法

chapter 7(中文版第九章)：关系

关系是离散数学中最重要的概念之一。它是一种用于描述集合之间关系的数学工具。在本章中，我们将介绍关系的基本概念，包括关系的定义、关系的性质、关系的表示以及关系的应用。

笛卡尔积

$A\times B={(a,b)|a\in A \wedge b\in B}$
集合的笛卡尔积就对应着他们所有可能的关系，是一个新的集合。每一种可能的关系就是这个集合的子集。

二元关系

• A (binary) relation from a set A to itself is called a relation on the set A.
• on set A: $R\subseteq A\times A$
• 逆关系：$R^{-1}={(y,x)|(x,y)\in R}$
• a relation on set A: from A to A
• reflation 自反 : $aRa$
• irreflexive 非自反： $任意a都有 a\not Ra$
• symmetric 对称： $任意aRb \leftrightarrow bRa$;如果要满足这一条件,iffa=b，则称该关系是反对称的。
• anti-symmetric 反对称： $任意aRb且bRa，则a=b$
• transitive 传递： $任意aRb且bRc，则aRc$；如果要满足这一条件,iffa=b，则称该关系是反对称的。
• Composite 合成：(𝑎,𝑐)∈𝑆∘𝑅⇔∃𝑏∈𝐵((𝑎,𝑏)∈𝑅∧(𝑏,𝑐)∈𝑆),tip:右结合

  易错习题

1. 判断：Let A={1，2，3，4}, R is a relation on A, R= {(1,2), (1,3), (2,4), (3,4)}is a function. 答案为F，涉及函数的定义必须是一对一。
2. The relation R, U =Z-{0}, (x, y) ∈ R if and only if xy≥1, so R is reflexive, symmetric and transitive. 注意是整数Z
3. R is “ less than or equal to” relation on Z×Z，then $R^{-1}$ = ≥.
4. How many of the 16 different relations on {0,1} contain the pair (0,1)? 答案：8 解析：首先研究{0,1} 自身的关系：${0,1}\times{0,1} ={(0,0),(0,1),(1,0),(1,1)}$。这个集合有16个子集，每个子集都是一个关系。其中有8个子集包含(0,1)。因此，有8个关系包含(0,1)。（排列组合的知识）
5. How many transitive relation on the set { a，b，c }? (171)
   • ${a,b,c}\times {a,b,c}={(𝑎,𝑎),(𝑏,𝑏),(𝑐,𝑐),(𝑎,𝑏),(𝑏,𝑎),(𝑎,𝑐),(𝑐,𝑎),(𝑏,𝑐),(𝑐,𝑏)}$

9.2 n元关系及其应用

An n-ary relation R on sets A1,…,An, is a subset：
$R\subset A_1 \times … \times A_n$.

n元关系：设A_1,A_2,…,A_n是集合，R是A_1,A_2,…,A_n的笛卡尔积的子集，即R则称R为A_1,A_2,…,A_n上的n元关系，这些集合称为关系的域，n是关系的阶数。

笛卡尔积->复合主键

• 函数：R is functional in the domain Ai if it contains at most one n-tuple (…, ai ,…) for any value ai within domain Ai.
• 选择 Select：设 A 是任意 n 元域 A=A1×…×An，设 C：A→{T，F} 是 A 的元素（n 元组）上的任何条件（谓词）。
  然后，选择运算符 sC 是将 A 上的任何 n 元关系 R 映射到 n 元关系的运算符，该 n 元关系由满足 C 的 R 中的所有 n 元组组成。 也就是 $sC（R） = {a\in R |C（a） = T}$
• 投影 Projection：将n元组映射到m元组中，其中m<=n.
  • 设 A = A1×…×An 是任意 n 元域，设 {ik}=（i1,…,im）是一系列索引，所有索引都落在 1 到 n 的范围内，也就是说，对于所有 1 ≤ k ≤ m，有1 ≤ ik ≤ n。
• 连接 Join：设R是m元关系，S是n元关系，连接运算Jp(R,S)是一个（m+n-p）元关系，其中p<=m且p<=n.它包含了所有的m+n-p元组，其中m元组a_1,a_2,…,a(m-p),c1,…c_p属于R,n元组c_1,…c_p,b_1,b_2,…,b(n-p)属于S.

练习

1. There are 2的$m^n$次方 n-tuple relations on the set S×S…×S when |S|=m.

9.3 关系的表示

9.3.1 关系0-1矩阵

可以用0-1矩阵表示一个有穷集之间的关系。设R是集合A和B之间的关系，A={a_1,a_2,…,a_m},B={b_1,b_2,…,b_n},则R的0-1矩阵是一个m行n列的矩阵，记为M(R),其中第i行第j列的元素为1当且仅当$a_iRb_j$.

如果定义在一个集合上的关系矩阵是方阵，可以用这个矩阵确定关系是否具有某种性质：

• 如果对角线上的所有元素都等于1，那么这个关系R就是自反的
• 对角线两边的元素和关于对角线对称的元素相等，说明关系R是对称的（也就是转置前后矩阵不变）
• 相应的，对角线两边的元素和关于对角线对称的元素都不相等，说明关系R是反对称的
• 关系矩阵的布尔运算并和交可以用来求关系的并和交
• 关系矩阵的布尔积可以用来表示关系的合成，注意右结合的特性

  9.3.2 有向图

  每个元素是一个点，每个有序对表示一条带有箭头的弧，弧线上的箭头代表的是方向。

环：形如（a,a）的从自身回到自身的弧线

用有向图表示关系:

• 当且仅当有向图的每个顶点都有环，则关系是自反的
• 当且仅当不同顶点之间的每一条边都有一条方向相反的边，则是对称的
• 相应的，一个关系是反对称的，当且仅当两个不同的顶点之间不存在方向相反的两条边

• 当且仅当存在一条边从x到y，一条边从y到z，就一定存在x到z的边(完成一个三角形)，则关系是传递的

  9.4 关系的闭包 closures of relations

• reflexive closure 自反闭包
  关系R的自反闭包等于$R\cup \Delta$,其中$\Delta$是集合A上的对角关系，即$\Delta={(a,a)|a\in A}$

• symmetric closure 对称闭包
  关系R的对称闭包可以通过增加所有形如（b,a）的有序对来获得，其中（a,b）是R中的有序对，但是（b,a）不是R中的有序对。

  也可以通过求关系和它的逆关系的并来获得，即$R\cup R^{-1}$，其中$R^{-1}={(b,a)|(a,b)\in R}$。

• transitive closure 传递闭包
  连通性关系$R^*$由形如（a,b）的有序对组成，使得从a到b存在一条长度至少为1的路径。传递闭包就是连通性关系。

  $R^*=\bigcup_{i=1}^{\infty}R^i$

  Let M(R) be the zero-one matrix of the relation R on a set with n elements. Then the zero-one matrix of the transitive closure R is $M(R) = M(R) V M(R)^2 V M(R)^3 V … V M(R)^n$

  $M(R)\cdot M(S)$的结果M中，M[i,j]=1的实际意义是

9.4.5 沃舍尔算法 Warshall’s algorithm

沃舍尔算法能高效地计算关系的传递闭包。只需要$2n^3$次比特运算就能算出n元集合关系的传递闭包。warshall算法的基础是一些列0-1关系矩阵，$w_1,w_2,…,w_k$,其中$w_1$是关系$R$的0-1矩阵，$w_k$是关系$R^k$的0-1矩阵。

参考链接：
https://blog.csdn.net/foreverzili/article/details/68481930

注意$W_n=M(R^*)$，$W_0=M(R)$，$W_k$是关系$R^k$的0-1矩阵。

效果上来说，warshall算法每一次得到的$Wk$是在原本0-1矩阵$M{R^{k-1}}\circ M_{R^{1}}$的基础上与上一次的结果的并集。

9.5 等价关系 equivalence relations

等价关系指的是一种二元关系，它是自反的、对称的和传递的。等价关系是一种特殊的关系，它可以用来对集合中的元素进行分类。

划分 partition

划分是把集合分成不相交的子集的过程。每个子集称为一个划分块。划分块的并就是原来的集合。划分块的交是空集。划分块的并是原来的集合。

等价类 equivalence class

设R是定义在集合A 上的等价关系。与A中的一个元素a 有关系的所有元素的集合叫作a的等价类。A的关于R的等价类记作[a]R。当只考虑一个关系时，我们将省去下标R并把这个等价类写作[a]。
换句话说，如果 R是定义在集合 A 上的等价关系，则元素 a的等价类是
$[a]r={s| (a,s)\in R}$.

如果$b\in [a]k$，b叫作这个等价类的代表元。一个等价类的任何元素都可以作为这个类的代表元。也就是说，选择特定元素作为一个类的代表元没有特殊要求。

定理

• 定理2：设R是定义在集合S上的等价关系。那么R的等价类构成S的划分。反过来，给定集合S的划分{A,|i∈I},则存在一个等价关系R,它以集合A;(i∈I)作为它的等价类。

练习

• The smallest equivalence relation on the set {1,2,3,4} containing the relation {(1,2),(1,4),(3,3),(4,1) }（include every element in the set）is R, then the equivalence class induced from R is {1,2,4}，{3}.题干意味着1和2、4有关系，3和自己有关系，得之
• 课件上12、13、14等证明题看看，有些复杂但是抓住定义的核心出发。

  9.6 偏序关系(poset\partial order)

  偏序指的是一种二元关系，它是自反的、反对称的和传递的。偏序关系是一种特殊的关系，它可以用来对集合中的元素进行排序。

定义在集合S上的关系R，如果满足自反、反对称和传递，则称为偏序。集合S 和定义在其上的偏序R一起被称为偏序集，记作（S，R）。集合S中的成员称为偏序集的元素。

偏序和等价在定义上的区别就在于，偏序关系是反对称的，而等价关系是对称的。

全序（线序）total order or a linear order

如果集合上关于某个关系，所有元素都可比，那么就称这个关系是全序或者线序的，也叫链chain。全序关系是一种特殊的偏序关系。

良序 well-ordered set

如果有限的全序集存在最小元素，这时候就称这个有限的全序集为良序集。

字典顺序

在两个偏序集（有序对的第一个元素和第二个元素所存在的偏序集合）的笛卡尔积上构造一个偏序。

Hase diagram

从图转变为哈斯图：

1. 去掉环
2. 去掉形如（a,c）的传递关系边，保留形如（a,b）,(b,c)的中间环节
3. 调整结点位置，小的放最下面，大的放最上面,这样边的方向也可以去掉了

不相连的结点就是不可比的。

最大元最小元/极大元极小元/上下界

在哈斯图中很容易识别出极大极小元(maximal element/minimal element)，就是最上面和最下面的元素。但是一个偏序可以有多个极大极小元。

有时在偏序集中存在一个元素大于每个其他元素，这样的元素称为最大元(greatest/least element)。当最大元存在时，他是唯一的。类似地，如果偏序集中存在一个元素小于每个其他元素，这样的元素称为最小元。当最小元存在时，他也是唯一的。

有时可以找到一个元素大于或等于偏序集的子集中的所有元素，这样的元素称为这个子集的上界，类似地，如果偏序集中存在一个元素小于或等于偏序集的子集中的所有元素，这样的元素称为这个子集的下界。

lattice 格

lattice的定义：设P是一个偏序集，如果P中任意两个元素都有最小上界和最大下界，则称P为格。

例如（Z^+,|）就是一个格，任意两个元素的最小上界是他们的最小公倍数，最大下界是他们的最大公约数。

格的判定

从一个哈斯图判断不是格，需要找到某两个结点，他们的上界集或者下界集中找不到最小/最大元。

topological sorting 拓扑排序

每个有穷非空偏序集，至少有一个极小元。

找到最小的然后把他删去，重复直到结束。

拓扑排序的本质是输入一个部分有序集，输出一个全部有序集。

比的不是数值的大小，是按照拓扑关系进行排序的。

第十章 图

10.1~10.2基本概念

• pseudo-graph 伪图：允许有自环和重边
• simple graph 简单图：不允许有自环和重边
• complete graph 完全图：每两个顶点之间都有边
• subgraph 子图：G的子图是G的顶点和边的子集

结论!Attention

• 无向图 奇数度的结点 有 偶数个
• 简单图 节点度数 小于 节点数
• 握手定理：对于任何图G，$\sum_{v\in V}deg(v)=2|E|$

  简单图

• 完整图$k_n$，边数为$\frac{n(n-1)}{2}$
• 圈图cycle：每个顶点的度都是2的简单图，记作$C_n$。$C_n$有n个顶点和n条边。

• 轮图wheel：给圈图$C_n$添加另一个顶点，并把这个新顶点与$C_n$中的n个顶点相连，得到的图称为轮图$W_n$。Graph $𝑊_n$ have n+1 vertices and 2n edges.

• n立方体图cubes：n立方体图$Q_n$是一个具有2^n个顶点的图，其中每个顶点都有n个邻接顶点，每个顶点的度都是n。用n bits来给顶点编号，那么只有编号是1位不同的顶点是相邻的。n+1立方体图只需要copy一份n立体图，然后编号再加一位。

  • 沿cube-n图中的一条边移动相当于将节点的二进制串修改一位。要沿回路回到起点，那么必对原二进制串修改了偶数次。因此，当n≥1时，$Q_n$ 是二分图。
  • 𝑄_𝑛有$2^n$个节点，每个节点有n条边，每条边计算了2次，所以边数为$\frac{n2^n}{2}=n2^{(n−1)}$
• $K{m,n}$:complete bipartite graph，m个顶点和n个顶点的两个集合，两个集合中的顶点之间都有边，两个集合中的顶点之间没有边。$K{m,n}$有m+n个顶点，mn条边。

二分图bipartite graph

二分图是一种特殊的图，它的顶点可以分成两个不相交的集合，使得每条边的两个顶点都分别属于两个不同的集合。二分图也称为二部图。称（V1,V2）为G顶点集的一个二部划分。

完全二分图：一个集合中的每一个顶点都与另一个集合中的每一个顶点相连的二分图。

• n立方体图记作Qn，是用顶点表示2n个长度为n的位串的图。沿cube-n图中的一条边移动相当于将节点的二进制串修改一位。要沿回路回到起点，那么必对原二进制串修改了偶数次。因此，当n≥1时，$Qn$ 是二分图。$𝑄𝑛$有$2^n$个节点，每个节点有n条边，每条边计算了2次，所以边数为$\frac{n2^n}{2}=n2^{(n−1)}$

• 引理：无向图G是二分图的充要条件是G的所有回路的长度为偶数。

二分图和匹配

寻找一种把工作分配给员工的方法可以视为在图模型中寻求匹配，其中，在简单图G=(V，E)中的一个匹配M就是图中边集E的子集，该子集中没有两条边关联相同的顶点。换句话说，匹配是边的子集，假设{s，t}和{u，v} 是匹配中不同的边，那么s、t、u和v是不同的顶点。若一个顶点是匹配M中的一条边的端点，则称该顶点在M中被匹配;否则称为未被匹配。包含最多边数的一个匹配称为最大匹配。在二分图G=(V，E)中的一个匹配M，其划分为(V1，V2)，若V:中的每个顶点都是匹配中的边的端点或|M|= |V|，则称匹配M是从V1到V2的完全匹配。

• 匹配：一个图的匹配是一个边的集合，其中任意两条边都没有公共顶点。
• 完全匹配：如果一个匹配包含图中的所有顶点，则称这个匹配为完全匹配。

• 最大匹配：一个图的最大匹配是边数最多的匹配。

• 霍尔婚姻定理:带有二部划分(V1, V;)的二分图G=(V, E)中有一个从V1到V2的完全匹配当且仅当对于V1的所有子集A,有|N(A)|≥|A|。

其他类型的图应用

• 局域网拓扑结构：star、ring和bus
• 并行计算的互联网络：
  并行算法把问题分成若干可并发解决的子问题。使用并行处理的时候，一个处理器需要另一个处理器产生的输出。因此这些处理器需要互连。可用适当类型的图来表示这些互连。常用的互连网络有以下几种：
  • 线性阵列：
    除了$P_1$和$P_n$之外的每个处理器都通过双向连接与相邻处理器$P_i-1$和$P_i+1$相连。这种互连网络的拓扑结构是一条线性的链。每个处理器最多有2个和其他处理器的直接连接。缺点是为了让处理器共享信息，有时候需要使用大量的称为“眺”的中间连接。
  • 栅格网络（或二维阵列）：
    是一种通用的互连网络，它可以用来连接处理器。处理器个数是2的平方数，双向连接把处理器连接到上下左右的四个处理器上（边界上的是2或3个）。
  • 超立方体网络：
    处理器个数是$2^m$。每个处理器都有到其他m个处理器的双向连接。连接到处理器P_i上的处理器的下标二进制表示恰好和i的二进制有一位不同。这种互连网络的拓扑结构是一个m维的超立方体。($Q_m$)。

从旧图构造新图

• 删除或者增加边
  • G-e=(V,E-{e})
  • G+e=(V,E∪{e})
• 边的收缩
  有时候我们在删除边之后不希望将该边的端点作为独立的顶点保留在所得到的子图中。这个情况下我们进行边的收缩。边的收缩就是将边的两个端点合并成一个顶点，然后删除原来的两个顶点，同时将原来与这两个顶点相邻的边都与新顶点相邻。
• 删除顶点
  • G-v=(V-v,E’)
  • G-V’=(V-V’，E’)
• 图的并集
  新的图的顶点集是两个图的顶点集的并集，新图的边集是两个图的边集的并集。

  10.3 图的表示和图的同构

  图的表示

• 邻接矩阵
• 邻接表
• 关联矩阵（边-顶点矩阵，用0-1表示顶点是否与边相关联）

  图的同构(isomorphism)

  如何判断两个图同构？

  图形不变量：图的某些性质在图同构的变换下保持不变，这些性质称为图的不变量。如果两个图同构，那么它们的不变量一定相等。但是如果两个图的不变量相等，它们不一定同构。

  图同构算法

  例如从顶点的度、相邻关系、路径（回路长度、数量等）方面判断是否同构。
• 特定度的顶点数量和边的数量
• 不同度的顶点之间的邻接关系
• 回路的长度和数量
• 答题的时候如果是同构，则写出顶点之间的对应关系

  10.4 连通性

• path通路
• circuit回路
• 割点：删去该点和关联的边之后连通子图数目增加
• 点连通度：割点集中最小的割点数目
• 割边：删去该边之后连通子图数目增加
• 边连通度：割边集中最小的割边数目

• 有向图的最大强连通分支&最大弱连通分支：

  • 有向图的强连通分支：~
  • 有向图的弱连通分支：对应的无向图的最大连通分支

• 邻接矩阵的幂：$A^k$中的元素$a_{ij}$表示从顶点i到顶点j的长度为k的路径数目。

证明题

1. Prove that the undirected graph is a connected graph or its complementary graph is a connected graph.
   如果图G(V,E)不连通的话，它的顶点可以分为两个非空集合A,B，其中对于任意在A中的点P和任意在B中的点Q都没有PQ这条边。
   这样的话，取其补图G’，则对于任意在A中的点P和任意在B中的点Q都有PQ这条边。这样的话，对于任意两点P,Q，如果它们分别处于A,B的话，它们之间就有边相连；否则，不失一般性设它们都在A中，由于B非空，我们可以在B中任取一点R，我们知道PR和QR这两条边都是存在的，所以P,Q是连在一起的。综上，知G’连通。

2. 若无向图G中只有两个奇数度结点，则这两个结点一定连通。
   证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。

10.5 欧拉通路和哈密顿通路

欧拉通路和欧拉回路（针对边）

• 欧拉通路：一条通路，经过图中每条边一次且仅一次
• 欧拉回路：一条回路，经过图中每条边一次且仅一次

条件

1. 欧拉回路：所有节点的度都是偶数
2. 一个图有欧拉通路而没有欧拉回路：有且仅有两个节点的度是奇数，其他节点的度都是偶数
3. Complete undirected graph Kn is an Euler graph when n is odd

   哈密顿通路与哈密顿回路

• 哈密顿通路：一条通路，经过图中每个顶点一次且仅一次
• 哈密顿回路：一条回路，经过图中每个顶点一次且仅一次
• 我们可以在$K_n$的任意一个顶点来构造一个哈密顿回路。

  充分条件（注意不是充要条件）

1. 狄拉克定理：如果G是一个有n个顶点的简单图，且n>=3，如果G的每个顶点的度数都大于或等于n/2，则G有哈密顿回路。
2. 欧尔定理：如果G是一个有n个顶点的简单图，且n>=3，并且对于G中每一对不相邻的顶点u和v，都有deg(u)+deg(v)>=n，则G有哈密顿回路。
3. $C_5$不符合以上两条，但是有哈密顿回路。

   证明不含有哈密顿回路

4. 任何含有度为1的节点的图都不含有哈密顿回路
5. 度为2的节点关联的两条边属于任意一条哈密顿回路。但不可能出现有四条边关联到同一个节点的情况。

练习

• $𝐾_𝑁$有$\frac{(𝑁(𝑁−1))}{2}$条边，每个哈密尔顿回路有$N$条边，因此边不重复的哈密尔顿回路最多有$⌊(𝑁−1)/2⌋$条
• A graph with cut edge cannot be an Euler graph. 欧拉图(存在欧拉回路的图)中的欧拉回路删除任意一条边之后仍是一条path，如果图中存在割边，那么删除这条边之后，会形成两个不连通的图。哈密尔顿图同理。
• A graph with cut vertex cannot be an Hamilton graph.
• If a graph is an Euler graph, it must be a strongly connected graph.

• Suppose G is an undirected simple graph with n vertices and m edges, and $𝑚=\frac{1}{2}(𝑛−1)(𝑛−2)+2$. Prove that G is a Hamilton graph. 证明：证G中任何不相邻两结点度数之和不小于n。

  反证法：若存在两结点u，v不相邻且 $d(u)+d(v) ≤ n-1$ , 设G1为G删去u,v两结点以及所有与u或v相连的边后的图。则G1为具有n-2个结点的简单图，它的边数$m’≥（\frac{1}{2}）\times（n-1）\times（n-2）+2-（n-1）$，所以$m’≥(1/2)\times (n-2)\times (n-3)+1$，这与G1是$n-2$个结点的简单图的题设矛盾（边数应该小于$K_{n-2}$的边数），因而G中任何两个相邻的结点度数和不少于n。所以G为Hamilton图。

10.6 最短通路问题

旅行商问题

• 旅行商问题：给定一个图，找到一条包含每个顶点一次且仅一次的回路，使得这条回路的长度最小。

TSP Problem: A traveling salesman wants to visit each of n cities exactly once and return to his starting point.

In which order should he visit these cities to travel the minimum total distance.

For a n cities TSP problem, there are $(n-1)!/2$ different Hamilton circuits to examine.

10.7 平面图

• planar平面图：可以画在平面上使得任何两条边都不交叉的图。这样的画法称为图的平面表示。
• region面：平面图的平面表示把整个平面分割成若干个区域，这些区域称为面，包括一个无界的面(其实就是纸面背景)。
• 交叉点：平面图的平面表示中，边的交叉点称为交叉点。
• The degree of each region：每个面的度数是与该面相邻的边数。

  10.7.2 欧拉公式

  欧拉公式：对于任何连通平面图，有$|V|-|E|+|F|=2$，其中|V|是顶点数，|E|是边数，|F|是区域数（面数），有时候也写作|r|。

以下推论是证明平面图的必要不充分条件而不是充要条件：

• 推论1：若G是e条边v个顶点的连通平面简单图，其中$v>=3$，则$e<=3v-6$。
• 推论2：若G是平面连通图，则G中有度数不超过5的顶点
• 推论3：若连通平面简单图有e条边v个顶点，$v>=3$并且没有长度为3的回路，则$e<=2v-4$。

  10.7.3 库拉兔斯基定理

• 初等细分：删除一条边（u, v），新增一个顶点(w)和两条边(w,u)、(w,v)。这样的操作称为初等细分。
• 同胚(homeomrphic)：如果两个图可以通过一系列初等细分互相转换，则称这两个图是同胚的。
• 库拉兔斯基定理：一个图是非平面图当且仅当它包含同胚于$K5$或$K{3,3}$的子图。

练习

• 想要判断是不是planar graph，先检验推论的必要条件，如果满足再尝试画出平面图表示
• 该图与K5有类似的结构，我们尝试通过判断其与K5同胚从而证明不是平面图（因为K5不是平面图）。
  首先移除度数不够4的顶点（因为K5中每个顶点度数都为4），即移除顶点f和顶点g。
  移除顶点f和顶点g后，边fd和边eg也随之移除。在顶点f和g上做elementary subdivision，从而连接ag和fb，从而与𝐾_5 同胚。
• Suppose that a connected planar simple graph with e edges and v vertices contains no simple circuits of length 4 or less. Show that e≤(5/3)v-(10/3) if v≥4.
• Proof: A connected planar simple graph drawn in the plane divides the plane into regions. The degree of each region is least 5 (Since the graphs discussed here are simple graphs contains no simple circuits of length 4 or less.)

2e≥5r. Hence, (2/5)e ≥r. Using r=e-v+2 we obtained e-v+2 ≤(2/5)e. It follows that e≤(5/3)v-(10/3).

1. The shape of a soccer ball can be represented by a polyhedron (多面体), called the truncated icosahedron(截断二十面体), whose faces are 12 regular pentagons(五边形) and 20 regular hexagons(六边形), having the same side length. Each pentagon is surrounded by 5 hexagons, whereas each hexagon is surrounded by 3 pentagons and 3hexagons.
   How many sides are there? And how many vertices?

• r, e, and v represent the number of regions, edges, and vertices of the graph
  Each side is shared by either two hexagons, or by one hexagon and one pentagon. There are 12 pentagons, each with 5 sides, and 20 hexagons, each with 6 sides.
  Therefore, summing the number of sides of each face, we get a total of 12 · 5 + 20 · 6 = 180 edges, but each edge is being counted twice (over counting), so the actual number of edges is e = 180/2 = 90.

Now, from the Euler formula, we have that v − e + r = 2. Since e = 90 and r = 12 + 20 = 32, we conclude that there are v = 60 vertices.

10.8 图着色

• 简单图的着色：用不同的颜色给图的顶点着色，使得任何两个相邻的顶点都着不同的颜色。这样的着色称为简单图的顶点着色。
• 图的色数：一个图的色数是给图的顶点着色所需的最少颜色数。记为$\chi(G)$
• 四色定理：平面图的色数不超过4。
• chromatic number：$\chi(G)$

  重要结论

• $K_n$的色数是n
• $C_n$的色数,如果n是偶数，那么$\chi(C_n)=2$，如果n是奇数，那么$\chi(C_n)=3$。
• 二分部图的色数是2，$K_{m,n}$的颜色数量是2；$Q_n$通常是二分图

  第九章 tree

  树：没有回路的连通图