小花生

study & life record.

离散数学（一）

发表于 分类于 ，

离散数学做题与整理（个人向）。

集合与关系

集合相等

证明两个集合相等时，考虑从两边互证包含关系。

基数运算

  • Simple Example：
    集合 $A$ 到集合 $B$ 的关系有几个（设基数分别为$a,\ b$）。
    解：集合 $A$ 到集合 $B$ 的普遍关系有 $ab$ 个元素。
    而集合 $A$ 到集合 $B$ 的每个关系都是这个普遍关系的子集。
    所以关系一共有 $2^{ab}$ 个。

闭包运算

自反(reflexive)闭包 $r(\rho)=\rho \bigcup I_A$
对称(symmetric)闭包 $s(\rho)=\rho \bigcup \widetilde \rho$
传递(transitive)闭包 $t(\rho)=\bigcup\limits_{i=1}^{\infty} \rho^i$

$A$ 上包含 $\rho$ 的最小等价关系是 $rts(\rho)$
（实际上是找到一个最小的自反、对称、传递的闭包，注意要先求 $s$ 再求 $t$）

等价关系，等价类

等价关系 = 自反+对称+可传递 的关系
$[\ a\ ]_\rho$ 表示$a$生成的等价类

偏序关系

偏序关系 = 自反+反对称+可传递 的关系
全序：任意两元素都可比的偏序关系
良序：任意非空子集都存在最小元素的偏序关系

注意辨析：一个良序一定是全序，一个有限的全序一定是良序。

Hasse图（次序图）： 上大下小，有边连接表示 “$\leq$”（注意是广义的 “$\leq$” ）

全序的次序图仅由一条竖直边上结点的序列组成（任意两元素可比）

函数

  • 内射：不同元素像不同
    满射：值域 = 值域包

函数的复合

$f:A\to B,\ g:B\to C$
复合：$(g\cdot f)(a)=g(f(a))$，注意与 关系的复合 形式不同

  • 如果 $f,g$ 都是内射，那么 $gf$ 是内射
    如果 $f,g$ 都是满射，那么 $gf$ 是满射
    如果 $f,g$ 都是双射，那么 $gf$ 是双射
  • 如果 $gf$ 是内射，那么 $f$ 是内射
    如果 $gf$ 是满射，那么 $g$ 是满射
    如果 $gf$ 是双射，那么 $f$ 是内射，$g$​ 是满射

逆函数

存在逆函数，一定要求是双射。

如果函数 $f:A\to B$ 是可逆的，则有
$$
\begin{aligned}
f^{-1}f=I_A\\
ff^{-1}=I_B
\end{aligned}
$$
对复合函数的逆：
$$
(gf)^{-1}=f^{-1}\cdot g^{-1}
$$

集合的基数

$A,B$ 等势/有相同的基数：存在一个双射函数 $f:A\to B$，记作 $A\sim B$​

  • 有理数集 $\mathbb Q$ 是可数集，基数记为$\aleph_0$
  • 实数集 $\mathbb R$ 是不可数集，基数记为$\aleph_1$

证明集合可数

  • 可排成无穷序列的形式

  • 可数个可数集的并集是可数集

图论

图的连通性

设 $G=(V,E)$ 是连通图，
$K(G)$ 点连通度：最小点割集的基数
$\sigma(G)$ 边连通度：最小边割集的基数

始终成立：$K(G)\leq\lambda(G)\leq\sigma(G)$

以下n表示结点数，m表示边数

树

  • $m=n-1$

  • $m = \sum kn_k$ ，$n = \sum n_k$ （其中 $n_k$ 表示出度为$k$的结点个数）

  • Simple Example：
    一颗正则3元树，有16个结点，求他的叶结点数。
    解： $m=3n_3\ \ \ n = n_0 + n_3\ \ \ m=n-1$
    直接解得 $n_0=11$

判断同构

不同构的验证：结点数，边数不同，各结点度数无法对应等；

同构的验证：找出符合同构条件的双射。

欧拉图

  • $\Leftrightarrow$ 每一结点度数为偶数

哈密顿图

  • $\Leftrightarrow$ 闭包为哈密顿图

  • $\Leftarrow$​ 闭包为完全图

    构造闭包：循环找出不相邻的 $u, v$ 两点，满足 $deg(u) + deg(v)\geq n$ ，连接

  • $\Rightarrow$ 删去 $n$ 个点后，分图数 $\leq n$

  • $\Leftarrow$ 结点度数均 $\geq n / 2$

  • $\Leftarrow$ 任意两不相邻结点度数和 $\geq n$

二部图

  • $\Leftrightarrow$ 所有回路偶数长

匹配：

  • $\Leftrightarrow$ 满足相异性条件：$V_1$ 中每 $k$ 个结点至少与$V_2$ 中 $k$ 个结点邻接。
  • $\Leftarrow$ 满足 t-条件：存在 $t > 0$
    1. $V_1$ 中每个结点，都至少有 $t$ 条边与其关联
    2. $V_2$ 中每个结点，都至多有 $t$ 条边与其关联

平面图

  • 欧拉公式：$n-m+k=2$（记得 $k$ 包含无限面）

  • $\Rightarrow$ $m \leq 3n-6$（$m\geq2$ 时）​

    证明过程：记所有面的边数的和为$\Sigma$
    则 $2m = \Sigma\geq 3k$，又由欧拉公式 $n+k-m=2$
    解得 $m\leq 3n-6$​，同时也可以得到 $k\leq 2n-4$

  • $\Leftrightarrow$ $Kuratowski$ 定理：不包含在度为2的节点内与$K_5\ or\ K_{3,3}$同构的子图。

解题常用套路

数学归纳法

跟自然数 n 有关的问题。

构建初始条件和递推关系证明。

反证法

正难则反（?）