逻辑和证明

命题逻辑

命题（$proposition$）

命题是一个陈述语句（即陈述事实的语句），它或真或假，但不能既真又假。

条件（$implies$）

令 $p$ 和 $q$ 为命题。条件语句 $p \rightarrow q$ 是命题“如果 $p$，则 $q$ ”。当 $p$ 为真而 $q$ 为假时，条件语句 $p \rightarrow q$ 为假，否则为真。在条件语句 $p \rightarrow q$ 中，$p$ 称为假设(前件、前提)，$q$ 称为结论(后件)。

$p$ $q$ $p \rightarrow q$
T T T
T F F
F T T
F F T

原命题：$p \rightarrow q$

逆命题（$converse$）：$q \rightarrow p$

逆否命题（$contrapositive$）：$\neg q \rightarrow \neg p$

反命题（$inverse$）：$\neg p \rightarrow \neg q$

双条件（$biconditional$）

令 $p$ 和 $q$ 为命题。双条件语句 $p \leftrightarrow q$ 是命题“ $p$ 当且仅当 $q$ ”。当 $p$ 和 $q$ 有同样的真值时，双条件语句为真，否则为假。双条件语句也称为双向蕴含。

$p$ $q$ $p \leftrightarrow q$
T T T
T F F
F T F
F F T

逻辑运算符的优先级

运算符 优先级
$\neg$ 1
$\wedge$ 2
$\vee$ 3
$\rightarrow$ 4
$\leftrightarrow$ 5

永真式（重言式） & 矛盾式 &可能式

永真式（$tautology$）：一个真值永远是真的复合命题（无论其中出现的命题变元的真值是什么），也称为重言式。

矛盾式（$contradiction$）：一个真值永远为假的复合命题。

可能式（$contingency$）：既不是永真式又不是矛盾式的复合命题。

命题等价式（$equivalent$）

逻辑等价式

如果 $p \leftrightarrow q$ 是永真式，则复合命题 $p$ 和 $q$ 称为是逻辑等价的。用记号 $p \equiv q$ 表示 $p$ 和 $q$ 是逻辑等价的。

谓词（$predicate$）与量词（$quantifier$）

全称量化

$P(x)$ 的全称量化是语句：“ $P(x)$ 对 $x$ 在其论域的所有值为真。”

符号 $\forall x P(x)$ 表示 $P(x)$ 的全称量化，其中 $\forall$ 称为全称量词。

命题 $\forall x P(x)$ 读做“对所有 $x$ , $P(x)$ ”或“对每个 $x$ ，$P(x)$”。一个使 $P(x)$ 为假的个体称为 $\forall x P(x)$ 的反例。

存在量化

$P(x)$ 的存在量化是语句：“论域中存在一个个体 $x$ 满足 $P(x)$ 。”

符号 $\exists x P(x)$ 表示 $P(x)$ 的存在量化，其中 $\exists$ 称为存在量词。

量词优先级

$\forall > \exists$

注意

$\forall x P(x) \vee Q(x)$ 是 $\forall x P(x)$ 和 $Q(x)$ 的析取

$\forall x (P(x) \vee Q(x))$ 是 $\forall x$ 对 $(P(x) \vee Q(x))$ 的析取

涉及量词的逻辑等价式

涉及谓词和量词的语句是逻辑等价的当且仅当无论用什么谓词代入这些语句，也无论为这些命题函数里的变量指定什么论域，它们都有相同的真值。我们用 $S \equiv T$ 表示涉及谓词和量词的两个语句 $S$ 和 $T$ 是逻辑等价的。

证明两个语句逻辑等价 $P(x) \equiv Q(x)$

  1. $(P(x) = T) \rightarrow (Q(x) = T)$
  2. $(Q(x) = T) \rightarrow (P(x) = T)$
  3. $P(x) \equiv Q(x)$

量词的否定（德 $\cdot$ 摩根律）

否定 等价语句
$\neg \exists x P(x)$ $\forall x \neg P(x)$
$\neg \forall x P(x)$ $\exists x \neg P(x)$

推理规则（$rule \ of \ inference$）

