离散数学笔记(个人向)

参考资料：
[1]: 离散数学复习笔记（已完结）
[2]: 离散数学期末复习笔记【精华版】
[3]: 离散数学笔记（期末复习用，持续更新…）
[4]: 离散数学学习笔记 - chy_2003 - 博客园
[5]: Markdown/LaTeX 数学公式和符号表

1.概述

离散数学分为四个主体部分：数理逻辑、集合论、代数系统以及图论。

2.数理逻辑

数理逻辑的演化

古典逻辑
- 三段论:大前提->小前提->结论
现代逻辑

包含有：

          命题逻辑
          谓词逻辑
        公理化集合论
           递归论
           证明论

1.命题逻辑

命题是一个能判断真假的陈述句，其包含:时间性、区域性、标准性
原子命题是指不能被分解成更简单命题的命题
命题连接词有否定，合取，析取，蕴含(条件)、等值 其中可以简述为或且非、所得、当且仅当
以值1为真，0为假，会有以下结果关系：
[注意]
1. 对于p->q,当且仅当p为真，q为假时，结果为假; 否则其他时候结果都应为真。
2. 对于p<->q来说，当且仅当p和q相同时，结果为真; 否则其余情况结果为假
3. 运算优先级 非>且>或>所得>当且仅当
  或者
  否定 > 合取 > 析取 > 条件 > 双条件
4. 不可兼或
- 又叫与或或者相似
- 符号是$\nabla$,实际上是$p\nabla q = \neg (p \leftrightarrow q)$
- 它是与双条件$\leftrightarrow$相对的算符，输出的内容是只要不相等结果就是真，相等结果就是假
1. 公式分类
  1. 重言式又叫永真公式，赋值永远是真的式子
  2. 矛盾式又叫永假公式，赋值永远是假的式子
  3. 可满足式 既有真值又有假值的式子
2. 命题等价
- 如果对两个公式Ａ,Ｂ不论作何种指派，它们的真值均相同，则称Ａ,Ｂ是逻辑等价的，亦说Ａ等价于Ｂ，记A⇔B.
- 定理 命题公式A⇔B的充要条件是A↔B为永真式。
- 常见的等价情况：
  1. $\neg \neg A \leftrightarrow A$ |负负得正
  2. $A \leftrightarrow A \vee A$
    $A \leftrightarrow A \wedge A$
  3. 结合律和交换律都成立
  4. $(A \vee B)\wedge C \leftrightarrow (A \wedge C)\vee(B \wedge C)$
    $(A \wedge B)\vee C \leftrightarrow(A \vee C)\wedge(B \vee C)$ |交换律成立
  5. 德·摩根律 $\neg (A \vee B) \leftrightarrow \neg A \wedge \neg B$ $\neg (A \wedge B) \leftrightarrow \neg A \vee \neg B$|取反开括号，括号内符号也要取反
  6. 双条件等价式 $A \leftrightarrow B \leftrightarrows (A \rightarrow B)\cap(B \rightarrow A)$ |当且仅当
  7. 互斥律 $A \vee \neg A = true$ $A \wedge \neg A = False$|自己与自己的反面辩证统一
  8. 吸收律 $A \vee (A \wedge B) \leftrightarrow A$ $A \wedge (A \vee B) \leftrightarrow A$|这个可以用维恩图解释
  9. 条件等价式* $A \rightarrow B \leftrightarrow \neg A \vee B$
  * 上述内容构成真值表.
- 证明两个命题公式等价，可以利用真值表进行等值演算或者利用等价代换(等价置换)进行证明。
1. 命题蕴含
- 命题公式Ａ称为永真蕴含命题公式Ｂ，当且仅当Ａ→Ｂ是一个永真式，记作：$A \Rightarrow B$
  *注意 $A \Rightarrow B$ 与 $A \rightarrow B$ 的区别
- 蕴含表
1. 条件否定
1. 与非
1. 或非
1. 对偶

2.范式

命题变项及其否定统称为文字。
由有限个简单合取式构成的析取式称为析取范式; 由有限个简单析取式构成的合取式称为合取范式。析取范式与合取范式统称为范式。
简单合取式又称小项，真值表中小项为“真”，全体小项的析取式（即为主析取范式）为永真式。
简单析取式又称大项，真值表中大项为“假”，全体大项的合取式（即为主合取范式）为永假式。
定理：对于任意命题公式，都存在与其等值的析取范式和合取范式。%给拆分命题提供了实证的支撑

定理：

* 一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式
* 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式

公式的析取范式与合取范式是不唯一的，公式的唯一的范式形式是主析取范式与主合取范式。
极项在含有$n$个命题变项的简单合取式(简单析取式)中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第$i$个命题变项或它的否定式出现在从左算起的第$i$位上(若命题变项无角标,就按字典顺序排列)，称这样的简单合取式(简单析取式)为极小项(极大项)。由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而$n$个命题变项共可产生$2^n$个不同的极小项。每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转化为十进制数为$i$，就将所对应极小项记作$m_i$。类似地，$n$个命题变项共可产生$2^n$个不同的极大项，每个极大项只有一个成假赋值，将其对应的十进制数$i$作极大项的角标，记作$M_i$。
关于极项，有以下结论：

* $2^n$个极大项/极小项互不等值
* $M_i$假，其余极大项真;$\ m_i$真，其余极小项假 * 设$m_i$和$M_i$是命题变项$p_1,p_2,p_3,…，p_n$形成的极小项和极大项，则会有以下转化关系: $\neg m_i \leftrightarrow M_i,\ \neg M_i \leftrightarrow m_i$
若由$n$个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项)，则称该析取范式(合取范式)为主析取范式(主合取范式)。
下面介绍求与给定公式等值的主析取范式和主合取范式的方法：
任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的
范式有很多的应用,以主析取范式为例,它可以用于：而主合取范式也是一样，可以通过将主析取范式与主合取范式互相转化的方法来实现：
主析取范式中没有出现的极小项的下标恰好是主合取范式中极大项的下标。于是，由公式的主析取范式，即可求出它的主合取范式。

3.推理理论

验证推理有效性的方法：

真值表    %把情况一个个写出来
命题推演

命题推演三要素：
```
推理依据
推理规则
推理方法
```

推理原则

1. P原则(引入前提原则)
在推导的任何步骤上，都可以引入前提。
2. T 规则(引入结论规则)
在推导过程中，如果前面有一个或多个命题公式永真蕴含命题公式 S，那么就可以把公式 S 也引入到推导过程之中。
3. CP规则
如果H1∧H2∧…∧Hn∧R => S,则H1∧H2∧…∧Hn => R→S

