考试范围

后五章

记忆常见的生成函数

TODO

如何找非齐次线性递推关系的特解? PPT 14页

一些题目

假设有一个由 $n$ 个不同元素组成的多重集, 每个元素可以重复无限次. 求从中选择 $r$ 个元素, 且每种元素至少选择一次的组合数.

Answer

先每种元素各取一个, 剩下还要取 $r - n$ 个, 这个时候就可重复组合问题, 使用星星隔板法就能得到数目为 $(n - 1 r - 1)$

考虑一个由 $n$ 个不同元素的集合. 求它的所有大小为偶数的子集的总数. 尝试使用二项式定理的性质来解决这个问题.

Answer

就是要求 $(2 n) + (4 n) + (6 n) + \dots$ , 将 $(1 + 1)^{n}$ 和 $(1 - 1)^{n}$ 的展开式加起来除以 $2$ 即可, 答案是 $2^{n - 1}$

求解以下的非齐次线性递推关系:

a_{n} = 2 a_{n - 1} + 3 a_{n - 2} + 5

给定初始条件 $a_{0} = 1$ 和 $a_{1} = 2$ .

Tip

这里的特解可以直接通过解方程 $x = 2 x + 3 x + 5$ 得到.

分析复杂度

T (n) = 4 T (n /2) + n^{2} lo g n

Tip

注意第二个递推式适用的是主定理的第二种情况, 而不是第三种. 尽管 $n^{2} lo g n = Ω (n^{2})$ , 但是我们找不到一个 $ε > 0$ 使得 $n^{2} lo g n = Ω (n^{2 + ε})$ . 所以最后的复杂度是 $n^{2} lo g^{2} n$ .

给出一个由主定理无法解决的递推关系, 并说明原因.

Answer

如 $T (n) = T (n) + 1$

已知 $∣ A ∣ = 5, ∣ B ∣ = 3$ , 求 $A \to B$ 的满射函数有多少个

Answer

由容斥原理有 $N = 3^{5} - (2 3) 2^{5} + (1 3) 1^{5} = 150$

证明只有 $5$ 种正多面体

Answer

设顶点数为 $v$ , 边数为 $e$ , 面数为 $r$ , 每个顶点的度数为 $x$ , 每个面的度数为 $y$ , 则由欧拉定理, $v - e + r = 2$ ; 由握手定理 $vx = ry = 2 e$ , 于是就有 $\frac{2}{x} + \frac{2}{y} = \frac{2}{e} + 1$ .

这里有个约束是 $y < 6$ . 因为当 $y = 6$ 时, 每个面是一个正六边形, 这时候正好铺成一个平面, 不能再形成立体图形了, 并且显然有 $y \geq 3$ , 于是 $y$ 只能取 $3, 4, 5$ .

计数

二项式定理

取特殊值

k = 0 \sum n (k n) = (1 + 1)^{n} = 2^{n}

k = 0 \sum n (- 1)^{k} (k n) = (- 1 + 1)^{n} = 0

k = 0 \sum n 2^{k} (k n) = (2 + 1)^{n} = 3^{n}

Pascal恒等式

(k n + 1) = (k - 1 n) + (k n)

就是杨辉三角的构造规则

Vandermonde恒等式

(r m + n) = k = 0 \sum r (r - k m) (k n)

从 $m$ 个男生和 $n$ 个女生中选取 $r$ 个人, 可以直接从 $m + n$ 个人中选出 $r$ 人, 也可以分类 $k$ 从 $0$ 到 $r$ , 选取 $k$ 个女生和 $r - k$ 个男生, 再把所有的可能的取法加起来.

当 $m = n$ 时的特例为

(n 2 n) = k = 0 \sum n (k n)^{2}

排列组合

多重集的排列

$a_{1}$ 出现了 $n_{1}$ 次, $a_{2}$ 出现了 $n_{2}$ 次, ..., $a_{k}$ 出现了 $n_{k}$ 次, 一共有 $n = n_{1} + n_{2} + \dots + n_{k}$ 个元素, 那么排列数目就是

\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

可重复的排列

一共有 $k$ 个元素, 要做一个 $r$ 排列, 那么总的方案数就是 $k^{r}$ .

可重复的组合

假设我们有 $k$ 种不同的元素, 我们想要从中选择 $r$ 个元素, 其中每种元素可以选择多次.

我们用星号来表示元素, 条形来表示分割, 比如说假设我们有 $3$ 种元素 ( $k = 3$ ) 分别是 $a$ , $b$ , 和 $c$ . 我们要从中选取 $5$ 个元素 ( $r = 5$ ),

如果我们选择 $2$ 个 $a$ , $1$ 个 $b$ , 和 $2$ 个 $c$ , 那么我们可以表示为: **|*|**
如果我们选择 $0$ 个 $a$ , $3$ 个 $b$ 和 $2$ 个 $c$ , 那么我们可以表示为: |***|**

现在, 问题就转化为: 我们需要将 $r$ 个星号和 $k - 1$ 个条形放在一起, 总共有多少种不同的排列方式.

(r r + ( k - 1 )) = (r r + k - 1) = \frac{( r + k - 1 )!}{r ! ( k - 1 )!}

多重集的组合

即可重复的组合+每个元素有重复上限. 没有一般的公式, 使用容斥原理:

假设我们有 $S = {2 \cdot a, 1 \cdot b, 1 \cdot c}$ , 并且我们要选出 $r = 3$ 个元素.

**无限制的情况: ** $N = (3 3 + 3 - 1) = (3 5) = 10$ (即可重复组合的公式)
违反限制情况:
- $∣ A_{a} ∣ = (3 - 2 - 1 3 + 3 - 2 - 1) = (0 3) = 1$ ( $a$ 超过 $2$ 个限制, 也就是 $a$ 选了 $3$ 个, 我们先选 $3$ 个 $a$ , 剩下的 $r = 0$ , $k = 3$ )
- $∣ A_{b} ∣ = (3 - 1 - 1 3 + 3 - 1 - 1 - 1) = (1 3) = 3$ ( $b$ 超过 $1$ 个限制, 那么就先 $2$ 个 $b$ , 剩下的 $r = 1, k = 3$ )
- $∣ A_{c} ∣ = (3 - 1 - 1 3 + 3 - 1 - 1 - 1) = (1 3) = 3$ ( $c$ 超过 $1$ 个限制)
- $∣ A_{a} \cap A_{b} ∣ = (3 - 3 - 1 3 + 3 - 3 - 1 - 1) = (- 1 1) = 0.$ 注意, 如果参数为负, 组合数就是0.因为我们不可能同时多选超过所有元素数量限制的元素
- 同理, $∣ A_{a} \cap A_{c} ∣ = 0$ , $∣ A_{b} \cap A_{c} ∣ = 0$ , 和 $∣ A_{a} \cap A_{b} \cap A_{c} ∣ = 0$ .
容斥原理:
- 最后结果 = $N - ∣ A_{a} ∣ - ∣ A_{b} ∣ - ∣ A_{c} ∣ + ∣ A_{a} \cap A_{b} ∣ + ∣ A_{a} \cap A_{c} ∣ + ∣ A_{b} \cap A_{c} ∣ - ∣ A_{a} \cap A_{b} \cap A_{c} ∣ = 10 - 1 - 3 - 3 + 0 + 0 + 0 - 0 = 3$ 所以答案是 $3$ , 也就是abc, aab, acc这三种