推理规则 永真式 名称
$\quad p$
$\quad p \rightarrow q$
$\therefore q$		 $(p \wedge (p \rightarrow q)) \rightarrow q$ 假言推理
$\quad \neg q$
$\quad p \rightarrow q$
$\therefore \neg p$		 $(\neg q \wedge (p \rightarrow q)) \rightarrow \neg p$ 取拒式
$\quad p \rightarrow q$
$\quad q \rightarrow r$
$\therefore p \rightarrow r$		 $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ 假言三段论
$\quad p \vee q$
$\quad \neg p$
$\therefore q$		 $((p \vee q) \wedge \neg p) \rightarrow q$ 析取三段论
$\quad p$
$\therefore p \vee q$		 $p \rightarrow (p \vee q)$ 附加律
$\quad p \wedge q$
$\therefore p$		 $(p \wedge q) \rightarrow p$ 化简律
$\quad p$
$\quad q$
$\therefore p \wedge q$		 $((p) \wedge (q)) \rightarrow (p \wedge q)$ 合取律
$\quad p \vee q$
$\quad \neg p \vee r$
$\therefore q \vee r$		 $((p \vee q) \wedge (\neg p \vee r)) \rightarrow (q \vee r)$ 消解律

格式

步骤 理由
1.表达式 前提引入
2.结论式 XX律，用XX步

一次一条结论， 不可跳步骤

量化命题的推理规则

推理规则 名称
$\quad \forall x P(x)$
$\therefore P(c)$		 全称实例
$\quad P(c)$，任意 $c$
$\therefore \forall x P(x)$		 全称引入
$\quad \exists x P(x)$
$\therefore P(c)$，对某个元素 $c$		 存在实例
$\quad P(c)$，对某个元素 $c$
$\therefore \exists x P(x)$		 存在引入

推理表

expressions_page_one

expression_page_two

集合、函数

集合（$set$）

集合是对象的一个无序的聚集，对象也称为集合的元素（element）或成员（member）。集合包含（contain）它的元素。我们用 $a \in A$ 来表示 $a$ 是集合 $A$ 中一个元素。而记号 $a \notin A$ 表示 $a$ 不是集合 $A$ 中的一个元素。

证明集合相等 （$A = B$）

  1. $A \subseteq B$
  2. $B \subseteq A$
  3. $A = B$

集合的大小

$|S|$ 表示集合的大小

幂集（$power \ set$）

给定集合 $S$，$S$ 的幂集（$power \ set$）是集合 $S$ 所有子集的集合。$S$ 的幂集记为 $\mathcal{P} (S)$

笛卡尔积（$Cartesian \ product$）

令 $A$ 和 $B$ 为集合。$A$ 和 $B$ 的笛卡儿积（$Cartesian \ product$）用 $A \times B$ 表示，是所有序偶 $(a, b)$ 的集合，其中 $a \in A, b \in B$。于是，$A \times B = {(a, b) | a \in A \wedge b \in B }$

集合运算

$A \cup B = \lbrace x | x \in A \vee x \in B \rbrace$

$A \cap B = \lbrace x | x \in A \wedge x \in B \rbrace$

$A - B = \lbrace x | x \in A \wedge x \notin B \rbrace = A \cap \overline{B}$

$\overline{A} \quad \quad = \lbrace x | x \in U \wedge x \notin A \rbrace$

集合恒等式

恒等式 名称
$A \cap U = A$
$A \cup \varnothing = A$		 恒等律
$A \cup U = U$
$A \cap \varnothing = \varnothing $		 支配律
$A \cup A = A$
$A \cap A = A$		 幂等律
$\overline{(\overline{A})} = A$ 补律
$A \cup B = B \cup A$
$A \cap B = B \cap A$		 交换律
$A \cup (B \cup C) = (A \cup B) \cup C$
$A \cap (B \cap C) = (A \cap B) \cap C$		 结合律
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$		 分配律
$\overline{A \cap B} = \overline{A} \cup \overline{B}$
$\overline{A \cup B} = \overline{A} \cap \overline{B}$		 德 $\cdot$ 摩根律
$A \cup (A \cap B) = A$
$A \cap (A \cup B) = A$		 吸收律
$A \cup \overline{A} = U$
$A \cap \overline{A} = \varnothing$		 互补律

扩展并集和交集

$\bigcup\limits_{i = 1}^{n} A_{i} = A_{1} \cup A_{2} \cup \cdot \cdot \cdot \cup A_{n}$

