离散数学

基础概念

集合的概念

包含$ M_{1} M_{2} $ : 每一个$M_{1}$的元素都属于$M_{2}$

不包含于 $ M_{1} M_{2}$：有一个$M_{1}$的元素不属于$M_{2}$

差集 $M_{2} \backslash M_{1}$: $M_{2}$里去除$M_{1}$ 的元素

真包含于 $M_{1} \subsetneq M_{2}$: 满足$ M_{1} M_{2} $，且 $M_{2} \backslash M_{1}$不是空集

对称差集 (symmetrische Diﬀerenz) $M_{1} \Delta M_{2}$：在$M_{1}$不在$M_{2}$和在$M_{2}$不在$M_{1}$的元素

集合的容量(Mächtigkeit/Kardinalität) $|M|$: 集合中(不同)元素的个数

有限集： $|M|<\infty$

全集(Universum)：$\Omega$

补集(Komplement)：$\bar{A}$

交集和并集(Schnitt und Vereinigung )

交集：$M_{1} \cap M_{2}$

如果 $M_{1} \cap M_{2}=\emptyset$，那么$M_{1}$和$M_{2}$是分离的(disjunkt)

\[ \begin{aligned} \cap S &:=\bigcap_{M \in S} M \\ \cup S &:=\bigcup_{M \in S} M \end{aligned} \]

$S$是集合的集合。交集表示所有M取交集，并集表示苏哟M取并集

若 \[S=\left\{M_{1}, \ldots, M_{k}\right\}\] ,那么可以写成 $\bigcup_{i=1}^{k} M_{i}:=\cup S \quad \bigcap_{i=1}^{k} M_{i}:=\cap S$

幂集(Potenzmenge)

\[ \mathcal{P}(M):=2^{M}:=\{A | A \subseteq M\} \]

幂集包含所有子集，比如 \[ \begin{aligned} \mathcal{P}(\{1,2\}) &=\{\emptyset,\{1\},\{2\},\{1,2\}\} \\ \mathcal{P}(\{1,2,3\}) &=\{\emptyset,\{1\},\{2\},\{3\}\\ &\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} \\ \mathcal{P}(\emptyset) &=\{\emptyset\} \\ \mathcal{P}(\{\emptyset,\{\emptyset\}\}) &=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\} \end{aligned} \]

划分(Partition)

划分$P$是幂集的子集，它们之间都是分离的，而且并起来刚好是M全集 \[ P \subseteq \mathcal{P}(M) \] 比如$\{1,2,3\}$的划分可以是： \[ \{\{1,2,3\}\},\{\{1\},\{2,3\}\},\{\{1,2\},\{3\}\},\{\{1,3\},\{2\}\},\{\{1\},\{2\},\{3\}\} \]

韦恩图和卡诺图

4个变量：

5个变量：

集合的关系公式

交换律，结合律 \[ \begin{array}{rlrl} A & =A \cup A & A \cup B & =B \cup A \\ A & =A \cap A & A \cap B & =B \cap A \\ A & =A \cup \emptyset & A \cup(B \cup C) & =(A \cup B) \cup C \\ \emptyset & =A \cap \emptyset & A \cap(B \cap C) & =(A \cap B) \cap C \end{array} \] 德摩根定律，和其他性质 \[ \begin{aligned} 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 \backslash(B \cup C) &=(A \backslash B) \cap(A \backslash C) \\ A \backslash(B \cap C) &=(A \backslash B) \cup(A \backslash C) \\ A &=A \cup(A \cap B) \\ A &=A \cap(A \cup B) \\ A \Delta B &=(A \backslash B) \cup(B \backslash A) \end{aligned} \] 带全集 \[ \begin{aligned} &A \cap \bar{A}=\emptyset \quad \quad \quad \bar{\bar{A}} = A\\ &\begin{array}{ll} A \cup \bar{A}=\Omega & \overline{A \cup B}=\bar{A} \cap \bar{B} \\ A \backslash B=A \cap \bar{B} & \frac{\overline{A \cap B}}{\bar{A} \cup \bar{B}} \end{array} \end{aligned} \]

练习题

根据式子化卡诺图

$G_{b}:=\overline{((B \cap A) \ \bar{B}) \backslash((B \cap A) \cap(C \cup A))}$

转换式子式子

证明等式: $\overline{ \overline{(\overline{C} \cup B) \cap(\overline{C} \cup A)} \cup \overline{B}}=(\overline{C} \cup(B \cap A)) \cap B$

\[ \begin{array}{rll} & \overline{ \overline{(\overline{C} \cup B) \cap(\overline{C} \cup A)} \cup \overline{B}} & (\overline{(F \cap G)}=\bar{F} \cup \bar{G}) \\ = &\overline{ \overline{((\bar{C} \cup B) \cap(\bar{C} \cup A)) \cap B}} & (F=\bar{F}) \\ = & ((\bar{C} \cup B) \cap(\bar{C} \cup A)) \cap B & (F \cup(G \cap H)=(F \cap G) \cup(F \cap H)) \\ = & (\bar{C} \cup(B \cap A)) \cap B & () \end{array} \]

元组Tupel

Tupel是带顺序和重复的集合 \[ (a, b, \emptyset,\{b, a\}, a) \neq(\emptyset,\{a, b\}, a, b) \]

序列Sequenz/Folge

序列以一定顺序列出对象:$\left(a_{1}, a_{2}, \dots\right)$，简短写为：$\left(a_{i}\right)_{i \in \mathbb{N}}$

比如 $(i)_{i \in \mathbb{N}_{0}}=(0,1,2,3, \dots),(1 / i)_{i \in \mathbb{N}}=(1,1 / 2,1 / 3,1 / 4, \dots)$

对于 $k \in \mathbb{N}$ 我们定义 $[k]:=\{1,2, \ldots, k\}$ ，且$[0]=\emptyset$

序列的长度

$|t|$ 或者$\#t$ 表示一个Tupel的长度。比如 \[ \begin{aligned} &|(a,(b, c))|=2\\ &|(a, a, a, a, a, a)|=6\\ &|(\{a, b\},\{b, a\}, \emptyset,(a,\{(b, \emptyset)\}))|=4 \end{aligned} \]

笛卡尔积(kartesische Produkt)

\[ A \times B=\{(a, b) | a \in A, b \in B\} \]

\[ A_{1} \times A_{2} \times \ldots \times A_{k}=\left\{\left(a_{1}, a_{2}, \ldots, a_{k}\right) | a_{1} \in A_{1}, a_{2} \in A_{2}, \ldots, a_{k} \in A_{k}\right\} \]

Tupel的次幂

\[ A^{k}=\underbrace{A \times \ldots \times A}_{k \text { mal }}=\left\{\left(a_{1}, \ldots, a_{k}\right) | a_{1} \in A, a_{2} \in A, \ldots, a_{k} \in A\right\} \]

同时满足：$A^{0}:=\{()\}$ 且 $A^{1}:=\{(a) | a \in A\} \neq A$

文字和语言(Wörter und Sprachen)

字符集(Alphabet)

字符集一般用$\Sigma$ 或者 $\Gamma$表示，如$\{a, \ldots, z, A, \ldots, Z, 0, \ldots, 9\}$ \[ \Sigma^{*}:=\bigcup_{k \in \mathbb{N}_{0}} \Sigma^{k}=\cup\left\{\Sigma^{k} | k \in \mathbb{N}_{0}\right\} \] $\Sigma^{*}$ 中的元素叫文字。对于空集 $()$ 通常用 $\varepsilon$ 或者 $\lambda$ 表示

为了避免疑惑，通常把文字$\left(a_{1}, a_{2}, \dots, a_{k}\right)$ 写成 $a_{1} a_{2} \dots a_{k}$

关系

给定集合 $A_{1}, A_{2}, \ldots, A_{k},$ 于是关系表示为 $R \subseteq A_{1} \times A_{2} \times \ldots \times A_{k}$

组合和投影

Join

\[ R \bowtie_{i=j} S=\left\{\begin{array}{cc} \left(r_{1}, \ldots, r_{k}, s_{1}, \ldots, s_{l}\right) |\left(r_{1}, \ldots, r_{k}\right) \in R, & \left(s_{1}, \ldots, s_{l}\right) \in S,&r_{i}=s_{j} \end{array}\right\} \]

Projektion

\[ \pi_{i_{1}, i_{2}, \ldots, i_{j}}(R)=\left\{\left(r_{i_{1}}, r_{i_{2}}, \ldots, r_{i_{j}}\right) |\left(r_{1}, \ldots, r_{k}\right) \in R\right\} \]

例如对于下面的数据表 \[ \begin{array}{c|c|cc|cc|c} A_{\mathrm{ld}} & A_{\text {Nachname }} & A_{\text {Vorname }} & A_{\text {ld }} & A_{\text {Matrikelnummer }} & A_{\text {ld }} & A_{\text {Geschlecht }} \\ \hline 1 & \text { Man } & \text { Spider } & 1 & 3141 & 1 & \mathrm{m} \\ 2 & \text { Brot } & \text { Bernd } & 2 & 271828 & 2 & \mathrm{b} \\ 3 & \text { Woman } & \text { Wonder } & 3 & 2017 & 3 & \mathrm{w} \\ 4 & \text { Gaga } & \text { Lady } & 4 & 3694 & 4 & \mathrm{w} \end{array} \]