圆排列

认为旋转等价, $n$ 个元素的圆排列的方案数为 $(n - 1)!$ .

项链排列

认为旋转和镜像等价, $n$ 个元素的项链排列的方案数为 $\frac{( n - 1 )!}{2}$

Catalan数

两个定价定义

递归定义

C_{n} = i = 0 \sum n - 1 C_{i} C_{n - 1 - i}, C_{0} = 0

通项公式

C_{n} = \frac{1}{n + 1} (n 2 n)

应用

括号匹配

$C_{n}$ 表示包含 $n$ 对括号的合法匹配的括号表达式的数量, 例如当 $n = 3$ 时, 合法的表达式有

((())), (() ()), (()) (), () (()), () () () .

二叉树计数

$C_{n}$ 表示有 $n$ 个节点的不同二叉树的数列, 事实上, 上面的每一个括号匹配都对应一个二叉树

我们可以将一个二叉树的中序过程与括号匹配对应起来

def tree_to_brackets(root):
    if not root:
        return ""
 
    result = "("
 
    # Process left subtree
    if root.left:
        result += tree_to_brackets(root.left)
    else:
        result += "" 
 
	result += ")"
 
    # Process right subtree
    if root.right:
        result += tree_to_brackets(root.right)
    else:
        result += "" 
 
    return result

例如

((()))

     ()
    /
   ()
  /
 ()

(()())


  ()
 /
()
 \
 ()

(())()

   ()
  /  \
 ()  ()