推理依据 主要指已知的逻辑等价式和逻辑蕴含式
推理
- 1.方法 直接证法 间接证法(反证法和附加前提条件证法,形如$A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$) 分情况证明法(形如$A_1\vee A_2\vee …\vee A_k\rightarrow B \Leftrightarrow (A_1\rightarrow B)\wedge(A_2\rightarrow B)\wedge…\wedge(A_k\rightarrow B)$) 2.种类 1）直接推理由一组前提，利用P规则，T规则直接推演得到有效结论的方法。 2）条件论证(附加前提条件证法) 如果要证明的结论是R→S形式，则可以把结论中R→S的前件R作为附加前提，与给定的前提一起推出后件S即可。 3）反证法又叫归谬法 要证明H1，H2，…，Hn=>C,只要证明 {H1，H2，…，Hn , ﹁C} 是不相容的即可解释：要证明H1，H2，…，Hn=>C,只要证明 H1∧H2∧…∧H3=>F 即可 4）归纳证明法方便推理在计算机上的实现。归结证明法又称消解法。首先介绍归结规则（归结定律）
  $(L \vee C_1)\wedge(\neg L \vee C_2)\Rightarrow C_1\vee C_2 $ *其中，$L$是一个变元，$C_1$和$C_2$是简单析取式。
  应用归结规则由两个含有相同变元(一个含变元，另一个含它的否定式)的简单析取式推出一个新的不含这个变元的简单析取式，对这个新的简单析取式又可以继续应用归结规则。 归结证明法的基本思想是采用归谬法，把结论的否定引人前提。如果推出空简单析取式，即推出$()$，则证明推理正确。 具体步骤为： (1) 把结论的否定引人前提 (2) 把所有前提，包括结论的否定在内，化成合取范式，并把得到的合取范式中的所有简单析取式作为前提 (3) 应用归结规则进行推 (4) 如果推出空简单析取式/推出0(即化到最后只剩下形如$A\wedge \neg A$的玩意)，则证明推理正确。 * 注意，在有的推理中，简单析取式只是一个文字，如$\neg q,s,\neg s$。在运用归结原理时，将它们看作$\neg q \vee 0,s\vee 0,\neg s\vee 0$进行计算
- 形式结构命题公式$A_1,A_2,…,A_k$推出$B$的推理正确|有效当且仅当
  
  蕴涵式$(A_1\cap A_2\cap …\cap A_k) \rightarrow B$为重言式。
  
  以上为推理的形式结构，并记为$(A_1 \wedge A_2 \wedge …\wedge A_k) \Rightarrow B$
推理定理(背下来或者画韦恩图理解) 可以把一个公式换成任何与它等值的公式，称作等值置换，简称置换。
推理证明设前提$A_1,A_2,…,.A_k$,结论$B$。如果一个公式序列的最后是B并且序列中的每一个公式或者是某个$A_i(1\leq i \leq k)$,或者是前面公式的有效结论，则称这个序列是由前提$A_1,A_2,…,A_k$推出结论$B$的证明。

4.谓词逻辑

前提

在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解，这样会产生两大缺点：
（1）不能研究命题内部的结构，成分和内部逻辑的特征；
（2）也不可能表达两个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。

完备集称$F:{0,1}^n \rightarrow { 0,1}$为n元真值函数。$F$的自变量为$n$个命题变项，值域为${0,1}$. 定理：每一个命题公式对应于一个真值函数，每一个真值函数对应于无数个命题公式。 设$S$是一个联结词集合(算符集)。如果任何$n$元真值函数都可以由仅含$S$中的联结词构成的公式表示，则称$S$是联结词完备集。
以下的联结词集都是完备集：
$S0={\neg,\wedge,\vee}$ $S1={\neg,\wedge,\vee,\rightarrow}$ $S2={\neg,\wedge,\vee,\rightarrow,\leftrightarrow}$ $S3={\neg,\wedge}$ $S4={\neg,\vee}$ $S5={\neg,\rightarrow}$
复合联结词即与非和或非两个关系算符。

与非：$p\uparrow q \leftrightarrow \neg(p\wedge q)$ 或非：$p \downarrow q \leftrightarrow \neg(p\vee q)$

*${\uparrow}$和${\downarrow}$都是联结词完备集。
谓语逻辑将原子命题分解成两部分：名称+行为，针对谓语分析的逻辑，被称为谓语逻辑。谓语逻辑是命题逻辑的扩充和发展。

客观世界中可以独立存在的具体或抽象对象称为个体,即名称; 表示个体的词称为个体词。若个体词以常量的方式表示特定个体，则称之为个体常量；若个体词以变量的方式泛指不确定的个体，则称之为个体变量。表示个体（客体）特征、性质或关系的词，称为谓词,即行为。

以下为相关性质:

谓词与个体常量一起可以表示一个命题;但如果对于一个含有个体变量的谓语函数，由一个谓词和一些个体变元组成的表达式，称为简单谓词函数。如果一个函数包含n个个体变元，则称为n元简单谓词函数。由简单谓词函数和命题连结词组成的表达式，称为复合谓词函数。谓词函数不是命题，只有当所有的个体变元都用确定的个体代入时，才表示一个命题。对于一个谓词函数，每个个体变元都有其取值范围，该取值范围，称为是该个体变元的个体域（论域）
量词
1. 全称量词 "$\forall$"的几种表示方法: $\forall x \ P(x)$: 对所有的$x$，$x$是$P(x)$情况 $\forall x \ \neg P(x)$: 对所有$x$，$x$不是$P(x)$的情况 $\neg \forall x \ P(x)$: 并不是对于所有的$x$，$x$是$P(x)$的情况 $\neg \forall x \ \neg P(x)$: 不存在一个$x$，使$x$不是$P(x)$的情况
2. 存在量词 "$\exists$"的几种表示用法： $\exists x \ P(x)$: 存在一个$x$，使$x$是$P(x)$的情况 $\exists x \ \neg P(x)$: 存在一个$x$，使$x$不是$P(x)$的情况 $\neg \exists x \ P(x)$: 不存在一个$x$，使得$x$是$P(x)$的情况 $\neg \exists x \ \neg P(x)$: 不存在一个$x$，使$x$不是$P(x)$的情况
例如： *要明确书写规范，先用括号()括住说明对象，再于其后用括号()括住行为事件(专用名词是谓语公式)
变元
1. 辖域紧接在量词后面括号内的谓语公式
  
  如$\forall x \ P(x)$中的$P(x)$
