离散数学

离散数学的学习笔记，包含数理逻辑、集合论、图论

因为实际写作时间是很久之前了，有些图过期了，我也不知道补什么…

有些公式渲染有问题，日后无聊再来改了（

数理逻辑

命题逻辑

联结词

汇总

$$\begin{array}{rlrl}& （\mathrm{否}\mathrm{定}）& & \mathrm{\neg }P\\ & （\mathrm{析}\mathrm{取}）& & P\vee Q\\ & （\mathrm{合}\mathrm{取}）& & P\wedge Q\\ & （\mathrm{蕴}\mathrm{含}）& & P\to Q\\ & （\mathrm{双}\mathrm{蕴}\mathrm{含}）& & P\leftrightarrow Q\\ & （\mathrm{否}\mathrm{定}\mathrm{双}\mathrm{蕴}\mathrm{含}/\mathrm{不}\mathrm{可}\mathrm{兼}\mathrm{析}\mathrm{取}）& & P\bar{\vee }Q\\ & （\mathrm{否}\mathrm{定}\mathrm{蕴}\mathrm{含}）& & P\stackrel{c}{\to }Q\\ & （\mathrm{否}\mathrm{定}\mathrm{合}\mathrm{取}）& & P\uparrow Q\\ & （\mathrm{否}\mathrm{定}\mathrm{析}\mathrm{取}）& & P\downarrow Q\end{array}$$

真值表

$P$	$Q$	$\mathrm{\neg }P$	$P\vee Q$	$P\wedge Q$	$P\to Q$	$P\stackrel{c}{\to }Q$	$P\leftrightarrow Q$	$P\bar{\vee }Q$	$P\uparrow Q$	$P\downarrow Q$
$T$	$T$	$F$	$T$	$T$	$T$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$F$	$T$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$T$	$F$	$T$	$F$	$F$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$	$F$	$T$	$F$	$T$	$T$

定义联结词的优先次序为：$\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$

等价公式

定义

两个命题公式 $A,B$ 真值表完全相同，则称二者 等价，记为 $A⟺B$

常用的等价公式

$$\begin{array}{rl}& \mathrm{德}\mathrm{摩}\mathrm{根}\mathrm{律}：\\ \mathrm{\neg }(P\wedge Q)& ⟺(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)\\ \mathrm{\neg }(P\vee Q)& ⟺(\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)\\ \\ & \mathrm{分}\mathrm{配}\mathrm{律}：\\ P\vee (Q\wedge R)& ⟺(P\vee Q)\wedge (P\vee R)\\ P\wedge (Q\vee R)& ⟺(P\wedge Q)\vee (P\wedge R)\\ \\ \\ & \mathrm{同}\mathrm{一}\mathrm{律}：\\ P\wedge T& ⟺P\\ P\vee F& ⟺P\\ \\ & \mathrm{吸}\mathrm{收}\mathrm{律}：\\ P\vee (P\wedge Q)& ⟺P\\ P\wedge (P\vee Q)& ⟺P\\ \\ & \mathrm{零}\mathrm{律}：\\ P\vee T& ⟺T\\ P\wedge F& ⟺F\\ \\ & \mathrm{否}\mathrm{定}\mathrm{律}:\\ P\vee (\mathrm{\neg }P)& ⟺T\\ P\wedge (\mathrm{\neg }P)& ⟺F\\ \\ & \mathrm{幂}\mathrm{等}\mathrm{律}:\\ P\wedge P& ⟺P\\ P\vee P& ⟺P\\ \\ & \mathrm{杂}\mathrm{类}:\\ P\wedge Q& ⟺\mathrm{\neg }P\to Q\\ P\to Q& ⟺\mathrm{\neg }Q\to \mathrm{\neg }P\end{array}$$

重言式和蕴含式

定义

• 重言式：无论对分量作怎样的真值指派，真值均为 $T$ 的命题公式
• 矛盾式（永假式）：……真值均为 $F$ 的命题公式
• 蕴含式：当且仅当 $P\to Q$ 为重言式时，称 $P$ 蕴含 $Q$，记作 $P⟹Q$
  • 对于 $P\to Q$ ，
    $Q\to P$ 称为其 逆换式，
    $\mathrm{\neg }P\to \mathrm{\neg }Q$ 称为其 反换式，
    $\mathrm{\neg }Q\to \mathrm{\neg }P$ 称为其 逆反式

定理

命题公式 $A,B$ 等价的充要条件：
$A\leftrightarrow B$ 为重言式
或
$P⟹Q$ 且 $Q⟹P$

证明蕴含式

对于 $P⟹Q$ ，满足以下其一：

1. 假定 $P$ 真值为 $T$ ，若由此能推出 $Q$ 的真值为 $T$
2. 假定 $Q$ 真值为 $F$，若由此能推出 $P$ 的真值为 $F$

则 $P⟹Q$ 成立

蕴含的性质

• 对于 $P⟹Q$ ，若 P 为重言式，则 Q 必为重言式
• 蕴含关系式可传递的
• 若 $P⟹Q$ 且 $P⟹R$ 则 $P⟹(Q\wedge R)$
• 若 $P⟹Q$ 且 $R⟹Q$ 则 $(P\vee R)⟹Q$

最小联结词组

$\{\mathrm{\neg },\vee \}$ 或 $\{\mathrm{\neg },\wedge \}$ 或 $\{\uparrow \}$ 或 $\{\downarrow \}$

对偶与范式

定义

• 对偶式：
  对于命题公式 $A$ ，
  将其中所有的 $\wedge$ 与 $\vee$ 互换，$\uparrow$ 与 $\downarrow$ 互换，$T$ 与 $F$ 互换，
  得到新的命题公式 $A^{\ast }$
  则称 $A^{\ast }$ 与 $A$ 互为对偶式
• 合取范式：
  一个命题公式具有形式：$A_1\wedge A_2\wedge \cdots \wedge A_n$ 时称其为 合取范式
• 析取范式：
  一个命题公式具有形式：$A_1\vee A_2\vee \cdots \vee A_n$ 时称其为 析取范式
• 小项：
  $n$ 个命题变元的合取式，
  每个变元与其否定不能同时出现，且必须出现且仅出现一次
• 大项：
  $n$ 个命题变元的析取式，
  每个变元与其否定不能同时出现，且必须出现且仅出现一次
• 主析取范式：
  仅由小项析取所组成的公式
• 主合取范式：
  仅有大项合取所组成的公式
• 编码：
  对于一个命题变元 $P$ ，$P,\mathrm{\neg }P$ 分别记为 $0,1$
  则对于每个小项/大项可以用二进制编码表示
  如 $P\wedge \mathrm{\neg }Q\wedge R$ 可以表示为 $m_{010}$
