离散数学

第一章 集合论

1.1 集合的基本概念

指定范围内的每一个对象被称为这个集合的元素

集合 中的元素个数被称为集合 的基数

基数有限的集合称为有限集，反之称为无限集

集合中的元素满足无序且互异

设 为任意两集合，如果 中每个元素都是 中的元素则称 是 的子集，也称 被 包含，或 包含 ，记作

设 为任意两集合，如果 则称 是 的真子集，记作

不含任何元素的集合叫做空集，记作

在一个相对固定的范围内，包含此范围内所有元素的集合称为全集或论集，用 或 表示

设 为任意集合，称 的所有不同子集构成的集合为 的幂集，记作 或 ，即

1. 称含有 个元素的集合为 元集
2. 若 为 元集，则称 的含有 个元素的子集为它的 元子集

1.2 集合的运算

称为 与 的并集，称 “”为并运算

称为 与 的交集，称 “”为交运算

称为 与 的差集，称 “”为差运算， 又可叫做相对补集

特别指出，当 时， 称为集合 的补集，记为 ， 称为补运算

称为 与 的对称差集，称 “”为对称差运算

1.3 无限集

设 为两个集合，若在 之间存在一一对应关系 则称 是等势的

凡与自然数集 等势的集合，称为可数集（可列集），该集合的基数记为 ，读作“阿列夫零”

1. 两个有限集等势当且仅当它们有相同的元素个数
2. 有限集不和其任何真子集等势
3. 可数集可以和其可数的真子集等势

称开区间 为不可数集，其基数称为 ，凡与开区间 等势的集合都是不可数集

第二章 命题逻辑

2.1 命题与命题联结词

能够判断真假的陈述句称为命题。称“真”和“假”为命题的真值

不能再分解为更简单命题的命题，称为原子命题（简单命题）；像“或者”这种连接命题的关联词称为命题联结词；由命题联结词联结原子命题而成的命题称为复合命题

1. 否定联结词

   设 是任意一个命题，称复合命题“非 ”为 的否定，记作 ，称符号 为否定联结词

2. 合取联结词

   设 是任意两个命题，称复合命题“ 并且 ”为 与 的合取，记作 ，称符号 为合取联结词

3. 析取联结词

   设 是任意两个命题，称复合命题“ 或 ”为 与 的析取，记作 ，称符号 为析取联结词

4. 蕴含联结词

   设 是任意两个命题，称复合命题“如果 ，则 ”为 与 的蕴含，记作 ，称符号 为蕴含联结词， 为蕴含式的前件， 为蕴含式的后件

5. 等价联结词

   设 是任意两个命题，称复合命题“ 当且仅当 ”为 与 的等价，记作 ，称符号 为等价联结词

自然语言描述	符号化结果
仅当
除非 ，否则非

2.2 命题公式、解释与真值表

原子命题又常被称作命题常量，或常值命题

字母 通常被称为命题变量，或命题变元

命题公式 又被称为 的真值函数

命题演算的合式公式，又称命题公式，可按递归规则定义

设 是出现在公式 中的所有命题变元，给它们各指定一个真值，则称这些指定的真值组成 的一个解释（或赋值），常记为

若赋值 使 取值为真则称这个赋值为成真赋值，也称 满足于 ；反之称成假赋值，也称 弄假与

个不同的解释及 对应的真值构成一张表称为 的真值表

任意解释 ，公式 的真值全为真则称 为永真公式（重言式）；如果全为假则称 为永假公式（矛盾式）；如果存在至少一个为真称为可满足公式

设 两个命题公式， 是出现在 中的所有命题变元。如果对于 的 组不同的解释， 与 的结果都相同，则称公式 与 等价，记作

的充要条件是 是永真公式

2.3 公式的标准型——范式

如果任意一个命题公式都可用 中的联结词进行等价表示，则称 是联结词的完备集

设 是一个联结词的完备集且 。如果至少存在一个命题公式不能用 中的联结词进行等价表示，则称 为极小联结词的完备集