2. 约束变元 在量词的辖域内，且与量词下标相同的变元。
3. 自由变元当且仅当不受量词的约束。
范式转化对于一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。如何对复杂的命题，将其相近的量词变量合并，考察我们对命题转化的理解。
1. 谓词演算的等价式与蕴含式
2. 辖域转化 根据谓语公式等价的定义，当个体域$E={a_1,a_2,…，a_n}$，可以得出：
  1. $(\forall x)P(x) \Leftrightarrow P(a_1)\wedge P(a_2)\wedge…\wedge P(a_n)$ %任意是交
  2. $(\exist x)P(x) \Leftrightarrow P(a_1)\vee P(a_2)\vee…\vee P(a_n)$ %存在是并
  3. 定理：提出来或提进去$\neg$会使范围符号变号 $(\forall x)\neg P(x) \Leftrightarrow \neg(\exist x)\ P(x)$ $(\exists x)\neg P(x)\Leftrightarrow \neg(\forall x)\ P(x)$
  4. 分配律 $(\forall x)(P(x)\wedge Q(x)) \Leftrightarrow (\forall x)P(x)\wedge (\forall x)Q(x)$%析取全 $(\exist x)(P(x)\vee Q(x)) \Leftrightarrow (\exist x)P(x)\vee (\exist x)Q(x)$%合取并
  5. 半分配律 $ (\forall\ x)P(x)\vee (\forall x)Q(x)\Rightarrow(\forall\ x)(P(x)\vee Q(x))$ $(\exist\ x)(P(x)\wedge Q(x)) \Rightarrow (\exist x)P(x)\wedge (\exist x)Q(x)$ %背下来，画韦恩图理解，思路是大包小，大可能包小可能
  6. 关系扩张 $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\forall x)P(x)\rightarrow (\forall x)Q(x)$ $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\forall x)P(x)\leftrightarrow (\forall x)Q(x)$ %任意的对象支持关系的分配扩张
  7. 量词作用域的扩张和拓展一类："$\wedge$" 和"$\vee$" $(\forall x)(P(x)\wedge Q(y))\Leftrightarrow (\forall x)P(x)\wedge Q(y)$ $(\forall x)(P(x)\vee Q(y))\Leftrightarrow (\forall x)P(x)\vee Q(y)$ $(\exist x)(P(x)\wedge Q(y))\Leftrightarrow (\exist x)P(x)\wedge Q(y)$ $(\exist x)(P(x)\vee Q(y))\Leftrightarrow (\exist x)P(x)\vee Q(y)$ 二类："$\rightarrow$"注意符号变化 $(\forall x)(P(x)\rightarrow Q(y))\Leftrightarrow (\exist x)P(x)\rightarrow Q(y)$ $(\exist x)(P(x)\rightarrow Q(y))\Leftrightarrow (\forall x)P(x)\rightarrow Q(y)$%变号了 $(\forall y)(P(x)\rightarrow Q(y))\Leftrightarrow P(x)\rightarrow (\forall y)Q(y)$ $(\exist y)(P(x)\rightarrow Q(y))\Leftrightarrow P(x)\rightarrow (\exist y)Q(y)$%没变号 定理：打开谓语公式进行辖域分配时，若变量出现在推导符的左边，则打开后改变符号;若出现在推导符的右边时，则不用改变符号
    
    推导过程 $\because P(x)\rightarrow Q(y)\Leftrightarrow \neg P(x)\vee Q(y)$ $\therefore (\forall x)(P(x)\rightarrow Q(y)) \Leftrightarrow ((\forall x)\neg P(x))\vee Q(y) \Leftrightarrow \neg((\exist x)P(x))\vee Q(y) \Leftrightarrow (\exist x)P(x)\rightarrow Q(y)$ $\Box$ 其余也是同理，而$Q(y)$不变号是由于与辖域内的变量不一致，不受影响
    
    在谓词演算中，由于在前提和结论中的谓词公式常带有量词，因而要使用命题演算的等价式和蕴含式需要消去和添加量词。
3. 谓词演算的推理推论
  
  命题推理的基本元素推理规则：P规则、T规则、CP规则推理方法：真值表法、直接证法、间接证法推理依据：等价式、蕴含式
4. 谓语演算的推理规则
  
  指定：区域推个体
  推广：个体推区域
  
  全称指定(US) $(\forall\ x)P(x)\Rightarrow P(c)$
  %c代表个体域中的任意元素
  存在指定(ES)
  $(\exist\ x)P(x)\Rightarrow P(c)$
  % 1.c代表个体域中的部分元素
  % 2.在每次使用时都要引入不同的个体,例如x就是一种个体 全称推广(UG) $P(c)\Rightarrow (\forall\ x)P(x)$
  %c要能够代表个体域中的所有元素 存在推广(EG)
  $P(c)\Rightarrow (\exist\ x)P(x)$
  %显然易见
例如：
%老老实实把推导符左边和右边的式子分别都按照规律一步一步的推导出来，一相比对，若相同则推导成功

3.集合论

1.基本概念

集合是包含不同对象的一个无序的聚集。
集合元素在集合里面叫做包含，例如$A$包含$a$，记作$a\in A$
描述集合有以下几种方法：
列举法、集合构造法、叙述法

上述方法在计算机科学中处于奠基地位,对于循环遍历使用颇多
当两个集合拥有全部相同的元素，则称两个集合相等，写作${x\in A}\cap{x\in B}\Leftrightarrow A=B$
特殊集合
1. 空集 $\Phi = {x|p(x)\wedge \neg p(x)}$
  
  $\Phi$ 是任何集合的子集
2. 幂集 $P(A) = {B|B\subseteq A}$
  
  幂集是 $A$ 的所有子集的集合
3. 全集 $U$或$E$
  
  在一个相对固定的范围内，包含此范围所有元素的集合，称为全集

2.集合的运算

并($\cup$)
1. $A\cup A=A$ %幂等律
2. $A\cup B = B\cup A$ %交换律
3. $(A\cup B)\cup C = A\cup(B\cup C)$ %结合律
4. $A\cup \Phi = A$ %同一律
5. $A\cup E = E$ %零律
交($\cap$)
1. $A\cap A=A$ %幂等律
2. $A\cap B = B\cap A$ %交换律
3. $(A\cap B)\cap C = A\cap(B\cap C)$ %结合律
4. $A\cap \Phi = A$ %同一律
5. $A\cap E = E$ %零律
补($^\complement$) 设$E$为全集，则称$A^\complement$为$A$关于$E$的补集，记作