• 编码表示主析取/合取范式：
  主析取范式可以表示为 $\sum _{i_1,i_2,\dots ,i_m}$
  主合取范式可以表示为 $\prod _{j_1,j_2,\dots ,j_n}$
  其中的 $i_k$ 为第 $k$ 个小项的二进制编码的十进制数
  其中的 $j_k$ 为第 $k$ 个大项的二进制编码的十进制数

求合取/析取范式步骤

1. 将公式中的联结词化为 $\mathrm{\neg },\wedge ,\vee$
2. 利用 德摩根律 将 $\mathrm{\neg }$ 移到各个命题变元之前
3. 利用 分配律、结合律 将公式归约为合取/析取范式

求主合取/主析取范式步骤

1. 化归为合取/析取范式
2. 除去合取/析取范式中所有为永真/假的合取/析取项
3. 合并相同的合取/析取项和所有相同的变元
4. 对合取/析取项补入没有出现的命题变元，然后用分配律展开公式

定理

• $\mathrm{\neg }A(P_1,P_2,\dots ,P_n)⟺A^{\ast }(\mathrm{\neg }{P}_1,\mathrm{\neg }{P}_2,\dots ,\mathrm{\neg }{P}_n)$
• 若 $A⟺B$ 则 $A^{\ast }⟺B^{\ast }$
• 任意两个不同的小项的合取式永假
• 全体小项的析取式永真
• 任意两个不同的大项的析取式永真
• 全体大项的合取式永假

推理理论

定义

• 前提、有效结论：
  对于命题公式 $H_1,H_2,\dots ,H_n,C$ ，
  当且仅当 $H_1\wedge H_2\wedge \cdots \wedge H_n⟹C$，
  称 $C$ 是 一组前提 $H_1,H_2,\dots ,H_n$ 的 有效结论
• $P$ 规则：
  前提在推导过程中的任何时候都可以引入使用
• $T$ 规则：
  在推导中，如果有一个或多个公式蕴含着公式 $S$ ，则 $S$ 可以引入推导中

真值表法

1. 列出 $H_1,H_2,\dots ,H_n,C$ 的所有对应真值
2. 找出 $H_1,H_2,\dots ,H_n$ 全为 $T$ 的行，若这几行对应的 $C$ 也有真值 $T$ 则推理成立

或者

2. 找出 $C$ 为 $F$ 的行，
   若这几行对应的 $H_1,H_2,\dots ,H_n$ 至少有一个真值为 $F$ 则推理成立

直接证法

例题： 证明 $(P\vee Q)\wedge (P\to R)\wedge (Q\to S)⟹S\vee R$

解：

$$\begin{array}{rlrlrlr}& (1)P\vee Q& & P& & （P\mathrm{规}\mathrm{则}，\mathrm{引}\mathrm{入}\mathrm{前}\mathrm{提}）& \\ & (2)\mathrm{\neg }P\to Q& & T(1)E& & （T\mathrm{规}\mathrm{则}，\mathrm{由}(1)\mathrm{等}\mathrm{价}\mathrm{得}\mathrm{到}(2)）& \\ & (3)Q\to S& & P& & （P\mathrm{规}\mathrm{则}，\mathrm{引}\mathrm{入}\mathrm{前}\mathrm{提}）& \\ & (4)\mathrm{\neg }P\to S& & T(2),(3)I& & （T\mathrm{规}\mathrm{则}，\mathrm{由}(2),(3)\mathrm{蕴}\mathrm{含}\mathrm{得}\mathrm{到}(4)）& \\ & (5)\mathrm{\neg }S\to R& & T(4)E& & （T\mathrm{规}\mathrm{则}，\mathrm{由}(4)\mathrm{等}\mathrm{价}\mathrm{得}\mathrm{到}(5)）& \\ & (6)P\to R& & P& & （P\mathrm{规}\mathrm{则}，\mathrm{引}\mathrm{入}\mathrm{前}\mathrm{提}）& \\ & (7)\mathrm{\neg }S\to R& & T(5),(6)I& & （T\mathrm{规}\mathrm{则}，\mathrm{由}(5),(6)\mathrm{蕴}\mathrm{含}\mathrm{得}\mathrm{到}(7)）& \\ & (8)S\to R& & T(7)E& & （T\mathrm{规}\mathrm{则}，\mathrm{由}(7)\mathrm{等}\mathrm{价}\mathrm{得}\mathrm{到}(8)，\mathrm{证}\mathrm{毕}）& \end{array}$$

~注：括号内仅为注释，实际书写中无括号内的内容~

间接证法

归谬法

对于要证明 $H_1\wedge H_2\wedge \cdots \wedge H_n⟹C$ 的情况，

只需要证明 $H_1\wedge H_2\wedge \cdots \wedge H_n\wedge \mathrm{\neg }C⟺F$，

其中 $\mathrm{\neg }C$ 称为 附加条件

例题： 证明：$A\to B,\mathrm{\neg }(B\vee C)$ 可逻辑推出 $\mathrm{\neg }A$

解：

$$\begin{array}{rlrlr}& (1)A\to B& & P& \\ & (2)A& & P(\mathrm{附}\mathrm{加}\mathrm{前}\mathrm{提})& \\ & (3)\mathrm{\neg }(B\vee C)& & P& \\ & (4)\mathrm{\neg }B\wedge \mathrm{\neg }C& & T(3)E& \\ & (5)B& & T(1),(2)I& \\ & (6)\mathrm{\neg }B& & T(4)I& \\ & (7)B\wedge \mathrm{\neg }B(\mathrm{矛}\mathrm{盾})& & T(5),(6)I\end{array}$$

$CP$ 规则

对于要证明 $H_1\wedge H_2\wedge \cdots \wedge H_n⟹R\to C$ 的情况，

只需要证明 $H_1\wedge H_2\wedge \cdots \wedge H_n\wedge R⟺C$，

其中 $R$ 称为 附加条件

例题： 证明：$A\to (B\to C),\mathrm{\neg }D\vee A,B$ 重言蕴含 $D\to C$

解：

$$\begin{array}{rlrlr}& (1)D& & P(\mathrm{附}\mathrm{加}\mathrm{前}\mathrm{提})& \\ & (2)\mathrm{\neg }D\vee A& & P& \\ & (3)A& & T(1),(2)I& \\ & (4)A\to (B\to C)& & P& \\ & (5)B\to C& & T(3),(4)I& \\ & (6)B& & P& \\ & (7)C& & T(5),(6)I\\ & (8)D\to C& & CP\end{array}$$

谓词逻辑

谓词

将 $A(a_1,a_2,\dots ,a_n)$ 中的 $A$ 称为 $n$ 元谓词

例如 $A$ 表示“是大学生”，$a$ 表示“张三”，

则 $A(a)$ 表示“张三是大学生”，其中 $A$ 为 一元谓词

命题函数

由一个谓词和一些客体变元组成的表达式，称为 简单命题函数

例如 $L(x,y,z)$

