设 G = ⟨V ,E⟩, G′ = ⟨V ′,E′⟩ 为两个图（同为无向图或同为有向图），若 V ′ ⊆ V且 E′ ⊆ E，则称 G′ 为 G 的子图 ，G 为 G′ 的母图，记作 G′ ⊆ G.又若 V ′ ⊂ V 或 E′ ⊂ E，则称子图 G′ 为 G 的真子图。若 V ′ = V，则称子图 G′ 为 G 的生成子图
导出子图
设 G = ⟨V ,E⟩, V1 ⊂ V 且 V1 = ∅，称以 V1 为顶点集，以 G 中两个端点都在V1 中的边组成边集 E1 的图为 G 的 V1 导出的子图，记作 G[V1]。
又设 E1 ⊂ E 且 E1 = ∅，称以 E1 为边集，以 E1 中边关联的顶点为顶点集 V1的图为 G 的 E1 导出的子图，记作 G[E1]
删除收缩与添加边
设 G = ⟨V ,E⟩ 为无向图.
设 e ∈ E，用 G − e 表示从 G 中去掉边 e，称作删除边 e . 又设 E′ ⊂ E，用G − E′ 表示从 G 中删除 E′ 中的所有边，称作 删除 E′。
设 v ∈ V，用 G − v 表示从 G 中去掉 v 及所关联的一切边，称作删除顶点v . 又设 V ′ ⊂ V，用 G − V ′ 表示从 G 中删除 V ′ 中所有的顶点，称作删除V ′设 e = (u, v) ∈ G，用 G\e 表示从 G 中删除 e 后，将 e 的两个端点 u, v 用一个新的顶点 w（可以用 u 或 v 充当 w）代替，并使 w 关联除 e 以外 u, v关联的所有边，称作边 e 的收缩
设 u, v ∈ V（u, v 可能相邻，也可能不相邻），用 G ∪ (u, v)（或G + (u, v)）表示在 u, v 之间加一条边 (u, v)，称作加新边
常称只有一个分支点，且分支点的度数为 n − 1 的 n(⩾ 3) 阶无向树为星形图，称其唯一的分支点为星心
生成树
定义
如果无向图 G 的生成子图 T 是树，那么称 T 是 G 的生成树．设 T 是 G 的生成树，G 的在 T 中的边称作 T 的树枝，不在 T 中的边称作 T 的弦．称 T 的所有弦的导出子图为 T 的余树，记作¯T
存在性定理
无向图 G 有生成树当且仅当 G 是连通图
证明：
🚨
构造性证明，这个产生生成树的方法称作破圈法
必要性显然。下面证明充分性．若 G 中无回路，则 G 为自己的生成树。若 G 中
含圈，任取一个圈，随意地删除圈上的一条边；若仍有圈，再任取一个圈并删去这
个圈上的一条边，重复进行，直到最后无圈为止。最后得到的图无圈（当然无回
路）、连通且是 G 的生成子图，因而是 G 的生成树
性质定理
设 G 为 n 阶 m 条边的无向连通图，则 m ⩾ n − 1（上面的一个推论）
设 T 为无向连通图 G 中的一棵生成树，e 为 T 的任意一条弦，则 T ∪ e 中存在G 中只含一条弦 e，其余边均为树枝的圈，而且不同的弦对应的圈也不同
基本回路系统
定义
设 T 是 n 阶 m 条边的无向连通图 G 的一棵生成树，设 为T 的弦， , r = 1, 2, · · · , m − n + 1, 为 T 添加弦产生的 G 中由弦和树枝构成的圈，称 为 G 的对应弦的 基本回路 或基本圈．称 {C1, C2, · · · ,Cm−n+1} 为 G 对应 T 的 基本回路系统，称 m − n + 1 为 G 的圈秩，记作ξ(G)
不难看出，无向连通图 G 的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同
广义回路空间
可以证明：任一简单回路都可以表示成基本回路的环和
无向图中的圈或若干个边不重的圈的并，称作广义回路．规定 ∅ 为广义回路。圈和简单回路都是广义回路．记无向图 G 的广义回路的全体（含 ∅）为。两个广义回路的环和仍是广义回路，即 中环和运算是封闭的
在 上定义数乘运算 易知对环和运算与数乘运算构成数域 上的 m − n + 1 维线性空间，称作广义回路空间。任一基本回路系统均是它的一个基
割集定理
设 T 是连通图 G 的一棵生成树，e 为 T 的树枝，则 G 中存在只含树枝 e，其余边都是弦的割集，且不同的树枝对应的割集也不同
广义割集系统
设 T 是 n 阶连通图 G 的一棵生成树， 为 T 的树枝，Si, i = 1, 2,· · · , n − 1, 是由树枝 ei 和弦构成的割集，则称 Si 为 G 的对应树枝 ei 的 基本割集．称 {S1, S2, · · · , Sn−1} 为 G 对应 T 的基本割集系统，称 n − 1 为 G 的割集秩，记作 η(G)
连通图 G 的割集秩 η(G) 不因生成树的不同而改变，但不同生成树对应的基本割集系统可能不同
广义割集空间
设无向图 G = ⟨V ,E⟩，∅V1 ⊂ V，记 V1 关于 V 的补集为¯V1，称(V1,¯V1) = {(u, v)|u ∈ V1, v ∈¯V1} 为广义割集 。规定 ∅ 为广义割集。显然，割集是广义割集，但广义割集不一定是割集
可以证明：任一广义割集都可以表示成基本割集的对称差（环和）
记 G 的广义割集的全体（含 ∅）为 S∗。在 S∗ 上定义数乘：0 · S = ∅, 1 · S = S
则 S∗ 关于对称差运算和数乘运算构成数域 F = {0, 1} 上的 n − 1 维线性空间，称作广义割集空间。任一基本割集系统均是它的一个基
连通带权图中的最小生成树
设无向连通带权图 G = ⟨V ,E, W⟩，T 是 G 的一棵生成树，T 的各边权之和称为 T 的权，记作 W(T)．G 的所有生成树中权最小的生成树称为 G 的最小生成树
设 T 为一棵非平凡的根树，∀vi, vj ∈ V (T)，若 vi 可达 vj，则称 vi 为 vj 的祖先，vj 为 vi 的后代 ；若 vi 邻接到 vj，即 ⟨vi, vj⟩ ∈ E(T)，则称 vi 为 vj 的父亲，而vj 为 vi 的儿子 ．若 vj, vk 的父亲相同，则称 vj 与 vk 是兄弟
根树分类
有序树：设 T 为根树，若将 T 中层数相同的顶点都标定次序，则称 T 为有序树
r叉树：若 T 的每个分支点至多有 r 个儿子，则称 T 为r 叉树
r叉正则树：若 T 的每个分支点都恰好有 r 个儿子，则称 T 为r 叉正则树
r叉完全正则树：若 T 是 r 叉正则树，且每个树叶的层数均为树高，则称 T 为r 叉完全正则树
根子树
设 T 为一棵根树，∀v ∈ V (T)，称 v 及其后代的导出子图Tv 为 T 的以 v 为根的根子树
为 T 的权，其中 l(vi) 是 vi 的层数．在所有有 t 片树叶，带权 w1, w2, · · · , wt 的2 叉树中，权最小的 2 叉树称作最优 2 叉树
Huffman 算法
前缀码
设 α1α2 · · · αn−1αn 是长为 n 的符号串，称其子串 α1, α1α2, · · · , α1α2 · · · αn 为该符号串的前缀．设 A = {β1, β2, · · · , βm} 是一个符号串集合，若 A 的任意两个符号串都互不为前缀，则称 A 为前缀码．由 0-1 符号串构成的前缀码称作2元前缀码
二叉树的周游
中序行遍法. 访问的次序为：左子树、树根、右子树
前序行遍法．访问的次序为：树根、左子树、右子树
后序行遍法．访问的次序为：左子树、右子树、树根
平面图
平面图的基本概念
定义
若能将无向图 G 画在平面上使得除顶点处外无边相交，则称 G 为可平面图 ，简称为平面图．画出的无边相交的图称作 G 的平面嵌入 ．无平面嵌入的图称作非平面图
在这里要提前指出并使用下述事实：在平面图理论中有两个具有特殊地位的图——，它们都是非平面图
定理1.1.1
平面图的子图都是平面图，非平面图的母图都是非平面图
定理1.1.2
设 G 是平面图，则在 G 中加平行边或环后所得的图还是平面图
面的定义
给定平面图 G 的平面嵌入，它的边将平面划分成若干个区域，每个区域都称作G 的一个面，其中有一个面的面积无限，称作 无限面 或外部面，其余面的面积有限，称作有限面 或内部面．包围每个面的所有边组成的回路组称作该面的边界，边界的长度称作该面的次数，记作deg( R )
平面图所有面的次数之和等于边数的两倍（类比于点的次数）
极大平面图
设 G 为简单平面图，若 G 是 Ki（1 ⩽ i ⩽ 4），或者在 G 的任意两个不相邻的顶点之间加一条边，所得图均为非平面图，则称 G 为极大平面图
性质：极大平面图是连通的，并且当阶数大于等于 3 时没有割点和桥
判定定理：设 G 是 n(⩾ 3) 阶简单连通的平面图，则 G 为极大平面图当且仅当 G 的每个面的次数均为 3
极小非平面图
若在非平面图 G 中任意删除一条边，所得的图为平面图，则称 G 为极小非平面图
欧拉公式
基本形式
设连通平面图 G 的顶点数、边数和面数分别为 n, m 和 r，则有n − m + r = 2
拓展形式
对于有 k(⩾ 2) 个连通分支的平面图 G，有 n − m + r = k + 1, 其中 n, m, r 分别为 G 的顶点数、边数和面数
推广性质
设 G 是连通的平面图，且每个面的次数至少为 l(⩾ 3)，则 G 的边数 m 与顶点数n 有如下关系：
推论：都是非平面图
设平面图 G 有 k(⩾ 2) 个连通分支，各面的次数至少为 l(⩾ 3)，则边数 m 与顶点数 n 应有如下关系：
设 G 是 n(⩾ 3) 阶 m 条边的极大平面图，则
设 G 是 n(⩾ 3) 阶 m 条边的简单平面图，则
设 G 是简单平面图，则 G 的最小度 δ ⩽ 5
上述定理在图着色理论中占重要地位
平面图的判定
三个定义
设 e = (u, v) 为图 G 的一条边，在 G 中删除 e，增加新的顶点 w，使 u, v 均与 w相邻，称作在 G 中插入 2 度顶点 w
设 w 为 G 中的一个 2 度顶点，w 与 u, v 相邻，删除 w，增加新边 (u, v)，称作在G 中消去 2 度顶点 w
若两个图 G1 与 G2 同构，或通过反复插入、消去 2 度顶点后同构，则称 G1 与G2 同胚
库拉托夫斯基（Kuratowski）定理
图 G 是平面图当且仅当 G 中既不含与 K5 同胚的子图，也不含与 K3,3 同胚的子图
图 G 是平面图当且仅当 G 中既没有可以收缩到 K5 的子图，也没有可以收缩到K3,3 的子图
平面图的对偶图
设 G 是一个平面图的平面嵌入，构造图 G∗ 如下：在 G 的每一个面 Ri 中放置一个顶点 vi∗。设 e 为 G 的一条边，若 e 在 G 的面 Ri 与 Rj 的公共边界上，则作边 e∗ = (vi∗, vj∗) 与 e 相交，且不与其他任何边相交．若 e 为 G 中的桥且在面Ri 的边界上，则作以 vi∗ 为端点的环 e∗ = (vi∗, vi∗)．称 G∗ 为 G 的对偶图
性质
定理（欧拉）
自对偶
如果图 G 存在一个平面嵌入，使得 G 同构于对偶图 G∗，那么称 G 为自对偶图
设 n ⩾ 4，在正 n − 1 边形 内放置一个顶点，连接这个顶点与上的所有顶点，所得的 n 阶简单图称作n 阶轮图，记作 Wn。特别地，n 为奇数的轮图称作奇阶轮图，n 为偶数的轮图称作偶阶轮图．图 1.4.2(c) 中，实边图为 5 阶轮图 W5．可以证明轮图都是自对偶图
支配集、覆盖集、独立集、匹配与着色
支配集、点独立集与点覆盖集
支配集
定义
设无向简单图G = ⟨V ,E⟩, V ∗ ⊆ V，若 ∀vi ∈ V − V ∗，∃vj ∈ V ∗ 使得(vi, vj) ∈ E，则称 V ∗ 为 G 的一个支配集，并称 vj 支配 vi。设 V ∗ 是 G 的支配集，且 V ∗ 的任何真子集都不是支配集，则称 V ∗ 为极小支配集 ．G 的顶点数最少的支配集称作 G 的最小支配集，最小支配集中顶点的个数称作 G 的支配数，记作 γ0(G)，简记为 γ0
应用：网站副本存放
点独立集
定义
设无向简单图G = ⟨V ,E⟩, V ∗ ⊆ V，若 V ∗ 中任何两个顶点均不相邻，则称 V ∗为 G 的点独立集 ，简称为独立集．若 V ∗ 再加入任何其他的顶点都不是独立集，则称 V ∗ 为极大点独立集；G 的顶点数最多的点独立集称作 G 的最大点独立集；最大独立集的顶点数称作 G 的点独立数 ，记作 β0(G)，简记为 β0
性质定理
设无向简单图 G = ⟨V ,E⟩ 没有孤立点，则 G 的极大点独立集都是极小支配集
点覆盖集
定义
设无向简单图 G = ⟨V ,E⟩, V ∗ ⊆ V，若 ∀e ∈ E, ∃v ∈ V ∗，使得 v 与 e 相关联，则称 V ∗ 为 G 的点覆盖集，简称为点覆盖，并称v 覆盖 e ．设 V ∗ 是 G 的点覆盖，若 V ∗ 的任何真子集都不是点覆盖，则称 V ∗ 为极小点覆盖 ．G 的顶点个数最少的点覆盖称为 G 的最小点覆盖；最小点覆盖中的顶点个数称作 G 的点覆盖数，记作 α0(G)，简记为 α0
性质定理
设无向简单图G = ⟨V ,E⟩ 没有孤立点, V ∗ ⊆ V，则 V ∗ 为 G 的点覆盖当且仅当 为 G 的点独立集
设 G = ⟨V ,E⟩ 是无孤立点的 n 阶无向图，V ∗ ⊆ V，则 V ∗ 是 G 的极小（最小）点覆盖当且仅当是 G 的极大（最大）点独立集，从而有α0 + β0 = n
G 中由匹配边和非匹配边交替构成的路径称作 交错路径 ，起点和终点不同，且都是非饱和点的交错路径称作 可增广的交错路径，G 中由匹配边和非匹配边交替构成的圈称作交错圈
性质定理
设 n 阶图 G 中无孤立点.
设 M 为 G 的一个最大匹配，对 G 中每个 M-非饱和点均取一条与其关联的边，组成边集 N，则 W = M ∪ N 为 G 的最小边覆盖
设 W1 为 G 的一个最小边覆盖，若 W1 中存在相邻的边就移去其中的一条，设移去的边集为 N1，则 M1 = W1 − N1 为 G 的最大匹配
G 的边覆盖数 α1 与匹配数 β1 满足：α1 + β1 = n
设图 G 无孤立点，M 是 G 的一个匹配，W 是 G 的一个边覆盖，则 |M| ⩽ |W|，且当等号成立时，M 是 G 的完美匹配，W 是 G 的最小边覆盖
设 M 是图 G 的一个匹配，则 M 为 G 的最大匹配当且仅当 G 中不含关于 M的可增广的交错路径
边覆盖集
定义
设无向简单图 G = ⟨V ,E⟩ 没有孤立点，E∗ ⊆ E，若对 ∀v ∈ V , ∃e ∈ E∗，使得 v与 e 相关联，则称 E∗ 为边覆盖集，简称为边覆盖，并称e 覆盖 v ．设 E∗ 为边覆盖，若 E∗ 的任何真子集都不是边覆盖，则称 E∗ 为极小边覆盖. G 的边数最少的边覆盖称为 G 的最小边覆盖. 最小边覆盖中的边数称作 G 的边覆盖数 ，记作 α1(G)，简记为 α1.
二部图中的匹配
完备匹配
设 G = ⟨V1, V2,E⟩ 为二部图，|V1| ⩽ |V2|，若 M 为 G 的一个匹配且|M| = |V1|，则称 M 为 V1 到 V2 的完备匹配
充要条件：相异性条件
设二部图 G = ⟨V1, V2,E⟩，其中 |V1| ⩽ |V2|，则 G 中存在 V1 到 V2 的完备匹配当且仅当 V1 中任意 k个顶点（1 ⩽ k ⩽ |V1|）至少与 V2 中的 k 个顶点相邻
充分条件：t条件
设二部图 G = ⟨V1, V2,E⟩，如果存在正整数 t，使得 V1 中每个顶点至少关联 t条边，而 V2 中每个顶点至多关联 t 条边，那么 G 中存在 V1 到 V2 的完备匹配
着色
点着色
设无向图 G 无环，对 G 的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称作图 G 的一种点着色，简称为着色。若能用 k 种颜色给 G 的顶点着色，则称 G 为k-可着色的。若 G 是 k-可着色的，但不是 (k − 1)-可着色的，则称 G 的色数 为 k。图 G 的色数记作 χ(G)，简记作 χ