$A^\complement = {x|x\in E 且 x\notin A}$
差/相对补($-$)
设$A,B$为任意两个集合，$A-B$称为$A$与$B$的差集或者B相对于A的补集,定义为：

$A-B = {x|x\in A 且 x\notin B}$
子集个数定理：若$|A| = n$,即集合$A$有$n$个元素，则$A$的子集个数为$|P(A)| = 2^n$,或记作$2^{|A|}$
分配律&吸收律
1. $A\cap(B\cup C) = (A\cap B)\cup(A\cap C)$
2. $A\cup(B\cap C) = (A\cup C)\cap(B\cup C)$ %分配律
3. $A\cap(A\cup B) = A$
4. $A\cup(A\cap B) = A$ %吸收律
其余内容(较重要)
1. $(A^\complement)^\complement = A$ %双重否定律
2. $A\cup A^\complement = E$ %排中律
3. $A\cap A^\complement = \Phi$ %矛盾律
4. $(A\cup B)^\complement = A^\complement \cap B^\complement$ $(A\cup B)^\complement = A^\complement \cap B^\complement$ 德摩根律在集合中的应用，取补的过程等同于命题的取反或者矩阵的取逆
5. $\Phi^\complement = E$ $E^\complement = \Phi$
6. $A - B = A\cap B^\complement$
7. $A - B = A - A\cap B$
8. $A \subseteq B \Leftrightarrow B^\complement \cap A^\complement$
9. $(B - A)\cup A = B\cup A$
对称差($\oplus$或$\Delta$) 定义：$A\oplus B = (A - B)\cup(B - A)$ 性质：
1. $A\oplus B = B\oplus A$
2. $(A\oplus B)\oplus C = A\oplus(B\oplus C)$
3. $A\oplus \Phi = A$
4. $A\oplus A = \Phi$ %自己和自己怎们会有剩
5. $A\oplus A^\complement = E$
6. $A\cap (B\oplus C) = (A\cap B)\oplus(A\cap C)$ %分配律仍成立
7. 若$A\oplus B = C$，则$A\oplus C = B$ %背下来
容斥原理

极其非常重要，总结就是奇数个集合加，偶数个集合减，有点像$ln(x)$

设$A$和$B$是任意有限集合，则会有:
1. $$|A\cup B| = |A| + |B| - |A\cap B|$$ %二维的情况
2. $$|\bigcup\limits_{i=1}^n A_i| = \sum\limits_{k=1}^{n}(-1)^{k+1}(\sum\limits_{1\leq i_1\leq\cdots\leq i_k\leq n}|A_{i_1}\cap\cdots \cap A_{i_k}|)$$%n个集合的情况 定理：将集合概念带入概率空间$(\Omega,\mathcal{F},\mathbb{P})$, 则可以在概率论中也适用容斥原理,写作： $$\mathbb{P}(\bigcup\limits_{k=1}^{n}A_i)=\sum\limits_{k=1}^{n}(-1)^{k-1}\sum\limits_{I\subset{1,\cdots,n};|I|=k}\mathbb{P}(A_I)$$
3. $$|A^\complement\cap B^\complement| = |(A\cup B)^\complement|=|E|-|A\cup B|$$%德摩根律的应用
序偶与笛卡尔积
- 序偶
  有序二元组的称呼，可以看作一个有顺序的集合，相当于键值对，记作$<A,B>$。其中$<A,B> \neq <B,A>$*
- 笛卡尔积
  - 若$A$与$B$是集合，那么$A$与$B$的笛卡尔积相当于$A\times B$,表示为$$A\times B = {<a,b>|\forall a\in A, b\in B}$$
  - 除此之外，规定$A\times\Phi = \Phi \times A = \Phi$
  - 笛卡尔积支持分配律和交换律
  - $n$个集合的笛卡尔积 $$A_1\times A_2\times\cdots \times A_n = (A_1\times A_2\times \cdots\times A_{n-1})\times A_n = {<x_1,x_2,\cdots ,x_n>|x_i\in A_i}$$
  - 定理:设$A,B,C,D$是四个非空集合，则$A\times B\subseteq C\times D$当且仅当$A\subseteq C且B\subseteq D$

3.关系

一个$A$到$B$的二元关系就是$A\times B$的子集
关系具有互斥性。对于一个笛卡尔积$X\times Y$，里面的任意一个序偶$<x,y>$只能属于或者不属于关系$R$，记作： $<x,y>\in R$ 或者 $<x,y>\notin R$
几个域名
1. 前域: 在二元关系$R = <x,y>$中所有键值对的键值${x}$，记作:
  $$dom\ R={x|(\exist y)(<x,y>\in R)}$$
2. 值域: 在二元关系$R = <x,y>$中所有键值对的值${y}$,记作:
  $$ran\ R = {y|(\exist x)(<x,y>\in R)}$$
3. 域: 前域和值域的并集，泛指与关系$R$有联系的数的范围。记作：
  $$FLD\ R = dom\ R \cup ran\ R$$
关系矩阵对于两个有限集合$A$和$B$, $R$是从$A$到$B$上的一个二元关系，那么则有相应的关系矩阵: $$M = [r_{ij}]{m\times n}，r{ij} = <a_i,b_j>$$
性质:
1. 简而言之为自反、对称、传递三大性质。
  1. 1. 自反关系 $$\forall x\in X, xRx成立$$
  2. 反自反关系自反的修正，不可能出现$xRx$则为反自反
  3. 对称关系对于关系$R$, $\forall x,y\in X$,每当$xRy$，就有$yRx$成立。
  4. 反对称关系即对称的反面:
    $$\neg (\exist x,y\in X)(<x,y>\in R\ \And\ <y,x>\in R)$$
  5. 传递关系对于$x,y,z\in R$, 若$xRy,yRz$，则$xRz$成立
2. 性质在关系矩阵(邻接矩阵)上的体现：
  1. 自反：对角线元素全是1
  2. 对称：对称矩阵
  3. 传递：结合数据结构理解，或者是允许间接寻址
3. 性质在关系图(邻接表\图示)上的体现：
  1. 自反：关系图中每个结点均有自回路
  2. 对称：关系图中若两个结点之间有有向弧，则必成对出现
  3. 传递：可以路线规划，挨个遍历结点
复合关系

$R$是$X$到$Y$的关系，$S$是$Y$到$Z$的关系，则$R$和$S$的复合关系$R\sdot S$称为$R$和$S$的复合关系.