\[ \pi_{3}\left(R \bowtie_{1=1}\left(T \bowtie_{2=1}\{(w)\}\right)\right) \]

二元关系

在二元关系中，只有两个集合$R \subseteq A \times B$

常用中缀表示法来表示二元关系：$a R b$ 代替 $(a, b) \in R$

它经常用在图论中

关系乘积

\[ R S=\{(a, d) | \text { es gibt } x \in B \cap C \text { mit }(a, x) \in R \text { und }(x, d) \in S\} \]

关系次幂

可以理解为，走几步可以到达的点 \[ \begin{aligned} &R^{0}:=\operatorname{ld}_{A}:=\{(a, a) | a \in A\}\\ &R^{1}:=R=R^{0} R\\ &R^{2}:=R R=R^{1} R\\ &R^{k+1}:=R^{k} R=R R^{k}=\underbrace{R R \ldots R}_{k+1 \mathrm{mal}} \text { für beliebiges } k \in \mathbb{N}_{0} \end{aligned} \] 特别的，有逆关系。可以理解为反向图 \[ R^{-1}:=\{(b, a) |(a, b) \in R\} \] 其他符号：

走1步以上能到的 \[ R^{+}:=\bigcup_{k \in \mathbb{N}} R^{k} \] 联通的 \[ R^{*}:=\bigcup_{k \in \mathbb{N}_{0}} R^{k}=R^{0} \cup R^{+} \] 最多走k步能到的 \[ R^{\leq k}:=\bigcup_{i=0}^{k} R^{i} \]

证明

$A$ 是有限集且，$n=|A|,$ 那么 $R^{*}=R^{\leq n-1}:$

先证明$R^{*} \subseteq R^{\leq n-1}$，再证明$R^{\leq n-1} \subseteq R^{*}$ 。后者根据定义显而易见

也就是证明，对于$s$ 到 $t$最多走$n-1$步。假设s先走到u，然后绕一圈再走到$u$，然后走到$t$。那么可以简化为$s$到$u$到$t$。所以我们可以得到一条简单路径(走过的所有点都不一样)。由于一共$n$个点，所以最多$n-1$步，得证。

二元关系的性质

reflexiv I

$\mathrm{Id}_{A} \subseteq R$, 每个点有自环
symmetrisch

对于所有$(s, t) \in R,$有$(t, s) \in R$。每条边都有反向边
asymmetrisch

对于所有$(s, t) \in R,$有。$(t, s) \notin R$ 。无自环，且无反向边
antisymmetrisch

若$(s, t) \in R,$且$(t, s) \in R$，那么$s=t$。无反向边
transitiv

若$(s, t) \in R$ ，且 $(t, u) \in R$，那么$(s, u) \in R$。传递性

等价关系(Äquivalenzrelationen)

共同点：reﬂexiv, transitiv, symmetrisch

等价类（Äquivalenzklasse）

\[ [a]_{R}=\{b \in A | a R b\} \]

例如：$[1]_{=z}=\{1\},[-5] \equiv_{3}=3 \mathbb{Z}+1$

商(Quotient)

A集合关于R的商： \[ A / R=\left\{[a]_{R} | a \in A\right\} \] 例如：$\mathbb{Z} /=_{\mathbf{z}}=\{\{x\} | x \in \mathbb{Z}\}, \mathbb{Z} / \equiv_{3}=\{3 \mathbb{Z}, 3 \mathbb{Z}+1,3 \mathbb{Z}+2\}$

序关系（Ordnungsrelationen）

共同点: reﬂexiv, antisymmetrisch, transitiv

Halbordnung

$R \subseteq A \times A$ 是 $A$上的偏序关系(partielle Ordnung)，当$R$ 满足reﬂexiv, antisymmetrisch, transitiv

Totalordnung

$R$ 是 $A$ 上的偏序关系，且对于每个再$R$中的 $a, b$ , 至少有 $aRb$ 或者 $bRa$ 。

Irreﬂexiv

$(a, a) \notin R$，无自环，也可以表示成：$R \cap \operatorname{ld}_{A}=\emptyset$

例如：$<_{\mathrm{z}}=\leq_{ \mathrm{z}} \backslash \mathrm{Id}_{\mathrm{Z}}$

Hasse图

Hasse图是画一张尽可能少边，表示关系的图

$S \subseteq R$ ，且$S^{*}=R$ 的最少 $S$

maximales/minimales Element

$m \in A$ 是关于 $R$ 的局部最大元素，若 $m R a$ 对于 $a \in A,$ 那么 $aR m$ 且 $a=m$

没有到其他元素的边

$m \in A$是关于 $R$ 的局部最小元素，若 $a R m$ 对于 $a \in A,$ 那么 $mR a$ 且 $a=m$

其他的点没有到它的边

größtes/kleinstes Element

$m$ 是关于 $R$ 的最大元素，若 $m R a$ 对于每个 $a \in A$ 成立

没有到其他元素的边，但每个元素都有一条边到它

$m$ 是关于 $R$ 的最小元素，若 $a R m$ 对于每个 $a \in A$ 成立

其他元素没有到自己的边，自己到每个元素都有边

函数

一个关系$R \subseteq A \times B$ 是一个函数，若对于每个 $a \in A$ , 只有一个 $b \in B$ 使得 $(a, b) \in R$ 。

一些记号

$f, g, h, \ldots$ 可以表示函数
$f: A \rightarrow B$ 的意思是，$f \subseteq A \times B$ 。也就是从A映射到B的函数
$f(a)$ 表示那个唯一的 $b \in B$ 使得 $(a, b) \in R$ 。
可以用右箭头 $\mapsto$ 来定义， $f: \mathbb{R} \rightarrow \mathbb{R}, x \mapsto x^{2}+1$
$B^{A}:=\{f: A \rightarrow B\}$ , 也是A到B的函数
$A=\times_{i=1}^{k} A_{i}$ 写成 $f\left(a_{1}, \dots, a_{k}\right)$ ，而不是$f\left(\left(a_{1}, \dots, a_{k}\right)\right)$
$f:\{()\} \rightarrow B$ 表示空函数

定义域和值域

$Dom(f)$ 是定义域 $A$
$Rng(f)$ 是集合 $\{f(a) | a \in A\}$

$f: A \rightarrow B\ ,X \subseteq A$ 且$Y \subseteq B$

$f^{-1}(Y)=\{a \in A | f(a) \in Y\} \subseteq \operatorname{Dom}(f)$

$f(X)=\{f(a) | a \in X\} \subseteq \operatorname{Rng}(f)$

半函数(partielle Funktion)

对于每个 $a \in A$ , 最多只有一个 $b \in B$ 使得 $(a, b) \in R$ 。

标记：$f: A \hookrightarrow B$ : $\operatorname{Dom}(f) \subseteq A$

操作

$f: A^{k} \rightarrow A$ 被称作关于A的k元操作(k-stellige Operationen)

二元操作

$\odot: A \times A \rightarrow A$。像这写二元操作经常会写中缀形式。如 $\left(x+_{\mathbb{R}} y\right)$ 代替 $+_{\mathbb{R}}(x, y)$

assoziativ ，若 $(a \odot b) \odot c=a \odot(b \odot c)$
kommutativ ，若 $a \odot b=b \odot a$
idempotent ，若 $a \odot a=a$

复合

$(g \circ f)(a):=g(f(a))$ 是$f: A \rightarrow B$ 和 $g: B \rightarrow C$ 的复合函数 \[ (g \circ f): A \rightarrow C, a \mapsto g(f(a)) \] 函数符合满足结合律，但不满足交换律 \[ \begin{aligned} (h \circ(g \circ f))(a) &=h((g \circ f)(a)) \\ &=h(g(f(a))) \\ &=(h \circ g)(f(a))=((h \circ g) \circ f)(a) \end{aligned} \]

函数的性质

injektiv，若从$f(a)=f\left(a^{\prime}\right)$ 可以推出 $a=a^{\prime}$

等价于： $\left|f^{-1}(\{b\})\right| \leq 1$ 对于每个 $b \in B$
surjektiv，若对每个 $b \in B$ 有 $a \in A$ 使得 $f(a)=b$

等价于：$f(A)=B, \operatorname{Rng}(f)=B,\left|f^{-1}(\{b\})\right| \geq 1$ 对于每个 $b \in B$ 成立
bijektiv，同时满足injektiv和surjektiv

等价于：$\left|f^{-1}(\{b\})\right|=1$ 对于每个 $b \in B$

一个bijektiv的函数我们叫Permutation

反函数

若 $f$ 是bijektiv的，那么$\left\{(b, a) | b \in B, a \in f^{-1}(\{b\})\right\} \in A^{B}$ 也是一个函数，且是它的反函数，用$f^{-1}$ 表示

证明

$R:=\left\{(b, a) | b \in B, a \in f^{-1}(\{b\})\right\} \in A^{B}$是一个函数

也就是要证明每个 $b \in B$ 只有1 个 $a \in A$

每个 $b$ 有一个映射值

对于任意的$b \in B$, 由于$f$ 是surjektiv的，那么每个$b \in B$ 有 $a \in A$ 使得 $f(a)=b$
若存在 $(b, a) \in R$ 且$\left(b, a^{\prime}\right) \in R,$ 那么$ a=a^{}$