$\bigcap\limits_{i = 1}^{n} A_{i} = A_{1} \cap A_{2} \cap \cdot \cdot \cdot \cap A_{n}$

$\overline{\bigcup\limits_{i = 1}^{n} A_{i}} = \overline{A_{1}} \cap \overline{A_{2}} \cap \cdot \cdot \cdot \cap \overline{A_{n}}$

$\overline{\bigcap\limits_{i = 1}^{n} A_{i}} = \overline{A_{1}} \cup \overline{A_{2}} \cup \cdot \cdot \cdot \cup \overline{A_{n}}$

函数

一对一 （单射）

函数 $f$ 称为是一对一（$one-to-one$）或单射函数（$injection$），当且仅当对于 $f$ 的定义域中的所有 $a$ 和 $b$ 有 $f(a)=f(b)$ 蕴含 $a = b$。一个函数如果是一对一的，就称为是单射的（$injective$）。

one-to-one

映上（满射）

一个从 $A$ 到 $B$ 的函数 $f$ 称为映上（$onto$）或满射（$surjection$）函数，当且仅当对每个 $b \in B$ 有元素 $a \in A$ 使得 $f(a)=b$。一个函数如果是映上的就称为是满射的（$surjective$）。

onto

一一对应（双射）

函数 $f$ 是一一对应（$one-to-one correspondance$）或双射（$bijection$）函数，如果它既是一对一的又是映上的。这样的函数称为是双射的（$bijective$）。

sample

合成（$composition$）

令 $g$ 为从集合 $A$ 到集合 $B$ 的函数，$f$ 是从集合 $B$ 到集合 $C$ 的函数，函数 $f$ 和 $g$ 的合成（$composition$），记作 $f \ o \ g$，定义为对任意$a \in A \quad (f \ o \ g)(a) = f(g(a))$

composition

算法

大 $O$ 记号

令 $f$ 和 $g$ 为从整数集或实数集到实数集的函数。如果存在常数 $C$ 和 $k$ 使得只要当定义 $x > k$ 时就有
$|f(x)| \le C|g(x)|$ 我们就说 $f(x)$ 是 $O(g(x))$ 的。

逻辑语言

$\exists C \in R^{+} \quad \exists k \in Z^{+} \quad \forall x > k : f(x) \le C \times g(x)$

性质

$f \preceq g$

$f = O(g)$

$f \in O(g)$

关系

关系及其性质

设 $A$ 和 $B$ 是集合，一个从 $A$ 到 $B$ 的二元关系 $R$ 是 $A \times B$ 的子集

自反（$reflexive$）

若对每个元素 $a \in A$ 有 $(a,a) \in R$，那么定义在集合 $A$ 上的关系 $R$ 称为自反的。

逻辑语言

$\forall a (a \in A \rightarrow (a, a) \in R)$

反自反（$irreflexive$）

若对每个元素 $a \in A$ 有 $(a,a) \notin R$，那么定义在集合 $A$ 上的关系 $R$ 称为反自反的。

逻辑语言

$\forall a (a \in A \rightarrow (a, a) \notin R)$

对称（$symmetric$）

对于任意 $a,b \in A$，若只要 $(a,b) \in R$ 就有 $(b,a) \in R$，则称定义在集合 $A$ 上的关系 $R$ 为对称的。

逻辑语言

$\forall a \forall b ((a, b) \in R \rightarrow (b, a) \in R)$

反对称（$antisymmetric$）

对于任意 $a,b \in A$，若 $(a,b) \in R$ 且 $(b,a) \in R$，一定有 $a = b$ 则称定义在集合 $A$ 上的关系 $R$ 为反对称的。

逻辑语言

$\forall a \forall b (((a, b) \in R \wedge (b, a) \in R) \rightarrow (a = b))$

传递（$transitive$）

若对于任意 $a,b,c \in A$，$(a,b) \in R$ 并且 $(b,c)\in R$ 则 $(a,c) \in R$，那么定义在集合 $A$ 上的关系 $R$ 称为传递的。

逻辑语言

$\forall a \forall b \forall c (((a, b) \in R \wedge (b, c) \in R ) \rightarrow (a, b) \in R)$

合成（$composition$）