复合关系即考验元素在关系间是否具有传递性。
逆关系 $R$是$X$到$Y$的二元关系，将所有序偶的元素次序颠倒，得到的关系就是$R$的逆关系，记作 $R^\complement$
闭包运算例如以下实例：
集合的划分
1. 覆盖
设$A$是一个非空集合，$S={S_1,S_2,\cdots,S_n}$,当
(1) $S_i \neq \Phi,\ (i=1,2,\cdots,n)$ (2) $S_1\cup S_2\cup \cdots \cup S_n=A\ (i=1,2,\cdots,n)$ 则称$S$是$A$的 覆盖
1. 划分
设$S={S_1,S_2,\cdots,S_n}$是$A$的一个覆盖，且$$S_i\cap S_j = \Phi\ (i\neq j,1\leq i,j\leq n)$$,则称每个$S_i$均为$S$这个划分的一个划分 划分一定是覆盖，但覆盖不一定是划分*

4.等价\轨道

等价类

$R$是$A$上的等价关系，对于$\forall x\in A$,称集合$[x]_R$为由 $x$ 生成的 $R$ 等价类，写作：
$$[x]_R = {y|y\in A\wedge xRy}$$ 或可写作：
$$[x]_R = {y|y=R(x),x\in A}$$
简称为x的等价类，简单写作：
$$y\in [x]_R\Leftrightarrow xRy$$

关于等价类有以下的性质：
1. 等价类$[x]_R$是一个集合，且$[x]_R\subseteq A$
2. $[x]_R$中的元素是在等价关系中$R$，与$x$有等价关系$R$的所有元素组成的集合。
3. $[x]_R\neq \Phi\ 当\ x\in [x]_R$
4. $\forall x,y\in [z]_R,<x,y>\in R$
5. 一种等价关系是对集合的一种划分，一个元素必将属于且只能属于一个等价类
6. $[x]_R=[y]_R$ 当且仅当 $<x,y>\in R$
7. $[x]_R\cap[y]_R = \Phi$ 当且仅当 $<x,y>\in R$
8. 所有等价类的并是原集合$A$
商集
- 商集是一类特殊的等价类\划分
- 定义：
  
  $R$是$A$上的等价关系，由$R$的所有等价类构成的集合 $$A/R = {[a]_R|a\in A}$$ ，被称为$A$关于$R$的商集，记作$A/R$
  
  例如:
  $A$为全体自然数${0,1,2,3,\cdots}$，R为两倍关系，例如$<2,4>\in R$ 而 $<4,2>\notin R$,则$A/R$为所有自然偶数${0,2,4,6,\cdots}$
相容关系
1. 定义
对于$A$上的关系，若$R$是自反的、对称的，则称$R$是相容关系。
1. 相容类
设$R$是集合$A$上的相容关系，若$C\subseteq A$,如果对于$C$中任意两个元素 $a_1,a_2$ 有 $a_1Ra_2$ ,则称$C$是由相容关系$R$产生的相容类。
序关系
1. 偏序关系 是偏序即意味着有排序
- 对于$A$上的关系$R$，若$R$是自反的、反对称的、传递的，则成$R$是$A$的一个偏序关系，记为$\preccurlyeq$
- 设$\preccurlyeq$为偏序关系，$$若 <x,y>\in\ \preccurlyeq,则记为 x\preccurlyeq y, 读作"x小于或等于y"$$
- 序偶$<A,\preccurlyeq>$被称为偏序集
- 覆盖在偏序集$<A,\preccurlyeq>$中，设$R$为非空集合$A$上的偏序关系，$x,y\in A$。$$如果x<y且不存在z\in A 使得下x<z<y，则称y覆盖x$$
1. 链与反链
  - 在偏序集合$<A,\preccurlyeq>$中，对于$A$的一个子集，如果每两个元素都是有关系的，则称该子集为链(chain)
  - 反之，若$A$的子集中每两个元素都是无关系\找不到关系的，则称该子集是反链。
2. 全序关系
  - 在偏序集$<A,\preccurlyeq>$中，若$A$是一个链，则称$<A,\preccurlyeq>$为全序集合或者线序集合。
3. 哈斯图
  - 哈斯图是对序关系关系图的一种简化画法,参照偏序表示中用的哈斯图（hasse diagram）是什么？
  - 具体画法参见哈斯图的画法介绍或者哈斯图的画法，以及利用哈斯图寻找极大元之类
  偏序集的Hasse图的作法如下：
  1. 用小圆圈(或小圆点)表示集合A中的元素;
  2. 如果a≤b,且a≠b,则将代表a的小圆圈画在代表b的小圆圈的下方。
  3. 只有当a是b的直接前辈(后裔)时，才将代表a的小圆圈和代表b的小圆圈用直线连接。
  - 哈斯图的应用

5.函数

定义设$F$为二元关系，若任意$x\in dom\ F$都存在唯一的$y\in ran\ F$, 使得$xRy$成立，则称$F$为函数。对于函数$F$，如果有$xFy$存在，则记为$y=F(x)$，并称$y$为$F$在$x$的值
特征
1. $F$的前域就是函数$F(x)$的定义域，记作 $dom\ F = X$。
2. $F$的值域为$ran\ F$且满足 $ran\ F\subset Y$, 称集合$Y$是$F$的共域
特殊映射
1. 满射
  
  若$ran\ F = Y$,则称映射为满射或上映射
2. 单射
  
  不同的$x$对应不同的$y$不会出现重复映射的情况。
3. 双射
  
  若映射$F$即是满射，又是入射,则称这个映射是双射的
复合函数

设$F,G$是函数，则称$F\sdot G$是复合函数。它满足： (1) $dom(F\cdot G) = {x|(x\in dom\ F)\wedge(F(x)\in dom\ G)}$ (2) 任意$x\in dom(F\cdot G)$, 有$F\sdot G(x) = F(G(x))$
反函数

设$F: A\rightarrow B$，且$F$为双射，当$F^{-1}: B\rightarrow A$存在且为双射时，称$F:A\rightarrow B$有反函数,也就是$F^{-1}$。
特征函数
1. $X_A: E\rightarrow {0,1}$, $X_A(x) = 1 \Leftrightarrow x\in A$ ，称用1代表在集合内，0代表不在集合内的特殊函数$X_A$叫特征函数。
2. 当 $\Phi\subset A\subset E$ 时，$X_A$ 为满射。
集合规模
- 势
  1. 等势定义
  设$A$,$B$是集合，如果存在着从$A$到$B$的双射函数(单射+满射)，则称$A$和$B$是等势的。,记作$A\approx B$。
  1. 双射定义
  给定两个集合$A$和$B$，两个集合的元素一一对应，则$A$，$B$等势，记作$A\thicksim B$(双射)
  1. 常见集合的势
    1. $N\approx Z\approx Q\approx N\times N$
    2. 任何实数区间都与实数集合$R$等势