由于$f(a)=b=f\left(a^{\prime}\right)$ ，且$f$ 是injektiv的，那么$ a=a^{}$

一些性质和证明

$f^{-1}$ 也是一个bijektiv的函数

$f^{-1}$ 是一个injektiv的函数

任取 $b, b^{\prime} \in B$ 且$b \neq b^{\prime}$，则要证 $f^{-1}(b) \neq f^{-1}\left(b^{\prime}\right)$。它的逆否命题(Kontraposition)是:

若 $f^{-1}(b)=f^{-1}\left(b^{\prime}\right)$ 那么 $b=b^{\prime}$ 或者$f: A \rightarrow B$不是函数（或两个都成立）

而若 $f^{-1}(b)=f^{-1}\left(b^{\prime}\right):=a$ 且 $b \neq b^{\prime}$，那 $f: A \rightarrow B$ 就不是函数
$f^{-1}$ 是一个surjektiv的函数

任取$a \in A$ ，让 $b:=f(a)$，那么 $f^{-1}(b)=a$

$f: A \rightarrow B$ 是一个bijektiv的函数，那么 $f^{-1}$ 是唯一一个函数 $g$ 使得$(g \circ f)=\operatorname{ld}_{A}$ 且$(f \circ g)=\operatorname{ld}_{B}$

$\left(f^{-1} \circ f\right)=\operatorname{ld}_{A}$ 成立

任取$a \in A$ ，让 $b:=f(a)$，那么 $a \in f^{-1}(\{b\})$，也就是 $a=f^{-1}(b)=f^{-1}(f(a))$
若 $g: B \rightarrow A$ 有性质 $(g \circ f)=\operatorname{ld}_{A},$ 那么 $g=f^{-1}$

$f^{-1}=\operatorname{ld}_{A} \circ f^{-1}=(g \circ f) \circ f^{-1}=g \circ\left(f \circ f^{-1}\right)=g \circ \operatorname{ld}_{B}=g$

若 $f: A \rightarrow B$ 且 $g: B \rightarrow A$ 满足 $(g \circ f)=\operatorname{ld}_{A}$ 和$(f \circ g)=\operatorname{ld}_{B}$，那么 $f, g$ 是 bijektiv的，且 $f^{-1}=g$ 和$g^{-1}=f$

$f$ 是 injektiv 的

若 $a, a^{\prime} \in A$ 且$f(a)=f\left(a^{\prime}\right)$，那么

$a=\operatorname{ld}_{A}(a)=(g \circ f)(a)=g(f(a))=g\left(f\left(a^{\prime}\right)\right)=(g \circ f)\left(a^{\prime}\right)=\operatorname{ld}_{A}\left(a^{\prime}\right)=a^{\prime}$
$f$ 是 surjektiv 的

对于每个 $b \in B$， $g(b)$ 是一个原映射

$b=\operatorname{ld}_{B}(b)=(f \circ g)(b)=f(g(b))$

因为$f^{-1}, g^{-1}$ 唯一，所以$f=g^{-1}$ 且 $g=f^{-1}$

$f: A \rightarrow B$ 且 $g: B \rightarrow C$ bijektiv, 那么 $(g \circ f): A \rightarrow C$ 有 $(g \circ f)^{-1}=\left(f^{-1} \circ g^{-1}\right)$

由于它们bijektiv, 那么存在 $f^{-1}, g^{-1}$
$(g \circ f) \circ\left(f^{-1} \circ g^{-1}\right)=\operatorname{ld}_{C}$ 和$\left(f^{-1} \circ g^{-1}\right) \circ(g \circ f)=\operatorname{ld}_{A}$成立

$(g \circ f) \circ\left(f^{-1} \circ g^{-1}\right)=g \circ f \circ f^{-1} \circ g^{-1}=g \circ \operatorname{ld}_{B} \circ g^{-1}=g \circ g^{-1}=\operatorname{ld}_{C}$

所以根据上一个定理$(g \circ f),\left(f^{-1} \circ g^{-1}\right)$ bijektiv，且 $(g \circ f)^{-1}=\left(f^{-1} \circ g^{-1}\right)$

若 $(g \circ f): A \rightarrow C$ bijektiv, 那么 $f: A \rightarrow B$ injektiv 且$g: B \rightarrow C$ surjektiv

$h:=(g \circ f)$, 由于 bijektiv ，存在 $h^{-1}$
$f: A \rightarrow B$ injektiv

若$f(a)=f\left(a^{\prime}\right)$ ，那么 $h(a)=h(a)=: c$ , 有$a=h^{-1}(c)=a^{\prime}$

$g$ 是 surjektiv, 因为 $b=f\left(h^{-1}(c)\right)$ 是c的原射 $c \in C$ ist

集合的势(Kardinalität)

集合的势是用来比较无限集的手段。

我们定义：

$|A| \leq|B|$ ，若存在一个injektiv的函数 $f: A \rightarrow B$

$|A|=|B|$，若存在一个bijektiv的函数 $f: A \rightarrow B$

例如

$|\mathbb{N}|=|2 \mathbb{N}|$ ，因为$\mathbb{N} \rightarrow 2 \mathbb{N}, n \mapsto 2 n$ 且 $2 \mathbb{N} \rightarrow \mathbb{N}, n \mapsto n$

我们说一个集合是可数的(abzählbar), 若$|A| \leq|\mathbb{N}|$ ，否则就是不可数的 (überabzählbar)

$|A|$ 就是集合的势数(Kardinalzahl)

不可数集合