称命题变元或命题变元的否定为文字

如果一个命题公式具有形式 其中 是文字，则称该命题公式为合取式或短语

如果一个命题公式具有形式 其中 是文字，则称该命题公式为析取式或子句

如果一个命题公式具有形式 其中 是析取式，则称该命题公式为合取范式

如果一个命题公式具有形式 其中 是合取式，则称该命题公式为析取范式

1. 单个的文字是合取式、析取式、析取范式、合取范式
2. 析取范式、合取范式仅含联结词
3. 有括号的公式必须作为一个整体来看，如 是合取范式但不是析取范式

在含有 个命题变元 的合/析取式中，若每个命题变元与其否定不同时存在但二者之一恰好出现一次且仅一次，则称此合/析取式为关于 的一个极小/大项

如果一个命题公式具有形式 其中 是极大项，则称该命题公式为主合取范式

如果一个命题公式具有形式 其中 是极小式，则称该命题公式为主析取范式

编码规则

利用真值表计算主范式的方法被称为真值表技术

设 是命题公式。对任意解释 ，如果 为真， 也为真，则称 是 的逻辑结果，或者 共同蕴含 ，记作

设 是命题公式，如果 是 的逻辑结果，则称 为有效的或者正确的，否则称为无效的，称 为一组前提， 为结论

等价公式转换法

1. 合取所有前提作为蕴含式的前件，结论作为蕴含式的后件
2. 化简蕴含式
3. 如果结果为 则推理有效否则无效

演绎法

推理规则

1. P 规则：引入前提
2. T 规则：引入推理过程的中间结果
3. CP 规则：如果逻辑结果为蕴含式，并将逻辑式的前件作为前提引入

引入的定理

1. I：推理定理
2. E：等价定理

反证法：在 的证明过程中，将 作为附加前提然后推出矛盾的方法

设 和 是两个析取式，如果 中有文字 ， 中有文字 ，则从 与 中分别消去 和 ，并将余下的部分析取构成一个新的析取式 ，这个过程称为消解， 被称为 和 的消解式

消解原理：如果 是 和 的消解式，则

第三章 谓词逻辑

3.1 自然语言的谓词符号化

在原子命题中，可以独立存在的客体称为个体词，用以刻画客体性质或客体之间关系的部分称为谓词

具体明确的个体称为个体常量，个体常量一般用带或不带下标的小写英文字母 等表示

泛指的或抽象的个体称为个体变量，一般用带或不带下标的小写英文字母 表示

个体变量的取值范围称为个体域（或论域），常用字母 表示

宇宙间的所有个体聚集在一起所构成的个体域称为全总个体域

设 是定义在 的 元函数，其中 为非空的个体域，如果 的值域是 ，则称 为 元命题函数或者 元谓词

表示全部数量关系的词语称为全称量词，记为

表示部分数量关系的词语称为存在量词，记为

其中 被称为作用变量

一般将量词加在对应的谓词之前，记为 。此时 被称为全称量词和存在量词的辖域

为了描述的统一性和方便性，将表示个体域的名词称为特性谓词，并用一元谓词表示。一般来说量词后的名词即为特性谓词

3.2 谓词公式与解释

函数的定义域和值域都是个体域

谓词的定义域是 ，值域是

元谓词符号化涉及到的符号总结如下

1. 常量符号：用带或不带下标的小写英文字母 表示，当个体域 给出时它可以是 中某个确定的元素

2. 变量符号：用带或不带下标的小写英文字母 表示，当个体域 给出时它可以是 中的任意元素

3. 函数符号：用带或不带下标的小写英文字母 表示，当个体域 给出时， 元函数 可以是 的任意一个函数

4. 谓词符号：用带或不带下标的大写英文字母 表示，当个体域 给出时， 元谓词 可以是 的任意一个谓词

谓词逻辑中的项递归定义