- 基数
  
  所有与集合 $A$ 等势的集合所组成的集合，叫做集合$A$的集合基数，记作$K[A]$。
- 可数
  1. 与自然数集合$N$等势的任意集合被称为可数的。
  2. 有限集 + 可数集 = 至多可数集
  3. 定理：可数集和任何无限子集是可数的。
  4. 任意无限集，必含可数子集
    任意无限集，必与某一真子集等势%无限与无限在一定规则下可以达成一一对应
- 定理：若集合$A$到$B$存在一个入射，则$A$势不大于$B$势，即$A\leq B$

4.代数系统

详细见于我的另外一条笔记《近世代数笔记(个人向)》，此处略

5.图论

1.图

定义

一个图是一个三元组$<V(G),E(G),\oint>$,其中$V(G)$是一个非空的结点集合，$E(G)$是边集合，$\oint$是$E$到结点序偶的函数。
1. 一个结点的度数，即连接该节点的边的数目，用$dut\ V$表示。若边有方向，则都可以分成出度、入度
2. 仅由孤立结点组成的图称为零图
3. 仅由一个一个孤立结点构成的图称为平凡图
4. 结点个数记为$deg\ V$
5. 含有平行边的图称为多重图
6. 不含由平行边和自环的图称为简单图
7. 由$n$个结点的无向完全图记作$K_n$
8. $n$个结点的无向完全图$K_n$的边数为$\frac{n}{2(n-1)}$
9. 如果$V(H)\subseteq V(G)$且$E(H)\subseteq E(G)$，则称$H$是$G$的子图，记作$H\subseteq G$
10. 若$H$是$G$的子图且$V(H)=V(G)$(结点情况相同)，则称$H$和$G$的生成子图。
11. 对于$G$的度数，$\Delta(G)$是$G$的最大度；$\delta(G)$是$G$的最小度
12. 若无向图$G=<V,E>$为连通图，图的结点集$V$有点集$V_1$，使得$G$中删除了$V_1$的所有结点以后，所得的图不再是连通图，但删除$V_1$的任何真子集后，所得的图仍是连通图，则可称$V_1$为点割集。当一个点构成点割集时，则称这个点是割点(使得体系能够连通的最关键的点)
13. 设无向图$G=<V,E>$为连通图，若边集$E_1$是$E$的子集，使得$G$中删除了$E_1$的所有边以后，所得的图不是连通图但删除了$E_1$的任何真子集后，所得的图仍是连通图，则称$V_1$为边割集。若一条边构成边割集，则称这条边是割边或者桥
14. 单向回路又被叫做初级回路.
性质
1. 每个图中，结点度数的总和等于边数的两倍 $$\sum\limits_{v\in V}deg\ V = 2|E|$$
2. 在任何图中，度数为奇数的结点必然是偶数个
3. 在有向图中,从顶点v0到顶点vn的一条路径是图中的边的序列,其中每一条边的终点是下一条边的起点。
路径与回路
1. 一条路径中，如果同一条边不出现两次，则称此路径是简单路径
2. 一条路径中，如果同一顶点不出现两次，则称此路径是基本路径(或叫链)
3. 如果路径的始点$V_0$和终点$V_n$相重合，即$V_n = V_0$，则此路径称为回路
4. 没有相同边的回路称为简单回路; 通过各顶点不超过一次的回路称为基本回路。
5. 路径$P$中所含的边的条数称为路径$P$的长度
连通
- 在无向图$G$中，若结点$u$和结点$v$之前存在一条路，则称$u$和$v$是连通的
- 连通性是结点集的等价关系。通过连通性，我们可以对这个图$G$做出一个划分，把$V$分成非空子集$V_1,V_2,V_3,\cdots,V_m$。使得两个结点$u_i$和$v_j$是连通的当且仅当它们同属一个$V_k$。
- 连通度k(G)
  
  记$$k(G) = min{|V_1||V_1是G的点割集}$$作为图$G$的点连通度(连通度)
  - 连通度数值上等于点割集元素个数，表示为了产生一个不连通图所需要删去的点的最少数目
  - 完全图$G$中，若 $k(G)=p-1$ 且删去 $p-1$ 个结点，会产生一个平凡图。
- 我们把子图$G(V_1),G(V_2),\cdots,G(V_m)$称作$G$的连结分支(不同划分)，把$G$的连通分支数目记作$W(G)$。
- 连通图(两种解释)
  1. 若图$G$只有一个连通分支，则$G$是连通图
  2. 如果图中任意一对顶点都是连通的，则称此图是连通图(也就是只有一种轨道),否则称$G$是非连通图。
- 边连通量
  
  $$\lambda(G) = min{|E_1||E_1是G的边割集}$$
  - 它在数值上等同于边割集的元素数目，表示为了产生一个不连通图需要删去的边最少数目
  - 对于一个不平凡图可以定义$\lambda(G) = 0$,此外一个不连通图也有$\lambda(G) = 0$。
- 定理：
  
  对于任何一个图，都有:$$k(G) < \lambda(G) < \delta(G)$$
- 一个连通无向图$G$中，结点$v$是割点的充要条件是：
  
  存在两个结点$u$和$w$，使得$u$和$w$的每一条路都通过$v$
强连通性和弱连通性
- 一个有向图$D=(V,E)$，将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图
- 如果一个有向图的基图是连通图，则有向图$D$是弱连通的，否则称$D$为非连通的.
- 若$D$中任意两点$u,v$都有从$u$可达$v$，或从$v$可达$u$,则称$D$是单向连通或者单侧连通的;
- 若$D$中每点$u$均可达其他任一点$v$,则称$D$是强连通的。
- 定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。
- 在简单有向图中，具有强连通性的最大图，称为强分图。
- 具有单侧连通性的最大子图，称为单侧分图。
- 具有弱连通性的最大子图，称为弱分图.
图的矩阵表示
1. 邻接表示
  - 即是在数据结构中学到的邻接表和邻接矩阵，主要介绍邻接矩阵.
  对于邻接矩阵$A$来说: 当$v_1\rightarrow v_2$时，$a_{ij} = 1$ 当$v_1\nrightarrow v_2$时，$a_{ij} = 0$ 在无向图中，$a_{ij} = a_{ji}$ ; 而在有向图中，$a_{ij} \neq a_{ji}$。
  - 定理：设$A(G)$是图$G$的邻接矩阵，则 $A(G)$ 中的$i$行，$j$列元素$a_{ij}$ 等于G中联结$v_i$和$v_j$的长度为l的路的数目
  - 若图的边无权重则无值域仅为${0,1}$; 反之若有权重则$a_{ij}$不一定为$1$
  - 对两个结点路径的探究应用面很广，例如马尔科夫链。找出最短路径有Dijkstra算法和Floyd算法；找出最短生成树(MST)的算法有Prim算法和Kruskai算法。以上详细见数据结构——图的应用算法详解