康托尔定理((Satz von Cantor)： $|A|<|\mathcal{P}(A)|$

证明：通过 $f: A \rightarrow \mathcal{P}(A), a \mapsto\{a\}$ 有 $|A| \leq|\mathcal{P}(A)|$

我们只要再证明：没有bijektiv的函数 $f: A \rightarrow \mathcal{P}(A)$。我们通过反证法Diagonalisierung证明

假设 $g: A \rightarrow \mathcal{P}(A)$ bijektiv。让 $M=\{a \in A | a \notin g(a)\} \in \mathcal{P}(A)$

由于 $g$ 已经是bijektiv的，那么存在 $m \in A$ 使得 $g(m)=M$ 。那么问题来了 $m \in M$ 吗

$m \in M$，那么 $m \notin g(m)$ , 而 $g(m) = M$ 所以 $m \notin M$ 矛盾
$m \notin M$，那么 $m \in g(m) = M$ ，又矛盾了

综上，不存在这个bijektiv的函数

多重集合

多重集合是考虑顺序的集合，我们用 $\{\}_{M}$来表示多重集 \[ \begin{aligned} \{a, b, c, a\}_{\mathrm{M}}=\{b, c, a, a\}_{\mathrm{M}} & \neq\{b, a, c\}_{\mathrm{M}} \\ &=\{a, b, c\}=\{a, b, b, c\} \neq\{a, b, b, c\}_{\mathrm{M}} \end{aligned} \] 对于固定的全集 $\Omega$ , 我们可以用数函数(Zählfunktionen) $ m _{0}^{} $来表达, 例如 $\Omega=\{a, b, c, d\}$ \[ \{a, b, c, a\}_{\mathrm{M}}=\{(a, 2),(b, 1),(c, 1),(d, 0)\} \] 表示a出现2次，b出现1次，c出现1次，d出现0次

图论

有向图(Digraphtn)

有向图由边集和点集构成 $G=(V, E)$ ，$E \subseteq V \times V$，若点集合$V$ 有限，那么图就是有限的

二分图

一个图是二分图(bipartit)，若 $V=A \cup B$ 且 $A \cap B=\emptyset$ (简写：$V=A \uplus B$) ，并且 $E \subseteq A \times B \cup B \times A$

没有A和B中自己的边。

路径

点的序列 $v_{0}, v_{1}, \dots, v_{l}$ ，叫路径(Pfad), 若对于每个 $i \in[l]$ 满足 $\left(v_{i-1}, v_{i}\right) \in E$，路径的长度是 $l$

简单路径

一个路径是简单路径，若每个点不重复出现。也就是最多有 $|V|-1$ 长度的简单路径

子图(Teilgraphen)

对于 $U \subseteq V$ ，我们写 $G[U]$ 表示 $(U, E \cap(U \times U))$ 子图。

一个有向图 $H=\left(V_{H}, E_{H}\right)$ 是 $G=\left(V_{G}, E_{G}\right)$ 的子图，若满足 $V_{H} \subseteq V_{G}$ 和 $E_{H} \subseteq E_{G}$

连通(Zusammenhang)

$G$ 是连通的(zusammenhängend)，若对于每个 $u, v \in V$ 满足 $u\left(E \cup E^{-1}\right)^{*} v$

$G$ 是强连通的(stark zusammenhängend)，若对于每个 $u, v \in V$ 满足 $u E^{*} v$ 和 $v E^{*} u$

$U \subseteq V$ 是一个(强)连通分量，若 $G[U]$ (强)连通

$U$ 是一个最大(强)连通分类，若没有满足 $U \subsetneq U^{\prime} \subseteq V$ 的 $U^{\prime}$ 使得 $G\left[U^{\prime}\right]$ 是一个(强)连通分量

环(Kreis)

环是一个路径 $v_{0}, v_{1}, \dots, v_{l}$ ，且$l \geq 1$ ，$v_{0}=v_{l}$。

一个环是简单的，若 $v_{0}, v_{1}, \dots, v_{l-1}$ 每2个都不同，即 $\left|\left\{v_{0}, v_{1}, \dots, v_{l}\right\}\right|=l$ 该环不包含更小的环

连向自己的边 $(u, u) \in E$，叫自环(Schleife)

有向无环图叫 azyklisch (DAG)

若 $u E v$ ，那么 $u$ 是 $v$ 的前驱(Vorgänger)， $v$ 是 $u$ 的后继(Nachfolger)

图同构(Isomorphie)

两个图 $G, H$ 是同构的 $G \cong H$ ，若存在一个双射(Bijektion) $\beta: V_{G} \rightarrow V_{H}$ 使得 $u E_{G} v$ 等价于 $\beta(u) E_{H} \beta(v)$

例如： $\beta(1)=5, \beta(2)=3, \beta(a)=7, \beta(b)=2$

无向图和简单图

一个有向图 $G=(V, E)$ 是无向的，若它对称 symmetrisch

一个有限的有向图是一个简单图，若它无向且没有自环，即 symmetrisch 和 irreflexiv

我们把 $(u, v),(v, u) \in E \subseteq V \times V$ 替换成 $\{u, v\} \in E \subseteq\left(\begin{array}{l}V \\ 2\end{array}\right)$

$\left(\begin{array}{l}V \\ 2\end{array}\right):=\{\{u, v\} \subseteq V | u \neq v\}$ 是所有两个元素的子集

我们不说前驱和后继，而是邻居(Nachbarschaft) $\Gamma(u)=\{v \in V |\{u, v\} \in E\}$，和度数 $\operatorname{deg}(u):=|\Gamma(u)|$

环

在无向图中，环的定义有些变换：$v_{0}, v_{1}, \ldots, v_{l}$ 且满足 $l \geq 3, v_{0}=v_{l}$，$\left|\left\{v_{0}, \ldots, v_{l}\right\}\right|=l$ 的是一个环

定理(判定二分图)

一个图是二分的，当且仅当没有奇数长度的环存在

一个二分图不含奇数长度的环

我们用反证法，假设 $G=(A \uplus B, E)$ 是一个有奇数长度环的二分图。不妨设(OBdA) $v_{0} \in A$

那么 $v_{1} \in B, v_{2} \in A$ ，$v_{l} \in B$ 因为 $l$ 是奇数。所以矛盾了
一个不含奇数长度的环是二分图

设 $G=(V, E)$ 是一个不含奇数长度环的图。不妨设$G$ 连通，否则可以分开看。

我们任取一个点 $x \in V$ 。定义$A, B \subseteq V,$ 使得 $x \in A$ ，对于其他的点 $v \in V \backslash\{x\}$：
- 若$v$ 到 $x$ 的最短路径是偶数 $v \in A$
- 若$v$ 到 $x$ 的最短路径是奇数 $v \in B$
若 $v_{1}, v_{2} \in A$ 或者 $v_{1}, v_{2} \in B$ ，由于这样构造图，那么有两条路径 $v_{1}, \dots, x$ 和 $v_{2}, \dots, x$，它们要么都是奇数或者都是偶数。

假如 $x^{\prime}$ 是第一个这两条路径中相同的点。那么$v_{1}, \ldots, x^{\prime}$ 和 $v_{2}, \ldots, x^{\prime}$，要么都是奇数，要么都是偶数。$v_{1}, \dots, x^{\prime}, \dots, v_{2}$ 它肯定是偶数长度的路径。所以不可能有 $\left\{v_{1}, v_{2}\right\} \in E$，因为不存在这样的环：$v_{1}, \dots, x^{\prime}, \dots, v_{2}, v_{1}$。所以它是二分图。

特殊图的分类

完全图(Vollständiger Graph)

\[ K_{n}:=\left([n],\left(\begin{array}{c} [n] \\ 2 \end{array}\right)\right) \]

环图(Kreisgraph)

\[ C_{n}:=([n],\{\{i,(i \bmod n)+1\} | i \in[n]\}) \text { 对于 } n \geq 3 \]

路径图(Pfadgraph)

\[ P_{n}:=([n],\{\{i, i+1\} | i \in[n-1]\}) \]

完全二分图

\[ K_{m, n}:=([m+n],\{\{i, j\} | i \in[m], j \in[m+n] \backslash[m]\})(m \leq n) \]

矩阵图(Gittergraph)

\[ M_{m, n}:=([m] \times[n],\{\{(i, j),(k, l)\}|| i-k|+| j-l |=1\}) \]

立方体图

\[ Q_{n}:=\left(\{0,1\}^{n},\left\{\{u, v\}|\quad\sum_{i=1}^{n}| u_{i}-v_{i} |=1\right\}\right) \text { mit } Q_{0}:=(\{\varepsilon\}, \emptyset) \]

满二叉树(Perfekter Binärbaum)

高度为h的满二叉树 \[ B_{h}:=\left(\{0,1\} \leq h,\left\{\{u, u x\} | u \in\{0,1\}^{<h}, x \in\{0,1\}\right\}\right) \]

节点 $u$ 有 $\operatorname{deg}(u) \leq 1$ 叫叶子(Blatt)，其他叫内部节点(innere Knoten)

数学归纳法证明

对于所有 $h \in \mathbb{N}_{0}: B_{h}$ 有 $2^{h}$ 个叶子

我们用数学归纳法证明

Induktionsbasis：证明 $B_{0}$ 有 $2^{0}=1$个叶子
Induktionsschritt：任选一个固定的$h \in \mathbb{N}_{0}$
- Induktionsannahme: $ B_{h} $它有 $2^{h}$ 个叶子
- Induktionsbehauptung: $ B_{h+1} $它有 $2^{h+1}$ 个叶子
- Beweis der Induktionsbehauptung:
  - $ B_{h+1} $ 中对于 $ B_{h} $ 的每一个叶子 $v $ 有两个叶子 $v_{1}, v_{2}$ 。所以 $ B_{h+1} $ 有 $ B_{h} $ 2倍的叶子
  - 所以 $ B_{h+1} $有 $ 2 ^{h}=2{h+1}$ 个叶子

对于所有 $h \in \mathbb{N}_{0}: B_{h}$ 有 $2^{h+1}-1$ 个节点

Induktionsbasis：$B_{0}$ 有 $2^{1}-1=1$个节点
Induktionsschritt：任选一个固定的$h \in \mathbb{N}_{0}$
- Induktionsannahme: $ B_{h} $它有 $2^{h-1}-1$ 个节点
- Induktionsbehauptung: $ B_{h+1} $它有 $2^{h+2}-1$ 个叶子
- Beweis der Induktionsbehauptung:
  - $ B_{h+1} $ 的节点数是 $ B_{h} $ 的节点数和 $ B_{h+1} $ 的叶子数之和。所以 $ B_{h+1} $ 有 $ B_{h} $ 2倍的叶子
  - 所以 $ B_{h+1} $的节点数$=(2^{h+1}-1)+2{h+1}=2 ^{h+1}-1=2{h+2}-1$

每个简单的有 $n \geq 1$ 个节点的连通图，有至少 $n - 1$ 条边

Induktionsbasis：只有1个节点的图，需要0条边连通n
Induktionsschritt：任选一个固定的$n \in \mathbb{N}$
- Induktionsbehauptung: 每个有 $n +1$ 个节点的连通图，有至少 $n$ 条边
- Induktionsannahme: 每个有 $m<n +1$ 个节点的连通图，有至少 $m-1$ 条边
- Beweis der Induktionsbehauptung:
  
  假设 $G=(V, E)$ 是一个连通图有 $|V|=n+1$ 条边。假设 $u$ 是其中任意一个固定的点，我们移除它，并且考虑$G^{\prime}=G[V \backslash\{u\}]$ ，那么对于子图$G^{\prime}$ 中的$G_{1}, \dots, G_{r}$有 \[ 1 \leq r \leq \operatorname{deg}(u) \quad|V|=1+\sum_{i \in[r]}\left|V_{i}\right| \quad|E|=\operatorname{deg}(u)+\sum_{i \in[r]}\left|E_{i}\right| \] 对于每个连通分量 $G_{i}=\left(V_{i}, E_{i}\right)$ 有 $\left|V_{i}\right| \leq n$ 且 $\left|E_{i}\right| \geq\left|V_{i}\right|-1$ 那么 \[ \begin{aligned} |E| &=\operatorname{deg}(u)+\sum_{i \in[r]}\left|E_{i}\right| \\ & \geq \operatorname{deg}(u)+\sum_{i \in[r]}\left(\left|V_{i}\right|-1\right) \\ &=|V|-1-r+\operatorname{deg}(u) \\ & \geq|V|-1 \\ &=n \end{aligned} \]

每个简单的有 $n \geq 3$ 个节点的连通图，且有至少 $n$ 条边的图一定存在环

Induktionsbasis：对于 $n=3$ 只有 $C_{3}$
Induktionsschritt：任选一个固定的$n \geq 3$
- Induktionsbehauptung: 每个有 $n+1$ 个节点，$n+1$ 条边的连通图存在环
- Induktionsannahme: 对于所有 $3 \leq m \leq n$ 每个有 $m$ 个节点，$m$ 条边的连通图存在环
- Beweis der Induktionsbehauptung:
  
  假设 $G$ 是连通图，有 $n+1 \geq 4$ 个点和 $m \geq n+1$ 条边。我们取任意一条固定的边 $\{u, v\} \in E$ 假设 $G'$ 是溢出这条边后的图。
  
  若$G'$ 仍然连通，那么从$u$ 到 $v$ 一定存在一条路径，通过我们去除的边就一定存在一个环
  
  若$G'$ 不连通，那么存在两个连通分量 $G_{u}, G_{v}$。假设 $ n_{u}, n_{v}$ 是点的个数，$m_{u}, m_{v}$ 是边的数量，那么 \[ n+1=n_{u}+n_{v} \quad m=m_{u}+m_{v}+1 \] 若这两个子图都不存在环，那么 $m_{u}<n_{u}$ 且 $m_{v}<n_{v}$，所以 $m=m_{u}+m_{v}+1<n_{u}+n_{v}=n+1$ 和$m \geq n+1$ 矛盾了。

度数

对于每个简单图 $G=(V, E)$ ，我们可以对度数排列：

对于$V=\left\{v_{1}, v_{2}, \ldots, v_{n}\right\}$ 有 $\left(\operatorname{deg}\left(v_{1}\right), \operatorname{deg}\left(v_{2}\right), \ldots, \operatorname{deg}\left(v_{n}\right)\right)$

一个图叫 $k$ -regulär 图，若对于每个 $v \in V$ 满足 $\operatorname{deg}(v)=k$

Handschlag定理

对于每个图 $G=(V, E)$ ，满足 \[ 2|E|=\sum_{i \in[n]} \operatorname{deg}\left(v_{i}\right) \]

证明：每条边 $\{u, v\} \in E$ 贡献了 $\operatorname{deg}(u)$ 和 $\operatorname{deg}(v)$ 两个度数

图的可实现性(Realisierbarkeit )

定理

存在一个 $n$ 个节点，度数是 $\left(d_{1}, \ldots, d_{n}\right)$ 的简单图当且仅当存在一个 $n-1$ 个节点，度数为 $\operatorname{sort}\left(d_{1}, \ldots, d_{n-d_{n}-1}, d_{n-d_{n}}-1, \ldots, d_{n-1}-1\right)$ 的简单图。其中 $\operatorname{sort}(t)$ 是升序排列

充分性：若存在一个 $n$ 个节点，度数是 $\left(d_{1}, \ldots, d_{n}\right)$ 的简单图，那么去除度数最大的边也存在。若度数不是升序，重新排序即可。
必要性：若存在一个 $n-1$ 个节点，度数是 $\left(d_{1}, \ldots, d_{n-1}\right)$ 的简单图，那么加入最大边也符合。

Havel-Hakimi算法

输入：升序度数 $\left(d_{1}, d_{2}, \ldots, d_{n}\right)$

若 $d_{1}<0$ 或 $d_{n} > n-1$ 那么不存在

若 $d_{n} = 0$ ，返回 $([n], \emptyset)$

否则 $\left(d_{1}^{\prime}, \ldots, d_{n-1}^{\prime}\right):=\left(d_{1}, \ldots, d_{n-d_{n}-1}, d_{n-d_{n}}-1, \ldots, d_{n-1}-1\right)$

求一个 Permutation函数 $\pi:[n-1] \rightarrow[n-1]$，使得 $\left(d_{\pi(1)}^{\prime}, \dots, d_{\pi(n-1)}^{\prime}\right)$ 重新升序排列。

然后递归求解 $G^{\prime}=\left([n-1], E^{\prime}\right)$ ，其中 $\operatorname{deg}(i)=d_{\pi(i)}^{\prime}$

返回 $G=([n], E)$ ，$E=\left\{\{\pi(u), \pi(v)\} |\{u, v\} \in E^{\prime}\right\} \cup\left\{\{n, n-1\}, \ldots,\left\{n, n-d_{n}\right\}\right\}$

树

一个简单图 $G=(V, E)$ 若无环且连通，那么它是一棵树
节点 $u$ 有 $\operatorname{deg}(u) \leq 1$ 叫叶子(Blatt)，其他叫内部节点(innere Knoten)

树的性质

若 $G=(V, E)$ 是一个树，那么 $|E|=|V|-1$

证：每个 $G=(V, E)$ 图，若$|E| \geq|V|$ 那么存在环。每个连通图有 $|E| \geq|V|-1$ 条边。所以 $|V|-1 \leq|E|<|V|$

每个节点数 $|V| \geq 2$ 的树 $G=(V, E)$ 只少有2个叶子

Induktionsbasis：对于 $n=2$ 命题正确
Induktionsschritt：任选一个固定的$n \geq 2$
- Induktionsbehauptung: 每个有 $n+1$ 个节点的树有2个叶子
- Induktionsannahme: 每个有 $2 \leq m \leq n$ 有2个叶子
- Beweis der Induktionsbehauptung:
  
  假设 $G$ 是连通图，有 $n+1 \geq 3$ 个点。我们知道，至少有一个点 $u\in V$ 度数为1。因为连通且无环
  
  假设 $w \in V$ 是 $u$ 的唯一个邻居，我们把 $u$ 和 $\{u,w\}$ 这条边。于是剩下的图 $G'$ 有 $n$ 个点，而且仍然是无环的，因为只是去除了一条边。$G'$ 仍然连通其他点到$u$ 的边都不使用 $\{u,w\}$ 这条边。所以$G'$ 只少有2个叶子。最高1个叶子是 $w$ 。若 $v \neq w$ 那么 $w,v$ 就是 $G$ 的叶子。

定义：假设 $G=(V, E)$ 是一个简单图，那么子图 $T=\left(V, E^{\prime}\right)$ ，$E^{\prime} \subseteq E$ 若是树，那它是一个$G$ 的生成树（Spannbaum）。

每个连通图 $G=(V, E)$ 至少有一个生成树

我们通过对 $k:=|E| \in N _{0}$ 的数学归纳法证明

Induktionsbasis：对于 $k=0$ 命题正确
Induktionsschritt：任选一个固定的$k \geq 0$
- Induktionsbehauptung: 每个有 $k+1$ 条边的树生成树
- Induktionsannahme: 每个有 $\leq k$ 条有生成树
- Beweis der Induktionsbehauptung:
  
  假设 $G=(V, E)$ 是连通图，有 $k+1$ 条边。任取 $\{u, w\} \in E$ 一条边。若 $G^{\prime}=\left(V, E^{\prime}\right)$ 是移除这条边后的图。我们最多可以有2个连通的子图 $T_{i}=\left(V_{i}, E_{i}\right)$。若只有一个图，那么 $T_{1}$ 就是 $G$ 的一个生成树。否则两个子图的生成树加上去除的边 $T=\left(V, E_{1} \uplus E_{2} \uplus \{\{u, w\}\}\right)$ 是 $G$ 的生成树

若 $G=(V, E)$ 是一个简单图，下面的命题是等价的

$G$ 是树

$G$ 连通且 $|V|=|E|+1$

$G$ 无环且 $|V|=|E|+1$

任意两个点都只有一条路径

若1则2

因为树连通且 $|V|=|E|+1$ 满足
若2则3

加上 $G$ 满足 $|V|=|E|+1$ 且有环。我们移除任意一条边会得到一个图 $G^{\prime}=\left(V, E^{\prime}\right)$ 且 $\left|E^{\prime}\right|=|E|-1=|V|-2$ 那么它不可能连通
若3则4

加上 $G$ 满足 $|V|=|E|+1$ 。首先我们证明连通性。也就是每2个点至少有一条简单路径。若$G_{1}, \dots, G_{l}$ 是 $G$ 的最大连通分量，由于$G$ 无环，那么 $G_{i}=\left(V_{i}, E_{i}\right)$ 也是无环的，而 $G_{i}$ 是连通的。所以它们都满足 $\left|V_{i}\right|=\left|E_{i}\right|+1$，所以有 \[ |V|=\sum_{i \in[l]}\left|V_{i}\right|=\sum_{i \in[l]}\left(\left|E_{i}\right|+1\right)=|E|+l \] 所以$l=1$ 所以$G$ 连通。

假设有两个点 $u,v$ 有两条不同的路径$v_{0}, v_{1}, \dots, v_{l}$ 和 $v_{0}^{\prime}, v_{1}^{\prime}, \dots, v_{l}^{\prime}$。假设 $a$ 是两条路径第一个不同的下标，$b$ 是$a$ 后第一个使得两条路径重合的下标。那么 $v_{a}, v_{a+1}, \dots, v_{b}, v_{b^{\prime}-1}^{\prime}, \dots, v_{a}^{\prime}$ 就是一个简单环。矛盾。
若4则1

显然满足4的必然无环且连通

有根树(Wurzelbaum)

$G=(V, E, r)$ 是树 $G=(V, E)$ 以 $r \in V$ 为根的有根树

高度 $h_{G}(v)$ 是一个节点 $v$ 在 $G$ 中的到根的距离
树的高度是 $h(G)=\max \left\{h_{G}(v) | v \in V\right\}$
- 我们写 $u E v$ 表示 $\{u, v\} \in E$ 且 $h_{G}(v)=h_{G}(u)+1$。若 $u E v$ 那么$u$ 是 $v$ 的爸爸，$v$ 是 $u$ 的孩子。$u E^{*} v$表示$u$ 是 $v$ 的前驱，$v$ 是 $u$ 的后驱
- 对于 $u \in V$ ，$\left(u E^{*}, E \cap\left(\begin{array}{c}u E^{*} \\ 2\end{array}\right), u\right)$是通过 $u$ 生成的子树(induzierte Teilbaum)

比如以 $\varepsilon$ 为根的完美二叉树 \[ (\underbrace{[2]^{<h},\left\{\{u, u 1\},\{u, u 2\} | u \in[2]^{<h-1}\right\}}_{=B_{h}}, \varepsilon) \]

欧拉回路和哈密顿环

哈密顿环(Hamiltonkreise) 是每个节点只访问一个的环。欧拉路径是每条边只经过1次的回路。

我们接下来只讨论简单图。

若 $G=(V, E)$ 是一个简单连通图，那么 $v_{0}, v_{1}, \ldots, v_{l}$ 在 $G$ 中的路径，且 $v_{0}=v_{l}$

欧拉回路，若$\left|\left\{\left\{v_{0}, v_{1}\right\},\left\{v_{1}, v_{2}\right\}, \ldots,\left\{v_{l-1}, v_{l}\right\}\right\}\right|=|E|$
哈密顿回路，若$\left|\left\{v_{0}, v_{1}, \dots, v_{l-1}\right\}\right|=|V|$

定理

一个简单连通图 $G=(V, E)$ 有欧拉回路，当且仅当每个节点的度数是偶数

充分性：每个点都要有一个出去的度数和进来的度数，所以每个点的度数是偶数

必要性：我们通过对 $k:=|E| \in N _{0}$ 的数学归纳法证明

Induktionsbasis：对于 $k=3$ ，每个图都是$C_{3}$的同构图，
Induktionsschritt：任选一个固定的$k \geq 3$
- Induktionsbehauptung: 有 $k+1$ 条边，每个点度数偶数的图有欧拉回路
- Induktionsannahme: 有 $|E|\leq k$ 每个点度数偶数的图有欧拉回路
- Beweis der Induktionsbehauptung:
  
  假设 $G=(V, E)$ 是连通图，有 $k+1$ 条边，每个点度数偶数。任取 $\{u, w\} \in E$ 一条边。若 $G^{\prime}=\left(V, E^{\prime}\right)$ 是移除这条边后的图，那么在$G'$ 中一定有一条从 $u$ 到 $w$ 的图。因为$u$ 在 $G$ 中的连通分量有偶数个奇数度数的节点，这不可能因为度数永远是边数的两倍。所以 $w$ 必然也在 $u$ 的连通分量中，所以 $u$ 到 $w$ 至少会有一条路径。所以这条路径就和前面移除的边形成了一个环 $\kappa=v_{0}, v_{1}, \dots, v_{l}, v_{0}$
  
  假设 $G''$ 是把这个环移除后的图，所以它最多有$k$ 条边(实际上$k-2$)。如果$G''$ 没有边，那么我们已经找到了欧拉回路。否则$G''$ 就有偶数度数的边。所以子图也存在欧拉回路，把两者合并就可以得证。

一个简单连通图 $G=(V, E)$ ，$|V|\ge 3$，若每个节点的度数至少是$\frac{|V|}{2}$ ，有哈密顿回路

假设 $G=(V, E)$ 是这样的图。令 $n=|V|$ 。那么$G$ 肯定连通。因为若有两个最大连通分量，那么小的那个最多 $\frac{n}{2}$ 个节点，所以节点度数最多 $\frac{n}{2} -1$。若 $\pi=v_{0}, v_{1}, \dots, v_{m}$ 是$G$ 中最长的简单路径，那么 $v_{0}$ 的每个邻居肯定在这条路径上，否则就不是最大的路径。若 $0<i_{1}<\ldots<i_{k} \leq m$ 是这些邻居的位置，那么 $\operatorname{deg}\left(v_{0}\right)=k \geq \frac{n}{2}$ ，$v_{i_{1}-1}, \dots, v_{i_{k}-1}$ 一定有一个是 $v_{m}$ 的邻居，否则它就只有$n-1-k \leq n-1-\frac{n}{2}<\frac{n}{2}$ 个度数了。所以我们可以找到这样一个$j \in [k]$ ，$\left\{v_{0}, v_{i_{j}}\right\},\left\{v_{i_{j}-1}, v_{m}\right\} \in E$ 。于是我们可以找到一个环 $\kappa=v_{0}, v_{1}, \dots, v_{i_{j}-1}, v_{m}, v_{m-1}, \dots, v_{i_{j}}, v_{0}$ 。假设有另一个不在路径上的节点$w$ ，那么之前就会有最长的路径。所以所有节点都必须在 $\kappa$ 上，它就是一个哈密顿回路。

平面图和节点染色

欧拉公式(Eulersche Polyederformel)

若 $G=(V, E)$ 是个连通的平面图，$f$ 是平面的数量，那么满足： \[ f-|E|+|V|=2 \]

通过对 $n=|E|-|V|+1 \in N _{0}$数学归纳法证明

Induktionsbasis：对于 $n=0$ ，那么 $|E|=|V|-1$ ，那么它是一个树$f=1$。
Induktionsschritt：任选一个固定的$n \geq 0$
- Induktionsbehauptung:欧拉公式对每个 $|E|-|V|+1=n+1$ 的图成立
- Induktionsannahme:欧拉公式对每个$|E|-|V|+1 \leq n$的图成立
- Beweis der Induktionsbehauptung:
  
  假设 $G=(V, E)$ 是连通平面图，且 $|E|-|V|+1=n+1$ 。可以发现 $|E| \geq|V|$。所以它一定有个环$\kappa$ ，我们把这个环中的任意一条边移除，剩下图 $G^{\prime}=G[E \backslash\{\{u, w\}\}]$ ，由于少了一条边，所以肯定会少一个平面。而$G'$ 是连通的平面图，所以有 $(f-1)-(|E|-1)+|V|=2$ 。也就是$f-|E|+|V|=2$

此外，欧拉公式在 $k$ 个连通分类里满足： \[ f-|E|+|V|=1+k \] 由欧拉公式得出的结论：

Minoren und Satz von Kuratowski

若 $G = (V, E)$ 是一个简单图，给定任意一条边 $e =(u,w) \in E$ . 那么 $G \setminus e$ 是移除 $e$ 后的简单图 \[ G / e=\left(V-\{w\},\left(E \cap\left(\begin{array}{c} V-\{w\} \\ 2 \end{array}\right)\right) \cup\{\{u, x\} \mid\{w, x\} \in E\}\right) \] 就是要把这条边的某个节点，以及它所连接的边都删除

Kuratowski 定理

节点染色

定义：染色

四色定理

五色定理

匹配

定义

Heirats问题

https://www.cnblogs.com/cly-none/p/Hall_Theorem.html

有优先级的匹配

Gale-Shapley-Algorithmus

首先，男生需要按照希望与之交往的顺序给所有女生排序，即最理想的女友排在最前、最不理想的放在最后。同样，每个女生也需要给男生排序。接着，男生将按照自己的名单一轮一轮地去追求喜欢的女生，女生也将按照自己的名单接受或拒绝对方的追求。

第一轮，每个男生都向自己名单上排在首位的女生表白。此时，一个女生可能面对的情况有三种：没有人跟她表白、只有一人跟她表白、有不止一人跟她表白。在第一种情况下，这个女生什么都不做，继续等待即可；在第二种情况下，女生接受那个人的表白，答应暂时和他做男女朋友；在第三种情况下，女生从所有追求者中选择自己最喜欢的那一位，答应和他暂时做男女朋友，并拒绝其他所有的追求者。

第一轮结束后，有些男生已经有女朋友了而有些男生仍然是单身狗。在第二轮表白行动中，每个单身男都会从所有还没拒绝过自己的女生中选出自己最喜欢的那一个，并向她表白，不管她现在是否是单身。和第一轮一样，每个被表白的女生需要从表白者中选择最喜欢的男生，并拒绝其他追求者。注意，如果这个女生当前已经有男朋友了，当她遇到了更好的追求者时，她将毫不犹豫地和现男友分手，投向新追求者的怀抱。这样以来，一些单身狗将脱单，而一些倒霉的恩爱狗（男）也会被分手，重新进入单身狗的行列。

在以后的每一轮中，单身狗们将发扬愈挫愈勇的顽强精神，继续追求列表中的下一个女生；女生则从包括现男友在内的所有追求者中选择最好的一个，并给其他所有追求者发好人卡。这样一轮一轮地进行下去，直到某个时刻所有人都不再单身，那么下一轮将不会有任何新的表白，每个人的对象也都将固定下来，整个过程自动结束——此时的搭配就一定是稳定的了。

邻接矩阵

定义

寻找路径

群论

代数结构algebraische Struktur $\mathcal{S}$ 是一个由全集和操作构成的

$U_{\mathcal{S}}$ 是全集 Grundmenge

$\operatorname{ar}(f)$ 是一种操作的元

比如可以这样写 $\left\langle U, f_{1}, \ldots, f_{k}\right\rangle$

Halbgruppe

Halbgruppe 是满足结合律assoziativ和交换律kommutativ的代数结构 $\left\langle A, \bullet^{2}\right\rangle$

(kommutatives) Monoid

(kommutatives) Monoid $\left\langle A, \bullet^{2}, 1^{0}\right\rangle$ 是Halbgruppe且有一个单位元，它满足 $\forall a:(a \cdot 1)=a=(1 \cdot a)$

(kommutative) Gruppe

是一个Monoid $\left\langle A, \bullet^{2}, 1^{0}\right\rangle$，且有逆元，满足 $\forall a \exists b:(a \bullet b)=1=(b \cdot a)$

它也叫 abelsche Gruppe

(unitärer) Ring

$\left\langle A,+^{2}, \bullet^{2}, 0^{0}, 1^{0}\right\rangle$是 Ring，满足

$\left\langle A, \bullet^{2}\right\rangle$ 是 Halbgruppe, $\left\langle A, \bullet^{2}, 1^{0}\right\rangle$ 是 Monoid
$\left\langle A,+^{2}, 0^{0}\right\rangle$ 是 Gruppe
满足分配律 \[ \forall a, b, c:(a \bullet(b+c))=(a \bullet b+a \bullet c) \wedge((a+b) \bullet c)=((a \bullet c)+(b \bullet c)) \]

Körper

$\left\langle A,+^{2}, \bullet^{2}, 0^{0}, 1^{0}\right\rangle$ 的Ring是 Körper 满足

$\left\langle A \backslash\{0\}, \bullet^{2}, 1^{0}\right\rangle$ 是Gruppe

Verband

Verband是$\left\langle A, \sqcup^{2}, \sqcap^{2}\right\rangle$，其中$\left\langle A, \sqcup^{2}\right\rangle$ 和$\left\langle A, \sqcap^{2}\right\rangle$ 都是 Halbgruppe

满足 $\forall a, b, c: a \sqcap(a \sqcup b)=a=a \sqcup(a \sqcap b)$ 和分配律：$a \sqcap(b \sqcup c)=(a \sqcap b) \sqcup(a \sqcap c)$

数论

定义：

$\mathbb{Z}_{N}:=\{0,1,2, \ldots, N-1\}$

取模运算

\[ a \bmod N:=\min \left\{r \in \mathbb{Z}_{N}: \frac{a-r}{N} \in \mathbb{Z}\right\}=a-\left\lfloor\frac{a}{N}\right\rfloor \cdot N \in \mathbb{Z}_{N} \]

互质的集合

\[ \mathbb{Z}_{N}^{*}:=\left\{k \in \mathbb{Z}_{N} \mid \operatorname{gg} T(k, N)=1\right\} \]

欧拉函数

\[ \varphi(N):=\left|\mathbb{Z}_{N}^{*}\right| \]

\[ \varphi(N)=\left|\mathbb{Z}_{N}^{*}\right|=N \prod_{p \in \mathbb{P}: p \mid N}\left(1-p^{-1}\right) \]

倍数集合

$V_{N, d}=\left\{x \in \mathbb{Z}_{N}: d \mid N\right\}$

$\left|V_{N, d}\right|=\lfloor N / d\rfloor$

排列的循环写法

\[ f=\left(x_{0}^{(1)}, x_{1}^{(1)}, \ldots, x_{l_{1}-1}^{(1)}\right)\left(x_{0}^{(2)}, x_{1}^{(2)}, \ldots x_{l_{2}-1}^{(2)}\right) \ldots\left(x_{0}^{(k)}, x_{1}^{(k)}, \ldots x_{l_{k}-1}^{(k)}\right) \]

等价类

\[ { }_{, n} a \equiv_{f} b \mathrm{gdw} . f(a)=f(b)^{\prime \prime} \]

\[ [a]_{n}=\{a+n z \mid z \in \mathbb{Z}\}=: a+n \mathbb{Z} \]

是剩余类

复习考试

数学归纳法

答案格式：

布尔值

基本题

给定一个布尔关系式, 写 Syntaxbaum, Wahrscheinlichkeitstabelle

\[ \begin{array}{ll} F_{1}:=\neg(p \wedge(\neg q \leftrightarrow p)) & F_{2}:=(\neg \neg \neg p \vee \neg \neg(q \vee(r \rightarrow p))) \\ F_{3}:=(((q \vee p) \leftrightarrow(q \wedge r)) \wedge \neg(p \rightarrow r)) & F_{4}:=((q \leftrightarrow p) \wedge((\neg p \rightarrow r) \wedge(\neg q \leftrightarrow r))) \\ F_{5}:=(((p \rightarrow r) \rightarrow(q \rightarrow r)) \rightarrow(p \rightarrow q)) & F_{6}:=((p \oplus q) \rightarrow((p \leftrightarrow s) \vee \neg r)) \end{array} \]

KNF和DNF

disjunktiver Normalform (DNF): \[ \bigvee_{i=1}^{m}\left(\bigwedge_{j=1}^{m_{i}} L_{i, j}\right) \] konjunktiver Normalform KNF: \[ \bigwedge_{i=1}^{m}\left(\bigvee_{j=1}^{m_{i}} L_{i, j}\right) \]

把一个式子转化成DNF

全化成not and or \[ \begin{aligned} (F \rightarrow G) & \equiv(\neg F \vee G) \\ (F \leftrightarrow G) & \equiv((F \rightarrow G) \wedge(G \rightarrow F)) \\ & \equiv \neg(F \oplus G) \\ (F \oplus G) & \equiv((F \vee G) \wedge(\neg F \vee \neg G)) \\ &\equiv((F \wedge \neg G) \vee(\neg F \wedge G))) \end{aligned} \]
把not 全移到syntaxbaum的最底下
然后用公式转化 \[ (F \wedge(G \vee H)) \equiv((F \wedge G) \vee(F \wedge H)) \quad \text { und } \quad((G \vee H) \wedge F) \equiv((G \wedge F) \vee(H \wedge F)) \]