1. 任意的常量符号或变量符号是项
2. 若 是 元函数符号， 是项，则 也是项
3. 有限次使用 1 和 2 后得到的符号串都是项

注意：项是个体域 中的某个个体次

若 是 元谓词， 是项，则称 为原子谓词公式，简称原子公式

合式谓词公式可按递归规则生成

给定公式 和 ， 为 和 的辖域，则 中 的出现都约束出现，称变元 为约束变元， 中的不同于 的其他变元的出现则是自由出现，称这些变元为自由变元

1. 约束变元改名规则，简称改名规则
   1. 将量词辖域内与作用变元相同的约束变元都用新的个体变元替换
   2. 新的变元一定要有别于改名辖域中的所有其他变元
2. 自由变元带入规则，简称带入规则
   1. 将公示中出现某个自由变元的每一处都用新的个体变元或个体常量替换
   2. 新变元不允许在原公式中以任何约束形式出现

设 是任意一个公式，若 中无自由变元则称 为封闭的公式，简称闭式，闭式一定是命题

谓词逻辑中谓词公式 的每一个解释 由如下四个部分组成

1. 非空的个体域
2. 中的每个常量符号，指定 中某个特定元素
3. 中每个 元函数符号，指定 到 的某个函数
4. 中的每个 元谓词符号，指定 到 的某个特定谓词

任意解释 ，谓词公式 的真值全为真则称 为永真公式；如果全为假则称 为永假公式；如果存在至少一个为真称为可满足公式

设 是谓词公式，如果谓词公式 是永真公式，那么 是等价的，记为

3.3 谓词公式的标准型——前束范式

具有形式 形式的谓词公式称为前束范式，其中 为量词 ， 为不含量词的公式

设公式 是一个前束合取范式，按照从左到右去掉 中的存在量词，若 是存在量词且 ，则直接用个体变量取代 中所有的 ，并在 中删去 ，若 都是全称量词，则在 中使用一个未使用过的函数符号如 ，并用 替换 中所有的 ，然后删去 。重复此过程直到没有存在量词。这样得到的公式称为 Skolem 范式

3.4 谓词逻辑的推理理论

在谓词公式 中，若 不自由出现在量词 的辖域中，则称 对于 是自由的

1. 推理规则

   1. UI：全称量词消去

      取代 的新变元在新公式中是自由出现的

   2. EI：存在量词消去

      如果 中还有出 以外的自由变元，需要用这些变元的函数符号来取代

   3. UG：全称量词引入

      对 自由才可以引入

   4. EG：存在量词引入

      取代 的 在原公式中不曾出现过

2. 推理定律

如果需要使用 UI 和 EI 规则并且选用的个体常量是同一个符号，则必须先使用 EI 规则再使用 UI 规则

第四章 二元关系

4.1 二元关系及其表示

由两个元素 按照一定次序组成的二元组称为有序偶对，简称序偶，记作

设 是两个集合，称集合 为集合 的笛卡尔积

设 是 个集合，称集合 为集合 的笛卡尔积

当 时，可记

设 为两个非空集合，称 的任意子集 为从 到 的一个二元关系，简称关系，记作 。如果 ，则称 为 上的一个二元关系，记作

序偶 ，可记作 ，读作“ 对 有关系 ”

当 时，称 为空关系

当 时，称 为全关系

当 时，称 为 上的恒等关系

设 是 个集合，称 的子集 为以 为基的 元关系

有 ，此时 称为 的前域， 称为 的后域， 称为 的定义域，记作 ， 称为 的值域，记作 ， 称为 的域

设 ， 是从 到 的二元关系，称矩阵 为关系 的关系矩阵

1. 如果 和 是两个 布尔矩阵，则布尔并也是 矩阵，记作
2. 如果 和 是两个 布尔矩阵，则布尔交也是 布尔矩阵，记作
3. 如果 和 是两个 布尔矩阵，则布尔积也是 布尔矩阵，记作

4.2 关系的运算