量词

用于划定论域的标记称作量词，

$\mathrm{\forall }x,\mathrm{\exists }x$ 分别表示 “所有的 $x$”、“存在一些 $x$”

例如：

1. 设 $M(x):x\mathrm{是}\mathrm{人}，H(x):x\mathrm{要}\mathrm{呼}\mathrm{吸}$
   则 $(\mathrm{\forall }x)M(x)\to H(x)$ 表示 “所有人都是要呼吸的”
2. 设 $P(x):x\mathrm{是}\mathrm{质}\mathrm{数}$
   则 $(\mathrm{\exists }x)(P(x))$ 表示 “存在一个数是质数”
3. 设 $M(x):x\mathrm{是}\mathrm{人}，R(x):x\mathrm{是}\mathrm{聪}\mathrm{明}\mathrm{的}$
   则 $(\mathrm{\exists }x)M(x)\wedge (R(x))$ 表示 “一些人是聪明的”

谓词公式与翻译

例题： 数学分析中的极限定义为：仍给一个小正数 $ϵ$ ，则存在一个正数 $\delta$ ，使得当 $0<|x-a|<\delta$ 时，有 $|f(x)-b|<\delta$，此时称 $\underset{x\to a}{lim}f(x)=b$

解：

设 $P(x,y):x\mathrm{大}\mathrm{于}y,Q(x,y):x\mathrm{小}\mathrm{于}y$

则 $\underset{x\to a}{lim}f(x)=b$ 可以表示为：

$$(\mathrm{\forall }ϵ)(\mathrm{\exists }\delta )(((P(ϵ,0)\to P(\delta ,0))\wedge Q(|x-a|,\delta ))\to (Q(|f(x)-b|,\delta ))$$

变元的约束

约束变元的换名

通过对谓词公式换名，使得每个变元在公式中仅以一种约束形式出现

例题： 对 $(\mathrm{\forall }x)(P(x)\to R(x,y))\wedge Q(x,y)$ 换名

解： 可换名为 $(\mathrm{\forall }z)(P(z)\to R(z,y))\wedge Q(x,y)$

自由变元的代入

例题： 对 $(\mathrm{\forall }x)(P(y)\wedge R(x,y))$ 代入

解： 代入后公式为 $(\mathrm{\forall }x)(P(z)\wedge R(x,z))$

若论域的元素是有限的，如论域元素为 $a_1,a_2,\dots ,a_n$，则

$$\begin{gathered} (\mathrm{\forall }x)A(x)=A(a_1)\wedge A(a_2)\wedge \cdots \wedge A(a_n) \\ (\mathrm{\exists }x)A(x)=A(a_1)\vee A(a_2)\vee \cdots \vee A(a_n) \end{gathered}$$

谓词演算的等价式和蕴含式

量词与联结词 $\mathrm{\neg }$ 的关系

$$\begin{gathered} \mathrm{\neg }(\mathrm{\forall }x)A(x)⟺(\mathrm{\exists }x)\mathrm{\neg }A(x) \\ \mathrm{\neg }(\mathrm{\exists }x)A(x)⟺(\mathrm{\forall }x)\mathrm{\neg }A(x) \end{gathered}$$

有关量词的等价式

$$\begin{array}{rl}(\mathrm{\forall }x)A(x)\to B& ⟺(\mathrm{\exists }x)(A(x)\to B)\\ (\mathrm{\exists }x)A(x)\to B& ⟺(\mathrm{\forall }x)(A(x)\to B)\\ \\ B\to (\mathrm{\forall }x)A(x)& ⟺(\mathrm{\forall }x)(B\to A(x))\\ B\to (\mathrm{\exists }x)A(x)& ⟺(\mathrm{\exists }x)(B\to A(x))\\ \\ (\mathrm{\forall }x)(A(x)\wedge B(x))& ⟺(\mathrm{\forall }x)A(x)\wedge (\mathrm{\forall }x)B(x)\\ (\mathrm{\exists }x)(A(x)\vee B(x))& ⟺(\mathrm{\exists }x)A(x)\vee (\mathrm{\exists }x)B(x)\\ \\ (\mathrm{\forall }x)(A\vee B(x))& ⟺A\vee (\mathrm{\forall }x)B(x)\\ (\mathrm{\exists }x)(A\wedge B(x))& ⟺A\wedge (\mathrm{\exists }x)B(x))\\ \\ (\mathrm{\exists })(A(x)\to B(x))& ⟺(\mathrm{\exists })A(x)\to (\mathrm{\forall }x)B(x)\end{array}$$

有关量词的蕴含式

$$\begin{array}{rl}(\mathrm{\forall }x)A(x)\vee (\mathrm{\forall }x)B(x)& ⟹(\mathrm{\forall }x)(A(x)\vee B(x))\\ (\mathrm{\exists }x)(A(x)\wedge B(x))& ⟹(\mathrm{\exists }x)A(x)\wedge (\mathrm{\exists }x)B(x)\\ \\ (\mathrm{\forall })(A(x)\to B(x))& ⟹(\mathrm{\forall }x)A(x)\to (\mathrm{\forall }x)B(x)\\ (\mathrm{\forall })(A(x)\leftrightarrow B(x))& ⟹(\mathrm{\forall }x)A(x)\leftrightarrow (\mathrm{\forall }x)B(x)\\ \\ (\mathrm{\exists }x)A(x)\to (\mathrm{\forall }x)B(x)& ⟺(\mathrm{\forall }x)(A(x)\to B(x))\end{array}$$

多元谓词的等价/蕴含式

$$\begin{array}{rl}(\mathrm{\forall }x)(\mathrm{\forall }y)A(x,y)& ⟺(\mathrm{\forall }y)(\mathrm{\forall }x)A(x,y)\\ (\mathrm{\exists }x)(\mathrm{\exists }y)A(x,y)& ⟺(\mathrm{\exists }y)(\mathrm{\exists }x)A(x,y)\\ \\ (\mathrm{\forall }x)(\mathrm{\forall }y)A(x,y)& ⟹(\mathrm{\exists }x)(\mathrm{\forall }y)A(x,y)\\ (\mathrm{\forall }x)(\mathrm{\forall }y)A(x,y)& ⟹(\mathrm{\forall }x)(\mathrm{\exists }y)A(x,y)\\ (\mathrm{\forall }x)(\mathrm{\forall }y)A(x,y)& ⟹(\mathrm{\exists }y)(\mathrm{\forall }x)A(x,y)\\ (\mathrm{\forall }x)(\mathrm{\forall }y)A(x,y)& ⟹(\mathrm{\forall }y)(\mathrm{\exists }x)A(x,y)\\ \\ (\mathrm{\exists }y)(\mathrm{\forall }x)A(x,y)& ⟹(\mathrm{\forall }x)(\mathrm{\exists }y)A(x,y)\\ (\mathrm{\exists }y)(\mathrm{\forall }x)A(x,y)& ⟹(\mathrm{\forall }x)(\mathrm{\exists }y)A(x,y)\\ \\ (\mathrm{\forall }x)(\mathrm{\exists }y)A(x,y)& ⟹(\mathrm{\exists }x)(\mathrm{\exists }y)A(x,y)\\ (\mathrm{\forall }y)(\mathrm{\exists }x)A(x,y)& ⟹(\mathrm{\exists }y)(\mathrm{\exists }x)A(x,y)\end{array}$$