设 $R$ 是从集合 $A$ 到集合 $B$ 的关系，$S$ 是从集合 $B$ 到集合 $C$ 的关系。$R$ 与 $S$ 的合成是由有序对 $(a,c)$ 的集合构成的关系，其中 $a \in A,c \in C$，并且存在一个 $b \in B$ 的元素，使得 $(a,b) \in R$ 且 $(b,c) \in S$。我们用 $S \ o \ R$ 表示 $R$ 与 $S$ 的合成。

幂（$power$）

设 $R$ 是集合 $A$ 上的关系。$R$ 的 $n$ 次幂 $R^{n} (n = 1,2,3, \cdot \cdot \cdot)$ 递归地定义为 $R^{1} = R$ 和 $R^{n + 1} = R^{n} \ o \ R$

关系（$relation$）的表示

矩阵（$matrix$）表示

可以用 0-1 矩阵表示有穷集之间的关系

matrix

部分关系矩阵形式

matrix_of_relation

图（$graph$）表示

一个有向图由顶点（或结点）集 $V$ 和边（或弧）集 $E$ 组成，其中边集是 $V$ 中元素的有序对的集合。顶点 $a$ 叫做边 $(a,b)$ 的始点，而顶点 $b$ 叫做这条边的终点。形如 $(a,a)$ 的边用一条从顶点 $a$ 到自身的弧表示。这种边叫做环。

graph_of_relation

关系的闭包（$closure$）

自反闭包 $r(R)$ ：包含 $R$ 关系，向 $R$ 关系中，添加有序对，变成自反的最小的二元关系。

对称闭包 $s(R)$ ：包含 $R$ 关系，向 $R$ 关系中，添加有序对，变成对称的最小的二元关系。

传递闭包 $t (R)$ ：包含 $R$ 关系，向 $R$ 关系中，添加有序对，变成传递的最小的二元关系。

沃舍尔算法（$Warshall$）

求传递闭包

Warshall

注意首先枚举中间的 $k$

等价关系（$equivalence \ relation$）

等价关系

定义在集合 $A$ 上的关系叫做等价关系，如果它是自反的、对称的和传递的。

证明等价关系即证明该关系具有自反，对称，传递性质

等价类

设 $R$ 是定义在集合 $A$ 上的等价关系。与 $A$ 中的一个元素 $a$ 有关系的所有元素的集合叫做 $a$ 的等价类。 $A$ 的关于 $R$ 的等价类记作 $[a]_{R}$。当只考虑一个关系时，我们将省去下标 $R$ 并把这个等价类写作 $[a]$。

换句话说，如果 $R$ 是定义在集合 $A$ 上的等价关系，则元素 $a$ 的等价类是 $[a]_{R} = \lbrace s| (a, s) \in R \rbrace$

如果 $b \in [a]_{R}$，$b$ 叫做这个等价类的代表元。

偏序（$partial \ ordering$）

偏序集

定义在集合 $S$上的关系 $R$，如果它是自反的、反对称的和传递的，就称为偏序。集合 $S$ 与定义在其上的偏序 $R$ 一起称为偏序集，记作 $(S,R)$。集合 $S$ 中的成员称为偏序集的元素

偏序集 $(S, \preccurlyeq )$中的元素 $a$ 和 $b$ 称为可比的，如果 $a \preccurlyeq b$ 或 $b \preccurlyeq a$ 。当 $a$ 和 $b$ 是 $S$ 中
的元素并且既没有 $a \preccurlyeq b$ ，也没有 $b \preccurlyeq a$ ，则称 $a$ 与是不可比的。

全序集

如果 $(S, \preccurlyeq )$ 是偏序集，且 $S$ 中的每对元素都是可比的，则 $S$ 称为全序集或线序集，且 $\preccurlyeq$ 称为全序或线序。一个全序集也称为链。

良序集（$well-ordered \ set$）

对于偏序集 $(S, \preccurlyeq )$ ，如果 $\preccurlyeq$ 是全序，并且 $S$ 的每个非空子集都有一个最小元素，就称它为良序集。

哈塞图

Hasse

偏序集 $(S, \preccurlyeq )$ 构造哈塞图 （上大下小，没有边则不可比较）

极大元（$maximal \ element$）与极小元（$minimal \ element$）