2. 可达性矩阵
  
  当$v_i$至少存在一条路到达$v_j$时，$a_{ij} = 1$ 当$v_i$不存在一条路到达$v_j$时或 $i=j$ 时，$a_{ij} = 0$
3. 完全关联矩阵&关联矩阵
  1. 关联矩阵关联矩阵$M(G)$是由$G$的结点和$G$的边集构成。
    
    当$v_i$关联$v_j$时，$a_{ij} = 1$ 当$v_i$不关联$v_j$时，$a_{ij} = 0$
    
    其具有相关性质如下：
    1. 图中每一边关联两个结点，故$M(G)$的每一列只有两个1.
    2. 每一行元素的和数是对应结点的度数。
    3. 一行中元素全为0，其对应的结点为孤立节点。
    4. 两个平行边其对应的两列相同。
    5. 同一个图当结点或边的编序不同时，其对应的$M(G)$仅有行序和列序的不同。
  2. 完全关联矩阵(有向图) 关联矩阵$M(G)$是由$G$的结点和$G$的边集构成的。
  当$v_i$是边$e_{ij}$的起点时，$a_{ij} = 1$ 当$v_i$是边$e_{ij}$的终点时，$a_{ij} = -1$ 当$v_i$不关联$v_j$时，$a_{ij} = 0$
  
  定理：如果一个连通图 $G$ 有 $r$ 个结点，则其完全关联矩阵 $M(G)$ 的秩为 $r-1$ ，即$$rank M(G) = r-1$$

2.特殊的图

欧拉图
- 参见哥尼斯堡七桥问题
- 给定无孤立节点图 $G$ ，若存在一条路，经过图中每边有且仅有1次，该条路称为欧拉路。
- 若存在一条回路，经过图中每条边一次且仅一次，则称为回路为欧拉回路。
- 具有欧拉回路的图也称作欧拉路。
- 一笔画定理：
  > 无向图 $G$ 具有一条欧拉路，当且仅当 $G$ 是连通的，且有零个或两个奇数度结点。
- 若对于有向图来说：
  - 给定有向图 $G$ ，通过图中每边有且仅有一次的一条单向路(回路)，称作单向欧拉路(回路)。
  - 一笔画定理
    
    有向图 $G$ 具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度[1]。
    一个有向图 $G$ 具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1[2]。
汉密尔顿图
- 详见于离散数学笔记（10.2）哈密顿图
- 欧拉图与哈密顿图对比，欧拉图遍历的是边，而哈密顿图遍历的是结点。
- 给定图 $G$ ，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。
- 若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。
- 具有汉密尔顿回路的图称作汉密尔顿图。
- 若图 $G＝<V，E>$ 具有汉密尔顿回路，则对于结点集 $v$ 的每个非空子集 $S$ 均有 $$W(G-S)≤|S|$$ 成立。其中 $W(G-S)$ 是 $G-S$ ($G$去掉$S$的剩余部分)中连通分支数。
- 汉密尔顿图的判定
  - 虽然汉密尔顿回路问题与欧拉回路问题在形式上极为相似，但对图G是否存在汉密尔顿回路还无充要的判别准则。
  - 下面是一个有 $n$ 个结点的无向图具有汉密尔顿路的充分条件：
    1. 若 $G$ 中每一对结点度数之和大于等于 $n-1$ ，则 $G$ 中存在一条汉密尔顿路。
    2. 若 $G$ 中每一对结点度数之和大于等于 $n$ ，则 $G$ 中存在一条汉密尔顿回路。
- 闭包给定 $G={V,E}$ ，有 $n$ 个结点，若将 $G$ 中度数之和至少为 $n$ 的非邻接结点点连接起来得到 $G'$ ，不断重复这一步骤，就得到了 $G$ 的闭包，记作 $C(G)$ .
平面图
- 详见于离散数学笔记（10.4）平面图和《图论》第三章：平面图
- 在一个平面画出一个图，如果图的每条边都互不相交，则称这个图为平面图,否则为非平面图。
- 如何判断是否相交：
  1. 观察法设$C=v_1v_2v_3···v_nv_1$是图$G$中的任何基本回路，$x=v_iv_j$和$x'=v_mv_n$是图$G$中的任意两条基本路径。若$x$和$x'$同在$C$的同一侧，则二者必然相交。
  2. 库拉托夫斯基定理
- 对于连通平面图 $G$ ，由图中的边所包围的区域，在区域内既无节点，也无边，这样的区域叫做面。
- 一个平面图，面数之和等于其边数的2倍
- 定理：(欧拉公式)
  
  设一个连通的平面图，$v$ 个结点，$e$ 个边和 $r$ 个面，则满足：
  $$v-e+r=2$$
  - 其关于具体情况有以下性质：
    1. 设 $G$ 是连通简单平面图，则满足:
      $$e\leq 3v-6$$
    2. 给定两个图 $G_1$ , $G_2$ ，如果它们是同构的，或者通过反复插入或出去度数为2的结点后，使得 $G_1$ 和 $G_2$ 同构，则称两图在2度结点内同构。
    3. 定理：(库拉图斯基定理)
      
      一个图是平面图，当且仅当它不包含与$K_{3.3}$或$K_5$ 同构的子图
      (也就是说，如果 K3,3 或 K5 可以通过不断细分变成这副图，则这幅图是非平面图。)
对偶图
- 对于每一个平面图，都有与其相对应的对偶图
- 1. 若 $G^*$ 与 $G$ 同构，称 $G$ 自对偶。
  2. 任何平面图 $G$ 的对偶图都是连通的。
- 如何构造对偶图：
  - 我们假设下面的例图是图$G$，与其对应的对偶图$G^$，那么对于G来说， **$G^$上面的每一个点，对应的是$G$里面的每一个面**.
    比如说下面就是$G^*$,红色的点就是对偶图中的点.
  - 对于 $G$ 中本来的每条边 $e$ ，他是两个面(比如说面 $f1$ 和 $f2$ )的交边，那么在对偶图里，我们对这两个面( $f1$ ，$f2$ )所映射在 $G^*$ 里的点连线( $f1^$ 连向 $f2^$ ). 如果 $f1 = f2$ (比如说 $G$ 中$5， 6$这条边)，边的两侧都是同一个面，那我们就建一条回边.
