# 集合

• 常见集合：

  N：正整数或自然数集合

  $N_m$：$1,2,...,m$

  Z：非负整数集合

  $Z_m$：$0,1,2,...,m-1$

  I：整数集合

  P：素数集合

  C：复数集合

• 寻常集：不包含自身作为元素

  不寻常集：包含自身作为元素

• 基数：集合 A 中不同元素的个数，记作$\#A$

• 幂集：设有集合 A，由 A 的所有子集组成的集合，称为集合 A 的幂集，记作$2^A$，即2^A=\left\

• 设 A 是具有基数$\# A$ 的有限集，则\#(2^A)=2^

• 补集：集合 A 关于全集合 U 的相对补集称为 A 的绝对补集，记作$A'$

• $a\in A$ 表示 a 是集合 A 的一个元素，$B \subset A$​表示 B 是 A 的一个子集，它意味着 B 中的每一个元素也是集合 A 中的元素

  • 若$A\in B,B\subset C$，则$A\in C$ $\color{red}$
  • $\color{red}$
    • 若$A\in B,B\subset C$，则$A\subset C$
    • 若$A\subset B,B\in C$，则$A\in C$
    • 若$A\subset B,B\in C$，则$A\subset C$

• A 与 B 的对称差：集合 A、B，由属于 A 但不属于 B 以及属于 B 但不属于 A 的所有元素构成的集合，记作$A \oplus B$，即$A \oplus B = (A-B)\cup (B-A)$