极大元： 当不存在 $b \in S$ 使得 $a \prec b$ ， $a$ 在偏序集 $(S, \preccurlyeq )$ 中是极大元。

极小元： 当不存在 $b \in S$ 使得 $b \prec a$ ， $a$ 在偏序集 $(S, \preccurlyeq )$ 中是极小元。

最大元（$greatest \ element$）与最小元（$least \ element$）

最大元：偏序集内元素 $a$ 大于每个其他的元素， $a$ 在偏序集 $(S, \preccurlyeq )$ 中是最大元。

最小元：偏序集内元素 $a$ 小于每个其他的元素， $a$ 在偏序集 $(S, \preccurlyeq )$ 中是最小元。

格（$lattice$）

如果一个偏序集的每对元素都有最小上界和最大下界，就称这个偏序集为格

拓扑排序（$topological \ sort$）

toposort

引理：每个有穷非空偏序集 $(S, \preccurlyeq )$ 至少有一个极小元。

图

图和图模型

一个图 $G=(V,E)$ 由顶点（或结点）的非空集 $V$ 和边的集合 $E$ 构成，每条边有一个或两个顶点与它相连，这样的顶点称为边的端点。边连接它的端点。

图的术语和几种特殊的图

基本术语

若 $u$ 和 $v$ 是无向图 $G$ 中的一条边 $e$ 的端点，则称两个顶点 $u$ 和 $v$ 在 $G$ 里邻接（或相邻）。这样的边 $e$ 称为关联顶点 $u$ 和 $v$ ，也可以说边 $e$ 连接 $u$ 和 $v$ 。

图 $G=(V,E)$ 中，顶点 $v$ 的所有相邻顶点的集合，记作 $N(v)$ ，称为顶点 $v$ 的邻居。若 $A$ 是 $V$ 的子集，我们用 $N(A)$ 表示图 $G$ 中至少和 $A$ 中一个顶点相邻的所有顶点的集合。所以 $N(A)=\bigcup\limits_{v \in A} N(v)$。

在无向图中，顶点的度是与该顶点相关联的边的数目，例外的情形是，顶点上的环为顶点的度做出双倍贡献。顶点 $v$ 的度表示成 $deg(v)$ 。

握手定理

设 $G = (V, E)$ 是有 $m$ 条边的无向图，则 $2m = \sum\limits_{v \in V} deg(v)$

无向图有偶数个度为奇数的顶点。

证明：

$2m = \sum\limits_{v \in V} deg(v) = \sum\limits_{v \in V_{1}} deg(v) + \sum\limits_{v \in V_{2}} deg(v)$

设 $V_{1}$ 是度数为偶数的集合， $V_{2}$ 是度数为奇数的集合

$2m$ 和 $\sum\limits_{v \in V_{1}} deg(v)$ 都是偶数，故 $\sum\limits_{v \in V_{2}} deg(v)$ 为偶数。

出度与入度（$degree$）

$deg^{+}(v)$ 表示 $v$ 的出度。

$deg^{-}(v)$ 表示 $v$ 的入度。

完全图（$K_{n}$）

完全图

圈图（$C_{n}$）

圈图

轮图（$W_{n}$）

轮图

立方体图（$Q_{n}$）

立方图

二分图（$bipartite \ graph$）

若把简单图 $G$ 的顶点集分成两个不相交的非空集合 $V_{1}$ 和 $V_{2}$ ，使得图中的每一条边都连接 $V_{1}$ 中的一个顶点与 $V_{2}$ 中的一个顶点（因此 $G$ 中没有边连接 $V_{1}$ 中的两个顶点或 $V_{2}$ 中的两个顶点），则 $G$ 称为二分图。当此条件成立时，称 $(V_{1},V_{2})$ 为 $G$ 的顶点集的一个
二部划分。

C6_二分图

完全二分图（$K_{m, n}$）

完全二分图

二分图和匹配（$match$）

最大匹配：包含最多边数的一个匹配。

霍尔婚姻定理： 带有二部划分 $(V_{1},V_{2})$ 的二分图 $G = (V,E)$ 中有一个从 $V_{1}$ 到 $V_{2}$ 的完全匹配当且仅当对于 $V_{1}$ 的所有子集 $A$ ，有 $|N(A)| \ge |A|$ 。

