图论笔记：预备知识⁽¹⁾

本笔记旨在复习图论课程知识点，内容采用GPT归纳总结。

集合

在图论中，图通常被形式化地定义为一个二元组$G=(V,E)$，其中$V$表示顶点集，$E$表示边集。由此可见，集合及其相关概念构成了图论的基本语言基础。因此，在引入图的定义之前，有必要对集合的概念进行严格而统一的说明。

1. 定义

在数学中，集合 | Set 是指由一些确定的、彼此可区分的对象所构成的整体，这些对象称为集合的元素。若 $x$ 是集合 $A$ 的元素，则记为：

若 $x$ 不是集合 $A$ 的元素，则记为

在理论层面上，集合概念的建立依赖于集合论。早期数学中采用的是朴素集合论，其基本思想是：任何能够被清楚描述的对象的全体都可以构成一个集合。这种直观定义方式在大多数数学应用中是可行的，但从逻辑角度看并不完备。

为避免由朴素定义引发的悖论，现代数学中通常采用公理化集合论作为基础，例如 Zermelo–Fraenkel 集合论（$\text{ZF}$）及其包含选择公理的扩展（$\text{ZFC}$）。在公理化集合论中，集合并非任意构造，而是通过一组公理所允许的操作逐步得到。图论作为应用数学分支，一般不直接涉及集合论公理体系，但其所有集合对象均默认建立在公理化集合论的框架之下。

在本笔记中，集合的使用遵循标准数学语义，不涉及集合论的基础性构造问题。

🌟 数学表示

在数学表达中，通常约定：

• 集合用大写拉丁字母表示，如：$A,B,V,E$
• 元素用小写拉丁字母表示，如：$a,b,v,e$

集合可以通过不同方式进行定义。若集合包含有限个元素，可以采用列举法：

若集合的元素满足某一确定性质，则可采用描述法：

其中 $U$ 表示讨论所限定的全集，$P(x)$ 为关于 $x$ 的判定条件。

在图论中，常见的表示方式包括

分别表示顶点 $v$ 属于顶点集 $V$，边 $e$ 属于边集 $E$。

🥸 基本性质

集合具有若干基本性质，这些性质在数学定义中是内在的，并在后续推理中默认成立。

• 确定性：对于任意对象 $x$ 与集合 $A$，命题 $x\in A$ 具有确定的真假值。

• 互异性：集合中的元素两两不同，元素是否属于集合只取决于“是否出现”，而不考虑出现次数。

• 无序性：集合中元素的排列顺序不影响集合本身，即：

  $$\{a,b,c\} = \{c,b,a\}$$

在图论中，这意味着顶点集与边集仅刻画“有哪些顶点和边”，而不引入额外的顺序结构。

🧮 常用符号

在后续内容中，将频繁使用集合相关符号，例如：

分别表示子集、真子集、交集、并集。本文不再对这些符号作逐一解释。

📝 一些特殊的集合

在图论及离散数学中，以下几类特殊的集合：

• 空集：不含任何元素的集合，记为：$\varnothing$ 。空集满足：对任意对象 $x$，均有 $x\notin \varnothing$；

• 单点集：仅包含一个元素的集合，形式为：$\{a\}$；

• 全集：在某一具体讨论语境下，包含所有研究对象的集合，通常记为 $U$。全集的具体内容依赖于问题背景。

• 幂集：设 $A$ 为任意集合，其幂集记为：

  $$\mathcal{P}(A) = 2^A = \{B|B\subseteq A\}$$

  即由集合 $A$ 的所有子集所构成的集合。若 $A$ 为有限集且 $|A| = n$，则有 $|\mathcal{P}(A)| = 2^n$；

2. 运算

在图论中，集合运算用于描述顶点集与边集之间的组合、重叠与差异，是刻画图结构的重要工具。下面在同一全集 $U$ 下，对常见的集合运算作统一而严格的说明。

👫 二元运算

设 $A,B\subseteq U$ ：

• 并集：$A\cup B = \{x|x\in A \lor x\in B\}$；
• 交集：$A\cap B = \{x|x\in A \land x\in B\}$；
• 差集：$A - B = \{x|x\in A \land x\notin B\}$；
• 对称差：$A\oplus B = (A-B)\cup(B-A)$ 等价地，也可表示为 $A\oplus B = (A\cup B) - (A\cap B)$；

🕺 一元运算

一元集合运算仅涉及单个集合，但其定义依赖于所选定的全集 $U$。

• 补集：$\overline{A} = U - A$

设 $S= \{A_i | i \in I\}$ 为一组集合，则其广义并/广义交定义如下：

• 广义并：$S$ 元素的元素构成的集合，记为 $\cup S$

  $$\bigcup_{i\in I} A_i = \cup S = \{x | \exist i \in I. x \in A_i\}$$

• 广义交：$S$ 元素的公共元素构成的集合，记为 $\cap S$

  $$\bigcap_{i\in I} A_i = \cap S = \{x | \forall i \in I. x \in A_i\}$$

3. 运算律

在集合运算中，各类运算并非彼此孤立，而是满足一系列稳定的运算规律。

常见运算律有：交换律、结合律、分配律、同一律、零元律、幂等律、吸收律、互补律；

这里着重讲解下德摩根律。在涉及补集、并集与交集的运算中，德摩根律起着核心作用。设 $A,B\subseteq U$，则有：

二元关系

在图论与离散数学中，二元关系是描述元素之间联系的核心工具。图、邻接关系、可达关系等概念，本质上都可以视为定义在某个集合上的二元关系。

1. 定义

🤝 序偶与笛卡尔积

设 $a,b$ 为两个元素，序偶记为：