设 是三个集合 ，则 与 的复合关系（合成关系）是从 到 的关系，记为 ，其中 符号 表示复合运算

设 是两个集合，，则从 到 的关系 称为 的逆关系，符号 表示逆运算

设 ，则 的 次幂 记为 ，定义如下

4.3 关系的性质

设 是 上的关系

关系性质	集合表示	关系图
自反性		中每个节点都有自环
反自反性		中每个节点都没有自环
对称性		图中两点间只有方向相反的两条边或者无边
反对称性		图中任意一对节点间至多有一条边
传递性		中任何两个不同的节点之间如果有一条路径则必定有一条边

绝对不能脱离基集讨论关系的性质

关系性质的保守性

1. 是自反的，则 也是自反的

2. 是反自反的，则 也是反自反的

3. 是对称的，则 也是对称的

4. 是反对称的，则 也是反对称的

5. 是传递的，则 也是传递的

4.4 关系的闭包

在给定关系中添加最少元素使其具有需要的特殊性质被称为求关系的闭包

自反闭包，对称闭包，传递闭包被记作

3. ，若 ，则

第五章 特殊关系

5.1 相容关系

设 是定义在非空集合 上的关系，如果 是自反的，对称的，则称 为 上的相容关系

给定非空集合 ，设有集合 ，如果

1. 且

则 被称作集合 的一个覆盖

5.2 等价关系

设 是定义在非空集合 上的关系，如果 是自反的，对称的和传递的，则称 为 上的等价关系

给定非空集合 ，设有集合 ，如果

1. 且

则 被称作集合 的一个划分，而 叫做这个划分的块或类

由等价关系产生的划分被称为集合 上关于 的商集，划分中的每一块被称为等价类

设 是非空集合 上的等价关系，对 ，称集合 为 关于 的等价类，或叫做 关于 生成的等价类，其中 称为 的生成元（代表元或典型元）

设 是非空集合 上的等价关系，由 确定的一切等价类构成的集合称为 上关于 的商集，记为 ，即

设 是非空集合 上的等价关系，则 对 的商集 是 的一个划分，称此划分为由 导出的等价划分

给定非空集合 的一个划分 设 则 是 上的等价关系，称此关系 是由划分 所导出的等价关系

5.3 次序关系

设 是定义在非空集合 上的关系，如果 是反自反的，反对称的和传递的，则称 为 上的拟序关系，简称拟序，记作 ，并将 记为 。序偶 称为拟序集

一个关系具有反自反性和传递性，意味着它一定有反对称性

设 是定义在非空集合 上的关系，如果 是反自反的和传递的，则称 为 上的拟序关系

设 是定义在非空集合 上的关系，如果 是自反的，反对称的和传递的，则称 为 上的偏序关系，简称偏序，记作 ，并将 记为 。序偶 称为偏序集

对于偏序关系，哈斯图的画法：

1. 去掉关系图中所有的自环
2. 对 将 画在 的下方且在图中去掉该边的箭头
3. 对 ，且 之间不存在 使得 ，则 之间连一条边

设 是偏序集， 是 的非空子集

1. 如果 则称 为 的最大元素，简称最大元

2. 如果 则称 为 的最小元素，简称最小元

3. 如果 则称 为 的极大元素，简称极大元

4. 如果 则称 为 的极小元素，简称极小元

设 是偏序集， 是 的任何一个子集

1. 如果 则称 为 的上界

2. 如果 则称 为 的下界

3. 令 ，则称 的最小元为 的最小上界或上确界，记作

4. 令 ，则称 的最大元为 的最大下界或下确界，记作

设 是一个偏序集关系，若 ，总有 或 之一成立，则称关系 为全序关系或者线序关系，简称全序或者线序。称 为全序集或者线序集，或者链

设 是一个偏序集关系，若 的任何一个非空子集都有最校园，则称 为良序关系，简称良序，此时 称为良序集

1. 良序 全序 偏序
2. 有限全序集一定是良序集