真子图：图 $G=(V,E)$ 的子图是图 $H = (W,F)$，其中 $W \subseteq V$ 且 $F \subseteq E$ 。若 $H \neq G$ ，则称图 $G$ 的子图 $H$ 是 $G$ 的真子图。

子图：令 $G=(V,E)$ 是一个简单图。图 $(W,F)$ 是由顶点集 $V$ 的子集 $W$ 导出的子图，其中边集 $F$ 包含 $E$ 中的一条边当且仅当这条边的两个端点都在 $W$ 中。

子图

图的并集：两个简单图 $G_{1} = (V_{1},E_{1})$ 和 $G_{2} = (V_{2}, E_{2})$ 的并图是带有顶点集 $V_{1} U V_{2}$ 和边集 $E_{1} U E_{2}$ 的简单图。 $G_{1}$ 和 $G_{2}$ 的并图表示成 $G_{1} U G_{2}$ 。

图的同构

图的表示

邻接表（适用稀疏图）（$adjacency \ table$）

无向图邻接表

有向图邻接表

邻接矩阵（适用稠密图）（$adjacency \ matrix$）

邻接矩阵

关联矩阵（$incidence \ matrix$）

关联矩阵

关联矩阵示例

图的同构（$isomorphism$）

设 $G = (V_{1},E_{1})$ 和 $G = (V_{2}, E_{2})$ 是简单图，若存在一对一的和映上的从 $V_{1}$ 到 $V_{2}$ 的函数 $f$ ，且 $f$ 具有这样的性质：对 $V_{1}$ 中所有的 $a$ 和 $b$ 来说， $a$ 和 $b$ 在 $G_{1}$ 中相邻当且仅当 $f(a)$ 和 $f(b)$ 在 $G_{2}$ 中相邻，则称 $G_{1}$ 与 $G_{2}$ 是同构的。这样的函数 $f$ 称为同构。两个不同构的简单图称为非同构的。

(同构：两个图更换顶点和边名字后完全一样，可以移动顶点和边的位置)

同构图

图同构的判定

必要条件

顶点数相等。

边数相等。

对应顶点的度数相等。

判定时先看必要条件，若相同，暴力移动一个图顶点的位置，看是否可以移动成另一个图。

例题

该图是同构的，可尝试同构。

连通性（$connectivity$）

无向图连通性

若无向图中每一对不同的顶点之间都有通路，则该图称为连通的。

无向图连通性

$G_{1}$ 连通， $G_{2}$ 不连通。

有向图连通性

若对于有向图中的任意顶点 $a$ 和 $b$ ，都有从 $a$ 到 $b$ 和从 $b$ 到 $a$ 的通路，则该图是强连通的。（同一个强连通分量内，任意两点可互达）

有向图连通性

$G$ 是强连通的， $H$ 不是强连通的。（$H$ 中 $b$ 可以到 $a$ ， $a$ 不可以到 $b$ ）

通路与同构

判断是否都具有特定长度的简单回路，来证明两个图是不是同构的。还可以用通路求出潜在的同构映射。

计算顶点间的通路数

设 $G$ 是一个图，该图的邻接矩阵 $A$ 相对于图中的顶点顺序 $v_{1}, v_{2}, ··· , v_{n}$ （允许带有无向或有向边、带有多重边和环）。从 $v_{i}$ 到 $v_{j}$ 长度为 $r$ 的不同通路的数目等于 $A^{r}$ 的第 $(i,j)$ 项，其中 $r$ 是正整数。

证明

用数学归纳法证明。设 $G$ 是带有邻接矩阵 $A$ 的图（假设 $G$ 的顶点具有顺序 $v_{1}, v_{2}, ··· , v_{n}$ ）。从 $v_{i}$ 到 $v_{j}$ 长度为 $1$ 的通路数是 $A$ 的第 $(i,j)$ 项，因为该项是从 $v_{i}$ 到 $v_{j}$ 的边数。

假设 $A^{r}$ 的第 $(i,j)$ 项是从 $v_{i}$ 到 $v_{j}$ 长度为 $r$ 的不同通路的个数。这是归纳假设。因为 $A^{r + 1} = A^{r}A$ ，所以 $A^{r + 1}$ 的第 $(i,j)$ 项等于 $
b_{i1} a_{1j} + b_{i2} a_{2j} + ··· + b_{in} a_{nj}$