其特点在于顺序不可交换，即一般有 $\left \langle a,b \right \rangle \neq \left \langle b,a \right \rangle$；

这一点与集合 $\{a,b\}$ 有本质区别，是后续区分“方向性关系”的基础。在序偶的基础上，可以定义 笛卡尔积 | Cartesian product 。设 $A,B$ 为两个集合，则 $A$ 与 $B$ 的笛卡尔积定义为：

也就是说，$A\times B$ 是由所有「第一个分量来自 $A$，第二个分量来自 $B$ 」的序偶所构成的集合。

笛卡尔积具有以下几个重要性质（设 $A,B$ 为有限集合）：

• 空集性质：$A=\varnothing \lor B=\varnothing \Rightarrow A\times B = \varnothing$；
• 非交换性：$A\neq \varnothing \land B\neq \varnothing \land A\neq B \Rightarrow A\times B \neq B\times A$；
• 非结合性：$A\neq \varnothing \land B\neq \varnothing \land C\neq \varnothing \Rightarrow (A\times B) \times C \neq A\times (B \times C)$；
• 分配率：笛卡尔积对左右可分配（利用集合运算可证明）；

🤠 二元关系

在笛卡尔积的基础上，可以严格定义二元关系。

设 $A,B$ 为集合，若

则称 $R$ 是一个从 $A$ 到 $B$ 的二元关系。当 $A=B$ 时，称 $R$ 是定义在集合 $A$ 上的二元关系。

对于 $\left \langle a,b \right \rangle \in R$ ，我们通常简记为 $aRb$ ，表示元素 $a$ 与元素 $b$ 满足关系 $R$。从集合论角度看，二元关系本质上是：笛卡尔积 $A\times B$ 的一个子集。

设 $A$ 为集合，以下是定义在 $A$ 上的几类常见特殊二元关系：

👀 二元关系表示

当集合是有限集时，二元关系可以通过多种等价方式表示，其中最常用的是矩阵表示和关系图表示。设 $R$ 是定义在 $A\times B$上的二元关系，其中

则二元关系有如下表示：

• 矩阵表示：关系 $R$ 可以用一个 $m\times n$ 的矩阵表示，其元素定义为：

  $$m_{ij} =\begin{cases} 1, & \langle a_i,b_j\rangle \in R \\ 0, & \langle a_i,b_j\rangle \notin R \end{cases}$$

  该表示方式用数值形式刻画序偶是否属于二元关系，在处理有限集合上的关系时具有良好的计算能力。

• 关系图表示：构造一个有向图来表示该关系，集合 $A$ 中的元素作为起点顶点，集合 $B$ 中的元素作为终点顶点。若 $\left \langle a,b \right \rangle \in R$，则从顶点 $a$ 向顶点 $b$ 引一条有向边。

  当 $A=B$ 时，该关系图即为一个定义在顶点集 $A$ 上的有向图，这是图论中有向图的关系论基础。

2. 运算

设 $A,B$ 为集合，$R\subseteq A \times B$ 是从 $A$ 到 $B$ 的一个二元关系。

🦊 基本运算

二元关系的基本运算如下：

• 关系的补：用于描述“在给定全集中未出现的序偶”，记为 $\overline{R}$，定义为：

  $$\overline{R} = (A\times B) - R$$

• 定义域、值域与域：为了刻画关系中真正“参与”关系的元素，通常引入以下几个集合。

  名称	说明	公式
  定义域	作为序偶第一分量出现过的所有元素	$\operatorname{dom}(R) = \{ a \in A |\exist b \in B, \langle a,b \rangle \in R \}$
  值域	作为序偶第二分量出现过的所有元素	$\operatorname{ran}(R) = \{ b \in B |\exist a \in A, \langle a,b \rangle \in R \}$
  域	在关系中实际出现过的所有元素	$\operatorname{fid}(R) = \operatorname{dom}(R) \cup \operatorname{ran}(R)$

• 逆运算：关系 $R$ 的逆关系定义为：

  $$R^{-1} = \{ \left \langle b, a \right \rangle | \left\langle a,b \right \rangle \in R\}$$

  逆关系本质上是将序偶中两个分量的位置交换，其中 $R^{-1} \subseteq B\times A$。

• 限制：设 $X\subseteq A$ ，$X$ 在关系 $R$ 下的限制定义为：

  $$R\uparrow X = \{ \langle a,b\rangle \in R | a \in X \}$$

  其作用为，只保留 第一分量属于指定子集 $X$ 的关系对。

• 像：设 $X\subseteq A$ ，$X$ 在关系 $R$ 下的像定义为：

  $$R[X] = \operatorname{ran}(R\uparrow X)$$

  反映的是像反映的是，集合 $X$ 通过关系 $R$ 能「到达」的所有元素。

复合关系描述的是两个关系“首尾相接”所形成的新关系，是后续讨论传递性和路径概念的重要基础。设 $R\subseteq A\times B, \quad S \subseteq B \times C$ ，则 $R$ 与 $S$ 的复合关系记为 $S\circ R$，定义为：

• 复合关系满足结合律，即只要关系的定义集合匹配，复合的顺序不影响最终结果：

  $$T\circ (S \circ R) = (T \circ S) \circ R$$

• 复合关系对并运算满足左右分配律：

  $$\begin{align*}R \circ (S \cup T) = (R \circ S) \cup (R \circ T) \\(S \cup T) \circ R = (S\circ R) \cup (T \circ R)\end{align*}$$

• 复合关系对交运算不满足等式形式的分配律，但存在包含关系。

  $$\begin{align*}R \circ (S \cap T) \subseteq (R \circ S) \cap (R \circ T) \\(S \cap T) \circ R \subseteq (S\circ R) \cap (T \circ R)\end{align*}$$

😈 性质与闭包