前束范式

定义

• 前束范式： $(◻v_1)(◻v_2)\dots (◻v_n)A$
• 前束合取范式：
  $(◻v_1)(◻v_2)\dots (◻v_n)[(A_{11}\vee A_{12}\vee \cdots \vee A_{1l_1})\wedge (A_{21}\vee A_{22}\vee \cdots \vee A_{2l_2})\wedge \cdots \wedge (A_{m1}\vee A_{m2}\vee \cdots \vee A_{m{l}_m})]$
• 前束析取范式：
  $(◻v_1)(◻v_2)\dots (◻v_n)[(A_{11}\wedge A_{12}\wedge \cdots \wedge A_{1l_1})\vee (A_{21}\wedge A_{22}\wedge \cdots \wedge A_{2l_2})\vee \cdots \vee (A_{m1}\wedge A_{m2}\wedge \cdots \wedge A_{m{l}_m})]$

例题： 将 $D:(\mathrm{\forall }x)[(\mathrm{\forall }y)P(x)\vee (\mathrm{\forall }z)q(z,y)\to \mathrm{\neg }(\mathrm{\forall }y)R(x,y)]$ 化为前束合取范式

解：

$$\begin{array}{rl}& 1.\mathrm{消}\mathrm{去}\mathrm{多}\mathrm{余}\mathrm{量}\mathrm{词}\\ & D⟺(\mathrm{\forall }x)[P(x)\vee (\mathrm{\forall }z)q(z,y)\to \mathrm{\neg }(\mathrm{\forall }y)R(x,y)]\\ & 2.\mathrm{换}\mathrm{名}\\ & D⟺(\mathrm{\forall }x)[P(x)\vee (\mathrm{\forall }z)q(z,y)\to \mathrm{\neg }(\mathrm{\forall }w)R(x,w)]\\ & 3.\mathrm{消}\mathrm{去}\mathrm{条}\mathrm{件}\mathrm{联}\mathrm{结}\mathrm{词}\\ & D⟺(\mathrm{\forall }x)[\mathrm{\neg }(P(x)\vee (\mathrm{\forall }z)q(z,y))\vee \mathrm{\neg }(\mathrm{\forall }w)R(x,w)]\\ & 4.\mathrm{将}\mathrm{\neg }\mathrm{放}\mathrm{入}\mathrm{括}\mathrm{号}\mathrm{内}\\ & D⟺(\mathrm{\forall }x)[(\mathrm{\neg }P(x)\wedge (\mathrm{\exists }z)\mathrm{\neg }q(z,y))\vee (\mathrm{\exists }w)\mathrm{\neg }R(x,w)]\\ & 5.\mathrm{将}\mathrm{量}\mathrm{词}\mathrm{化}\mathrm{到}\mathrm{左}\mathrm{侧}\\ & D⟺(\mathrm{\forall }x)(\mathrm{\exists }z)(\mathrm{\exists }w)[(\mathrm{\neg }P(x)\wedge \mathrm{\neg }q(z,y))\vee \mathrm{\neg }R(x,w)]\\ & 6.\mathrm{化}\mathrm{简}\mathrm{得}\mathrm{到}\mathrm{结}\mathrm{果}\\ & D⟺(\mathrm{\forall }x)(\mathrm{\exists }z)(\mathrm{\exists }w)[(\mathrm{\neg }P(x)\vee \mathrm{\neg }R(x,w))\wedge (\mathrm{\neg }q(z,y)\vee \mathrm{\neg }R(x,w))]\end{array}$$

谓词演算的推理理论

$$\begin{gathered} \mathrm{全}\mathrm{称}\mathrm{指}\mathrm{定}\mathrm{规}\mathrm{则}(US)： \\ \frac{(\mathrm{\forall }x)P(x)}{\therefore P(c)} \\ \mathrm{全}\mathrm{称}\mathrm{推}\mathrm{广}\mathrm{规}\mathrm{则}(UG)： \\ \frac{P(x)}{\therefore (\mathrm{\forall }x)P(x)} \\ \mathrm{存}\mathrm{在}\mathrm{指}\mathrm{定}\mathrm{规}\mathrm{则}(ES)： \\ \frac{(\mathrm{\exists }x)P(x)}{\therefore P(c)} \\ \mathrm{存}\mathrm{在}\mathrm{推}\mathrm{广}\mathrm{规}\mathrm{则}(EG)： \\ \frac{P(c)}{\therefore (\mathrm{\exists }x)P(x)} \end{gathered}$$

例题： 证明 $(\mathrm{\forall }x)(H(x)\to M(x))\wedge H(s)⟺M(s)$

解：

$$\begin{array}{rlrlr}& (1)(\mathrm{\forall }x)(H(x)\to M(x))& & P& \\ & (2)H(s)\to M(s)& & US(1)& \\ & (3)H(s)& & P& \\ & (4)M(s)& & T(2),(3)I& \end{array}$$

集合论

集合

集合的概念及表示

定义

• 子集（包含）：
  若有 $(\mathrm{\forall }x)(x\in A\to x\in B)$ 则称 $A$ 为 $B$ 的子集 或 $A$ 包含在 $B$ 内，
  记作 $A\subseteq B$

  • 包含关系具有自反性、传递性

• 真子集：
  若有 $(\mathrm{\forall }x)(x\in A\to x\in B)\wedge (\mathrm{\exists }x)(x\in B\wedge x\notin A)$ 则称 $A$ 是 $B$ 的真子集，
  记作 $A\subset B$

• 空集：
  不包含任何元素的集合，记作 $\varnothing$

  • $\varnothing \ne \{\varnothing \},\varnothing \in \{\varnothing \}$

• 全集：
  在一定范围内，若所有集合均为某一个集合的子集，
  则该集合称为 全集，记作 $E$

• 幂集：
  给定集合 $A$ ，由 $A$ 的所有子集为元素组成的集合，
  称为集合 $A$ 的 幂集，记作 $\mathcal{P}(A)$

• 编码表示幂集：

  $$\begin{gathered} \mathrm{例}\mathrm{如}:\mathrm{设}S=\{a,b,c\},\mathrm{则} \\ \mathcal{P}(S)=\{S_i|i\in J\}, \\ J=\{i|i\mathrm{是}\mathrm{二}\mathrm{进}\mathrm{制}\mathrm{数}\mathrm{且}000\le i\le 111\}， \\ \mathrm{其}\mathrm{中}{S}_{000}=\varnothing \end{gathered}$$