5.4 函数

设 是集合 到 的关系，如果对每个 ，都存在唯一 使得 ，则称关系 为 到 的函数或映射，记为 。

为函数的定义域，记为

为函数的值域，记为

当 时，通常记为 ，此时称 为函数 的自变量（原像），称 为 在 下的函数值（像）

设 是从集合 到 的函数

1. 如果 ，则称 为从 到 的单射或一对一映射
2. 如果 则称 为从 到 的满射
3. 如果 既是单射又是满射，则称 为从 到 的双射或一一映射
4. 如果 ，则称 为 上的函数；当 上的函数 是双射时，称 为变换

设 和 是两个函数，如果 与 的符合关系 是从 到 的函数，则称 为函数 和 的复合函数

设 ，如果 是从 到 的函数，则称 是函数 的逆函数

设 是有限集合，从 到 的双射函数称为 上的置换或排列，记为 ， 称为置换的阶

第六章 图

6.1 图的基本概念

一个图是一个序偶 ，记为

1. 是有限非空集合， 称为结点，简称点， 称为结点集
2. 是有限集合，称为边集。 中的每个元素都有 中的结点对与之对应，称之为边

若边 与无序结点对 对应，则称 为无向边，这时称 为边的两个端点，也称结点 与边 是彼此相关联的 若边 与序偶 对应，则称 为有向边（弧），这时称 为边的始点（弧尾），称 为边的终点（弧头），统称为 的端点

对于一个图 ，将其记为 并写出 的集合表示，这称为图的集合表示，画图则称为图的图形表示

设图 且结点已经有了从 到 的次序，则 阶方阵 称为 的**邻接矩阵，其中

设图 1. 设 用 表示从 中去掉边 得到的图，即 ，该操作称为删除边。又设 ，用 表示从 中删除 中所有边得到的图，即 ，该操作称为删除边集 2. 设 ，用 表示从 中去掉结点 及 关联的所有边得到的图，即 ，该操作称为删除结点。又设 ，用 表示从 中去掉 中所有结点及关联的所有边得到的图，即 ，该操作称为删除结点子集。 3. 设 ，用 表示从 中删除 ，将 的两个端点 用一个新的结点 代替，使 关联 以外 关联的所有边，该操作称为边的收缩。一个图 可以收缩为图 ，是指 可以从 经过若干次边的收缩而得到 4. 设 ，用 表示在 之间加一条边，该操作称为加新边

图 中，若两个结点 是 的端点，则称它们互为邻接点 具有公共结点的两条边称为邻接边 两个端点相同的边称为环或自回路 图中不与任何结点相邻接的结点称为孤立结点 仅由孤立结点组成的图称为零图 仅含一个结点的零图称为平凡图 含有 个结点 条边的图称为 图

每条边都是无向边的图称为无向图 每条边都是有向边的图称为有向图 有有向边也有无向边的图的图称为混合图

在有向图中，两结点间（包括结点自身）若有同始点同终点的几条边，则这几条边称为平行边 在无向图中，两结点间（包括结点自身）若几条边，则这几条边称为平行边 两结点 间相互平行的边的条数称为边 的重数 含有平行边的图称为多重图，非多重图称为线图，无环的线图称为简单图

赋权图 是一个三元组 或四元组 其中 是点集， 是边集， 是 到非负实数集合的函数， 是 到非负实数集合的函数

设有图 和

1. 若 则称 是 的子图，记为
2. 若 且 则称 是 的真子图，记为
3. 若 则称 是 的生成子图
4. 若 以 为节点集，两个端点均在 中的边为边集的 的子图称为 导出的 子图，简称 的导出子图

设 为一个具有 个结点的无向简单图，如果 中任意两个节点间都有边相连，则称 为无向完全图，简称完全图，记为 设 为一个具有 个结点的有向简单图，如果 中任意两个节点间都有方向相反的两条边相连，则称 为有向完全图，简称完全图，记为