• 集合的运算定律

  • 同一律： $A\cup \varnothing = A$，$A \cap U=A$
  • 互补律：$A \cup A' = U$，$A \cap A' = \varnothing$
  • 对合律：$(A')' = A$
  • 等幂律：$A \cup A = A,A \cap A = A$
  • 零一律：$A \cup U = U, A \cap \varnothing = \varnothing$
  • 吸收率：$A \cup (A \cap B) = A, A \cap (A \cup B) = A$
  • 德摩根律：$(A \cup B)' = A' \cap B', (A \cap B)' = A' \cup B'$

• 对称差运算

  • $A \oplus B = B \oplus A$
  • $(A \oplus B)\oplus C = A \oplus (B \oplus C)$
  • $A \cap (B \oplus C) = (A \cap B)\oplus (A \cap C)$
  • $A \oplus \varnothing =A, A\oplus U = A'$
  • $A \oplus A=\varnothing, A\oplus A'=U$
  • $A\oplus(A\oplus B)=B$

• 分划：设$\pi= \left\{A_i\right\}_{i \in K}$ 是集合 A 的某些非空子集的集合，如果集合 A 的每个元素在且只在其中之一$A_i$ 中，即如果

  1. 当$i \neq j$ 时，$A_i \cap A_j = \varnothing$

  2. $\bigcup\limits_{i \in K}A_i = A$

     则称集合$\pi$ 时集合 A 的一个分划

# 关系

# 集合的笛卡尔积

• 序偶：有序二元组

• 笛卡尔积：设$A_1,A_2,...,A_n$ 时、是任意集合，所有有序 n 元组$(a_1,a_2,...,a_n)$ 的集合，称为$A_1,A_2,...,A_n$ 的笛卡尔积，记作$A_1 \times A_2 \times...\times A_n$

  即A_1 \times A_2 \times...\times A_n = \left\

• $A \times B \neq B \times A$

  $A \times B = B \times A = \varnothing$

• $A \times (B \cup C) = (A \times B) \cup (A \times C)$

  证明与笛卡尔积有关的定理利用序偶

# 关系

• 笛卡尔积$A_1 \times A_2 \times...\times A_n$ 的任何一个子集称为$A_1,A_2,...,A_n$ 上的 n 元关系

• 设$\rho$ 是 A 到 B 的一个关系，定义域$D_{\rho}$，值域R_

• 逆关系\widetilde{\rho} = \left\

• 若$\rho$ 是由 A 到 B 的一个关系，且$(a,b)\in \rho$，则称 a 对 b 有关系$\rho$，记作$a\rho b$，

  如果$(a,b)\notin \rho$，则记作$a\rho'b$

• 集合 A 上的关系：由集合 A 到 A 自身的关系

• 普遍关系$U_A$：若$\rho = A^2$，则称$\rho$ 为 A 上的普遍关系，即U_A = \left\

  恒等关系$I_A$：I_A=\left\

• 复合关系：\rho_1 \cdot \rho_2 = \left\

• $(\rho_1 \cdot \rho_2)\cdot \rho_3 = \rho_1 \cdot (\rho_2 \cdot \rho_3)$

  证明与关系有关的定理利用序偶

# 关系的表示方法

• 关系矩阵
  • 设$\rho_1$ 是 A 到 B 的关系，$\rho_2$ 是 B 到 C 的关系，它们的关系矩阵分别为$M_{\rho_1}、M_{\rho_2}$，则复合关系$\rho_1 \cdot \rho_2$ 的关系矩阵M_{\rho_1 \rho_2}=M_{\rho_1} \cdot M_
  • $M_{\rho ^n}=M_{\rho}^n$
• 关系图

# 集合 A 上关系的性质和闭包运算

• 设$\rho$ 是集合 A 上的关系

  • 若对于所有的$a\in A$，有$a\rho a$，则称$\rho$ 是自反的，否则是非自反的

    若对于所有的$a\in A$，有$a\rho'a$，则称$\rho$ 是反自反的

  • 对于所有的$a,b \in A$，若每当有$a\rho b$ 就有$b\rho a$，则称$\rho$ 是对称的，否则是非对称的

    对于所有的$a,b \in A$，若每当有$a\rho b$ 和$b\rho a$，就必有$a=b$，则称$\rho$ 是反对称的，也可描述为对于所有的$a,b \in A$，若$a \neq b$，则$a\rho b$ 和$b\rho a$ 不能同时出现

  • 对于所有的$a,b,c \in A$，若每当有$a\rho b和b\rho c$ 就有$a\rho c$，则称$\rho$ 是可传递的，否则，$\rho$ 是不可传递的

• A 上关系的性质在关系矩阵上的体现

  • $\rho$ 是自反的：主对角线上的元素全为 1
  • $\rho$ 是对称的：关于主对角线对称
  • $\rho$ 是反对称的：对于$i\neq j$，若$r_{ij}=1$，则$r_{ji}=0$

• A 上的关系的性质在关系图上的体现

  • $\rho$​是自反的：每个结点引出一个单边环
  • $\rho$ 是反自反的：每个结点无单边环
  • $\rho$ 是对称的：对每一由结点$a_i$ 指向结点$a_j$ 的边，必有一相反的边
  • $\rho$ 是反对称的：任何两个不同的借点之间最多有一条边

• 设$\rho$ 是集合 A 上的关系

  • $\rho$ 的自反闭包$r(\rho)$：$r(\rho)=\rho \cup I_A$
  • $\rho$ 的对称闭包$s(\rho)$：s(\rho)=\rho \cup \widetilde
  • $\rho$ 的传递闭包$t(\rho)$：t(\rho)=\bigcup_\limits{i=1}^\infty \rho^i​（若$\# A=n$，则t(\rho)=\bigcup _\limits{i=1}^n \rho^i）

  ${\color{red}r(\rho)、s(\rho)、t(\rho)分别是集合A上包含\rho最小的自反关系、对称关系、可传递关系}$

  (可以利用关系图得到传递闭包，只要能到达就有一条线连接)

• 设$\rho_1$、$\rho_2$ 是集合 A 上的关系，且$\rho_1 \subset \rho_2$，则$r(\rho_1) \subset r(\rho_2)$，$s(\rho_1) \subset s(\rho_2)$，$t(\rho_1) \subset t(\rho_2)$

# 集合 A 上两类重要的关系

# 等价关系

定义：集合 A 上的关系$\rho$，如果它使自反、对称且可传递的，则称$\rho$ 为 A 上的等价关系

# 等价类：

定义：设$\rho$ 是集合 A 上的等价关系，则 A 中等价于 a 的全体元素的集合，成为 a 所生成的等价类，用$[a]_{\rho}$ 表示，即[a]_{\rho}=\left\

性质：

1. A 中每一个元素生成的等价类非空
2. 彼此等价的元素属于同一个等价类
3. 彼此不等价的元素属于不同的等价类，且这些等价类之间没有公共元素

# 分划：

定义：设$\rho$ 是集合 A 上的等价关系，则等价类的集合$\left\{[a]_{\rho} |a\in A\right\}$ 构成 A 的一个分划

说明：每一个等价类就是一个分化块，因为 A 的每一元素的等价类（在$\rho$ 下）是唯一的，所以分划也是唯一的，这种由等价关系$\rho$ 的等价类所组成的 A 的分划，称为 A 上由$\rho$ 所导出的等价分化，用$\pi_{\rho}^A$​​表示

# 商集：

等价类的集合$\left\{[a]_{\rho}|a\in A\right\}$ 称为 A 关于$\rho$ 的商集，记作$A/\rho$，$A/\rho$ 的基数称为$\rho$ 的秩

$res_m(i)$ 表示用 m 除以 i 所得的余数

# 细分：

如果$I_2$ 的每一个分化块都是$I_1$ 的某一个分化块的子集，则$I_2$ 是$I_1$ 的细分

# 偏序

偏序定义：集合 A 上的关系$\rho$，如果它是自反、反对称、可传递的，则称$\rho$ 是 A 上的一个偏序关系，用$\leq$ 表示；显然一个偏序的逆也是偏序，用$\geq$ 表示。

全序定义：一个集合 A 上的偏序，若对于所有的$a,b\in A$，有$a\leq b$ 或$b \leq a$，则称它为 A 上的一个全序。$\color{red}$

良序定义：一个集合 A 上的偏序，若对于 A 的每一个非空子集$S \subset A$，在 S 中存在一个元素$a_s$（S 中的最小的元素），使得对于所有$s \in S$，有$a_s \leq s$​，则称它为 A 上的一个良序。$\color{red}$

特点：

• 全序或者良序一定是偏序
• 偏序不一定是全序或者良序
• 一个偏序如果是良序则一定是全序

# 函数

# 函数

$A \times B$ 的每一个子集都是由 A 到 B 的关系，其中一部分子集可以用来定义由 A 到 B 的函数，用$B^A$ 表示这些函数的集合，即$B^A=\left\{f|f:A\rightarrow B\right\}$，$\color{red}{当A、B都是有限集}$ $\color{red}{的时候}$，$\#A=m,\#B=n$，从 A 到 B 不同函数共有$n^m$，即\#(B^A)=(\# B)^

# 三种特殊函数

定义：

• 内射：当$a_i \neq a_j$ 时，有$f(a_i) \neq f(a_j)$，也就是当$f(a_i) = f(a_j)$ 时，有$a_i=a_j$（集合 A 中的不同元素在 B 中有不同的像）
• 满射：B 中每一个元素都是 A 中至少一个元素的像
• 双射：集合 A 和集合 B 的元素间一一对应

特点：

​ 如果 A、B 都是有限集

• $\#A \leq \#B$ 时，f 有可能时内射
• $\#A\geq \#B$​时，f 有可能是满射
• $\#A=\#B$​时，f 有可能是双射

# 函数的复合

设有函数$f:A\rightarrow B$ 和$g:B\rightarrow C$，那么：

1. 如果 f 和 g 都是内射，则$gf$ 也是内射
2. 如果 f 和 g 都是满射，则$gf$ 也是满射
3. 如果 f 和 g 都是双射，则$gf$​​也是双射

设有函数$f:A\rightarrow B$ 和$g:B\rightarrow C$，那么：

1. 如果$gf$ 是内射，则 f 是内射
2. 如果$gf$ 是满射，则 g 是满射
3. 如果$gf$ 是双射，则 f 是内射，g 是满射

# 逆函数

1. 设函数$f:A\rightarrow B$ 是一个双射，则逆函数$f^{-1}$ 也是一个双射
2. 设函数$f:A\rightarrow B$ 是一个双射，则$(f^{-1})^{-1}=f$
3. 如果函数$f:A\rightarrow B$ 是可逆的，则有$f^{-1}f=I_A,ff^{-1}=I_B$
4. 设有函数$f:A\rightarrow B$ 和$g:B\rightarrow A$，当且仅当$gf=I_A,fd=I_B$ 时，有g=f^
5. 设有函数$f:A\rightarrow B$ 和$g:B\rightarrow A$，且 f 和 g 都是可逆的，则(gf)^{-1}=f^{-1}g^

# 集合的基数

# 概念

概念：集合的基数即集合中不同元素的个数

等势：设有集合 A、B，如果存在双射函数$f:A\rightarrow B$，则说 A 和 B 有相同的基数，或者说 A 和 B 等势，记作$A\sim B$

注：对于有限集来说，A 和 B 有相同的基数指的是它们元素个数相同

有限集：如果集合 A 与集合$N_m=\left\{1,2,...,m\right\}$ 属于同一基数类，则称集合 A 是有限集。有限集的基数就是该集合中的元素个数。

可数集：如果集合$A\sim N$，则称 A 为可数集。可数集的基数记作$\aleph_0$。 一个集合是可数集的充分必要条件是它全部元素可以排成一个无穷序列的形式。

** 可计数集：** 有限集和可数集称为可计数集。

# 性质

1. 可数集的无限子集仍是可数集

2. 任一无限集 A 必包含一可数子集

3. 设集 A 可数，集 B 有限，且$A\cap B=\varnothing$，则$A\cup B$ 可数

4. 若 A、B 都是可数集，$A\cap B=\varnothing$，则$A\cup B$​可数

5. 有限个可数集的并是可数集

6. 可数个 (互不相交的) 可数集的并依旧是可数集

7. 设有集合 A，B，若 A 的子集$A_1$ 和 B 的子集$B_1$，使得$A\sim B_1,B\sim A_1$，则$A\sim B$

# 图论

# 基本概念

# 概念

• n 阶图：有 n 个结点的图

• (n, m) 图：n 个结点 m 条边

  (n, 0) 图：零图

  (1, 0) 图：平凡图

• 完全图：任意两个不同结点都相邻接的图叫完全图

  补图：由 G 所有节点和为了使 G 变成完全图添加的边构成的图

• d 次正则图：所有节点都具有同一度 d

• 子图：$\widetilde{V}$ $\subset$ $V$, $\widetilde{E}$ $\subset$ $E$

  真子图：$\widetilde{V}$ $\subset$ $V$, $\widetilde{E}$ $\subset$ $E$ , 且 $\widetilde{E}$ $\neq$ $E$

  生成子图：$\widetilde{V}$ $=$ $V$ , $\widetilde{E}$ $\subset$ $E$

• 图的同构：两个图存在边与边之间的双射关系

• 伪图：设 $G = (V, E)$ , V 是一个有限非空集合，E 是 V 中任意元素的非有序对偶的多重集

  • 在 E 中允许出现相同元素的对偶
  • 在 E 中无序对偶 {${Vi, Vj}$} 可能出现 r 次

• 多重图： 没有长度为 1 的环的伪图

  简单图：没有自环且没有重数大于 1 的边

• 邻接（结点与结点，边与边）、关联（结点与边）、孤立点、孤立边

# 性质定理

• 握手定理 ---- 在 (n, m) 图中，$\sum\limits_{i=1}^{n}$deg($vi$)$=2m$​;
• n 阶完全图$Kn$ 中，$m=$$\frac{1}{2}$n(n-1);
• 两个图同构的必要条件：
  1. 它们有相同的结点数和相同的边数
  2. 对应结点的度数相同

# 路

# 概念

• 开路、真路、回路、环
  • 没有重复结点的开路是真路
  • 没有重复结点的回路是环
• 短程、距离

# 性质定理

• 设 G 是具有结点集$V={v_1,v_2,...,v_n}$ 的图，则对于任意两个相连接的结点$v_i,v_j \in V (v_i \neq v_j)$，其短程是一条长度不大于 n-1 的真路

# 图的矩阵表示

设$G = (V, E)$，其中 V = \left\

• 邻接矩阵$A = (a_{ij})$

  a_{ij} =\left\{ \begin{aligned} 1& &{若\left\{ v_i, v_j \right\}} \in E \\ 0& &否则 \end{aligned} \right. $$​ - 一个图的邻接矩阵是对角线元素均为0的0-1矩阵，反之，一个对角线全为0的0-1矩阵一定可以唯一地做一个图 - 如果两个图的邻接矩阵可以通过行列变换得到，那么这两个图同构 - 图G的邻接矩阵A的第i行（或第i列）出现1的个数就是节点$v_i$​的度 - $A^l (l = 1, 2, 3, ...)$的$(i, j)$项元素$a_{ij}^{(l)}$是连接$v_i$到$v_j$长度为l的路的总数

  $$b_{ij} = \left\{ \begin{aligned} 1& &若v_i和e_j是关联的 \\ 0& &否则 \end{aligned} \right.$$

  • I 中每一列都正好包含两个 1，并且任何两个列都是不相同的
  • 第 i 行中的 1 的个数即为节点$v_i$ 的度

• 连接矩阵$C = (c_{ij})$

  c_{ij} = \left\{ \begin{aligned} 1& &若从v_i到v_j存在一条路 \\ 0& &否则 \end{aligned} \right.$$​ - 当C中所有元素都为1时图是连通 的

# 概念

• 连通图：如果存在一条路连接$v_i$ 和$v_j$，则称结点$v_i$ 与$v_j$ 是连接的，若 G 中任意两个节点均是连接的，则称图 G 是连通的

• 割边：如果在图 G 中删去边$\left\{v_i, v_j\right\}$ 后，图 G 的分图数增加，则称边$\left\{v_i,v_j\right\}$ 是 G 的割边

• 割点：如果在图 G 中删去结点$v_i$ 及与其相关联的边之后，图 G 的分图数增加，则称结点$v_i$ 是 G 的割点

• 边割集：设图$G = (V, E)$ 是一连通图，若有 E 的子集 S，使得在图 G 中删去 S 中的所有边后，得到的子图 G-S 变成具有两个分图的不连通图，而删去了 S 的任一真子集后，得到的子图仍然是连通图，则称 S 是 G 的一个边割集

• 点割集：设图$G = (V, E)$ 是一连通图，若有 V 的子集$V_1$ 使得在图 G 中删除了$V_1$ 中的所有结点之后，所得到的子图$G - V_1$ 不连通或为平凡图，则称$V_1$ 是 G 的一个点割集

  （割点是点割集的特例）

• 断集：设$G = (V, E)$ 是一连通图，$V_1 \subset V$, G 中端点分别属于$V_1$ 和$V_1'$ 的所有边的集合，则成为 G 的断集

  边割集是断集的特例

• 关联集：设 v 是图$G = (V,E)$ 的一个结点，与 v 相关联的所有边的集合，称为结点 v 的关联集，记作$S(v)$

• 点连通度：$K(G) = min\left\{\ \#V_i|V_i是G的点割集\right\}$，点连通度是为了使 G 成为一个非连通图需要删除的点的最少数目

• 边连通度：λ$(G) = min\left\{ \# S|S是G的断集\right\}$，边连通度是为了使 G 成为一个非连通图需要删去的边的最少数目

# 性质定理

• 图 G 中，边$\left\{v_i,v_j\right\}$ 为割边的充要条件是边$\left\{v_i,v_j\right\}$ 不在 G 的任何环中出现
• 在图 G 中，结点 v 为割点的充要条件是存在两个结点 u 和 w，使得连接 u 和 w 的所有路中都出现结点 v
• 对于一个给定的图$G = ( V, E)$，如果能把结点集 V 分成两个互补的子集$V$ 和$V'$，使得同一结点集中的任意两个结点之间，至少存在一条不包含另一个结点子集中的任何结点的路，那么 G 中的端点分别在$V_1$ 和$V_1'$​中的边组成 G 的一个边割集
• 对于任意的图$G = (V, E)$，有$K(G) \leq \lambda(G) \leq \delta(G)$（其中$\delta(G)$ 是图 G 的最小度

# 欧拉图

# 概念

• 欧拉回路：在图 G 中找到一个回路，它通过 G 的每条边一次且仅一次
• 欧拉路：具有欧拉回路的图
• 欧拉图：通过图 G 每条边一次且仅一次的开路

# 性质定理

• 一个连通图 G 为欧拉图的充要条件是 G 的每一结点的度均为偶数
• 连通图 G 具有一条连接结点$v_i$ 和$v_j$ 的欧拉路的充要条件是，$v_i$ 和$v_j$​是 G 中仅有的具有奇数度的结点
• 欧拉回路的边不可以重复但是结点可以重复，所以欧拉回路不一定是环路

# 哈密顿图

# 概念

• 哈密顿环：找到一个环它通过图 G 的每个结点一次且仅一次

  哈密顿路：通过图 G 每个结点一次且仅一次的开路

  哈密顿图：具有哈密顿环的图

• 闭图：设 G 是具有 n 个结点的图，若对于$deg(u)+deg(v) \geq n$​的每一对结点 u 和 v，均有 u 和 v 相邻接，则称图 G 是闭图

• 闭包：图 G 的闭包是一个与 G 有相同结点集的闭图，记作$G_c$，使$G \subset G_c$，且异于$G_c$ 的任何图 H，若$G \subset H \subset G_c$，则 G 不是闭图

  图 G 的闭包是包含图 G 的最小闭图

# 性质定理

• 图 G 的闭包是唯一的
• 每个哈密顿图都一定是连通的
• 若图$G = (V,E)$ 是哈密顿图，则对于 V 的任何一个非空子集 S，有$W(G-S)\leq\#S$，这里$W(G-S)$ 表示 G - S 中分图的个数
• 设 G 是具有 n 个结点的图，若有结点 u 和 v 不相邻接，且$deg(u) + deg(v) \geq n$，则当且仅当图$G+\left\{u,v\right\}$ 是哈密顿图时，图 G 时哈密顿图
• 设有图 G 当且仅当$G_c$​是哈密顿图时，图 G 是哈密顿图
• 若图 G 的闭包$G_c = K_n$，且$n \geq 3$，则 G 是哈密顿图
• 设图$G = (V, E)$，$\#G \geq 3$，若 V 中任意两个不相邻的结点 u 和 v，均有$deg(u) + deg(v) \geq n$，则 G 是哈密顿图
• 设图$G = (V, E)$，$\#V \geq 3$，若对于任意的$v \in V$，均有$deg(v) \geq \frac{n}{2}$，则 G 是哈密顿图

# 树

# 概念

• 树：不包含环的连通图

  树林：不包含环的图

  树叶：度为 1 的结点

• 生成树：若连通图 G 的生成子图 T 是一棵树，T 是 G 的生成树

  最小生成树：在所有生成树中有最小权值

• 若 G 是一$(n,m)$ 连通图，G 的生成树$T_G$ 是一$(n,n-1)$ 图

  环秩：在得到$T_G$ 之前需要删除的边的总数为$m-(n-1)$，该数为环秩，环秩是为了 “弄破” G 的所有环而必须由 G 中删去的边的最小数目

  弦：被删去的每一条边

  枝：在生成树$T_G$ 中的边

# 性质定理

• 在$(n,m)$ 树中，$m = n - 1$

• 具有两个或更多个结点的树至少有两片树叶

• 两个节点之间由唯一的真路连接的图就是树

  $m=n-1$ 的连通图是树

  $m=n-1$​且无环的图是树

# 有向树

# 概念

• 有向树：一个不包含环的有向图 G，若它只有一个结点$v_0$ 入度为 0，而所有其它结点入度为 1

• 根：节点$v_0$

  树叶或终点：出度为 0 的结点

  级：从$v_0$ 到结点$v_i$ 的距离

• m 元树：在一有向树中，若每一个结点的出度都小于或等于 m

  完全 m 元树：若每个结点的出度等于 m 或 0

• 外部结点：树叶结点

  内部结点：分支结点

• 外部路径长度：根到所有外部结点的距离和

  内部路径长度：根到所有内部结点的距离和

  树的路径长度：根到所有结点的距离和

• 有序树：规定了每一级上结点的次序，一般规定同一级结点的次序为从左到右

• 前缀码：在一个序列的集合中，如果没有一个序列是另一个序列的前缀，则称该序列的集合为前缀码

• 最优树：一颗带权$W_1,W_2,...,W_t$ 的二元树，如果在所有带权$W_1,W_2,...,W_t$ 的二元树中具有最小的权，则称为最优树

# 性质定理

• 一颗二元树第 i 级的最大结点数是$2^i$，高度为 h 的二元树的最大结点数为$2^{h+1}-1$​
• 设 T 为一颗完全二元树（T 不为孤立结点）有 r 个内部结点，内部路径长度为 I，外部路径长度为 E，则$E=I+2r$
• 设 T 为一颗二元树，有$n_0$ 个叶节点，$n_2$ 个出度为 2 的结点，则$n_2=n_0-1$
• 设 T 是一颗完全二元树，有 n 个结点，$n_0$ 个叶节点，则$n=2n_0-1$
• 设 T 是一颗完全 m 元树，有$n_0$ 个叶节点，t 个分支结点，则$(m-1)t=n_0-1$

# 二部图

# 概念

• 二部图：若一个图 G 的结点集 V 能分成两个子集$V_1$ 和$V_2$ 使得$V_1 \cup V_2=V$,$V_1 \cap V_2 = \varnothing$，使得 G 的每一条边$\left\{V_i,V_j\right\}$ 的端点$v_i \in V1, v_j \in V_2$，则称图 G 是一个二部图

  完全二部图：如果$V_1$ 的每一个结点和$V_2$ 的每一个结点想邻接，则 G 为完全二部图

• 匹配：设 G 是具有互补结点子集$V_1$ 和$V_2$ 的二部图，其中$V_1=\left\{v_1,v_2,...,v_q\right\}$，$V_1$ 对$V_2$ 的匹配是 G 的一个子图，它由 q 条边$\left\{v_1,v_1'\right\},\left\{v_2,v_2'\right\},...,\left\{v_q,v_q'\right\}$ 组成，其中$v_1',v_2',...v_q'$ 是$V_2$ 中 q 个不同的元素

# 性质定理

• 图 G 为二部图的充要条件是至少有两个节点，它的所有回路均为偶数长
• 二部图存在$V_1$ 对$V_2$ 的匹配的必要条件是$\# V_2 \geq \#V_1$
• 二部图存在$V_1$ 对$V_2$ 的匹配的充要条件是$V_1$ 中每 k 个结点至少和$V_2$​中 k 个结点相邻接
• 二部图存在$V_1$ 对$V_2$ 的匹配的充分条件是，存在某一整数$t>0$ 使
  1. 对$V_1$ 中每个结点，至少有 t 条边与其相关联
  2. 对$V_2$ 中每个结点，至多有 t 条边与其相关联

# 平面图

# 概念

• 平面图：能画于平面上而无任何交叉

# 性质定理

• 平面图的欧拉公式：设 G 是一连通的平面图，则有$n-m+k=2$ 这里的 n、m、k 分别是图 G 的结点数、边数、面数（包括无限面）
• 有两条或者更多条边的任何连通的平面图 G 中，有$m \leq 3n-6$

# 有向图

# 概念

• 弱连通：看作无向图时是连通的

  单向连通：任何两个结点$v_i$ 和$v_j$ 中至少有一个由另一个出发是可达的

  强连通：任何两个结点$v_i$ 和$v_j$ 都是相互可达的

  强连通的有向图是单向连通的，单向连通的有向图是弱连通的

• 强分图、单向分图、弱分图分别是 G 的极大连通子图、极大单向连通子图、极大弱连通子图

# 性质定理

• 一个连通的有向图具有欧拉回路的充要条件是，G 的每一个结点的入度和出度相等

  一个连通的有向图具有欧拉路的充要条件是，除了两个结点外，G 的每一个结点的入度和出度相等