根据真值表转化DNF和KNF

比如这个 \[ \text { ITE }(p, q, r):=((p \rightarrow q) \wedge(\neg p \rightarrow r)) \]

DNF

把真值为1的行全找出来，然后对应p, q, r 来构造1 \[ \begin{aligned} \operatorname{ITE}(p, q, r) \equiv D_{F}=&(\neg p \wedge \neg q \wedge r) \vee(\neg p \wedge q \wedge r) \\ &(p \wedge q \wedge \neg r) \vee(p \wedge q \wedge r) \end{aligned} \]

画图，直接填色即可

KNF

把真值为0的找出来，然后对应p，q，r构造0 \[ \begin{aligned} \operatorname{ITE}(p, q, r) \equiv K_{F}=&(p \vee q \vee r) \wedge(p \vee \neg q \vee r) \\ &(\neg p \vee q \vee r) \wedge(\neg p \vee q \wedge \neg r) \end{aligned} \]

画图，先取反转成DNF，然后根据DNF画图，然后画完再反过来

KNF转DNF

先画出Syntaxbaum, 然后给每一个中间节点一个变量名，然后就可以构造 \[ q_{0} \wedge\left(q_{0} \leftrightarrow\left(q_{1} \vee q_{2}\right)\right) \wedge\left(q_{1} \leftrightarrow\left(p_{1} \wedge p_{2}\right)\right) \wedge\left(q_{2} \leftrightarrow\left(p_{3} \wedge p_{4}\right)\right) \] 然后变形 \[ \begin{aligned} E_{F}:=q_{0} & \wedge\left(\neg q_{0} \vee q_{1} \vee q_{2}\right) \wedge\left(q_{0} \vee \neg q_{1}\right) \wedge\left(q_{0} \vee \neg q_{2}\right) \\ \wedge &\left(q_{1} \vee \neg p_{1} \vee \neg p_{2}\right) \wedge\left(\neg q_{1} \vee p_{1}\right) \wedge\left(\neg q_{1} \vee p_{2}\right) \\ \wedge &\left(q_{2} \vee \neg p_{3} \vee \neg p_{4}\right) \wedge\left(\neg q_{2} \vee p_{3}\right) \wedge\left(\neg q_{2} \vee p_{4}\right) \end{aligned} \]