设 为简单图， 为完全图，则称 为 的补图，记为

6.2 握手定理

1. 图 中以 为端点的边数（有环算两次）称为结点 的度数，简称度，记为
2. 有向图 中以 为始点的边数称为结点 的出数，记为 ，以 为终点的边数称为结点 的入数，记为
3. 度数为 的点称为悬挂结点，以悬挂节点为端点的边称为悬挂边

图论的基本定理（握手定理）

图中结点度数和等于边数的 倍，即

推论：

1. 图中度数为奇数的点的个数为偶数
2. 有向图中各节点的出度之和等于入读之和等于边数

设 ，称 为 的度数序列

6.3 图的同构

设有图 和 ，若存在双射函数 ，使 当且仅当 并且重数相同，则称 与 同构，记为

6.4 通路与回路

设有图 中结点和边相继交错出现的序列

1. 若 中 两端点是 ，则称 为结点 到 的通路， 称为始点， 称为终点，统称为贿赂的端点。 称为通路的长度，当 时，此通路称为回路
2. 若通路中所有边互不相同，则称为简单通路（迹） 若回路中所有边互不相同，则称为简单回路（闭迹）
3. 若通路中所有结点互不相同，则称为基本通路，初级通路、路径 若回路中除头尾所有结点互不相同，则称为基本回路，初级回路、圈

到 长度 的通路数目可以通过邻接矩阵幂计算

1. 如果 到 存在通路则称 到 可达的
2. 如果 到 可达，则称 到 的长度最短的通路为短程线，其长度称为 到 的距离

设有线图 且结点已经有了从 到 的次序，称 阶方阵 为 的可达性矩阵，其中

设有线图 ， 分别是 的邻接矩阵和可达性矩阵，则有

其中 表示 的布尔积 次幂

6.5 图的连通性

若无向图 中任何两个结点都是可达的，则称 是连通图，反之为非连通图（或分离图）

无向图 中节点之间的可达关系定义如下

则 是 上的等价关系

无向图 中节点之间的可达关系 的每个等价类导出的子图都称为 的一个连通分支。 表示 中的连通分支个数

设有向图 1. 略去所有边的方向得到无向图 ，如果 是连通图则称 是连通图或弱连通图，否则为非连通图 2. 若 中任何一对结点直接至少有一个到另一个是可达的，则称 是单向连通图 3. 若 中任何一对节点都相互可达，则称 是强连通图

能找到一条经过所有节点的回路，则是强连通图 能找到一条经过所有节点的通路，则是单向连通图

在有向图 中，设 是 的子图，若 1. 是强联通图（单向连通图、弱连通图） 2. ，若 ，则 不是强联通图（单向连通图、弱连通图）

则称 为 的强联通分支（单向连通分支、弱连通分支）或强分图（单向分图、弱分图）

第七章 特殊图

7.1 树

连通而不含回路的无向图称为无向树，简称树

树中度数为 的结点称为叶，度数大于 的结点称为分支点（内部节点）

每个连通分支都是树的无向图称为森林

平凡图称为平凡树

平凡树没有叶

给定图 ，若 的某个生成子图是树，则称之为 的生成树，记为

生成树上的边称为树枝

中不在 的边称为弦

的所有弦的集合称为生成树的补

给定连通赋权图 ，生成树 的每个数值所赋权值之和称为 的权，记为

中具有最小权的生成树称为 的最小生成树

7.2 根树

一个有向图略去所有边的方向后得到的无向图是一棵树则称之为有向树

一棵非平凡的有向树，如果恰有一个节点入度为 ，其他节点入度为 ，则称之为根数或外向树。

入度为 的点称为根

出度为 的点称为叶

入度为 出度不为 的点称为内点

内点和根统称为分支点

从根到任一结点 的通路长度称为 的层数，称层数相同的结点在同一层上

所有节点的层数中最大的称为根数的高

在跟树种，若 到 可达，则称 是 祖先， 是 的后代