其中 $b_{ik}$ 是 $A^{r}$ 的第 $(i,k)$ 项。根据归纳假设， $b_{ik}$ 是从 $v_{i}$ 到 $v_{k}$ 长度为 $r$ 的通路数。

从 $v_{i}$ 到 $v_{j}$ 长度为 $r+1$ 的通路，包括从 $v_{i}$ 到某个中间顶点 $v_{k}$ 长度为 $r$ 的通路以及从 $v_{k}$ 到 $v_{j}$ 的边。根据计数的乘积法则，这样的通路个数是从 $v_{i}$ 到 $v_{k}$ 长度为 $r$ 的通路数（即 $b_{ik}$ ）与从 $v_{k}$ 到 $v_{j}$ 的边数（即 $a_{kj}$）积。当对所有可能的中间顶点 $v_{k}$ 求这些乘积之和时，根据计数的求和法则，就可以得出所需要的结果。

欧拉通路（$Euler \ path$）与哈密顿通路 （$Hamilton \ path$）

欧拉回路和欧拉通路

欧拉回路（$Euler \ circuit$）：图 $G$ 中的欧拉回路是包含 $G$ 的每一条边的简单回路。

欧拉通路（$Euler \ path$）：图 $G$ 中的欧拉通路是包含 $G$ 的每一条边的简单通路。

欧拉回路和欧拉通路充要条件

欧拉回路

含有至少 $2$ 个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都为偶数。

欧拉通路

连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有 $2$ 个度为奇数的顶点。

（欧拉回路与欧拉通路不共存）

哈密顿回路和哈密顿通路

哈密顿回路（$Hamilton \ circuit$）：经过图 $G$ 中每一个顶点恰好一次的简单回路称为哈密顿回路。

哈密顿通路（$Hamilton \ path$）：经过图 $G$ 中每一个顶点恰好一次的简单通路称为哈密顿通路。

哈密顿回路的充分条件

（注意是充分条件）

狄拉克定理： 如果 $G$ 是有 $n$ 个顶点的简单图，其中 $n \ge 3$ ，并且 $G$ 中每个顶点的度都至少为 $n/2$ ，则 $G$ 有哈密顿回路。

欧尔定理：如果 $G$ 是有 $n$ 个顶点的简单图，其中 $n \ge 3$ ，并且对于 $G$ 中每一对不相邻的顶点 $u$ 和 $v$ 来说，都有 $deg(u) + deg(v) \ge n$ ，则 $G$ 有哈密顿回路。

最短通路问题

Dijkstra

Dijkstra

平面图（$planar \ graph$）

若可以在平面中画出一个图而边没有任何交叉（其中边的交叉是表示边的直线或弧线在它们的公共端点以外的地方相交），则这个图是平面图。这种画法称为这个图的平面表示。

平面图

欧拉公式

设 $G$ 是带 $e$ 条边和 $v$ 个顶点的连通平面简单图。设 $r$ 是 $G$ 的平面图表示中的面数。则 $r = e - v + 2$ 。

推论 $1$ ：若 $G$ 是 $e$ 条边和 $v$ 个顶点的连通平面简单图，其中 $v \ge 3$ ，则 $e \le 3v - 6$ 。

推论 $2$ ：若 $G$ 是连通平面简单图，则 $G$ 中有度数不超过 $5$ 的顶点。

推论 $3$ ：若连通平面简单图有 $e$ 条边和 $v$ 个顶点， $v \ge 3$ 并且没有长度为 $3$ 的回路，则 $e \le 2v - 4$ 。

推论 $4$ ：若连通平面简单图有 $e$ 条边和 $v$ 个顶点， $v \ge 3$ 并且没有长度为 $x$ 的回路，则 $e \le \frac {x + 1}{x - 1} (v - 2)$ 。

证明推论 $4$ ：

握手定理： $2e = \sum\limits_{v \in V} deg(v)$ 。

面的度数之和等于边数的两倍 $2e = \sum\limits_{所有区域R} deg(R)$ 。

没有长度为 $x$ 的回路意味着面的度必然至少为 $x + 1$ 。（该条件需要证明，本证明直接使用结论）

$\sum\limits_{所有区域R} deg(R) \ge (x + 1) * r$