定理

• 集合 $A,B$ 相等的充要条件为：二者互为子集
• 对于任意一个集合 $A$ ，$\varnothing \subseteq A$
• 给定一个有 $n$ 个元素的集合 $A$ ，则 $\mathcal{P}(A)$ 有 $2^n$ 个元素

集合的运算

定义

• 交集 $\cap$：

  $$S=A\cap B=x|(x\in A)\wedge (x\in B)$$

  $S$ 称为 $A$ 和 $B$ 的 交集

• 并集 $\cup$：

  $$S=A\cup B=x|(x\in A)\vee (x\in B)$$

  $S$ 称为 $A$ 和 $B$ 的 并集

• 补集 $-$：

  $$S=A-B=\{x|x\in A\wedge x\notin B\}=A\cap \sim B=A-(A\cap B)$$

  $S$ 称为 $B$ 对于 $A$ 的补集

  • $E-A$ 称为 $A$ 的 绝对补，记作 $\sim A$

• 对称差 $\oplus$：

  $$\begin{array}{rl}S=A\oplus B& =\{x|x\in A\overline{\vee }x\in B\}\\ & =(A-B)\cup (B-A)\\ & =(A\cap \sim B)\cup (B\cap \sim A)\\ & =(A\cup B)-(A\cap B)\end{array}$$

  $S$ 称为 $A$ 和 $B$ 的 对称差

定理

• 公式

  $$\begin{array}{rl}A\cap (B\cup C)& =(A\cap B)\cup (A\cap C)\\ A\cup (B\cap C)& =(A\cup B)\cap (A\cup C)\\ A\cup (A\cap B)& =A\\ A\cap (A\cup B)& =A\\ \sim (A\cup B)& =\sim A\cap \sim B\\ \sim (A\cap B)& =\sim A\cup \sim B\\ A\cap (B-C)& =(A\cap B)-(A\cap C)\end{array}$$
• $$A\subseteq B⟹\begin{array}{rl}& 1.A\cap B=A\\ & 2.A\cup B=B\\ & 3.\sim B\subseteq \sim A\\ & 4.(B-A)\cup A=B\end{array}$$

集合的划分与覆盖

定义

• 覆盖：
  给定一个集合 $S=\{S_1,S_2,\dots ,S_m\}$ 使得 $\bigcup _{i=1}^m{S}_i=A$ 则称 $S$ 为 $A$ 的 覆盖
• 划分：
  若 $S$ 是 $A$ 的覆盖的同时，有 $S_i\cap S_j=\varnothing (i\ne j)$ 则称 $S$ 为 $A$ 的 划分
• 交叉划分：
  对于一个集合的两种划分 $\{A_1,A_2,\dots ,A_r\},\{B_1,B_2,\dots ,B_s\}$ ，
  所有 $C_k=A_i\cap B_j\ne \varnothing$ 组成的集合，称为是原来两种划分的 交叉划分
• 加细：
  给定集合 $X$ 的任意两个划分 $\{A_1,A_2,\dots ,A_r\},\{B_1,B_2,\dots ,B_s\}$ ，
  若对于每一个 $A_j$ 都有 $B_k$ 使得 $A_j\subseteq B_k$ ，则称
  $\{A_1,A_2,\dots ,A_r\}$ 为 $\{B_1,B_2,\dots ,B_s\}$ 的 加细

定理

• 对于同一个集合的两种划分，其交叉划分 仍是 原集合的一种划分
• 两种划分的交叉划分，都是原来两种划分的加细

关系

序偶

定义

• 序偶：
  序偶用于表示事物之间的关系，记作 $⟨a_1,a_2,\dots ,a_n⟩$，称为 $n$ 元组

• 笛卡尔乘积/直积：

  $$A\times B=\{⟨x,y⟩|(x\in A)\wedge (y\in B)\}$$

  这使得两个元素集合构造出一个序偶集合

  • 由于序偶内的元素顺序不可变，所以 $A\times B\ne B\times A$
  • 由于 $⟨a,⟨b,c⟩⟩$ 不是三元组，
    所以 $(A\times B)\times C\ne A\times (B\times C)$ ，且前者得到的才是三元组

• 记 $\stackrel{n}{\overbrace{A\times A\times \cdots \times A}}=A^n$

定理

• 对于任意三个集合 $A,B,C$ ，有

  $$\begin{gathered} A\times (B\cup C)=(A\times B)\cup (A\times C) \\ A\times (B\cap C)=(A\times B)\cap (A\times C) \\ (B\cup C)\times A=(B\times A)\cup (C\times A) \\ (B\cap C)\times A=(B\times A)\cap (C\times A) \end{gathered}$$

• 若 $C\ne \varnothing$ 则

  $$A\subseteq B⟺A\times C\subseteq B\times C⟺C\times A\subseteq C\times B$$

• 设 $A,B,C,D$ 为四个非空集合，则

  $$A\subseteq C\wedge B\subseteq D⟺A\times B\subseteq C\times D$$

关系及其表示

定义

• 关系：
  将一个由序偶组成的集合称为一个 关系，记作 $R$ ，
  $R$ 中的任一序偶 $⟨a,b⟩$ 可以记作 $⟨a,b⟩\in R$ 或 $xRy$
  不在 $R$ 中的任一序偶可以记作 $⟨a,b⟩\notin R$ 或 $x\mathrm{R̸}y$

• 前域、值域、域：
  $domR$ 称为 $R$ 的前域，$ranR$ 称为 $R$ 的值域，
  二者一起称作 $R$ 的域，记作 $FLDR$

  $$\begin{gathered} \mathrm{dom}R=\{x|(\mathrm{\exists }y)(⟨x,y⟩\in R)\} \\ \mathrm{ran}R=\{y|(\mathrm{\exists }x)(⟨x,y⟩\in R)\} \\ \mathrm{FLD}R=\mathrm{dom}R\cup \mathrm{ran}R \end{gathered}$$

• 直积与关系：
  对于任一两个集合 $X,Y$ ，二者的直积 $X\times Y$ 的子集 $R$ 称为 $X$ 到 $Y$ 的关系
  对于其子集 $X\times Y,\varnothing$ ，分别称为 $X$ 到 $Y$ 的 全域关系 和 空关系

• 恒等关系：

  $$I_X=\{⟨x,x⟩|x\in X\}$$

  $I_X$ 称为 $X$ 上的 恒等关系