若 是根数中的有向边，则称 是 父亲， 是 儿子

两个结点是同一结点的儿子，则彼此称兄弟

如果在根树中规定每一层上结点次序，则称有序树

设 为根树

1. 若 的每个分支点都至多 个儿子，则称 为k元树（或 k叉树）
2. 若 的每个分支点都恰有 个儿子，则称 为完全k元树
3. 若 是完全k元树且每个叶结点的层数均为树高，则称 为满k叉树
4. 若k元树有序，则称 为有序k元树
5. 若完全k元树有序，则称 为有序完全k元树
6. 若满k元树有序，则称 为有序满k元树
7. 的任一结点及其所有后代导出的子图 称为 的以 为根的子树。有序2元树每个节点的两个儿子分别称为左儿子和右儿子。有序2元树的每个节点的两棵子树分别称为左子树和右子树

在完全k元树中，叶数为 ，分支点数为 ，则 根树的遍历

1. 先根次序
2. 中根次序
3. 后根次序

根树转化为2元树

从根开始只保留最左边儿子，相邻弟弟变为右儿子

森林转化为2元树

每棵树转为2元树，然后一次将每棵2元树变为左边2元树根的子树

设 为长度 的符号串，则其子串 为其长度为 的前缀

7.3 欧拉图

设无孤立结点图 ，经过所有边一次且仅一次的通路（回路）称为欧拉通路（回路）

具有欧拉回路的图叫欧拉图

规定：平凡图为欧拉图

无向图找奇点

有向图找入度不等于出度的点

设 ，若 则称 为 的桥或割边

7.4 哈密顿图

经过图中每个节点一次且仅一次的通路（回路）称为哈密顿通路（回路）

存在哈密顿回路的图称为哈密顿图

对于哈密顿图 ，任意

对于存在哈密顿回路的无向图

（为必要条件而非充分条件，如彼得森图）

设 是 个点的简单无向图，若对任意两个不相邻的点 均有 则 中存在哈密顿通路

设 是 个点的简单无向图，若对任意两个不相邻的点 均有 则 中存在哈密顿回路

设 是 个点的简单无向图，若对任意 ，均有 则 是哈密顿图

（为充分条件而非必要条件，如六边形）

7.5 偶图

若无向图的点集能够划分为两个子集满足任意一条边的两个端点都不在同一集合，则称 为偶图，二部图，二分图， 为互补结点子集，通常纪为

在偶图 中，若 中每个节点都与 每个结点连一条边，则称 为完全偶图，完全二部图，完全二分图，记为 ，其中

判断偶图

找奇环

在偶图中， 若存在 的子集 ，其中 是 个不同的 中的结点，则称 为 到 的一个完全匹配，简称匹配

存在匹配的必要条件是

霍尔定理（婚姻定理）

偶图中存在 到 的充要条件是 中任意 个结点至少与 中的 个结点相邻接

条件通常称为相异性条件

t条件（充分非必要）

中每个节点至少关联 条边

中每个节点至多关联 条边

即找 中最小度数和 中最大度数即可

7.6 平面图

各边在非结点上交叉称为交叉点，相交的边称为交叉边

若能吧一个无向图 所有节点和边画在平面上，使得任意两边除公共结点为没有其他交叉点，则称 为平面图，否则为非平面图

没有交叉边的图形称为平面图的平面表示

对于平面图 的一个平面表示

由边所包围的内部不含图的结点和边的区域称为 的一个面

保卫盖面的诸边所构成的回路称为这个面的边界

面 的边界的长度称为该面的次数，记为

区域面积有限的的称为有限面，反之称为无限面

图中所有面的次数之和等于边数的两倍

欧拉公式

对于联通平面图， 个结点， 条边和 个面，则 对于一个简单连通平面图，若 ，则 若每个面的次数至少为 ，则 库拉托夫斯基定理

一个图是平面图的充要条件是其任何子图都不可能收缩为 或