DNF转KNF

分配率展开

DPLL算法

给定一个KNF, 可以看这个式子是否有肯能成立。就是分类讨论思想。最后得到 $\{\{\}\}$ 是不满足, $\{\}$ 是可满足。

扩展DPLL

OLR: 只有1个变量的式子，直接把那个变量设置为true

PLR：只有 p 出现，没有非p出现（或者反过来），那么直接设为true/false

然后再分类讨论

怎么找最小的DNF和KNF

从KV图中看出来

Erfüllbarkeit

gültig $F = 1$

unerfüllbar $F=0$

erfüllbar 存在一个Belengung 使得 $F=1$

$F \models G$ 意思是 $F\rightarrow G$ 是 gültig 的

基本等价式

\[ F \leftrightarrow G \equiv(F \wedge G) \vee(\neg F \wedge \neg G) \]

合并项Resolution

图论

平面个数

\[ f-|E|+|V|=1+k \]

其中 $k$ 是强连通分量的个数。

Baum

若 $G=(V, E)$ 是一个树，那么 $|E|=|V|-1$

$(1,1,1,2,2,2,3)$ 不是树，因为 $(2,2,2)$ 可以组成一个环，另一个组成树

dreifärbbar

找一个isomorph 的图，然后染色

Hamilton-Kreis