`()(())

()
 \
 ()
 /
()

()()()

()
 \
 ()
  \
  ()

递推关系

求解递推关系

一般的有重根的情况

Let $c_{1}, c_{2}, \dots, c_{k}$ be real numbers. Suppose that the characteristic equation

r^{k} - c_{1} r^{k - 1} - \dots - c_{k} = 0

has $t$ distinct roots $r_{1}, r_{2}, \dots, r_{t}$ with multiplicities $m_{1}, m_{2}, \dots, m_{t}$ , respectively, so that $m_{i} \geq 1$ for $i = 1, 2, \dots, t$ and $m_{1} + m_{2} + \dots + m_{t} = k$ . Then a sequence ${a_{n}}$ is a solution of the recurrence relation

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}

if and only if

a_{n} = (α_{1, 0} + α_{1, 1} n + \dots + α_{1, m_{1} - 1} n^{m_{1} - 1}) r_{1}^{n} + (α_{2, 0} + α_{2, 1} n + \dots + α_{2, m_{2} - 1} n^{m_{2} - 1}) r_{2}^{n} + \dots + (α_{t, 0} + α_{t, 1} n + \dots + α_{t, m_{t} - 1} n^{m_{t} - 1}) r_{t}^{n}

for $n = 0, 1, 2, \dots$ , where $α_{i, j}$ are constants for $1 \leq i \leq t$ and $0 \leq j \leq m_{i} - 1$ that can be derived from initial conditions.

非齐次的情况

先找到特解 $a_{n}^{(p)}$ , 和齐次解 $a_{n}^{(h)}$ .

If ${a_{n}^{(p)}}$ is a particular solution of the non-homogeneous linear recurrence relation with constant coefficients

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} + F (n)

then every solution is of the form ${a_{n}^{(p)} + a_{n}^{(h)}}$ , where ${a_{n}^{(h)}}$ is a solution of the associated homogeneous recurrence relation

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}

比如说对于以下非齐次递推关系

a_{n} = 3 a_{n - 1} - 2 a_{n - 2} + n

对应的齐次递推关系是

a_{n} = 3 a_{n - 1} - 2 a_{n - 2}

特征方程 $r^{2} - 3 r + 2 = 0 ⟹ r = 1, 2$ . 于是齐次解的形式为

a_{n}^{(h)} = C_{1} (1)^{n} + C_{2} (2)^{n} = C_{1} + C_{2} 2^{n}

我们再用待定系数法, 猜想 $a_{n}^{(p)}$ 的形式为 $A n^{2} + B n$ , 可以解得 $A = - \frac{1}{2}, B = - \frac{5}{2}$ . 那么我们可以得到通解

a_{n} = a_{n}^{(h)} + a_{n}^{(p)} = C_{1} + C_{2} 2^{n} - \frac{1}{2} n^{2} - \frac{5}{2} n

主定理

If each dividing and combining process of size $n$ takes a time of $f (n)$ , the runtime of the algorithm can be expressed by the recurrence relation

T (n) = a T (\frac{n}{b}) + f (n)

The master theorem indicates that, for constants $a \geq 1$ and $b > 1$ with $f$ asymptotically positive, the following statements are true:

Case 1. If $f (n) = O (n^{l o g_{b} a - ε})$ for sone $ε > 0$ , Then $T (n) = Θ (n^{l o g_{b} a})$
Case 2. If $f (n) = Θ (n^{l o g_{b} a})$ , then $T (n) = Θ (n^{l o g_{b} a} lo g n)$
Case 3. If $f (n) = Ω (n^{l o g_{b} a + ε})$ for some $ε > 0$ (and $a f (\frac{n}{b}) \leq c f (n)$ for some $c < 1$ for all $n$ sufficiently large), then $T (n) = Θ (f (n))$

这个是算法中的一般形式, 离散数学中将 $f (n)$ 简化为 $n^{d}$ , 这个时候, 对于递推关系

T (n) = a T (\frac{n}{b}) + n^{d}

如果 $d < lo g_{b} a ⟺ b^{d} < a$ , 那么 $T (n) = O (n^{l o g_{b} a})$ (这个时候第一个递归项是主导的)
如果 $d = lo g_{b} a ⟺ b^{d} = a$ , 那么 $T (n) = O (n^{d} lo g n)$ (这个时候两者达到一种平衡, 所以要把两项都计算进去, 每一层的工作量是 $n^{d}$ , 一共有 $lo g_{b} n$ 层, 也就是 $O (lo g n)$ 层)
如果 $d > lo g_{b} a ⟺ b^{d} > a$ , 那么 $T (n) = O (n^{d})$ (这个时候第二项是主导的)

Furthermore, if we are in Case 1 when $n = b^{k}$ and $a \neq = 1$ , then

f (n) = C_{1} n^{l o g_{b} a} + C_{2}

where $C_{1} = f (1) + \frac{c}{a - 1}$ and $C_{2} = - \frac{c}{a - 1}$

对于第一种的特殊情况, $T (n)$ 的增长速度就是 $O (n^{l o g_{b} a})$ , 这个时候就可以设函数具有如上的关系

生成函数

形式

Furthermore, if we are in Case 1 when $n = b^{k}$ and $a \neq = 1$ , then

f (n) = C_{1} n^{l o g_{b} a} + C_{2}

where $C_{1} = f (1) + \frac{c}{a - 1}$ and $C_{2} = - \frac{c}{a - 1}$

常见的生成函数和数列的对应关系

$G (x)$	$a_{k}$	说明
$(1 + x)^{n}$	$C (n, k)$	二项式定理
$(1 + a x)^{n}$	$C (n, k) a^{k}$	二项式定理
$(1 + x^{r})^{n}$	$C (n, k / r)$ if $r ∣ k$ ; 0 otherwise	二项式定理
$\frac{1 - x ^{n + 1}}{1 - x}$	1 if $k \leq n$ ; 0 otherwise	等比数列求和
$\frac{1}{1 - x}$	1	等比数列求和的极限
$\frac{1}{1 - a x}$	$a^{k}$	等比数列求和的极限
$\frac{1}{1 - x ^{r}}$	1 if $r ∣ k$ ; 0 otherwise	等比数列求和
$\frac{1}{( 1 - x ) ^{2}}$	$k + 1$	等比数列求和的极限公式两边求导
$\frac{1}{( 1 - x ) ^{n}}$	$C (n + k - 1, k) = C (n + k - 1, n - 1)$	求 $n$ 次导
$\frac{1}{( 1 + x ) ^{n}}$	$(- 1)^{k} C (n + k - 1, k) = (- 1)^{k} C (n + k - 1, n - 1)$	求 $n$ 次导
$\frac{1}{( 1 - a x ) ^{n}}$	$C (n + k - 1, k) a^{k} = C (n + k - 1, n - 1) a^{k}$	求 $n$ 次导
$e^{x}$	$\frac{1}{k !}$	Taylor级数
$ln (1 + x)$	$\frac{( - 1 ) ^{k + 1}}{k}$	Taylor级数

应用

生成函数在计数问题中的应用

线性方程解的个数

问题: 求方程 $e_{1} + e_{2} + e_{3} = 17$ 的非负整数解的个数, 其中 $2 \leq e_{1} \leq 5, 3 \leq e_{2} \leq 6$ 且 $4 \leq e_{3} \leq 7$ .

解法: 满足约束条件的解的个数是以下表达式中 $x^{17}$ 的系数:

(x^{2} + x^{3} + x^{4} + x^{5}) (x^{3} + x^{4} + x^{5} + x^{6}) (x^{4} + x^{5} + x^{6} + x^{7})

这是因为我们通过从第一个和中选择 $x^{e_{1}}$ , 从第二个和中选择 $x^{e_{2}}$ , 从第三个和中选择 $x^{e_{3}}$ , 得到乘积中的一项 $x^{17}$ . 这个乘积中 $x^{17}$ 的系数是 3 .

放入自动售货机的代币方式

问题: 确定将价值$1, $2和$5的代币放入自动售货机以支付 $r$ 美元的物品的方式的数量, 考虑两种情况:

代币的插入顺序不重要.
代币的插入顺序重要.

解法:

顺序不重要: 答案是以下生成函数中 $x^{r}$ 的系数:
$(1 + x + x^{2} + \dots) (1 + x^{2} + x^{4} + \dots) (1 + x^{5} + x^{10} + \dots)$
顺序重要: 插入 n 个代币得到总价值 r 美元的方法数是 $(x + x^{2} + x^{5})^{n}$ 中 $x^{r}$ 的系数. 因此, 总的插入方法数是以下生成函数中 $x^{r}$ 的系数:
$n = 0 \sum \infty (x + x^{2} + x^{5})^{n} = \frac{1}{1 - x - x ^{2} - x ^{5}}$

使用生成函数求解递归关系

问题: 求解递归关系 $a_{k} = 3 a_{k - 1}$ , 其中 $k = 1, 2, 3, \dots$ , 初始条件为 $a_{0} = 2$ .

解法: 设 $G (x)$ 为序列 ${a_{k}}$ 的生成函数, 即 $G (x) = \sum_{k = 0}^{\infty} a_{k} x^{k}$ . 首先注意:

x G (x) = k = 0 \sum \infty a_{k} x^{k + 1} = k = 1 \sum \infty a_{k - 1} x^{k}

根据递归关系, 我们有:

G (x) - 3 x G (x) = k = 0 \sum \infty a_{k} x^{k} - 3 k = 1 \sum \infty a_{k - 1} x^{k} = a_{0} + k = 1 \sum \infty (a_{k} - 3 a_{k - 1}) x^{k} = 2

因为 $a_{0} = 2$ 且 $a_{k} = 3 a_{k - 1}$ . 因此,

G (x) - 3 x G (x) = 2 ⟹ G (x) = \frac{2}{1 - 3 x}

利用恒等式 $\frac{1}{1 - a x} = k = 0 \sum \infty a^{k} x^{k}$ , 可以得到 $a_{k} = 2 \cdot 3^{k}$ .

另一个例子: 求解递归关系:

a_{n} x^{n} = 8 a_{n - 1} + 1 0^{n - 1}, a_{0} = 1

仍然有:

G (x) - 8 x G (x) = k = 0 \sum \infty a_{k} x^{k} - 8 k = 1 \sum \infty a_{k - 1} x^{k} = 1 + k = 1 \sum \infty 1 0^{k - 1} x^{k} = \frac{9}{10} + \frac{1}{10} \frac{1}{1 - 10 x}

因此

G (x) = \frac{1}{1 - 8 x} \frac{9 ( 1 - 10 x ) + 1}{10 ( 1 - 10 x )} = \frac{1 - 9 x}{( 1 - 8 x ) ( 1 - 10 x )} = \frac{1}{2} (\frac{1}{1 - 8 x} + \frac{1}{1 - 10 x})

得到

a_{k} = \frac{1}{2} (8^{n} + 1 0^{n})

使用生成函数证明恒等式

问题: 证明

k = 0 \sum n (k n)^{2} = (n 2 n)

解法: 首先注意到, 根据二项式定理, $(n 2 n)$ 是 $(1 + x)^{2 n}$ 中 $x^{n}$ 的系数. 又因为

(1 + x)^{2 n} = [(0 n) + (1 n) x + \dots + (n n) x^{n}]^{2}

这个表达式中 $x^{n}$ 的系数是:

(0 n) (n n) + (1 n) (n - 1 n) + \dots + (n n) (0 n)

这等于 $\sum_{k = 0}^{n} (k n)^{2}$ , 因为 $(k n) = (n - k n)$ .

指数生成函数

对于序列 ${a_{k}}$ , 它的指数生成函数(e.g.f)定义为:

A (x) = n = 0 \sum \infty \frac{a _{n} x ^{n}}{n !}

当元素的顺序很重要时, 例如排列或有标记的结构, 指数生成函数尤其有用. 它们允许进行类似于普通生成函数的加法和乘法运算.

例子: 求集合 ${a, b, c}$ 的长度为 $n$ 的带重复排列的指数生成函数, 其中 $a$ 的数量为奇数, $b$ 的数量为偶数, $c$ 的数量为任意数. 我们考虑以下函数:

i = 0 \sum \infty \frac{x ^{2 i + 1}}{( 2 i + 1 )!} i = 0 \sum \infty \frac{x ^{2 i}}{( 2 i )!} i = 0 \sum \infty \frac{x ^{i}}{i !}

已知如果有 $3$ 个 $a$ , $4$ 个 $b$ 和 $2$ 个 $c$ , 共有 $(3 4 2 9)$ 种排列. 考虑上面乘积中 $x^{9} /9!$ 的系数. 获取 $x^{9}$ 项的一种方式是:

\frac{x ^{3}}{3 !} \frac{x ^{4}}{4 !} \frac{x ^{2}}{2 !} = \frac{9 !}{3 ! 4 ! 2 !} \frac{x ^{9}}{9 !} = (3 4 2 9) \frac{x ^{9}}{9 !}

也就是说, 这一项计算了有 $3$ 个 $a$ , $4$ 个 $b$ 和 $2$ 个 $c$ 的排列的数量. 最终 $x^{9} /9!$ 的系数将是许多此类项的总和, 计算所有可能选择的奇数个 $a$ , 偶数个 $b$ 和任意数量的 $c$ 的排列贡献.

注意:

i = 0 \sum \infty \frac{x ^{i}}{i !} = e^{x}, i = 0 \sum \infty \frac{x ^{2 i}}{( 2 i )!} = \frac{1}{2} i = 0 \sum \infty \frac{x ^{i} + ( - x ) ^{i}}{i !} = \frac{e ^{x} + e ^{- x}}{2}

类似地:

i = 0 \sum \infty \frac{x ^{2 i + 1}}{( 2 i + 1 )!} = \frac{e ^{x} - e ^{- x}}{2}

因此, 我们寻求的生成函数是

\frac{e ^{x} - e ^{- x}}{2} \frac{e ^{x} + e ^{- x}}{2} e^{x} = \frac{1}{4} (e^{3 x} - e^{- x})

关系

基本性质

自反性: $(a, a) \in R$
对称性: $(a, b) \in R ⟹ (b, a) \in R$ .
非对称性: 不存在 $(a, b) \in R \land (b, a) \in R$
反对称性: $(a, b) \in R \land (b, a) \in R ⟹ a = b$
传递性: $(a, b), (b, c) \in R ⟹ (a, c) \in R$

用集合符号表示

Property	Set Restriction
Reflexive	$I_{A} \subset R$
Non-reflexive	$R \cap I_{A} = \emptyset$
Symmetric	$R = R^{- 1}$
Antisymmetric	$R \cap R^{- 1} = I_{A}$
Asymmetric	$R \cap R^{- 1} = \emptyset$
Transitive	$R \circ R \subset R$

$n$ 元关系

定义

设 $A_{1}, A_{2}, \dots, A_{n}$ 是一系列集合. 在这些集合上的一个 $n$ -元关系是 $A_{1} \times A_{2} \times \dots \times A_{n}$ 的一个子集. 集合 $A_{1}, A_{2}, \dots, A_{n}$ 被称为关系的域, 而 $n$ 被称为它的度.

简单来说, $n$ -元关系就是由 $n$ 个集合的元素组成的元组( $n$ -tuple)构成的集合.

操作符

选择 (Selection)

设 $R$ 是一个 $n$ -元关系, $C$ 是 $R$ 中元素可能满足的条件. 那么选择操作符 $s_{C}$ 将 $n$ -元关系 $R$ 映射到由 $R$ 中所有满足条件 $C$ 的 $n$ -元组组成的 $n$ -元关系.

例如, 考虑一个包含学生姓名, 年龄和专业的 3-元关系. 选择操作符可以用来选择年龄大于 20 岁的学生.

投影 (Projection)

投影 $P_{i_{1}, i_{2}, \dots, i_{m}}$ , 其中 $i_{1} < i_{2} < \dots < i_{m}$ , 将 $n$ -元组 $(a_{1}, a_{2}, \dots, a_{n})$ 映射到 $m$ -元组 $(a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{m}})$ , 其中 $m \leq n$ .

例如, 一个包含学生姓名, 年龄和专业的 3-元关系, 投影操作符可以用来只保留学生的姓名和专业, 从而得到一个 2-元关系.

连接 (Join)

设 $R$ 是一个度为 $m$ 的关系, $S$ 是一个度为 $n$ 的关系. 连接 $J_{p} (R, S)$ , 其中 $p \leq m$ 且 $p \leq n$ , 是一个度为 $m + n - p$ 的关系, 它由所有 $(m + n - p)$ -元组 $(a_{1}, a_{2}, \dots, a_{m - p}, c_{1}, c_{2}, \dots, c_{p}, b_{1}, b_{2}, \dots, b_{n - p})$ 组成, 其中 $m$ -元组 $(a_{1}, a_{2}, \dots, a_{m - p}, c_{1}, c_{2}, \dots, c_{p})$ 属于 $R$ , $n$ -元组 $(c_{1}, c_{2}, \dots, c_{p}, b_{1}, b_{2}, \dots, b_{n - p})$ 属于 $S$ .

连接操作符基于两个关系中公共的 $p$ 列进行连接, 类似于数据库中的 Join 操作.

关系的表示

01矩阵
有向图

关系的闭包

一个关系 $R$ 的闭包是指包含 $R$ 的, 并且具有某些特定性质的最小关系. 换句话说, 我们给关系 $R$ 添加最少量的元组, 使其满足特定的性质, 而得到的新的关系就是闭包.

自反闭包

R \cup I_{A}

对称闭包

$R \cup R^{- 1}$ , where $R^{- 1} = {(b, a) ∣ (a, b) \in R}$

传递闭包

联通关系

Let $R$ be a relation on a set $A$ . The connectivity relation $R^{*}$ consists of these pairs $(a, b)$ such that there is a path of length at least one from $a$ to $b$ in $R$ .

Because $R^{n}$ consists of the pairs $(a, b)$ such that there is a path of length $n$ from $a$ to $b$ . It follows that $R^{*}$ is the union of all the sets $R^{n}$ . In other words

R^{*} = n = 1 ⋃ \infty R^{n}

Now we can see that, the transitive closure of a relation $R$ equals the connectivity relation $R^{*}$

Warshall 算法

function Warshall(A): 
	n = number of vertices 
	for k from 1 to n: 
		for i from 1 to n: 
			for j from 1 to n: 
				A[i][j] = A[i][j] or (A[i][k] and A[k][j]) 
	return A

等价关系

A binary relation $\sim$ on a set $X$ is said to be an equivalence relation, if and only if it is reflexive, symmetric and transitive. That is, for all $a, b$ and $c$ in $X$ :

$a \sim a$ (reflexivity)
$a \sim b ⟺ b \sim a$ (symmetry)
$(a \sim b) \land (b \sim c) ⟹ a \sim c$ (transitivity)

等价类

Let $R$ be an equivalence relation on a set $A$ . The set of all elements that are related to an element $a$ of $A$ is called the equivalence class of $a$ . The equivalence class of $a$ with respect to $R$ is denoted by $[a]_{R}$ . When only one relation is under consideration, we can delete the subscript $R$ and write $[a]$ for this equivalence class.

Let $R$ be an equivalence relation on a set $A$ . These statements for elements $a$ and $b$ of $A$ are equivalent

$a R b$
$[a] = [b]$
$[a] \cap [b] \neq = \emptyset$

Let $R$ be an equivalence relation on a set $S$ . Then the equivalence classes of $R$ form a partition of $S$ . Conversely, given a partition ${A_{i} ∣ i \in I}$ of the set $S$ , there is an equivalence relation $R$ that has the sets $A_{i}$ , $i \in I$ , as its equivalence classes.

比如说 $Z_{n}$ 将整数根据除 $n$ 的模进行划分, 可以通过这个建立等价类

偏序关系

定义

一个集合 $S$ 上的二元关系 $⪯$ 是偏序关系当且仅当对于任意 $a, b, c \in S$ :

$a ⪯ a$ （自反性）
$(a ⪯ b \land b ⪯ a) \Rightarrow a = b$ （反对称性）
$(a ⪯ b \land b ⪯ c) \Rightarrow a ⪯ c$ （传递性）

简单来说, 偏序关系就是一种定义在集合上的“小于等于”的关系, 它不要求集合中的任意两个元素都可比较.

如果集合中的任意两个元素都可比较, 则该偏序关系被称为全序关系

如果一个全序集 $S$ 的任意子集都含有一个最小的元素, 那么 $S$ 被称为良序集

比如说, $N$ 是良序集; 而 $Z$ 是全序集, 却不是良序集; 自然数的整除关系 $(N, ∣)$ 就不是一个全序集.

良序归纳法

假设 $S$ 是一个良序集, 我们要证明性质 $P (x)$ 对于所有 $x \in S$ 都成立. 那么, 我们只需要证明以下条件:

归纳步骤: 对于任意 $y \in S$ , 如果对于所有满足 $x ≺ y$ 的 $x \in S$ , 性质 $P (x)$ 都成立, 那么性质 $P (y)$ 也成立. (这里 $x ≺ y$ 表示 $x ⪯ y$ 且 $x \neq = y$ ).

更准确地说, 如果 $\forall y \in S, [\forall x \in S, x ≺ y ⟹ P (x)] ⟹ P (y)$ , 那么 $\forall x \in S, P (x)$ .

和一般归纳法的区别: 良序归纳法不需要显式的基本情况. 因为在良序集中总是存在最小元素, 归纳步骤"自动覆盖"了最小元素的情况. 如果 $x_{0}$ 是 $S$ 的最小元素(即不存在 $x \in S$ 使得 $x ≺ x_{0}$ ), 在归纳步骤中, 当 $y = x_{0}$ 时, 条件 "对于所有满足 $x ≺ y$ 的 $x \in S$ , 性质 $P (x)$ 都成立"自动为真, 因为根本不存在这样的 $x$ .

Hasse 图

图中的每个节点代表偏序集中的一个元素
对于图中的边
- 如果 $a < b$ (即 $a \leq b$ 且 $a \neq = b$ ), 并且不存在另一个元素 $c$ 使得 $a < c < b$ , 那么在图中, 从 $a$ 到 $b$ 画一条向上的边.
- 通常, 我们不会画出自反的环(即 $a \to a$ 的边)
- 我们也不画出所有传递的边, 比如, 如果 $a \to b$ 且 $b \to c$ 我们不会再画一条 $a \to c$ 的边.
- 边的方向总是向上的, 所以图中箭头可以省略.

简而言之, 哈斯图只画出覆盖关系 (covering relation). 如果 $a < b$ 并且不存在 $c$ 使得 $a < c < b$ , 那么称 $a$ 被 $b$ 覆盖, 用 $a \to b$ 表示这种覆盖关系.

The following figure shows the process to construct the Hasse diagram of $({1, 2, 3, 4, 5, 6, 8, 12}, ∣)$

最大最小元素

极大元 (Maximal Element) 和极小元 (Minimal Element)

在一个偏序集 $(S, ⪯)$ 中, 如果元素 $a$ 满足不存在任何元素 $b \in S$ 使得 $a ≺ b$ , 那么 $a$ 就被称为 极大元. 简单来说, 没有其他元素“大于” $a$ 了.
在一个偏序集 $(S, ⪯)$ 中, 如果元素 $a$ 满足不存在任何元素 $b \in S$ 使得 $b ≺ a$ , 那么 $a$ 就被称为 极小元. 简单来说, 没有其他元素“小于” $a$ 了.
在Hasse图中, 极大元是位于“最顶端”的元素, 而极小元则是位于“最底端”的元素.

最大元 (Greatest Element) 和最小元 (Least Element)

在一个偏序集 $(S, ⪯)$ 中, 如果元素 $a$ 满足对于所有 $b \in S$ 都有 $b ⪯ a$ , 那么 $a$ 就被称为 最大元. 换句话说, 所有其他元素都“小于等于” $a$ . 如果存在最大元, 那么它是唯一的.
在一个偏序集 $(S, ⪯)$ 中, 如果元素 $a$ 满足对于所有 $b \in S$ 都有 $a ⪯ b$ , 那么 $a$ 就被称为 最小元. 换句话说, 所有其他元素都“大于等于” $a$ . 如果存在最小元, 那么它是唯一的.

注意: 最大元一定是极大元, 最小元一定是极小元; 反之则不成立. 一个偏序集可能没有最大元或最小元, 但是可以有多个极大元或极小元.

上界 (Upper Bound) 和下界 (Lower Bound)

考虑偏序集 $(S, ⪯)$ 中的一个子集 $A$ . 如果存在元素 $u \in S$ 使得对于 $A$ 中所有元素 $a$ , 都有 $a ⪯ u$ , 那么 $u$ 就被称为 $A$ 的一个上界. 简单来说, 上界“大于等于” $A$ 中的所有元素.
如果存在元素 $l \in S$ 使得对于 $A$ 中所有元素 $a$ , 都有 $l ⪯ a$ , 那么 $l$ 就被称为 $A$ 的一个下界. 简单来说, 下界“小于等于” $A$ 中的所有元素.

最小上界 (Least Upper Bound) 和最大下界 (Greatest Lower Bound)

如果 $x$ 是子集 $A$ 的一个上界, 并且比 $A$ 的所有其他上界都“小”, 那么 $x$ 就被称为 $A$ 的 最小上界 (也称为上确界, supremum).
如果 $y$ 是子集 $A$ 的一个下界, 并且比 $A$ 的所有其他下界都“大”, 那么 $y$ 就被称为 $A$ 的 最大下界 (也称为下确界, infimum).

格

一个格（lattice）是指一个偏序集, 其中每对元素都有一个最小上界和一个最大下界.

举例来说, 正整数集合 $Z^{+}$ 在整除关系 $∣$ 下构成一个格. 对于任意两个正整数 $a$ 和 $b$ :

它们的最小上界是它们的最小公倍数
它们的最大下界是它们的最大公约数

因此, $(Z^{+}, ∣)$ 是一个格. 同理, 实数集 $R$ 在标准的“小于等于”关系 $\leq$ 下构成一个格.

任意两个实数 $a$ 和 $b$ 的最小上界是它们的较大值 $max (a, b)$ .
任意两个实数 $a$ 和 $b$ 的最大下界是它们的较小值 $min (a, b)$ .

拓扑排序

def topological_sort_kahn(graph):
    """
    使用 Kahn 算法对有向无环图进行拓扑排序. 
 
    Args:
         graph: 一个字典, 表示有向图, 键是节点, 值是该节点指向的节点列表. 
          例如: {'a': ['c'], 'b': ['c'], 'c': ['d'], 'e':['f'], 'd':[], 'f':[]}
 
    Returns:
         一个列表, 包含拓扑排序后的节点, 如果图中存在环, 则返回 None. 
    """
    in_degree = defaultdict(int) # 存储每个节点的入度
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
 
    queue = deque([node for node in graph if in_degree[node] == 0]) # 初始时入度为0的节点入队列
    result = []  
 
    while queue:
        node = queue.popleft() 
        result.append(node) 
 
        for neighbor in graph.get(node, []): 
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0: # 如果邻居节点的入度变为 0 入队
                queue.append(neighbor)
 
    if len(result) != len(graph): # 如果结果列表中节点数量小于图中节点数量, 说明有环
        return None
    else:
        return result

图

基本类型

简单图 (Simple Graph):
- 无向图
- 没有环(连接自己的边)
- 没有多重边(两个顶点之间超过一条边)
多重图 (Multigraph): 多重图允许同一对顶点之间存在多条边.
伪图 (Pseudograph):
- 可以有环
- 可以有多重边
完全图 (Complete Graph): 表示为 $K_{n}$ , 具有 $n$ 个顶点, 且每对不同的顶点之间都恰好有一条边相连.
二分图 (Bipartite Graph): 二分图的顶点被划分为两个不相交的集合, $V_{1}$ 和 $V_{2}$ . 每条边都连接 $V_{1}$ 中的一个顶点和 $V_{2}$ 中的一个顶点, 确保没有边连接同一集合内的顶点.
完全二分图 (Complete Bipartite Graph): 完全二分图, 表示为 $K_{m, n}$ , 其顶点集被划分为两个子集, 分别具有 $m$ 和 $n$ 个顶点. 当且仅当一个顶点属于第一个子集, 另一个顶点属于第二个子集时, 两个顶点之间才存在边.

Cycles

A cycle $C_{n}$ , $n \geq 3$ , consists of $n$ vertices $v_{1}, v_{2}, \dots, v_{n}$ and edges ${v_{1}, v_{2}}, {v_{2}, v_{3}}, \dots, {v_{n - 1}, v_{n}}$ and ${v_{n}, v_{1}}$ .

Wheels

We obtain a wheel $W_{n}$ when we add an additional vertex to a cycle $C_{n}$ , for $n \geq 3$ , and connect this new vertex to each of the $n$ vertices in $C_{n}$ , by new edges.

$n$ -Cubes

An $n$ -dimensional hypercube, or $n$ -cube, denoted by $Q_{n}$ , is a graph that has vertices representing the $2^{n}$ bit strings of length $n$ . The vertices are adjacent if and only if the bit strings that they represent differ in exactly on bit position.

邻居和关联

邻居指点和点之间的关系
关联指点和边之间的关系

度

无向图

在无向图中, 顶点 $v$ 的度, 记为 $de g (v)$ , 就是与其相连的边的数量. 但是, 一个顶点上的环对该顶点的度贡献两次.

有向图

在有向图中, 我们需要区分入边和出边:

顶点 $v$ 的入度, 记为 $de g^{-} (v)$ , 是指以 $v$ 为终点的边的数量
顶点 $v$ 的出度, 记为 $de g^{+} (v)$ , 是指以 $v$ 为起点的边的数量

就像在无向图中一样, 有向图中的环对它所在的顶点的入度和出度都贡献 $1$ .

握手定理

设 $G = (V, E)$ 是一个有 $m$ 条边的无向图. 那么

2 m = v \in V \sum de g (v)

换句话说, 无向图中所有顶点的度之和等于边数的两倍. 即使该图有多重边或环, 该定理也成立.

握手定理的一个关键推论是, 一个无向图总是具有偶数个奇数度的顶点.

二分图匹配

在一个简单图 $G$ = ( $V$ , $E$ ) 中, 一个匹配 $M$ 是图的边集合 $E$ 的一个子集, 其中任意两条边都没有公共顶点. 换句话说, 如果我们从一个匹配中选择两条不同的边, 那么它们四个端点必须是不同的顶点.

一个顶点如果是一个匹配 $M$ 中某条边的端点, 则称该顶点是 已匹配的; 否则称为未匹配的.

一个 最大匹配 是指包含尽可能多边的匹配.

在二分图中, 从 $V_{1}$ 到 $V_{2}$ 的一个 完备匹配 是指一个匹配, 其中 $V_{1}$ 中的每个顶点都是已匹配的. 这意味着匹配中的边的数量等于 $V_{1}$ 中顶点的数量.

Hall婚姻定理

提供了一个判断是否存在完备匹配的关键条件:

一个具有二部划分 ( $V_{1}$ , $V_{2}$ ) 的二分图 $G$ = ( $V$ , $E$ ) 存在从 $V_{1}$ 到 $V_{2}$ 的完备匹配, 当且仅当 对于 $V_{1}$ 的所有子集 $A$ , 都有 $∣ N (A) ∣ \geq ∣ A ∣$ .

这里:

$N (A)$ 代表 $A$ 的邻域, 它是 $V_{2}$ 中所有与 $A$ 中至少一个顶点相邻的顶点的集合.
$∣ N (A) ∣$ 和 $∣ A ∣$ 分别表示集合 $N (A)$ 和 $A$ 中的元素（顶点）的数量.

简单来说, 如果 $V_{1}$ 中任何顶点的子集, 其在 $V_{2}$ 中的邻居数量都至少和该子集中的顶点数量一样多, 那么就存在一个完备匹配.

想象在一场舞会, 男生想找自己喜欢的女生跳舞:

如果有一群男生发现, 他们喜欢的女生总共比他们的人数还少, 那么肯定有男生要“被迫”落单, 也就是无法找到完备匹配.
但是, 如果任意一群男生喜欢的女生都至少等于他们的人数, 那么我们就可以合理安排, 让每个男生都找到舞伴, 并且没有重复的舞伴, 也就是能找到完备匹配.

Hall婚姻定理背后的直观思想是: 潜在的“资源”必须充足, 才能保证每个个体都被满足. 只有当每个子集都有足够多的邻居时, 才能确保整个集合存在完备匹配.

子图

在图论中, 图 $G = (V, E)$ 的子图是指一个图 $H = (W, F)$ , 其中 $W$ 是 $V$ 的子集, $F$ 是 $E$ 的子集. 如果 $H$ 不等于 $G$ , 则 $H$ 被认为是 $G$ 的真子图.

有一种特殊的子图叫做诱导子图.

点诱导子图选定原图的顶点子集, 然后保留原图中连接这些顶点的所有边
边诱导子图通过选定原图的边子集, 然后包含这些边以及他们对应的端点

对点和边的操作

删点

从图中移除一个指定的顶点以及所有与该顶点相连的边

删边

从图中移除一条指定的边

收缩边

将一条边的两个端点合并成一个新顶点, 同时保留其他边(适当地连接到新顶点).

给定图 $G = (V, E)$ 和边 $e = (u, v) \in E$ , 收缩边 $e$ 将 $u$ 和 $v$ 合并为一个新顶点 $w$ , 所有原来和 $u$ 或 $v$ 相连的边现在都连接到 $w$ .

细分边

在一条边中插入一个新的顶点, 将原来的边变成两条新的边.

图合并

将两个或多个图组合成一个新的图给定两个图 $G_{1} = (V_{1}, E_{1})$ 和 $G_{2} = (V_{2}, E_{2})$ , 它们的并集(或不相交并集, 取决于是否允许共享顶点和边)生成一个新图 $G = (V, E)$ , 其中 $V = V_{1} \cup V_{2}$ , $E = E_{1} \cup E_{2}$ . 如果两个图有相同的顶点, 则会保留这些相同的顶点.

图的表示

邻接列表

通过列出每个顶点以及其对应的相邻顶点来表示图. 例如:

顶点 (Vertex)	相邻顶点 (Adjacent Vertices)
$a$	$b, c, e$
$b$	$a$
$c$	$a, d, e$
$d$	$c, e$
$e$	$a, c, d$

邻接矩阵

a_{ij} = {1, 0, 如果 {v_{i}, v_{j}} 是图 G 的一条边, otherwise .

关联矩阵

关联矩阵使用矩阵来表示图, 其中行表示顶点, 列表示边. 矩阵中的元素表示顶点是否关联到边.

m_{ij} = {1, 0, 当边 e_{j} 与 v_{i} 关联时, otherwise .

关联矩阵还可以表示多重边和环. 多重边在矩阵中对应列的条目是相同的, 因为它们与相同的顶点对相关联.

在关联矩阵中, 每一个列只能有两个 $1$ , 或者一个 $1$ (环的情况). 如果两个列相同, 那么它们就对应于两个多重边.

图的同构

如果两个简单图之间存在一个一一对应的关系, 使得在一个图中相邻的两个顶点在另一个图中对应的顶点也相邻, 反之亦然, 那么这两个图就是同构的 (isomorphic).

也就是我能构造一个 $V \to V$ 的双射, 使得图的结构保持不变.

要判断两个图是否同构, 可以考虑以下不变的性质:

顶点的数量
边的数量
每个度的顶点的数量
存在特定长度的简单环（回路）如果两个图在以上任何一个性质上不同, 那么这两个图就不是同构的.

或者可以考虑

它们的补图同构吗

连通性

连通性、路径和回路

路径是连接一系列顶点的边的序列, 回路是一条起点和终点相同的路径. 如果路径或回路不包含重复的边, 则称其为简单的.

注意区别回路和环, 在这门课的语境下

回路是一条起点和终点相同的路径
环, 即自环, 是自己连向自己的一条边

如果一个无向图中任意两个不同的顶点之间都存在路径, 则称该无向图是连通的. 相反, 如果至少存在一对顶点之间没有连接路径, 则称该图是不连通的.

在连通的无向图中, 任意两个不同的顶点之间总是存在一条简单路径

连通分量是一个最大的连通子图, 意思是

它是原图的一个子图
它是连通的
它不属于任何一个更大的连通子图

一个不连通的图将有两个或更多的连通分量

割点、割边和连通度

割点, 也称为关节点, 是指删除后会使图不连通的顶点. 割边或桥是指删除后会导致图的连通分量增加的边.

对于非完全图, 顶点连通度, 记为 $κ (G)$ , 是指为使图不连通需要删除的最小顶点数. 如果一个图的顶点连通度大于等于 $k$ , 则称该图是 $k$ -连通的.

也就是说, 如果一个图是 $k + 1$ -连通的, 那么它必然也是 $k$ -连通的.

边连通度, 记为 $λ (G)$ , 定义为具有多个顶点的连通图中, 为使图不连通必须删除的最小边数.

顶点连通度和边连通度之间存在以下不等式关系:

κ (G) \leq λ (G) \leq v \in V min de g (v)

这表示顶点连通度小于等于边连通度, 边连通度小于等于图中任意顶点的最小度数.

有向图中的连通性

有向图引入了强连通和弱连通的概念. 如果对于图中的每一对顶点, 都存在从顶点 $a$ 到顶点 $b$ 的路径, 且存在从顶点 $b$ 到顶点 $a$ 的路径, 则称有向图是强连通的. 如果忽略边的方向后, 任意两个顶点之间都存在路径, 则称有向图是弱连通的.

强连通分量 是有向图中最大的强连通子图. 有向图中的任意两个顶点要么在同一个强连通分量中, 要么在不相交的强连通分量中.

欧拉路径, 欧拉回路和哈密顿回路

欧拉回路 (Euler Circuit)

在一个图 $G$ 中, 欧拉回路是一条简单回路, 它包含图 G 的每一条边.

可以想象成一笔画问题, 你要用笔不重复地画完所有线条, 并且最后回到起点.

对于连通无向图而言, 存在欧拉回路的充要条件是, 每个点的度都是偶数.

对于一个强连通的有向图而言, 存在欧拉回路的充要条件是, 每个点的出度等于入度.

如何寻找欧拉回路?

不断地找环
然后在环与环之间的交点上把它们连接起来

欧拉路径 (Euler Path)

在一个图 $G$ 中, 欧拉路径是一条简单路径, 它包含图 G 的每一条边.

还是想象成一笔画问题, 你要用笔不重复地画完所有线条, 但最后不一定要回到起点.

对于连通无向图而言, 存在欧拉回路的充要条件是, 每个点的度都是偶数, 或者有且仅有两个点有奇数的度数.

对于弱连通有向图(忽略边的方向并将其视为所有顶点之间都存在路径), 存在欧拉路径的充要条件是满足以下两种情况之一:

每个顶点的入度等于出度, 这意味着它也具有欧拉回路.
恰好存在一个顶点出度 = 入度 + 1(起始顶点), 且恰好存在一个顶点的入度 = 出度 + 1(结束顶点), 且所有其他顶点的入度等于出度.

如何寻找欧拉路径?

如果有奇度点, 就从奇度点开始找.

哈密顿回路 (Hamilton Circuit)

在一个图 $G$ 中, 哈密顿回路是一条简单回路, 它经过图 G 的每一个顶点恰好一次.

哈密顿回路的必要条件

狄拉克定理 (Dirac's Theorem): 如果一个图有 $n$ 个顶点, 且 $n \geq 3$ , 并且每个顶点的度 (连接到该顶点的边的数量) 都至少是 $n /2$ , 那么这个图就存在哈密顿回路. 换句话说, 如果图中每个顶点都与至少一半的其他顶点相邻, 那么这个图中就一定能找到一条访问所有顶点一次的回路.
奥尔定理 (Ore's Theorem): 如果一个图有 $n$ 个顶点, 且 $n \geq 3$ , 并且对于每一对不相邻的顶点 $u$ 和 $v$ , 它们的度之和大于等于 $n$ , 那么这个图就存在哈密顿回路. 这个定理表明, 如果图中任何两个不相邻的顶点他们的度之和足够大的话, 也能够保证图中存在哈密顿回路.

总结与比较:

欧拉回路/路径 关注的是边, 要求遍历所有边且只遍历一次.
哈密顿回路 关注的是顶点, 要求遍历所有顶点且只遍历一次.
欧拉回路/路径和哈密顿回路/路径并不互相保证: 一个图有欧拉回路不代表有哈密顿回路, 反之亦然.
图中可能存在多个欧拉回路/路径或哈密顿回路.

中国邮递员问题(Chinese Postman Problem, CPP)

找到一条图中回路, 这条回路能够遍历图中的每一条边至少一次, 并且路径的总长度最短,

如果图中存在欧拉回路, 那么这就是最优路线, 并且路径的总长度就是图中所有边的权重之和
如果图中不存在欧拉回路,

平面图

一个平面图是一个可以在平面上绘制的图, 并且没有任何边会交叉. 更正式地说, 如果一个图可以嵌入在平面中(等价于可以嵌入一个球面), 那么这个图就是平面的, 这意味着每个顶点都映射到平面上不同的点, 并且每条边都映射到一条连续的曲线. 代表边的曲线除了可能在它们的端点(顶点)相交外, 不能相交.

欧拉公式指出, 对于任何连通的平面图, 顶点数 ( $v$ ) 减去边数 ( $e$ ) 加上区域数 ( $r$ ) 等于 $2$ :

v - e + r = 2

注意欧拉公式是不能用来判断平面图, 因为除非我们已经把图画在一个平面上, 否则就没有区域的概念了.

可以通过这样一种方式来记忆欧拉公式

如果给平面图添加一个顶点并连一条边到原来的图上, 则 $v, e, r$ 分别的变化量为 $+ 1, + 1, 0$ . 要使总的变化量不变, 故 $v$ 和 $e$ 的符号必然相反
如果给平面图未连接的两个顶点加上一条新边, 则 $v, e, r$ 分别的变化量为 $0, + 1, + 1$ , 要使总得变化量不变, 故 $e$ 和 $r$ 的符号也必然相反.

欧拉公式可以用来推导出平面图必须满足的不等式(必要条件). 例如:

在一个至少有 $3$ 个顶点的简单平面图中, $e \leq 3 v - 6$ .
在一个至少有 $3$ 个顶点, 且没有长度为 $3$ 的回路的简单平面图中, $e \leq 2 v - 4$ .
每个连通的简单平面图至少有一个顶点的度数小于或等于 $5$ .

Kuratowski定理提供了一种确定图是否是平面图的方法(充要条件). 这个定理指出, 一个图是平面图当且仅当它不包含一个子图, 该子图是 $K_{5}$ (5 个顶点的完全图) 或 $K_{3, 3}$ (两个各有 3 个顶点的完全二分图) 的细分.

一个图的细分是通过用包含一个或多个顶点的路径替换原始图中的边而得到的图.

图的着色

顶点着色数

图着色是指给图的每个顶点分配一种颜色, 使得任何两个相邻的顶点都被分配不同的颜色. 一个图的色数是给这个图着色所需的最少颜色数. 图 $G$ 的色数记为 $χ (G)$ .

四色定理指出, 平面图的色数不大于 $4$ .

当且仅当可以将两种不同的颜色分配给图的每个顶点, 使得任何两个相邻的顶点被分配不同的颜色时, 一个简单图才是二分图. 这意味着二分图的色数为 $2$ .

更精确的色数界限:

ω (G) \leq χ (G) \leq Δ (G) + 1

$ω (G)$ 表示图 G 中最大团(clique)的大小, 也就是图中最大的完全子图的顶点数. $ω (G)$ 是色数的下限, 因为最大团里的所有顶点都需要不同的颜色.
$Δ (G)$ 表示图 G 中顶点的最大度(maximum degree), 即与一个顶点相连的最大的边的数量. $Δ (G) + 1$ 是色数的上限. 表明一个贪心算法最多需要 $Δ (G) + 1$ 种颜色完成着色.

边着色数

与顶点着色不同, 边着色是指给图的每条边分配一种颜色, 使得任何两条共享同一个顶点的边都被分配不同的颜色. 一个图的边着色数通常用 $χ^{'} (G)$ 表示, 是给这个图进行边着色所需的最少颜色数.

Vizing 定理

$χ^{'} (G) = Δ (G)$ 或者 $χ^{'} (G) = Δ (G) + 1$

对于任何图, Vizing 定理表明其边色数 $χ^{'} (G)$ 只能是 $Δ (G)$ 或者 $Δ (G) + 1$ . 也就是说一个图的边色数要么等于它的最大度, 要么等于它的最大度加一.

树

树的内点就是有孩子的顶点如果 $m$ 叉树的每一个内点都恰好有 $m$ 个孩子, 则我们称它们满 $m$ 叉树

树的高度定义如下

空树的高度为 $- 1$
只有一个根节点的树的高度为 $0$

满 $m$ 叉树

一棵完全 $m$ 叉树是其中每个树叶都在同一层上的满 $m$ 叉树带有 $i$ 个内点的满 $m$ 叉树含有 $n = mi + 1$ 个顶点

因为除了根之外的每个顶点都是内点的孩子带有 $i$ 个内点的满 $m$ 叉树含有 $l = (m - 1) i + 1$ 个树叶
总边数等于内节点数乘以 $m$ , 即 $e = im$
总顶点数等于总边数加 $1$ , 即 $n = mi + 1$
总顶点数等于内点数加上树叶数 $n = i + l$
所以 $l = (m - 1) i + 1$

平衡 $m$ 叉树

若一颗高度为 $h$ 的 $m$ 叉树的所有树叶都在 $h$ 或者 $h - 1$ 层, 则这棵树是平衡的

哈夫曼编码

核心思想: 频率高的符号使用较短的编码, 频率低的符号使用较长的编码 是一种前缀码: 没有任何一个编码是其他任何编码的前缀, 因此解码时不会有歧义

构造哈夫曼树

构建最小堆: 将所有节点插入到一个最小堆（优先队列）中, 最小堆的比较标准是节点的频数. 频数低的节点排在前面.
合并节点:
- 从最小堆中取出两个频数最小的节点.
- 创建一个新的父节点, 其频数为这两个节点频数之和.
- 将两个取出节点设为新父节点的左孩子和右孩子（左右孩子的顺序并不影响最终结果）.
- 将新父节点插入回最小堆中.
重复合并: 重复步骤 3, 直到最小堆中只剩下一个节点, 这个节点就是哈夫曼树的根节点.
生成编码: 从根节点开始, 遍历哈夫曼树:
- 左分支用 '0' 表示.
- 右分支用 '1' 表示.
- 从根节点到每个叶节点的路径上的 '0' 和 '1' 组成的字符串, 就是对应字符的哈夫曼编码

有序根树

地址 (即路径表示)

根节点为 $0$ , 表示为如 $1, 2, 2$ 等, 代表每一层选择了第几个孩子

最小生成树

Prim

Prim算法的主要思想是通过迭代地添加连接最小生成树中一个顶点和不在最小生成树中的顶点的最小权重边, 来构造一个加权无向图的最小生成树. 简单来说, 它从任意一个顶点开始, 通过始终连接到最近的可用的顶点来贪婪地扩展树.

Kruskal

Kruskal算法的主要思想是按照边的权重从小到大的顺序依次考虑图中的所有边. 如果当前考虑的边连接的两个顶点属于不同的连通分量, 就将这条边添加到最小生成树中, 并将这两个连通分量合并为一个. 重复这个过程, 直到所有顶点都属于同一个连通分量, 此时所选的边就构成了最小生成树. 简单来说, Kruskal 从权重最小的边开始, 逐步构建最小生成树, 并且避免形成环路.

Lin's Notes Garden

Explorer

Discrete Mathematics Final

考试范围

TODO

一些题目

计数

二项式定理

取特殊值

Pascal恒等式

Vandermonde恒等式

排列组合

多重集的排列

可重复的排列

可重复的组合

多重集的组合

圆排列

项链排列

Catalan数

两个定价定义

递归定义

通项公式

应用

括号匹配

二叉树计数

递推关系

求解递推关系

一般的有重根的情况

非齐次的情况

主定理

生成函数

形式

常见的生成函数和数列的对应关系

应用

生成函数在计数问题中的应用

线性方程解的个数

放入自动售货机的代币方式

使用生成函数求解递归关系

使用生成函数证明恒等式

指数生成函数

关系

基本性质

n元关系

定义

操作符

选择 (Selection)

投影 (Projection)

连接 (Join)

关系的表示

关系的闭包

自反闭包

对称闭包

传递闭包

联通关系

Warshall 算法

等价关系

等价类

偏序关系

定义

良序归纳法

Hasse 图

最大最小元素

格

拓扑排序

图

基本类型

Cycles

Wheels

n-Cubes

邻居和关联

度

无向图

有向图

握手定理

二分图匹配

Hall婚姻定理

子图

对点和边的操作

删点

删边

$n$ 元关系

$n$ -Cubes

满 $m$ 叉树

平衡 $m$ 叉树