因此，$\frac {2e}{x + 1} \ge r$ 。

欧拉公式：$r = e - v + 2$ 。

所以，$e \le \frac {x + 1}{x - 1} (v - 2)$ 。

库拉图斯基定理

一个图是非平面图当且仅当它包含一个同胚于 $K_{3,3}$ 或 $K_{5}$ 的子图。（判定平面图重要定理）

若一个图是平面图，则通过删除一条边 $\lbrace u,v \rbrace$ 并且添加一个新顶点 $w$ 和两条边 $\lbrace u,w \rbrace$与 $\lbrace w, v \rbrace$ 获得的任何图也是平面图。这样的操作称为初等细分。若可以从相同的图通过一系列初等细分来获得图 $G = (V_{1},E_{1})$ 和图 $G = {V_{2},E_{2}}$ ，则称它们是同胚的。

同胚的图

图着色（$Coloring$）

简单图的着色是对该图的每个顶点都指定一种颜色，使得没有两个相邻的顶点颜色相同。

图的着色数是着色这个图所需要的最少颜色数。图 $G$ 的着色数记作 $\chi (G)$ 。

四色定理

平面图的着色数不超过 $4$ 。（可用于证反）

图着色应用

把互斥的两个顶点建边，求着色。

例：安排期末考试，频率分配等。

树（$tree$）

树的概述

树是没有简单回路的连通无向图。

一个无向图是树当且仅当在它的每对顶点之间存在唯一简单通路。

有根树 （$rooted \ tree$）

有根树是指定一个顶点作为根并且每条边的方向都离开根的树。

树叶：没有孩子的节点。

若有根树的每个内点都有不超过 $m$ 个孩子，则称它为 $m$ 叉树。若该树的每个内点都恰好有 $m$ 个孩子，则称它为满 $m$ 叉树。把 $m = 2$ 的 $m$ 叉树称为二叉树。

树的性质

带有 $n$ 个顶点的树含有 $n - 1$ 条边。

计算满 $m$ 叉树中的顶点数

带有 $i$ 个内点的满 $m$ 叉树含有 $n = mi + 1$ 个顶点。

证 除了根之外的每个顶点都是内点的孩子。因为每个内点有 $m$ 个孩子，所以在树中除了根之外还有 $mi$ 个顶点。因此，该树含有 $n = mi + 1$ 个顶点。

假定 $T$ 是满 $m$ 叉树。设 $n$ 是树的顶点数， $i$ 是该树的内点数， $l$ 是树叶数。一旦 $n, i, l$ 中的一个已知，另外的两个量就随之确定了。

  1. $n$ 确定， $i = (n - 1) / m \quad \quad \quad \quad l = [(m - 1)n + 1] / m$
  2. $i$ 确定， $n = mi + 1 \quad \quad \quad \quad \quad \ \ l = (m - 1)i + 1$
  3. $l$ 确定， $n = (ml - 1) / (m - 1) \quad i = (l - 1) / (m - 1)$

在高度为 $h$ 的 $m$ 叉树中至多有 $m^{h}$ 个树叶。

树的应用

二叉搜索树 （$binary \ search \ tree$）

决策树（$decision \ tree$）

基于二元比较的排序算法至少需要 $\lceil logn! \rceil$ 次比较。（即 $nlogn$ ）

前缀码（$prefix \ code$）

$Huffman$ 编码。

博弈树 （$game \ tree$ ）

对称状态要剪枝

掌握决策树画法

石子游戏

石子游戏

井字游戏

井字游戏

树的遍历

前序遍历（$preorder$）

前序遍历

中序遍历（$inorder$）

中序遍历

后序遍历（$postorder$）

后序遍历

生成树（$spanning \ tree$）

设 $G$ 是简单图。 $G$ 的生成树是包舍 $G$ 的每个顶点的 $G$ 的子图。

简单图是连通的当且仅当它有生成树。

深度优先搜索（$dfs$）

深度优先搜索

宽度优先搜索（$bfs$）

宽度优先搜索

最小生成树 ($MST$)

连通加权图里的最小生成树是具有边的权之和最小的生成树。

普林算法（$Prim$）

Prim

克鲁斯卡尔算法（$Kruskal$）

Kruskal

后记

$Created by GitSteve1025$

祝大家取得理想成绩！！！