一个简单连通图 $G=(V, E)$ ，$|V|\ge 3$，若每个节点的度数至少是$\frac{|V|}{2}$ ，有哈密顿回路

Euler-Kreis

一个简单连通图 $G=(V, E)$ 有欧拉回路，当且仅当每个节点的度数是偶数

排列组合

$\N^{12}$ 是正整数 $12$ 个, $\N_{0}^{12}$ 是自然数 $12$ 个, $[n]^k$ 是正整数 $k$ 个，$[n]_{0}^{k}$ 是自然数

拿取模型

一共 $n$ 个球，从 $1$ 编号到 $n$.

不放回拿取，考虑顺序 \[ A_{n, k}:=\left\{\left(s_{1}, \ldots, s_{k}\right) \in[n]^{k}||\left\{s_{1}, s_{2}, \ldots, s_{k}\right\} \mid=k\right\} \\ \left|A_{n, k}\right|=n \cdot(n-1) \cdot \ldots \cdot(n-k+1)=\frac{n !}{(n-k) !} \]
不放回拿球，不考虑顺序 \[ B_{n, k}:=\left\{\left(s_{1}, \ldots, s_{k}\right) \in[n]^{k}: s_{1}<s_{2}<\ldots<s_{k}\right\} \\ \left|B_{n, k}\right|=\frac{n !}{(n-k) ! k !} \]
有放回拿取，不考虑顺序