• 关系矩阵：
  对于矩阵 $M_R=[r_{ij}{]}_{m\times n}$ 其中

  $$r_{i,j}=\{\begin{array}{l}1,⟨x_i,y_j⟩\in R\\ 0,⟨x_i,y_j⟩\notin R\end{array},i=1,2,\dots ,m;j=1,2,\dots ,n.$$

  这样的矩阵称为 $R$ 的 关系矩阵

定理

• 对于 $X$ 到 $Y$ 的两个关系 $Z,S$ ，二者的交、并、补、差 仍是 $X$ 到 $Y$ 的关系

关系的性质

定义

• 自反

  $$(\mathrm{\forall }x)(x\in X⟹xRx)$$

• 对称

  $$(\mathrm{\forall }x)(\mathrm{\forall }y)(x\in X\wedge y\in X\wedge xRy⟹yRx)$$

• 传递

  $$(\mathrm{\forall }x)(\mathrm{\forall }y)(\mathrm{\forall }z)(x\in X\wedge y\in X\wedge z\in X\wedge xRy\wedge yRz⟹xRz)$$

• 反自反、反对称
  反自反要求集合内 所有元素 不自反，反对称要求集合内 所有元素 不对称

  • 因此存在某种关系，即不自反，也不反自反
    也存在某种关系，既不对称也不反对称

从关系矩阵看性质

1. 自反 $⟺$ 对角线上所有元素均为 $1$
2. 对称 $⟺$ 关系矩阵是对称的
3. 反自反 $⟺$ 对角线元素全为 $0$
4. 反对称 $⟺$ 以主对角线对称的元素不同时为 $1$

复合关系和逆关系

定义

• 合成运算：
  设 $R$ 为 $X$ 到 $Y$ 的关系，$S$ 为 $Y$ 到 $Z$ 的关系，则 $R\circ S$ 称为 $R,S$ 的复合关系
  表示为

  $$R\circ S=\{⟨x,z⟩|x\in X\wedge z\in Z\wedge (\mathrm{\exists }y)(y\in Y\wedge ⟨x,y⟩\in R\wedge ⟨y,z⟩\in S\}$$

  这称为关系的 合成运算

• 记 $\stackrel{n}{\overbrace{R\circ R\circ \cdots \circ R}}=R^n$

• 逆关系：

  $$R^c=\{⟨y,x⟩|⟨x,y⟩\in R\}$$

利用矩阵运算求合成运算

$$\begin{gathered} M_{R\circ S}=M_R\circ M_S=[w_{ik}] \\ {w}_{ik}=\underset{j=1}{\overset{n}{\bigvee }}(u_{ij}\wedge v_{jk}) \end{gathered}$$

有关逆关系的公式

• 设 $R,R_1,R_2$ 都是 $A$ 到 $B$ 的二元关系

  $$\begin{array}{rl}& (R_1\cup R_2{)}^c=R_1^c\cup R_2^c\\ & (R_1\cap R_2{)}^c=R_1^c\cap R_2^c\\ & (A\times B{)}^c=B\times A\\ & (\overline{R}{)}^c=\overline{R^c},\overline{R}=A\times B-R\\ & (R_1-R_2{)}^c=R_1^c-R_2^c\end{array}$$

• 对于任一两个关系 $T,S$ ，$(T\circ S{)}^c=S^c\circ T^c$

对称定理

• $R$ 是对称的，当且仅当 $R=R^c$
• $R$ 是反对称的，当且仅当 $R\cap R^c\subseteq I_X$

关系的闭包运算

定义

设 $R$ 是 $X$ 上的二元关系，如果有另一个关系 $R^{\prime }$ 满足：

1. $R^{\prime }$ 是自反的/对称的/可传递的
2. $R\subseteq R^{\prime }$
3. 对于任何自反的/对称的/可传递的关系 $R^{″}$ ，
   如果有 $R\subseteq R^{″}$ 就有 $R^{\prime }\subseteq R^{″}$

则称 $R^{\prime }$ 为 $R$ 的自反/对称/传递 闭包，记作

$$r(R)/s(R)/t(R)(\mathrm{reflexive},\mathrm{symmetrical},\mathrm{transitive})$$

定理

• $R$ 是自反的，当且仅当 $r(R)=R$

  $R$ 是对称的，当且仅当 $s(R)=R$

  $R$ 是传递的，当且仅当 $t(R)=R$

• 自反闭包的求解：

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

• 对称闭包的求解：

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

• 传递闭包的求解：

  $$t(R)=\bigcup _{i=1}^k{R}^k,k\le n（n\mathrm{为}\mathrm{元}\mathrm{素}\mathrm{个}\mathrm{数}）$$

• 闭包之间的关系：

  $$\begin{gathered} rs(R)=sr(R) \\ rt(R)=tr(R) \\ st(R)\subseteq ts(R) \end{gathered}$$

$Floyd$ 算法求解传递闭包

对于 $R$ 的关系矩阵 $M$ 依照以下步骤进行修改

for k from 1 to n:
	for i from 1 to n:
        for j from 1 to n:
            if (M[i][j] == 0)
            	M[i][j] = M[i][k] * M[k][j]

等价关系与等价类

定义

• 等价关系：
  一个关系若同时是自反的、对称的、传递的，则称该关系为 等价关系

• 等价类：
  设 $R$ 是集合 $A$ 上的等价关系，对与 $\mathrm{\forall }a\in A$ ，
  集合 $[a{]}_R=\{x|x\in A,aRx\}$ 称为元素 $a$ 形成的 $R$ 等价类

• 商集：
  对于集合 $A$ 上的等价关系 $R$ ，
  其等价类集合 $\{[a{]}_R|a\in A\}$ 称作 $A$ 关于 $R$ 的商集，记作 $A/R$

定理

• 对于集合 $A$ 上的等价关系 $R$ ，$a,b\in A$，则

  $$aRb⟺[a{]}_R=[b{]}_R$$

• 集合 $A$ 上的一个等价关系可以确定 $A$ 的一个划分，
  该划分就是 $A/R$

• 集合 $A$ 的一个划分能确定 $A$ 上的一个等价关系

• 对于集合上的两个等价关系 $R_1,R_2$ ，

  $$A/R_1=A/R_2⟺R_1=R_2$$

求划分确定的等价关系

例题： 设集合 $A=\{a,b,c,d,e\}$ ，划分 $S=\{⟨a,b⟩,⟨c⟩,⟨d,e⟩\}$ ，
求划分 $S$ 所确定的 $A$ 上的一个等价关系 $R$
解：

$$\begin{array}{rl}& R_1=⟨a,b⟩\times ⟨a,b⟩\\ & R_2=⟨c⟩\times ⟨c⟩\\ & R_3=⟨d,e⟩\times ⟨d,e⟩\\ \\ \therefore & R=R_1\cup R_2\cup R_3=\{⟨a,a⟩,⟨b,b⟩,⟨c,c⟩,⟨d,d⟩,⟨e,e⟩,\\ & ⟨a,b⟩,⟨b,a⟩,⟨d,e⟩,⟨e,d⟩\}\end{array}$$

相容关系与相容类

定义

• 相容关系：
  一个关系若同时是自反的、对称的，则称该关系为 相容关系
  • 对于相容关系的关系图，不画自回路，使用单线来代替回弧线
• 相容类：
  对于集合 $A$ 上的相容关系 $r$ ，若 $C\subseteq A$ ，
  如果 $C$ 中的任意两个元素 $a_1,a_2$ 有 $a_{1}r{a}_2$ ，称 $C$ 是由相容关系 $r$ 产生的 相容类
• 最大相容类：
  若一个相容类，不能真包含在其他相容类，则称其为 最大相容类，记作 $C_r$
• 完全覆盖：
  对于一个集合 $A$ 的所有最大相容类，
  这些最大相容类组成的集合，构成了 $A$ 的一个覆盖，
  称为 完全覆盖，记作 $C_r(A)$

定理

• 相容关系图中，最大完全多边形的顶点集合 就是最大相容类，
  此外，孤立节点 和 不是完全多边形的边的两个节点 也是最大相容类
  （详见下面例题）
  
  
  其中 $\{a_1,a_2,a_4,a_6\},\{a_3,a_4,a_6\}$ 构成最大多边形，
  $\{a_4,a_5\}$ 为非最大多边形边的两个节点，$\{a_7\}$ 为孤立节点
• 给定集合 $A$ 的覆盖 $\{A_1,A_2,\dots ,A_n\}$ ，
  由它确定的关系 $R=A_1\times A_1\cup A_2\times A_2\cup \dots A_n\times A_n$ 是相容关系
• 相容关系 $r$ 与完全覆盖 $C_r(A)$ 一一对应

序关系

定义

• 偏序：
  对于集合 $A$ 上的一个关系 $R$ ，同时满足自反性、反对称性、传递性，
  则称 $R$ 为 $A$ 上的一个偏序关系，将这个关系记作 $⪯$ ，序偶 $⟨A,⪯⟩$ 称作偏序集

• 盖住：
  在偏序集合 $⟨A,⪯⟩$ 中，如果 $x,y\in A,x⪯y,x\ne y$
  且没有其他元素 $z$ 满足 $x⪯z,z⪯y$ ，则称 $y$ 盖住 $x$ ，记

  $$\mathrm{COV}A=\{⟨x,y⟩|x,y\in A;y\mathrm{盖}\mathrm{住}x\}$$

  • 盖住关系是 唯一的，所以可以用盖住的性质画出偏序集合图，称为 哈斯图，

    作图规则如下：

• 链、反链：
  设 $⟨A,⪯⟩$ 是一个偏序结合，在 $A$ 的一个子集中，
  如果每两个元素都是有关系的，则称这个子集为 链，
  如果每两个元素都是无关的，则称这个子集为 反链

  • 规定，若 $A$ 的子集只有一个元素，则这个子集既是链也是反链

• 全序/线序集合：
  在偏序集 $⟨A,⪯⟩$ 中，如果 $A$ 是一个链，则称 $⟨A,⪯⟩$ 为 全序集合 或 线序集合 ，在这种情况下，称二元关系 $⪯$ 为 全序关系 或 线序关系

  • 即 $\mathrm{\forall }x,y\in A$ 都有 $x⪯y$ 或者 $y⪯x$ 成立，不存在两个无关的元素

• 极大元、极小元：
  设 $⟨A,⪯⟩$ 是一个偏序集，且 $B$ 是 $A$ 的子集，对于 $B$ 中的一个元素 $b$ ，
  如果 $B$ 中没有任何元素 $x$ 满足 $b\ne x$ 且 $b⪯x$ 则称 $b$ 为 $B$ 的 极大元，
  如果 $B$ 中没有任何元素 $x$ 满足 $b\ne x$ 且 $x⪯b$ 则称 $b$ 为 $B$ 的 极小元

  • 极大元和极小元 不是唯一的
    

• 最大元、最小元：
  设 $⟨A,⪯⟩$ 是一个偏序集，且 $B$ 是 $A$ 的子集，对于 $B$ 中的一个元素 $b$ ，
  如果 $B$ 中每一个元素 $x$ 满足 $x⪯b$ 则称 $b$ 为 $B$ 的 最大元，
  如果 $B$ 中每一个元素 $x$ 满足 $b⪯x$ 则称 $b$ 为 $B$ 的 最小元

  • 如果存在最大/最小元，则一定是 唯一的

• 上界、下界
  设 $⟨A,⪯⟩$ 是一个偏序集，且 $B$ 是 $A$ 的子集，对于一个元素 $a\in B$
  若 $B$ 的任意元素 $x$ ，满足 $x⪯a$ ，则称 $a$ 为 $B$ 的 上界
  若 $B$ 的任意元素 $x$ ，满足 $a⪯x$ ，则称 $a$ 为 $B$ 的 下界

  • 上界和下界 不是唯一的

• 最小上界/上确界、最大下界/下确界：
  设 $⟨A,⪯⟩$ 是一个偏序集，且 $B$ 是 $A$ 的子集，对于 $B$ 的任一上界 $a$
  若 $B$ 的所有上界 $y$ ，满足 $a⪯y$ ，
  则称 $a$ 为 $B$ 的 最小上界（上确界），记为 $\mathrm{LUB}B$
  若 $B$ 的所有上界 $y$ ，满足 $y⪯a$ ，
  则称 $a$ 为 $B$ 的 最大下界（下确界），记为 $\mathrm{GLB}B$

• 良序集合：
  任一偏序集合，若它的每个非空子集存在最小元素，
  则称这种偏序集为 良序集合

定理

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

图论

路与回路

定义

路、回路

• 路：连接各个节点
• 回路：头尾节点相同的路
• 通路：不存在重复节点的路
• 圈：除头尾节点外不存在重复节点的回路
• 迹：不存在重复边的路

连通性

• 连通：两节点之间存在路
• 连通分支：将一个图划分为若干子图，两个节点只有属于同一个集合时连通，连通分支数记为 $W(G)$
• 点割集：如果将集合中所有点及其相连的边从图中移除，会导致图变得不连通（即图的连通分支数增加）
• 割点：单独构成点割集的点
• 点连通度：在保持图连通的前提下，至少需要移除多少个顶点（及其相连的边）才能使图不连通，记为 $k(G)$
• 边割集：如果移除该边集中的所有边后，图会变得不连通的边集
• 割边：单独构成边割集的边
• 边连通度：在保持图连通的前提下，至少需要移除多少条边才能使图不连通，记为 $\lambda (G)$

最短路

• 两节点之间的最短路记为两节点的距离（或短程线），用 $d(u,v)$ 表示
• $D=maxd(u,v)$ 称为图的直径

强弱连通（在有向图中）

单侧连通：图中存在一对节点仅单侧可达（不要求图为连通图）
强连通：图中任意两节点相互可达
弱连通：单侧连通的有向图转为无向图后是连通的
强/弱/单侧分图：具有强/弱/单侧性质的最大子图

定理

• 两节点间必然存在一条不多于 $n-1$ 条边的路
• 两节点间必然存在一条小于 $n$ 条边的通路
• 连通图只有一个连通分支
• $k(K_p)=p-1$（完全图的点连通度为 $\mathrm{节}\mathrm{点}\mathrm{数}-1$）
• $k(G)\le \lambda (G)\le \delta (G)$（点连通度≤边连通度≤最小度数）
• 两节点间每一条路都经过的节点为割点
• 强连通 $⟺$ 图中存在一个回路，该回路至少包含每个节点一次
• 有向图中的每个节点只位于一个强分图中
• 对于邻接矩阵 $A(G)$，$(A(G){)}^k$ 中，$a_{ij}$ 表示从 $v_i$ 到 $v_j$ 的长度为 $k$ 的（回）路的数量
• 对于有 $n$ 个节点的连通图， $rankM(G)=r-1$
• 对于有 $n$ 个节点，$w$ 个最大连通子图的连通图，$M(G)$ 是完全关联矩阵，$rankM(G)=n-w$

欧拉图与哈密顿图

定义

欧拉图

• 欧拉路径：一条经过所有边且不重复的路
• 欧拉回路：一条经过所有边且不重复的回路
  • 有向图中为单向欧拉路径（回路）

哈密顿图

• 哈密顿路径：经过所有节点恰好一次的路径
• 哈密顿回路：经过所有节点恰好一次的回路

闭包

G, G' = <V, E>
节点总数 n
while G'中存在非邻接节点 and 两节点度数之和大于等于 n:
	连接这两个节点

$C(G)=G^{\prime }$ 称为 $G$ 的闭包

定理

欧拉图

• 对于无向图，当且仅当其连通且奇数度节点有 0 或 2 个时，有欧拉路径
• 对于无向图，当且仅当所有节点全为偶数度节点时，有欧拉回路
• 对于有向图，当且仅当其连通且{有两个节点，一个入度比出度大 1 另一个入度比出度小 1}，其余节点入度等于出度时，有欧拉路径
• 对于有向图，当且仅当其连通且所有节点入度等于出度时，有欧拉回路

哈密顿图

• 若一个图有哈密顿回路，则对任意一个节点子集 $S$，
  $G-S$ 的连通分支数 $W(G-S)\le |S|$
• 对于一个图，若其为简单图且每一对节点度数之和大于等于 $n-1\to$ 该图有哈密顿路径（这不是充要条件）
• 对于一个图，若其为简单图且每一对节点度数之和大于等于 $n\to$ 该图有哈密顿回路（这不是充要条件）
• 一个简单图的闭包是哈密顿图 $⟺$ 该简单图也为哈密顿图

平面图

定义

• 平面图：边之间没有交点的图（可以通过改画图像得到）
• 面：边所包围的区域
• 边界：构成面的边所形成的回路
• 面的次数：面的边界长度
• 在 $k$ 度节点内同构：对两个图通过多次添加或删除度数为 $k$ 的节点，后使得两图同构

定理

• 对于有限平面图，面的次数和等于边数的两倍
• 欧拉公式：$V-E+R=2$
• 判断非平面图的充分条件：对于一个连通的简单平面图，若 $V\ge 3⟶E\le 3V-6$
• 判断平面图的充要条件：一个图是平面图 $⟺$ 该图不包含与 $K_{3,3},K_5$ 在 $2$ 度节点内同构的子图

对偶图与着色

定义

对偶

• 对偶图：$G$ 和 $G^{\ast }$ 互为对偶图，对于 $G$ 中的每一个面（包括外面），$G^{\ast }$ 中均有一个对应的节点在其内部，反之亦然
• 自对偶图：$G$ 与其对偶图 $G^{\ast }$ 同构

着色

• 最少着色数：$x(G)$
• $WelchPowell$ 着色法：

for node in sorted_node (按度数降序排序后的节点):
	if node 未着色：
		对 node 及其的所有不邻接节点着相同颜色
		换一种颜色
	if 所有节点已着色:
		break

定理

• $x(K_n)=n$
• 对于一个至少有三个节点的连通平面图，必存在度数小于 5 的节点
• 任意平面图，最多为 5-色 (?)

树与生成树

定义

• 树：无向图
  • 无回路的连通图
  • 每个节点之间仅有一条路
  • $E=V-1$
  • $\lambda (G)=1$
• 生成树：一个图的子图是树，该树称为生成树
• 最小生成树：一个图的所有生成树中，边权和最小的那棵树

定理

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

• 图中的一条回路/边割集和该图的任何一颗生成树的补至少有一条公共边

• $Kruskal$ 算法得到最小生成树：

  V = {}, E = {}
  G = <V, E>
  sum = 0
  for edge in sorted_edges（按边权升序排列的边）:
      if 加入该边不会出现环:
          将该边加入图中
      if G 是生成树（边数等于 n-1）:
      	break

根树及其应用

定义

• 有向树：不考虑边的方向时是一颗树的有向图
• 根树：恰有一个节点入度为 0，其余节点入度为 1 的有向树，入度为 0 的为根，出度为 0 的为叶，出度不为 0 的为分支点或内点
• （完全）$m$ 叉树：每一个节点的出度均（恰好等于）小于等于 $m$ 的根树
• 内部/外部通路长度：根到分支节点/叶节点的通路的长度
• 带权二叉树：有 $t$ 个叶节点，每个叶节点带有权值 $w_1,w_1,...,w_t$
• 最优带权二叉树（哈夫曼树）：
  • 对于带权为 $w_i$ 的叶节点，其通路长度为 $L(w_i)$
  • 将 $w(T)=\sum _{i=1}^t{w}_{i}L(w_i)$ 称为该带权二叉树 $T$ 的权
  • 最优树为 $w(T)$ 最小的那棵树
• 前缀码：一个 $01$ 序列集合，没有一个序列是其他序列的前缀
  • 前缀码和二叉树一一对应

定理

• 对于完全 $m$ 叉树，树叶数为 $t$，分枝点数为 $i$，则有 $i(m-1)=t-1$
• 对于有 $n$ 个分枝点的完全二叉树，内部通路长度总和为 $I$，外部通路长度总和为 $E$，有 $E=I+2n$
• 对于带权 $w_1\le w_2\le ...\le w_t$ 的最优树 $T$：
  • 带权 $w_1,w_2$ 的叶节点 $v_{w_1},v_{w_2}$ 互为兄弟节点
  • $v_{w_1},v_{w_2}$ 的父节点的通路长度最长
  • 若将 $v_{w_1},v_{w_2}$ 的父节点改为带权 $w_1+w_2$ 的叶节点，得到的新树 $T{}^{\prime }$ 也是最优树

参考文献

• 《离散数学》左孝凌版