- 自对偶图
  - 如果图 $G$ 的对偶图 $G^*$ 同构于 $G$ ，则称图 $G$ 是自对偶图。
  - 关于自对偶有以下性质：
    1. 对于 $n$ 个结点的完全图 $K_n$ ，有$\chi(Kn) = n$
    2. 设 $G$ 为一个至少具有三个结点的连通平面图，则 $G$ 中必定有一个节点 $u$ ，使得 $$deg\ u ≤ 5$$
    3. 定理：
      
      任意平面图 $G$ 最多是$5-$色的
    4. 若 $G$ 是自对偶的，则 $e = 2v-2$ .
- 关于对偶的详情可见于帖子图论（十三）——平面图和对偶图或者平面图转对偶图、平面图->对偶图
图着色问题
- 图着色问题(Graph Coloring Problem, GCP)又叫着色问题，是最著名的$NP-$完全问题之一。
- 着色问题一般分为两类：
  1. 图的 $m$ 可着色判定问题给定无向连通图 $G$ 和 $m$ 种不同的颜色。用这些颜色为图 $G$ 的各顶点着色，每个顶点着一种颜色。是否有一种着色法使 $G$ 中每条边的 $2$ 个顶点着不同颜色。
  2. 图的 $m$ 可着色优化问题若一个图最少需要 $m$ 种颜色才能使图中每条边连接的 $2$ 个顶点着不同颜色，则称这个数 $m$ 为该图的色数。
- 关于着色问题的实践可见于帖子图着色问题（超详细！！！）
树与生成树
- 一个连通且无回路的无向图称为树。
- 度数为 $1$ 的结点称为树叶或者叶结点。
- 度数大于 $1$ 的结点称为分支结点或者内点。
- 一个无回路的无向图称为森林，它的每个连通分支是树。
- 关于树有以下性质：
  1. 给定图 $T$ ，以下关于树的定义是等价的：
    1. 无回路的连通图
    2. 无回路且 $e = v-1$，其中 $e$ 为边数，$v$ 为结点数。
    3. 连通且e = v-1
    4. 无回路，但增加一条新边，得到一个且仅有一个回路
    5. 连通，但是删去任一条边后不连通
    6. 每一对结点之间有一条且仅有一条路
  2. 任一棵树中至少有两片树叶(一个叶结点和一个根结点)
  3. 若图G的生成子图是一棵树，则称该树为G的生成树。
    - 设 $G$ 有一条生成树 $T$ ，则 $T$ 的边称作树枝。
    - 图中不在生成树中的边称作弦。
    - 所有弦的集合称作生成树T的补。
  4. 定理：
    
    连通图至少有一棵生成树
  5. 一条回路和任何一棵生成树的补至少有一条公共边。(why?)
  6. 一个边割集和任何生成树的补至少有一条公共边。(why？)
  7. 在图 $G$ 的所有生成树中，树的权重和最小的那棵生成树，称作最小生成树。求最小生成树的两种算法可见于《数据结构笔记(个人向)》中。
- 根树
  - 如果一个有向图在不考虑边的方向是是一棵树，那么，这个有向图称为有向树。
  - 一棵有向树，如果恰有一个结点的入度为 $0$ ，其余所有结点的入度都为 $1$ ，则称为根树(数据结构中的那种树出现了)。
  - 根数入度为 $0$ 的结点称为根，出度为 $0$ 的结点称为叶，出度不为 $0$ 的结点叫做分支枝点或者内点。
  - 根树包含一个或多个结点，这些结点中取一点称为根，则其他所有结点都被分成有限个子根树.
  - 在根树中，若每一个结点的出度小于或等于 $m$ ，则称这个树为m叉树。
  - 如果每一个结点的出度恰好等于 $m$ 或 $0$ ，则称这棵树为完全m叉树，若其所有树叶层次相同，称为正则m叉树。当m=2时，称为二叉树。
  - 在根树中，一个结点的通路长度就是从树根到此结点的通路中的边数。我们把分支枝点的通路长度称为内部通路长度。树的通路长度叫做外部通路长度。
  - 关于根树，我们有以下性质和定理：
    1. 设有完全 $m$ 叉树，其树叶数为 $t$ ，分枝结点数为 $i$ ，则：$$(m-1)i = t-1$$
    2. 若完全二叉树中有 $n$ 个分枝点，且内部通路长度的总和为 $I$ ，外部通路长度的总和为 $E$ ，则：$$E = I+2n$$
    3. 对于带 $t$ 个叶子的带权二叉树中，若带权为 $w_i$ 的树叶，其通路长度为$L(w_i)$ 。我们把$$w(T) = \sum\limits_{i=1}^{t} w_iL(w_i)$$ 称为该带权二叉树的权重。在所有带权的$w_1,w_2,w_3,\cdots w_t$的二叉树中，$w(T)$ 最小的那棵树称为最优树。
    4. 若 $T$ 为带权 $w_1\leq w_2\leq\cdots\leq w_t$的最优树，则：
      带权$w_1$,$w_2$的树叶$v_{w_1}$，$v_{w_2}$是兄弟结点。
      
      以树叶$v_{w_1}$，$v_{w_2}$为子结点的分枝结点，其内通路长度最长。
    5. 设 $T$ 为带权 $w_1≤ w_2,≤···≤w_t$ 的最优树，若将以带权 $w_1$ 和 $w_2$ 的树叶为子结点的分枝结点改为带权 $w_1+w_2$ 的叶子结点，从而得到一棵新树 $T'$ ，则这棵 $T'$ 也是最优树。
前缀码问题
- 也就是与哈夫曼编码有关的内容，即由哈夫曼树来构造的对应编码.
- 详细可以见于我的笔记《数据结构(个人向)》或者数据结构复习笔记

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

离散数学笔记(个人向)

1.概述

2.数理逻辑

1.命题逻辑

2.范式

3.推理理论

4.谓词逻辑

3.集合论

1.基本概念

2.集合的运算

3.关系

4.等价\轨道

5.函数

4.代数系统

5.图论

1.图

2.特殊的图

FilesExpand file tree

DiscreteMath_note.md

Latest commit

History

DiscreteMath_note.md

File metadata and controls

离散数学笔记(个人向)

1.概述

2.数理逻辑

1.命题逻辑

2.范式

3.推理理论

4.谓词逻辑

3.集合论

1.基本概念

2.集合的运算

3.关系

4.等价\轨道

5.函数

4.代数系统

5.图论

1.图

2.特殊的图