\[ C_{n, k}:=\left\{\left(s_{1}, \ldots, s_{k}\right) \in[n]^{k}: s_{1} \leq s_{2} \leq \ldots \leq s_{k}\right\} \\ \left|D_{k, n}\right|=\left(\begin{array}{c} k+n-1 \\ k \end{array}\right)=\left|C_{n, k}\right| \\ D_{k, n}:=\left\{\left(k_{1}, \ldots, k_{n}\right) \in \mathbb{N}_{0}^{n} \mid k_{1}+k_{2}+\ldots+k_{n}=k\right\} \]

考虑顺序： $[n]^{k}$

二项式定理

\[ (x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{k} y^{n-k} \]

第二类斯特林数

把 $n$ 个物品分给 $k$ 个小孩，使得每个人至少有 $1$ 个物品, 所有可能性是(物品和小孩都是有序的)

\[ F_{n, k}:=\left\{\left(s_{1}, \ldots, s_{k}\right) \in[n]^{k}||\left\{s_{1}, s_{2}, \ldots, s_{k}\right\} \mid=n\right\} \] > $n=6,k=4$ 时候， $(3,1,3,2,2,4)$表示 1号礼物给3号小孩，2号礼物给1号小孩，3号礼物给3号小孩......

如果小孩是无序的，那么是 \[ S_{k,n} \] 第二类斯特林数： \[ \left|F_{n, k}\right|=n ! \cdot S_{k, n} \] 计算： \[ \begin{array}{lll} S_{n, k} & =S_{n-1, k-1}+k \cdot S_{n-1, k} & \text { für } n>k>0 \\ S_{n, 0} & =0 & \text { für } n>0 \\ S_{n, n} & =1 \end{array} \] 第二类斯特林数可以看成是一个surjektiv的函数$[k]$ 映射到 $[n]$上.

第一类斯特林数

$[n]$ 的排列中有 $k$ 个环的数量$s_{n, k}=\left[\begin{array}{l}n \\ k\end{array}\right]$ \[ \left[\begin{array}{c} n+1 \\ k \end{array}\right]=\left[\begin{array}{c} n \\ k-1 \end{array}\right]+n \cdot\left[\begin{array}{l} n \\ k \end{array}\right] \operatorname{mit}\left[\begin{array}{l} n \\ n \end{array}\right]=1,\left[\begin{array}{c} n+1 \\ 0 \end{array}\right]=0 \]

划分为制定个数的组

$n$ 个人，分成 $\lambda_{1}$ 个 $1$ 元组， $\lambda_{2}$ 个2元组 ... $\lambda_{n}$ 个n元组，有多少种情况。其中 $\sum_{i=1}^{n} i \lambda_{i}=n$ \[ \frac{n !}{(1 !)^{\lambda_{1}} \cdots(n !)^{\lambda_{n}} \cdot \lambda_{1} ! \cdots \lambda_{n} !} \] 一共 $n!$ 种情况，每个组可以不同排列于是除以$ (1 !)^{{1}} (n !)^{{n}}$，相同元组之间又可以互相交换，于是除以 $ {1} ! {n} !$.

无序划分

$n$ 元钱放到 $k$ 个兜里, 使得每个兜至少有 $1$ 元钱。 \[ P_{n, k}:=\left\{\left(s_{1}, \ldots, s_{k}\right) \in \mathbb{N}^{k} \mid s_{1}+\ldots+s_{k}=n, s_{1} \leq s_{2} \leq \ldots \leq s_{k}\right\} \] 计算： \[ \begin{array}{lll} \left|P_{n, k}\right|=\left|P_{n-1, k-1}\right|+\left|P_{n-k, k}\right| \quad & \text { für } k>0 \\ \left|P_{n, 0}\right|=0 \quad &\text { für } n>0 \\ \left|P_{n, k}\right|=0 \quad &\text { für } k>n \\ \left|P_{n, n}\right|=1 \end{array} \]

如果兜是有区别的，那么就是 \[ n-1\choose k-1 \]

群论

扩展欧几里得算法(EEK)

先算a，b和k。其中 $a' = b \% a$ , $k = 倍数$ , $t' = s$ , $s' = t-k' \cdot s$

求乘法逆元 $a^{-1} \equiv_{n}(\alpha \bmod n)=716$

Teilerfremende Reste modulo

和 $N$ 互素的集合
\[ \mathbb{Z}_{N}^{*}:=\left\{k \in \mathbb{Z}_{N} \mid \operatorname{ggT}(k, N)=1\right\} \] > $\mathbb{Z}_{15}^{*}=\{1,2,4,7,8,11,13,14\}$

欧拉函数

\[ \varphi(N):=\left|\mathbb{Z}_{N}^{*}\right| \] > $\varphi(15)=\left|\mathbb{Z}_{15}^{*}\right|=|\{1,2,4,7,8,11,13,14\}|=8$ \[ \varphi(n)=n \cdot \prod_{p \in \mathbb{P}_{n}}\left(1-p^{-1}\right) \] > $\varphi(15)=15\left(1-\frac{1}{5}\right)\left(1-\frac{1}{3}\right)=(5-1)(3-1)=8$

Ordnung eines Elements

对于群 $\mathbb{G} \hat{=}\langle\mathbb{G}, \bullet, 1\rangle$ , $a \in \mathbb{G}$ , $k \in \mathbb{N}_{0}$: \[ a^{0}:=1 \quad a^{k+1}:=a \cdot\left(a^{k}\right) \quad a^{-(k+1)}:=\left(a^{-1}\right) \cdot\left(a^{-k}\right) \] 并且 $\langle a\rangle:=\left\{a^{k} \mid k \in \mathbb{Z}\right\}=\left\{\ldots,\left(a^{-1}\right)^{3},\left(a^{-1}\right)^{2}, a^{-1}, 1, a, a^{2}, a^{3}, \ldots\right\}$，

$\left. \text{ord}(a):=\min \left\{k \in \mathbb{N} \mid a^{k}=1\right\} \text { (mit min } \emptyset:=\infty\right)$

Die Ordnung von a muss ein Teiler von $\left|\mathbb{Z}_{n}^{*}\right|=\varphi(n)$ sein.

若 $\langle a\rangle= \mathbb{G}$ 那么 $a$ 是 Erzeuger

求ord，它是 $\left|\mathbb{Z}_{n}^{*}\right|$ 因子的倍数，所以可以一个个尝试。

定理

\[ \operatorname{ord}(a)=\operatorname{ord}\left(a^{-1}\right) \]

\[ a^{k}=a^{k \ \bmod \ \operatorname{ord}(a)} \]

\[ a^{-1}=a^{\text {ord }(a)-1} \] > 求大的次幂 $113^{90} \bmod 47$

费尔马小定理

\[ a^{p-1} \equiv 1(\bmod p), gcd(a,p)=1 \]

欧拉降幂

若 $a$ 和 $n$ 互质 \[ a^b = a^{b \% \varphi(n)} \]

判断Erzeuger

若 $\langle\mathbb{G}, \bullet, 1\rangle$ 循环的zyklisch 且有限 $N:=|\mathbb{G}|$ 那么满足

$a\in \mathbb{G}$ , $\langle a\rangle = \mathbb{G}$ 当且仅当 $\forall p \in\{p \in \mathbb{P}: p \mid N\}: a^{N / p} \neq 1$ ，也就是对于所有除了 $N$ 所有约数算出来都不等于1

Gruppenexponent

\[ \lambda_{\mathbb{G}}:=\operatorname{kgV}(\{\operatorname{ord}(a) \mid a \in \mathbb{G}\}) \]

\[ \lambda_{\mathbb{G}}=\min \left\{\lambda \in \mathbb{N} \mid \forall a \in \mathbb{G}: a^{\lambda}=1\right\} \]