图论第一章图的基本概念图的定义图的同构完全图 & 偶图 & 补图度 & 度序列度的频序列子图图的运算途径 & 迹 & 路 & 圈 & 距离 & 直径图的连通性偶图判断定理赋权图最短路问题邻接矩阵关联矩阵邻接谱图的邻接代数图空间 (几乎不考)l 部图的概念与特征Turán 定理Turán 定理应用第二章树树的概念树的性质树的中心树的形心生成树的概念 & 性质生成树的计数回路系统简介Kruskal 算法破圈法Prim 算法第三章图的连通度割边及其性质割点及其性质块及其性质连通度和边连通度连通度的性质Menger 定理应用图的宽距离和宽直径第四章 Euler 图 & Hamilton 图欧拉图Fleury 算法中国邮递员问题哈密尔顿图应用度极大的非 Hamilton 图旅行售货员问题E 图和 H 图的联系第五章匹配与因子分解图的匹配Berge 定理偶图的匹配与覆盖问题的提出偶图的匹配存在性判定定理点覆盖与 König 定理Tutte 定理与完美匹配因子分解1-因子分解2-因子分解森林分解完全图的森林分解方法最优匹配 & 匈牙利算法 (几乎不考)匈牙利算法 (几乎不考)最优匹配 (几乎不考)匹配在矩阵理论中的应用第六章平面图平面图的概念平面图的性质平面嵌入概念的推广凸多面体与平面图极大平面图及其性质极大外平面图及其性质对偶图平面图的判定涉及平面性的不变量简介平面性算法第七章图的着色图的边着色偶图的边色数一般简单图的边色数几类特殊简单图的边色数边着色的应用顶点着色关于色数的若干结论四色定理 && 五色定理顶点着色的应用与色数有关的几类图色多项式的概念递推计数法 (掌握一种即可)理想子图法 (必须掌握)色多项式的性质第八章 Ramsey 定理独立集与覆盖边独立集与边覆盖Ramsey 数 R(m, n)第九章有向图有向图有向图的连通性图的定向问题有向树、跟树m 元树最优树

图论

第一章图的基本概念

图的定义

定义 1： $G$ $(V,E)$ $G=(V,E)$ ，其中：

$V$ 是一个非空集合，称为顶点集点集 $V(G)$ ，其元素称为顶点或点
$E$ $V$ 边集 $E(G)$ 边 $E$ 中可出现多次

注意： $n(G)$ $m(G)$ -> 边数

相关概念

相关联： $e=uv$ $u$ $v$ $e$ 端点 $u$ $v$ $u$ $v$ $e$ 相关联
相邻：若两条边有一个共同的端点，则称这两条边相邻
孤立点：不与任何边相关联的点
自环（环）：两端点重合的边
重边：连接两个相同顶点的边的条数，叫做边的重数。重数大于 1 的边称为重边
有限图：点集与边集均为有限集合的图标称为有限图
平凡图：只有一个顶点而无边的图称为平凡图
空图：边集为空的图称为空图
简单图：即没有自环也没有重边的图称为简单图
复合图：除去简单图，其他图都称为复合图

图的同构

定义 2： $G_1=(V_1,E_1)$ $G_2=(V_2,E_2)$ $u_1,v_1 \in V_1$ $u_2,v_2 \in V_2$ $u_1 \leftrightarrow u_2$ $v_1 \leftrightarrow v_2$ $u_1v_1 \in E_1$ $u_2v_2 \in E_2$ $u_1v_1$ $u_2v_2$ 两图同构 $G_1 \cong G_2$

注意

两个同构的图均有相同的结构，没有本质的差异，差异只是顶点和边的名称不同
图同构的几个必要条件：1. 顶点数相同；2. 边数相同；3. 若将各点所关联的边数记录下来，则所得到的数组相同
在图的图形表示中可以不给图的点和边标号，称这样的图为非标定(号)图，否则称为标定(号)图。非标定图实际上是代表一类相互同构的图。不误解时我们也不严格区分标定图与非标定图
判定图的同构是很困难的。对于规模不大的两个图，判定其是否同构，可以采用观察➕推证的方法

完全图 & 偶图 & 补图

定义 3：任意两点均相邻的简单图完全图 $n$ $K_n$ $E_{K_n} = n(n-1)/2$

定义 4：点集 $X$ $Y$ $X$ $Y$ 中，则这样的图称为 $(X,Y)$ 的偶图（或二部图）

完全偶图 $(X,Y)$ $X$ $Y$ $|X|=m$ $，|Y|=n$ $K_{m,n}$

定义 5： $G=(V,E)$ $H=(V,E_1 \setminus E)$ $G$ 补图 $H= \overline G$ $E_1 = \{ uv | u \ne v，u,v \in V \}$

解释： $E_1$ $V$ $E_1 \setminus E \longleftrightarrow E_1 - E$

定理 1： $n$ $G$ $G \cong \overline G$ $n \equiv 0,1\pmod{4}$

证明： $G$ $G$ $m(G) + m(\overline G) = m(K_n) = \frac{n(n-1)}{2}$ $m(G) = \frac{n(n-1)}{4}$
$G$ $m(G)$ $\frac{n(n-1)}{4}$ $n \equiv 0 \pmod{4}$ $(n-1) \equiv 0 \pmod{4}$

度 & 度序列

定义 6： $v$ $G$ $G$ $v$ $v$ 度数 $v$ 度 $d_G(v)$ $d(v)$

相关术语和记号

$\delta(G)$ ： $G$ 的顶点的最小度
$\Delta(G)$ ： $G$ 的顶点的最大度
奇点：度数为奇数的顶点
偶点：度数为偶数的顶点
$k$ 正则图： $k$ 的简单图

$K_n$ $K_{n,n}$ 均为正则图

定理 2 (握手定理)： $m$ $G=(V,E)$ $\sum\limits_{v \in V}d(v)=2m$

推论 1：任意图中，奇点的个数为偶数

证明： $V_1$ $V_2$ $G$ $\sum\limits_{v \in V_1}d(v) + \sum\limits_{v \in V_2}d(v) = 2m(G)$
显然第二个求和式为偶数，而第一个求和式中的每一项都为奇数，所以第一个求和式必然有偶数项，即度数为奇数的顶点个数必为偶数

推论 2：正则图的阶数和度数不同时为奇数（有歧义，注意断句！！！即阶数和度数不能均为奇数）

证明： $G$ $k$ $k$ $G$ 的点数必为偶数

例： $\Delta$ $\delta$ $G$ $\delta \le \frac{2m}{n} \le \Delta$

证明： $n\delta \le \sum\limits_{v \in V(G)}d(v) = 2m \le n\Delta$ $\delta \le \frac{2m}{n} \le \Delta$

定义 7： $G$ $d_1,d_2,\cdots ,d_n$ $(d_1,d_2,\cdots ,d_n)$ $G$ 的度序列

定理 3： $(d_1,d_2,\cdots ,d_n)$ $\sum d_i$ 为偶数

证明： $(d_1,d_2,\cdots ,d_n)$ $\sum d_i$ 为偶数
$\sum d(i)$ 为偶数，则数组中奇数的个数必为偶数
$G$ $d_i$ $d_i / 2$ $d_j$ $(d_j-1)/2$ 个环
$\sum d_i$ $(d_1,d_2,\cdots ,d_n)$ 是图的度序列

定义 8： $(d_1,d_2,\cdots ,d_n)$ ，若存在一个简单图，以它为度序列，则称这个数组是可图的。可图的序列简称为可图序列或图序列

主要研究 3 个问题

判定问题：什么样的整数数组是可图序列？
计数问题：一个可图序列对应多少不同构的图？
构造问题：如何画出可图序列对应的所有不同构的图？

定理 4 (Havel-Hakimi 定理)： $\Pi=(d_1,d_2,\cdots,d_n)$ $n-1 \ge d_1 \ge d_2 \ge \cdots \ge d_n，\sum d_i = 2m$ $\Pi$ $\Pi_1=(d_2-1,d_3-1,\cdots,d_{d_1+1}-1,d_{d_1+2},\cdots,d_n)$ 是可图的

$\Pi_1$ $\Pi_1$ $n-1$ $\Pi$ $d_1$ $d_1$ $d_2 \sim d_{d_1+1}$ $\Pi_1$ $d_1$ 个数
证明： $d_i$ 非递增排列）
$G$ $\Pi$ $d(v_i)=d_i$
$v_1$ $v_2,v_3,\cdots,v_{d_1+1}$ $v_1$ $\Pi_1$
情形二：（待补充。。。）

例： $\Pi = (5,5,3,3,2,2,2)$ 是否可图？

解：根据定理可得下列非负整数组
$\Pi_1 = (4,2,2,1,1,2)$ $\Pi_1 = (4,2,2,2,1,1)$
$\Pi_2 = (1,1,1,0,1)$
$\Pi_2$ $\Pi = (5,5,3,3,2,2,2)$ 是可图的

度的频序列

定理 5： $G$ $n$ 个点的度不能互不相同

证明： $G$ $\Delta(G) \le n-1$
$G$ $1 \le d(v) \le n-1，\forall v \in V(G)$ $n$ $[1,n-1]$ $n-1$ $n$ 个顶点，故至少存在一个顶点和其他的顶点度数相同
$G$ $G_1$ $G$ $1 \le d(v) \le n-2, \forall v \in V(G_1)$ $G_1$ 中必有两顶点度数相同
$G$ 有两个以上的孤立点，则定理显然成立 -> 存在两个以上度数为 0 的顶点

定义 9： $n$ $G$ $s$ $d_1,d_2,\cdots,d_s$ $d_i$ $b_i$ $\sum b_i = n$ $(b_1,b_2,\cdots,b_s)$ $G$ 的频序列 -> 频序列表示每个度数出现的频率的数组序列

定理 6： $n$ $G$ 和它的补图有相同的频序列

证明： $v$ $G$ $n-1$ $d_G(v) + d_{\overline G}(v) = n-1$
$G$ $b_i$ $d_i$ $b_i$ $G$ $n-1-d_i$
$G$ 与其补图有相同的频序列

子图

定义 10： $G$ $H$ $V(H) \in V(G)，E(H) \in E(G)$ $H$ $G$ $H$ $G$ 子图 $H \in G$ $G$ $H$ 的母图

注意

$G$ $G$ 自身空图 $G$ 的一个子图
$H \in G$ $H \ne G$ $H \subset G$ $H$ $G$ 的真子图
$G$ 生成子图 $V(H) = V(G)$ $H$ -> $H$ $G$ 中的顶点集合相同

定义 11： $V^{'}$ $V$ $V^{'}$ $V^{'}$ $G$ $V^{'}$ $G[V^{'}]$ ；简称为 $G$ 的导出子图 -> 又称 $G$ 的点导出子图

注意

$G-V^{'}$ $G$ $V^{'}$ $V^{'}=\{v\}$ $G-\{v\}$ $G-v$
$G-V^{'} = G[V\setminus V^{'}]$ $G[V\setminus V^{'}] \Leftrightarrow G[V-V^{'}]$

定义 12： $E^{'}$ $E$ $E^{'}$ $E^{'}$ $G$ $E^{'}$ $G[E^{'}]$ ，简称为 $G$ 的边导出子图

注意

$G-E^{'}$ $G$ $E^{'}$ $E^{'}=\{e\}$ $G-\{e\}$ $G-e$
$G-E^{'} \ne G[E\setminus E^{'}]$ $G-E^{'}$ $G[E \setminus E^{'}]$ 多一些点

对比： $G-V^{'} = G[V\setminus V^{'}]$ $G-E^{'} \ne G[E\setminus E^{'}]$
$G-V^{'}$ $G-E^{'}$ 仅删除对应的边，可能会留下一些孤立的点

图的运算

相关术语和概念

$G_1$ $G_2$ 不相交：无公共顶点
$G_1$ $G_2$ 边不重：无公共边
$G_1 \bigcup G_2$ ： $V(G_1) \bigcup V(G_2)$ $E(G_1) \bigcup E(G_2)$ $G$ $G_1$ $G_2$ $G_1+G_2$
$G_1 \bigcap G_2$ ：类似并图的定义，但二者至少要有一个公共顶点
$G_1 - G_2$ ： $G_1$ $G_2$ 中的边组成的图
$G_1 \Delta G_2$ ： $G_1 \Delta G_2 = (G_1 \bigcup G_2) - (G_1 \bigcap G_2) = (G_1-G_2) \bigcup (G_2-G_1)$

定义 13： $G_1$ $G_2$ $G_1+G_2$ $G_1$ $G_2$ $G_1$ $G_2$ 的联图 $G_1 \vee G_2$

$K_m \vee K_n = K_{m+n}$ $K_n$ $n$ 阶完全图

定义 14： $G_1=(V_1,E_1)，G_2=(V_2,E_2)$ $V=V_1 \times V_2$ $u=(u_1,u_2)$ $v = (v_1,v_2)$ $(u_1 = v_1 \ \And\And \ u_2 \ adj \ v_2)$ $(u_2 = v_2 \ \And\And \ u_1 \ adj \ v_1)$ $u$ $v$ $G$ $G_1$ $G_2$ 的积图 $G=G_1 \times G_2$ $u_i \ adj \ v_i$ $u_i$ $v_i$ 邻接

主要理解笛卡尔积，把笛卡尔积的结果中，存在一端相等，另一端相邻的点连接起来
不分前后顺序

定义 15： $G_1=(V_1,E_1)，G_2=(V_2,E_2)$ $V=V_1 \times V_2$ $u=(u_1,u_2)$ $v=(v_1,v_2)$ $(u_1 \ adj \ v_1)$ $(u_1=v_1 \ \And\And \ u_2 \ adj \ v_2)$ $u$ $v$ $G$ $G_1$ $G_2$ 的合成图 $G=G_1[G_2]$

若首端相邻，直接相连起来；若首端相等，第二端相邻，则连接起来
分前后顺序

汇总： $G_1$ $n_1，m_1$ $G_2$ $n_2，m_2$ ，经过联、积、合成三种运算，图的点数和边数为：

运算	点数	边数
$G_1 \vee G_2$	$n_1 + n_2$	$m_1 + m_2 + n_1n_2$
$G_1 \times G_2$	$n_1n_2$	$n_1m_2 + n_2m_1$
$G_1[G_2]$	$n_1n_2$	$n_1m_2 + n^2_2m_1$
$G_2[G_1]$	$n_1n_2$	$n_2m_1 + n^2_1m_2$

定义 16： $G_1$ $G_2$ $G_1$ $G_2$ 的联合 $G_1 \cdot G_2$

途径 & 迹 & 路 & 圈 & 距离 & 直径

定义 17： $G=(V,E)，w=v_0e_1v_1e_2\cdots e_kv_k$ $G$ $v_i \in V，e_i \in E$ $w$ $e_i$ $v_{i-1}$ $v_i$ $w$ $v_0$ $v_k$ 的途径（或通道或通路），简称 $(v_0,v_k)$ 途径

顶点和分别称为的起点和终点，其他点称为内部点，途径中的边数称为它的长度
在简单图中，途径可以简单地由其顶点序列来表示

定义 18：边不重复的途径称为迹；点不重复的迹称为路

定义 19：起点和终点相同的途径、迹和路分别称为闭途径（也称为环游）、闭迹（也称为回路）和圈

途径：边 & 点无要求迹：边不重复路：边 & 点不重复
递进关系：途径 -> 迹 -> 路
闭途径 -> 闭迹 -> 圈
$k$ $k$ 圈 $k$ 奇圈 $k$ 为偶数时称为偶圈。3 圈时常称为三角形。自环是长度为 1 的圈

注意

$u$ $v$ $u$ $v$ $\Longrightarrow$ $\rightarrow$ 路
从途径中删除重复的点和边即变成路
$u$ $u$ $\Longrightarrow$ $\rightarrow$ 圈
从闭迹中删除重复的点即变成圈
$u$ $u$ $\Longrightarrow$ $\nrightarrow$ 圈
闭途径可能存在一种情况，即在重边时无环，但也为闭途径的情况
$u -> v -> u$ ，但是却不存在圈
闭迹刚好避免了上述的情况，所以可以 $\rightarrow$ 圈

定义 20： $u$ $v$ $u$ $v$ 的距离 $d(u,v)$

定义 21： $G$ 的直径 $d(G)=max\{d(u,v) \ | \ u,v \in V\}$

例：完全图的直径是 1

例： $G$ $w_1=v_1v_2v_3，w_2=v_1v_2v_3v_4v_2，w_3=v_1v_2v_3v_2v_3v_4$ ，则:

$w_1$ 是长度为 2 的路
$w_2$ 是长度为 4 的迹
$w_3$ 是长度为 5 的途径
$v_1v_2v_5v_1$ 是长度为 3 的圈
$v_1v_2v_3v_4v_2v_5v_1$ 是长度为 6 的回路
$d(G) = 2$

图的连通性

定义 22： $G$ $u$ $v$ 连通的 $u$ $v$ 间存在途径；否则称 $u$ $v$ 不连通

定义 23： $G$ $G$ 连通图 $G$ 非连通图 $G$ 连通分支 $G$ $G$ 分支数 $w(G)$

例： $w(G)=1$ $w(D) = 3$

例： $n$ $n-1$ $n-1$ ，则至少有一个圈

证明： $G$ 的顶点数作数学归纳
$n=1,2$ $n=k$ 时成立
$n=k+1$ 时，分两种情况讨论
$G$ $2m = \sum d(v) \ge 2n \Rightarrow m > n-1$
$G$ $u$ $G-u$ $G-u$ $n-1$ $G$ $n$ 条边
$G$ 是简单图
$G$ $W_0$ $W_0$ 满足「边数 = 点数 - 1」
$G$ $u$ $W_0$ $W_0$ $v$
$uv$ $W_0$ $W_1$ $W_1$ 也满足「边数 = 点数 - 1」
$W$ $n-1$
$G$ $n-1$ $x$ $y$ $W$ $G$ 中相邻
$xy$ $W$ $x$ $y$ 的路便构成了一个圈

例： $\delta \ge 2$ $G$ 中必然含有圈

证明：只就连通的简单图证明即可！
$W=v_1v_2\cdots v_{k-1}v_k$ $G$ 中的一条最长子路
$\delta \ge 2$ $v_k$ $v_{k-1}$ 的相邻顶点
$W$ $G$ $v_1,v_2,\cdots ,v_{k-2}$ 中之一
$v_m$ $v_mv_{m+1}\cdots v_kv_m$ $G$ 中的一个圈

例： $G$ $m$ $n$ $G$ $\Delta =n-2$ $m \ge 2n - 4$

证明： $d(v) = \Delta = n - 2$ $v$ $v_1,v_2,\cdots,v_{n-2}$ $u$ 是剩下的一个顶点
$d(G)=2$ $u$ $v$ $u$ $v_1,v_2,\cdots,v_{n-2}$ $d(G) > 2$ $\infty$ ）
$u$ $v_1,v_2,\cdots,v_k$ 相邻
$u$ $v_{k+1},\cdots,v_{n-2}$ $v_1,v_2,\cdots,v_k$ $n-2$ 条边
$2n - 4$ 条边

定理 7： $G$ 是不连通的，则其补图是连通图

证明： $G$ $G$ 中至少有两个分支
$u,v$ $G$ 的任意两个顶点
$u$ $v$ $G$ 中不邻接，则在补图中它们邻接
$u$ $v$ $G$ $G$ $w$ $u$ $v$ $w$ $uwv$ $u$ $v$ 连通
$G$ 的补图是连通图

定理 8： $G$ $n$ $G$ $u$ $v$ $d(u) + d(v) \ge n-1$ $G$ $d(G) \le 2$

证明： $G$ $x$ $y$ $x$ $y$ 的路
$x$ $y$ 相邻，则上述论断成立
$x$ $y$ $w$ $x$ $y$ 均相邻
$G$ $n-2$ $k$ $x$ $y$ $l$ $y$ $x$ $m$ $x$ $y$ 均不相邻
$d(x) = k，d(y)=l$
$k+l+m=n-2$ $d(x)+d(y)=n-2-m \le n-2$ $d(u)+d(v) \ge n-1$ 矛盾！！

偶图判断定理

定理 9：一个图是偶图当且仅当它不包含奇圈

证明：一个图是偶图当且仅当每个连通分支是偶图，一个圈只能属于一个连通分支，因此我们只需要对连通图证明即可
$G$ $(X,Y)$ $C=v_0v_1\cdots v_kv_0$ $G$ 的任意一个圈
$v_0 \in X$ $v_{2i} \in X$ $v_{2i+1} \in Y$
$v_0 \in X$ $v_kv_0$ $v_k \in Y$ $C$ 是偶圈 -> 顶点是偶数，故形成边后也是偶数边

充分性 $G$ 是不包含奇圈的连通图
$u$ $V$ $(X,Y)$ 如下：
$X= \{x \ | \ d(u,x) \ is \ even \ , x \in V(G)\}$
$Y= \{y \ | \ d(u,y) \ is \ odd \ , y \in V(G)\}$
$(X,Y)$ 是一个二分类
$X$ $v$ $w$ $v \in X \ and \ (v \ adj \ w)$ $d(u,w)$ 必为奇数
$Y$ $v$ $w$ ，必不相邻！！
$(X,Y)$ $G$ 的一个二分类

赋权图

定义 24： $G$ $e$ $w(e)$ $e$ 权 $G$ 连同它边上的权称为赋权图

$H$ $H$ $H$ 的权 $W(H)$

定义 25： $G$ $u$ $v$ $G$ $u$ $v$ $u$ $v$ 最短路 $u$ $v$ 距离 $d(u,v)$

各边的权均为 1 的赋权图中的路长与非赋权图中的路长是一致的

最短路问题

数学模型： $a$ $b$ $(a,b)$ 路

Dantzig 算法 (顶点标号法)： $(a,b)$ $a$ $G$ 的所有其他顶点的最短路

$a_1=a，t(a_1)=0，A_1=\{a_1\}，T_1=\varnothing$
$A_i=\{a_1,a_2,\cdots,a_i\}$ $1 \le k \le i$ $t(a_k)$ $a_k \in A$ $b^{(i)}_k \in B^{(i)}_k = N(a_k) - A_i$ $l(a_kb^{(i)}_k)=\min \limits_{v \in B^{(i)}_k}l(a_kv)$
$m_i，1 \le m_i \le i$ $b^{(i)}_{m_i}$ $t(a_{m_i}) + l(a_{m_i}b^{(i)}_{m_i})$ $a_{i+1}=b^{(i)}_{m_i}，t(a_{i+1})=t(a_{m_i})+l(a_{m_i}a_{i+1})，T_{i+1}=T_i \cup \{a_{m_i}a_{i+1}\}$
$a_{i+1}=b$ $A_{i+1}=A_i \cup \{a_{i+1}\}$ ，转到第二步

记号说明：

$l(e)：$ $e$ 的权重
$t(a_k)：$ $a_k$ $a_1=a$ $a_k$ 的最短路长度
$A_i=\{a_1,a_2,\cdots,a_i\}：$ 已经标号的顶点集合
$T_i：$ $a_1$ $a_i$ 的最短路上的边所在的集合
$N(a_k)：$ $a_k$ 相邻的所有点的集合，称为 $a_k$ 的邻集

例： $a$ $b$ 的距离

解： $i=1，A_1=\{a\}，t(a)=0，T_1=\varnothing$
$k=1$ $N(a)=\{v_1,v_2,v_3\}，B^{(1)}_1=N(a)-A_1=\{v_1,v_2,v_3\}，\min \limits_{v \in B^{(1)}_1}l(av)=1，b^{(1)}_1=v_3$
$m_1=1，a_2=b^{(1)}_1=v_3，t(v_3)=t(a)+l(av_3)=1，T_2=\{av_3\}$
$i=2，A_2=\{a,v_3\}$
$k=1$ $N(a)=\{v_1,v_2,v_3\}，B^{(2)}_1=N(a)-A_2=\{v_1,v_2\}，\min \limits_{v \in B^{(2)}_1}l(av)=1，b^{(2)}_1=v_1$
$k=2$ $N(v_3)=\{a,v_2,v_6\}，B^{(2)}_2=N(v_3)-A_2=\{v_2,v_6\}，\min \limits_{v \in B^{(2)}_2}l(v_3v)=7，b^{(2)}_2=v_2$
$m_2=1，a_3=b^{(2)}_1=v_1，t(v_1)=t(a)+l(a,v_1)=2，T_3=T_2 \cup \{a_1a_3\}=\{av_3,av_1\}$
$i=3，A_3=\{a,v_3,v_1\}$
$k=1$ $N(a)=\{v_1,v_2,v_3\}，B^{(3)}_1=N(a)-A_3=\{v_2\}，\min \limits_{v \in B^{(3)}_1}l(av)=8，b^{(3)}_1=v_2$
$k=2$ $N(v_3)=\{a,v_2,v_6\}，B^{(3)}_2=N(v_3)-A_3=\{v_2,v_6\}，\min \limits_{v \in B^{(3)}_2}l(v_3v)=7，b^{(3)}_2=v_2$
$k=3$ $N(v_1)=\{a,v_2,v_4\}，B^{(3)}_3=N(v_1)-A_3=\{v_2,v_4\}，\min \limits_{v \in B^{(3)}_3}l(v_1v)=1，b^{(3)}_3=v_4$
$m_3=3，a_4=b^{(3)}_3=v_4，t(v_4)=t(v_1)+l(v_1,v_4)=3，T_4=T_3\cup\{v_1v_4\}=\{av_3,av_1,v_1v_4\}$
$i=4，A_4=\{a,v_3,v_1,v_4\}$
$k=1$ $N(a)=\{v_1,v_2,v_3\}，B^{(4)}_1=N(a)-A_4=\{v_2\}，\min \limits_{v \in B^{(4)}_1}l(av)=8，b^{(4)}_1=v_2$
$k=2$ $N(v_3)=\{a,v_2,v_6\}，B^{(4)}_2=N(v_3)-A_4=\{v_2,v_6\}，\min \limits_{v \in B^{(4)}_2}l(v_3v)=7，b^{(4)}_2=v_2$
$k=3$ $N(v_1)=\{a,v_2,v_4\}，B^{(4)}_3=N(v_1)-A_4=\{v_2\}，\min \limits_{v \in B^{(4)}_3}l(v_1v)=6，b^{(4)}_3=v_2$
$k=4$ $N(v_4)=\{v_1,v_2,v_5,b\}，B^{(4)}_4=N(v_4)-A_4=\{v_2,v_5,b\}，\min \limits_{v \in B^{(4)}_4}l(v_4v)=3，b^{(4)}_4=v_5$
$m_4=4，a_5=b^{(4)}_4=v_5，t(v_5)=t(v_4)+l(v_4,v_5)=6，T_5=T_4\cup\{v_4v_5\}=\{av_3,av_1,v_1v_4,v_4v_5\}$
$i=5，A_5=\{a,v_3,v_1,v_4,v_5\}$
$b^{(5)}_1=v_2，b^{(5)}_2=v_2，b^{(5)}_3=v_2，b^{(5)}_4=v_2，b^{(5)}_5=v_2$
$m_5=4，a_6=b^{(5)}_4=v_2，t(v_2)=t(v_4)+l(v_4,v_2)=7，T_6=T_5\cup\{v_4v_2\}=\{av_3,av_1,v_1v_4,v_4v_5,v_4v_2\}$
$i=6，A_6=\{a,v_3,v_1,v_4,v_5,v_2\}$
$b^{(6)}_1=\varnothing，b^{(6)}_2=v_6，b^{(6)}_3=\varnothing，b^{(6)}_4=b，b^{(6)}_5=v_6，b^{(6)}_6=v_6$
$m_6=6，a_7=b^{(6)}_6=v_6，t(v_6)=t(v_2)+l(v_2,v_6)=9，T_7=T_6\cup\{v_2v_6\}=\{av_3,av_1,v_1v_4,v_4v_5,v_4v_2,v_2v_6\}$
$i=7，A_7=\{a,v_3,v_1,v_4,v_5,v_2,v_6\}$
$b^{(7)}_1=\varnothing，b^{(7)}_2=\varnothing，b^{(7)}_3=\varnothing，b^{(7)}_4=b，b^{(7)}_5=b，b^{(7)}_6=\varnothing，b^{(7)}_7=b$
$m_7=7，a_8=b^{(7)}_7=b，t(b)=t(v_6)+l(v_6,b)=11，T_8=T_7\cup \{v_6b\}=\{av_3,av_1,v_1v_4,v_4v_5,v_4v_2,v_2v_6,v_6b\}$
$a$ $b$ $d(a,b)=t(b)=11$ $a \rightarrow v_1 \rightarrow v_4 \rightarrow v_6 \rightarrow b$

邻接矩阵

定义 26： $n$ $G=(V,E)，V=\{v_1,v_2,\cdots,v_n\}$ $G$ 邻接矩阵 $n \times n$ $A(G)=[a_{ij}]$ $A$ $v_i$ $v_j$ $a_{ij}=1$ $a_{ij}=0$

注： $a_{ij}$ $v_i$ $v_j$ $A$ 为 推广的邻接矩阵

邻接矩阵的性质

邻接矩阵是一个对称方阵
简单标定图的领结矩阵的各行(列)元素之和是该行(列)对应的点的度
$A_1$ $A_2$ $A_1$ $A_2$ $P$ $A_1=P^{-1}A_2P$
$G$ $G$ 的点的一种标定法使它的邻接矩阵有约化的形式
$\begin{matrix} A = (\begin{matrix} A_{11} & 0 \\ 0 & A_{22} \end{matrix}) \end{matrix}$

例：

\begin{matrix} A = (\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{matrix}) A^{2} = (\begin{matrix} 1 & 0 & 2 & 0 \\ 0 & 5 & 0 & 2 \\ 2 & 0 & 5 & 1 \\ 0 & 2 & 1 & 2 \end{matrix}) \end{matrix}

$v_1$ $v_1$ 的长为 2 的途径的数目为 1
$v_1$ $v_2$ 的长为 2 的途径的数目为 0
$v_1$ $v_3$ 的长为 2 的途径的数目为 2
$v_1$ $v_4$ 的长为 2 的途径的数目为 0
$v_2$ $v_2$ 的长为 2 的途径的数目为 5

定理 10： $G$ $A$ $p$ $A^n$ $i$ $j$ $a^{(n)}_{ij}$ $v_i$ $v_j$ $n$ 的途径的数目

证明：

推论： $A$ $G$ 的邻接矩阵，则：

$A^2$ $a^{(2)}_{ii}$ $v_i$ $A^3$ $a^{(3)}_{ii}$ $v_i$ 的三角形的数目的两倍
$G$ $i \neq j$ $v_i$ $v_j$ $A^n$ $a^{(n)}_{ij} \neq 0$ $n$

关联矩阵

定义 27： $G$ 关联矩阵 $B(G)=[b_{ij}]$ $B$ $n \times m$ $v_i$ $e_j$ $b_{ij}=1$ $b_{ij}=0$

关联矩阵的每列和为 2；其每行的和为对应顶点的度数

邻接谱

定义 28： $G$ $A(G)$ $f_{\lambda}(G)=|\lambda I - A(G)|=\lambda ^n + a_1\lambda^{n-1} + a_2\lambda^{n-2} + \cdots + a_{n-1}\lambda + a_n$ ，称为 $G$ 的特征多项式

定义 29： $G$ 的特征多项式的特征值及其重数，称为 $G$ 的邻接谱谱 $Spec(G)$

例： $K_n$ 的谱

解： $K_n$ 的邻接矩阵为：
$\begin{matrix} A (K_{n}) = (\begin{matrix} 0 & 1 & \dots & 1 \\ 1 & 0 & \dots & 1 \\ ⋱ \\ 1 & 1 & \dots & 0 \end{matrix}) \end{matrix}$
计算得：
$\begin{matrix} | λ I - A (K_{n}) | = | \begin{matrix} λ & - 1 & \dots & - 1 \\ - 1 & λ & \dots & - 1 \\ ⋱ \\ - 1 & - 1 & \dots & λ \end{matrix} | = (λ - n + 1) (λ + 1)^{n - 1} \end{matrix}$
因此：
$\begin{matrix} S p e c (K_{n}) = (\begin{matrix} - 1 & n - 1 \\ n - 1 & 1 \end{matrix}) \end{matrix}$
小笔记：
$| \begin{matrix} λ & - 1 & \dots & - 1 \\ - 1 & λ & \dots & - 1 \\ ⋱ \\ - 1 & - 1 & \dots & λ \end{matrix} | = | \begin{matrix} λ - (n - 1) & λ - (n - 1) & \dots & λ - (n - 1) \\ - 1 & λ & \dots & - 1 \\ ⋱ \\ - 1 & - 1 & \dots & λ \end{matrix} |$ $\begin{matrix} = (λ - n + 1) | \begin{matrix} 1 & 1 & \dots & 1 \\ - 1 & λ & \dots & - 1 \\ ⋱ \\ - 1 & - 1 & \dots & λ \end{matrix} | = (λ - n + 1) | \begin{matrix} 1 & 1 & \dots & 1 \\ 0 & λ + 1 & \dots & 0 \\ ⋱ \\ 0 & 0 & \dots & λ + 1 \end{matrix} | = (λ - n + 1) (λ + 1)^{n - 1} \end{matrix}$
$(\lambda - n + 1)(\lambda + 1) ^{n-1} = 0$ $\lambda$ 的取值
$\lambda$ 不同值出现的次数
$Spec(K_n)$ ：第一行是特征值；第二行是重数

例：若两个非同构的图具有相同的谱，则称它们是同谱图。求证：下面两图是同谱图

解： $G$ $H$ 显然不同构
$f_{\lambda}(G)=f_{\lambda}(H)=\lambda^6-7\lambda^4-4\lambda^3+7\lambda^2+4\lambda-1$
$G$ $H$ 是同谱图
？？？？？？？？？？？？？？？？？？？？

例： $G=(n,m)$ $Spec(K_n) = \begin{pmatrix} \lambda_1 & \lambda_2 & \cdots & \lambda_s \\ m_1 & m_2 & \cdots & m_s \end{pmatrix}$ $\sum \limits^s_{i=1}m_i\lambda^2_i=2m$

证明： $A$ $A^2$ $\sum \limits^s_{i=1}m_i\lambda^2_{i}=\sum \limits^n_{i=1}a^{(2)}_{ii}$
$A^2$ $\sum \limits^n_{i=1}a^{(2)}_{ii}=\sum \limits^n_{i=1}d(v_i)=2m$
$\sum \limits^s_{i=1}m_i\lambda^2_i=2m$

例： $\lambda$ $G=(n,m)$ $|\lambda| \le \sqrt{\frac{2m(n-1)}{n} }$

证明：

图的邻接代数

定义 30： $A$ $G$ $\Lambda(G)=\{a_0I+a_1A+\cdots+a_kA^k\} \ | \ a_i \in C,k\in N$ $C$ 上的向量空间，称该空间为 $G$ 的邻接代数

$n$ $n-1$ $n$ $n$
$n$ $n$ $K_n$ 的直径显然为 1，不同特征值的个数恰好为 2

定理 11： $G$ $n$ $d(G) + 1 \le \dim \Lambda(G) \le n$

证明：

定理 12： $G$ $n$ $A(G)$ $s$ $d(G) + 1 \le s \le n$

证明：

图空间 (几乎不考)

$m$ $2^m$

$G_1,G_2,\cdots,G_N \ (N=2^m)$ $G$ 的全部生成子图

定理 13： $M=\{G_1,G_2,\cdots,G_N\}$ $\Delta$ $0 \cdot G_i = \varnothing，1 \cdot G_i=G_i$ $F=\{0,1\}$ $m$ 维向量空间

l 部图的概念与特征

定义 31： $G$ $V$ $V = \bigcup \limits^l_{i=1}，V_i \cap V_j = \varnothing，i \neq j$ $V_i$ $V_i$ $G$ 是一个 $l$ 部图

$l=2$ $G$ 就是偶图
$n$ $n$ 部图
$l_1 < l_2 \le n$ $l_1$ $l_2$ 部图

例：

定义 32： $l$ $G$ $|V_i|=n_i$ $u \in V_i，v \in V_j，i \neq j，i,j=1,2,\cdots,l$ $G$ $l$ 部图 $G=K_{n_1,n_2,\cdots,n_l}$

$l$ $K_{n_1,n_2,\cdots,n_l}=\overline{K_{n_1}} \vee \overline{K_{n_2}} \vee \cdots \vee \overline{K_{n_l}}$
$l$ $K_{n_1,n_2,\cdots,n_l}$ $\sum \limits^l_{i=1} n_i$ $\sum \limits_{1\le i < j < \le l} n_in_j$
任意部的点和其他部的所有点均相连

例：

定义 33： $n$ $l$ $G$ $n=kl+r \ (0 \le r < l) \ |V_1|=|V_2|=\cdots = |V_r|=k+1，|V_{r+1}|=|V_{r+2}|=\cdots =|V_l| = k$ $G$ $n$ $l$ 几乎等部图 $T_{l,n}$

$|V_1|=|V_2|=\cdots =|V_l|$ $l$ 几乎等部图称为 $l$ 等部图

$V$ $V_1=\{v_4\}，V_2=\{v_3,v_5\}，V_3=\{v_1,v_2,v_6\}$
$V$ $V_1=\{v_1,v_5\}，V_2=\{v_2,v_3\}，V_3=\{v_4,v_6\}$
$V_1=\{v_2,v_4,v_6\}，V_2=\{v_1,v_3,v_5\}$ ，且划分唯一

定理 14：连通偶图的 2 部划分是唯一的

证明：

定理 15： $n$ $K_{n_1,n_2}$ $m=n_1n_2$ $m \le \lfloor n^2/4 \rfloor$

证明：

定理 16： $n$ $l$ $G$ $G \cong T_{l,n}$

证明：

Turán 定理

定义 34： $G$ $H$ $n$ $G$ $H$ $\mu : V(G) \rightarrow V(H)$ $v \in V(G)$ $d_G(v) \le d_H(\mu (v))$

$G$ $H$ $m(G) \le m(H)$ 。但逆命题不成立。
例：（1，1，2，4）与（3，3，3，3）没有度弱关系！

定理 17： $n$ $G$ $K_{l+1}$ $G$ $l$ $H$ $G$ $H$ $G \cong H$

定理 18 (Turán)： $G$ $n$ $K_{l+1}$ $m(G) \le m(T_{l,n})$ $G \cong T_{l,n}$ $m(G)=m(T_{l,n})$

$K_{l+1} \notin G$ $m(T_{l,n}) = C^2_l (n/l)^2$

例： $n$ $G$ $K_3 \notin G$ $G$ $n^2/4$ 条边

$m(G) \le m(T_{2,n}) = C^2_2(n/2)^2 = (n/2)^2$

例： $G$ $K_4 \notin G$ $G$ 最多有 27 条边

$m(G) \le m(T_{3,9}) = C^2_3(9/3)^2 = 3 \times (9/3)^2 = 27$

Turán 定理应用

工兵排雷问题： $n$ $g$ $h$ 米。问：在任意的两个人之间均能保持联系的条件下，若发生意外，平均伤亡人数最低的可能值为多少？

定理 19： $A=\{x_1,x_2,\cdots,x_n\}$ $A$ $\sqrt{2}/2$ $\lfloor n^3/3 \rfloor$ $n$ $A^* =\{x_1,x_2,\cdots,x_n\}$ $\lfloor n^2/3 \rfloor$ $\sqrt{2}/2$

第二章树

树的概念

定义 35：不含圈的图称为无圈图树 $T$ 表示

平凡图称为平凡树

定义 36：无圈图称为森林

注意

树与森林都是简单图
树与森林都是偶图 -> 定理 9
在一棵树中，度数为 1 的顶点称为树叶，度数大于 1 的顶点称为分支点

树的性质

定理 20：每棵非平凡树至少有两片树叶

定理 21： $G$ $n$ $m$ 条边的图，则下列命题等价：

$G$ 是树
$G$ 无环且任意两个不同点之间存在唯一的路
$G$ 连通，删去任一边便不连通
$G$ $n=m+1$
$G$ $n=m+1$
$G$ 无圈，添加任何一条边可得唯一的圈

注意

树是含有边数最少的连通图，因此树也被称为最小连通图
树是含有边数最多的无圈图

推论： $(n,m)$ $G$ $k$ $m=n-k$

证明： $G$ $n_i$ $m_i \ (1 \le i \le k)$
$m_i=n_i-1，i=1,2,\cdots,k$
$m=\sum \limits^k_{i=1}m_i=\sum \limits^k_{i=1}(n_i-1)=n-k$

例： $G$ $\Delta$ $G$ $\Delta$ 片叶子

证明： $G$ $n$ $m$ $\Delta -1$ 片叶子
$2m=\sum (d(v) \ge 1 \cdot(\Delta - 1) + 2\cdot(n-\Delta) + \Delta \cdot1 = 2n-1 > 2n-2)$
$m > n-1$ $G$ 是树矛盾！

例： $T$ $T$ $T$ 有多少片树叶？

解： $T$ $x$ $T$ 有 13 个顶点
$1 \times x + 2 \times 3 + 5 \times (13-3-x)=2 \times 12$
$x=8$ $T$ 有 8 片树叶

练习： $T$ $i$ $n_i \ (1 \le i \le k)$ $n_1=2 + n_3 + 2n_4 + \cdots + (k-2)n_k$

证明：

例： $G$ $2k$ $G$ $k$ $P_1,P_2,\cdots,P_k$ $E(G)=E(P_1)\bigcup E(P_2)\bigcup \cdots \bigcup E(P_k)$

证明：

例： $(d_1,d_2,\cdots,d_n)$ $\sum d_i=2(n-1)$

证明：

例： $T$ $k$ $G$ $\delta(G) \ge k-1$ $T$ $G$ 的某个子图

证明： $k$ 作归纳证明

树的中心

定义 37： $G=(V,E)$ $v \in V$ $e(v) = \max\{d(u,v) \ | \ u \in V\}$ $e(v)$ $v$ 的离心率 $r(G)=\min\{e(v) \ | \ v \in V\}$ $r(G)$ 为 $G$ 的半径

$G$ $G$ 的最大离心率

定义 38： $v$ $e(v)=r(G)$ $v$ $G$ 中心点 $G$ $G$ 的中心

例： $u$ $r(G)=4$ $d(G)=8$ $u$

定理 22：每棵树的中心由一个点或两个相邻点组成

证明： $T$ $n$ 作归纳证明
$n=1$ $n=2$ 时，结论显然成立
...

树的形心

定义 39： $T$ $u$ $T$ $T$ $u$ 分枝 $u$ 分枝数 $T$ $u$ $u$ 的权 $T$ 中权值最小的点形心点 $T$ 的形心

注：树的形心好比物体的重心

例：在右图树中，每个顶点处的数字表示该顶点的权值，权值为 4 的顶点为该树的形心

定理 23：

$n$ $T$ 的形心由一个点或两个相邻点组成
$T$ $n/2$
$T$ $n/2$

证明：

生成树的概念 & 性质

定义 40： $G$ $T$ $T$ $G$ 生成树 $T$ $G$ 生成森林 $G$ 中非生成树的边称为弦

例：

定理 24：每个连通图至少包含一颗生成树

推论： $G$ $(n,m)$ $m \ge n-1$

$m = n - 1$
$m \ge n-1$

生成树的计数

$K_6$ $6^{6-2}=1296$ 棵生成树，而不同构的 6 阶树仅 6 棵

定义 41： $G$ $e$ 被收缩 $e$ $G\cdot e$

注： $|V(G\cdot e)| =|V(G)-1|$ $|E(G\cdot e)| =|E(G)-1|$ $|\omega (G\cdot e)| =\omega (G)$ $\omega (G)$ -> 团数
$T$ $T \cdot e$ 也是树

例： $(b)$ $(a)$ $e_1,e_2,e_3,e_4,e_5$ 后得到的图

$\tau (G)$ $G$ 的生成树的个数

定理 25 (Cayley)： $e$ $G$ $\tau(G)=\tau(G-e)+\tau(G\cdot e)$

证明： $G$ $e$ $G-e$ 的生成树
$\tau (G-e)$ $G$ $e$ 的生成树的个数
$\tau(G\cdot e)$ $G$ $e$ 的生成树的个数
$e$ $e$

例： $G$ $\tau (G)$

解：
$\tau(G)=4+4=8$

定理 26 (矩阵树定理)： $G$ $V=\{v_1,v_2,\cdots,v_n\}$ $A=(a_{ij})$ $G$ $C=(c_{ij})$ $n$ 阶方阵，其中：

\begin{matrix} c_{i j} = {\begin{matrix} d (v_{i}) & i = j \\ - a_{i j} & i \neq j \end{matrix} \end{matrix}

$G$ $C$ 的任意一个余子式的值

例： $G$ $\tau (G)$

解：
$\begin{matrix} C = [\begin{matrix} 3 & - 1 & - 1 & - 1 \\ - 1 & 2 & - 1 & 0 \\ - 1 & - 1 & 3 & - 1 \\ - 1 & 0 & - 1 & 2 \end{matrix}] \end{matrix}$
$C$ $i$ $i$ $C_i$ ，则：
$\begin{matrix} C_{1} = [\begin{matrix} 2 & - 1 & 0 \\ - 1 & 3 & - 1 \\ 0 & - 1 & 2 \end{matrix}] \end{matrix}$
所以：
$\begin{matrix} τ (G) = | G_{1} | = [\begin{matrix} 2 & - 1 & 0 \\ - 1 & 3 & - 1 \\ 0 & - 1 & 2 \end{matrix}] = 12 - 2 - 2 = 8 \end{matrix}$

定理 27： $\tau(K_n)=n^{n-2}$

证明一：显然
$\begin{matrix} C = [\begin{matrix} n - 1 & - 1 & \dots & - 1 \\ - 1 & n - 1 & \dots & - 1 \\ \dots & \dots & \dots & \dots \\ - 1 & - 1 & \dots & n - 1 \end{matrix}] \end{matrix}$
$C$ $i$ $i$ $C_i$ ，则：
$\begin{matrix} C_{i} = {[\begin{matrix} n - 1 & - 1 & \dots & - 1 \\ - 1 & n - 1 & \dots & - 1 \\ \dots & \dots & \dots & \dots \\ - 1 & - 1 & \dots & n - 1 \end{matrix}]}_{(n - 1) \times (n - 1)} \end{matrix}$
所以
$\begin{matrix} τ (K_{n}) = {| \begin{matrix} n - 1 & - 1 & \dots & - 1 \\ - 1 & n - 1 & \dots & - 1 \\ \dots & \dots & \dots & \dots \\ - 1 & - 1 & \dots & n - 1 \end{matrix} |}_{(n - 1) \times (n - 1)} = | \begin{matrix} 1 & 1 & \dots & 1 \\ - 1 & n - 1 & \dots & - 1 \\ \dots & \dots & \dots & \dots \\ - 1 & - 1 & \dots & n - 1 \end{matrix} | = {| \begin{matrix} 1 & 1 & \dots & 1 \\ 0 & n & \dots & 0 \\ \dots & \dots & \dots & \dots \\ 0 & 0 & \dots & n \end{matrix} |}_{(n - 1) \times (n - 1)} = n^{n - 2} \end{matrix}$
证明二： $K_n$ $N=\{1,2,\cdots,n\}$
$N$ $n-2$ $n^{n-2}$
$K_n$ 的生成树的集合与这种序列的集合之间建立一一对应
$T$ $K_n$ $s_1$ $T$ $s_1$ $t_1$
$T$ $s_1$ $s_2$ $T-s_1$ $s_2$ $t_2$
$t_{n-2}$
很容易看出，最后剩下一条边
上述逆过程：
$T$ $v$ $(t_1,t_2,\cdots,t_{n-2})$ $d_T(v)-1$ $T$ $1$ 度顶点恰好是在该序列中未出现的那些顶点
$N$ $T$ $t_i$ $N$ $T$ $t_i$
$n-2$ $T$ 为空
$N$ 中剩余的两个顶点

回路系统简介

定义 42： $T$ $G=(V,E)$ $m$ $n$ $G$ $e_1,e_2,\cdots,e_{m-n+1}$ $T$ $C_r$ $T$ $e_r$ $(r=1,2,\cdots,m-n+1)$ $C_r$ $e_r$ 基本回路 $\{C_1,C_2,\cdots,C_{m-n+1}\}$ $T$ 的基本回路系统

例： $T$ $G$ 的一棵生成树，求所有基本回路

解：基本回路为：

定理 28： $G$ 的任一回路均可表示成若干个基本回路的对称差 -> 对称差 click

Kruskal 算法

定义 43： $G$ $G$ 的最小生成树

注：最小生成树不一定是唯一的

Kruskal 算法

$e_1$ 使得其权值最小
$e_1,e_2,\cdots,e_k$ $E-\{e_1,e_2,\cdots,e_k\}$ $e_{k+1}$ ，使得：
- $G[e_1,e_2,\cdots,e_{k+1}]$ 为无圈图
- $e_{k+1}$ 的权值尽可能小
当步骤 2 不能进行时，停止

例： $G$ 的最小生成树

解： $T$ $W(T)=1+1+2+3+4+5=16$

破圈法

$G$ 的任意圈开始，去掉该圈中权值最大的一条边，称之为破圈
$G$ 中没有圈为止
$G$ $G$ 的最小生成树

例： $G$ 最小生成树

解：过程如图所示

Prim 算法

$G$ $u$ $u$ 关联的且权值最小的边作为最小生成树的第一条边
在与一条已经选取的边只有一个公共端点的所有边中，选择权值最小的边
重复步骤 2 直至得到一棵生成树

例：用 Pirm 算法求下图的最小生成树

解：过程如图所示

第三章图的连通度

割边及其性质

定义 44： $e$ $\omega (G-e) > \omega (G)$ $e$ $G$ 的割边

$G$ $G$ 不连通的边，故非平凡树的每条边均为割边

例： $e_1$ $e_2$ 为割边，而其余边均不为割边

定理 29： $e$ $G$ $e$ $G$ 的任何圈中

证明： $G$ $e$ $G$ $G$ 连通
必要性： $e=uv$ $G$ $e$ $C$ $P=C-e$ $P$ $G-e$ $(u,v)$ 路
$G-e$ $x$ $y$ $G$ $G$ $(x,y)$ $\varGamma$
$\varGamma$ $e$ $\varGamma$ $G-e$ $(x,y)$ 路
$\varGamma$ $e$ $P$ $e$ $G-e$ $(x,y)$ $G-e$ $e$ $e$ $G$ 的任何圈中
充分性： $e=uv$ $e$ $G$ $G-e$ $G-e$ $(u,v)$ $P$ $P+e$ $G$ $e$ $e$ $G$ 的任何圈中” 矛盾！
$e$ $G$ 的割边

注：以上定理表明圈中的边一定不是割边，所以删去圈中的边不会破坏图的连通性

推论： $e$ $G$ $e$ $G$ $G-e$ 仍连通

例：求证：

$G$ $G$ 没有割边
$G$ $k$ $(k \ge 2)$ $G$ 无割边

证明： $e=uv$ $G$ 的割边
$G-e$ $u \ or \ v$ $u \ or \ v$ 的度数必为奇数，而其余点的度数为偶数，与 “度数为奇数的顶点的个数为偶数” 矛盾！

$e=uv$ $G$ 的割边
$G_1$ $G-e$ $u$ $G_1$ $u$ $k-1$ $k$
$G_1$ $S$ $T$ $|S|=s，|T|=t$
$S$ $u$ $ks-1=|E(G_1)|=kt$
$k\ge 2$ $e$ 一定不是割边
$k(s-t)=1$ $s-t$ $k \ge 2$
故等式不可能成立

割点及其性质

定义 45： $G=(V,E)$ $v$ 割点 $E$ $E_1$ $E_2$ $G[E_1]$ $G[E_2]$ $v$

注意

$\omega (G-v) > \omega (G)$ $v$ $G$ 的割点
$G$ $v$ $G$ $\omega (G-v) > \omega (G)$
$G$ $G$ 不连通的点
$K_2$ ）
$\nRightarrow$ $K_2$ ）
$\nRightarrow$ 有割边（八字形的图）
$\ge 3$ $\Rightarrow$ 有割点
$\ge 3$ $\nRightarrow$ 有割边

例： $u_1,u_2,u_3,u_4$ 是割点，其余点均不为割点

定理 30： $v$ $G$ $v$ $G$ $d(v)>1$

证明：必要性： $d(v)=1$ $v$ 是树叶，显然不可能是割点
充分性： $v$ 的度数大于 1
$x$ $y$ $v$ $x$ $y$ $G-v$ $x$ $y$ $v$ 是割点

定理 31： $v$ $G$ $v$ $G$ $V(G-v)$ $V_1$ $V_2$ $x \in V_1，y \in V_2$ $v$ $(x,y)$ 路上

证明：

例：求证：无环非平凡连通图至少有两个点不是割点

证明： $G$ 是无环非平凡连通图，所以存在非平凡生成树。
非平凡生成树至少两片树叶，它们不能为生成树的割点
$G$ 的割点

例：求证：恰有两个非割点的连通简单图是一条路

证明： $T$ $n$ $G$ 的任意一棵生成树
$G$ $n-2$ $T$ $n-2$ $T$ $T$ 是一条路
$G$ 的任意生成树为路
一个简单图的任意生成树为路，则该图为圈或路
$G$ $G$ 为路

例： $v$ $G$ $v$ $G$ 的补图的割点

证明： $\overline G -v =\overline{G-v}$
$v$ $G$ $G-v$ $G-v$ 的补图是连通图
$G$ $v$ 不会增加图的连通分支数
$v$ $G$ 的补图的割点

块及其性质

定义 46：没有割点的连通图称为块图块 $G$ $B$ $G$ $B$ $B$ $G$ 的块

注意

仅有一个点的块，要么是孤立点，要么是环
仅有一条边的块，要么是割边，要么是环
至少有两个点的块无环
至少有三个点的块无环、无割边

例： $G$ $(a)$ $G$ $(b)$ 所示

定理 32： $G$ $3$ $G$ $G$ 无环并且任意两点都位于同一个圈上

证明：充分性： $G$ 显然连通
$v$ $x$ $y$ $v$ 之外的任意两点
$x$ $y$ $x$ $y$ 之间至少有两条不相交的路
$v$ $x$ $y$ $v$ 不是割点
$G$ $G$ 是块
？？？？？？？？？？？？？？？？？？？

推论： $G$ $3$ $G$ $G$ 无孤立点且任意两条边都在同一个圈上

证明：

定理 33： $v$ $G$ $v$ $G$ 的两个不同的块

证明：必要性： $v$ $G$ 的割点
$E(G)$ $E_1$ $E_2$ $G[E_1]$ $G[E_2]$ $v$
$B_1$ $B_2$ $G[E_1]$ $G[E_2]$ $v$ $G$ $v$ $G$ 的两个不同块
充分性： $v$ $G$ $B_1$ $B_2$
$B_1$ $B_2$ $v$ 是割点
？？？？？？？？？？？？？？？？？？？？

注：两个不同块的公共顶点只能是割点，即块与块只能由割点相联结，因此可以通过割点搜寻块

定义 47： $G$ $B_1,B_2,\cdots,B_k$ $G$ $v_1,v_2,\cdots,v_t$ $G$ $G$ 块割点树 $bc(G)$ $G$ $uv$ $bc(G)$ $u$ $v$ $G$ 的割点，另一个是该割点联结的块

注意

$bc(G)$ 是一个没有圈的连通图，即为树
$G$ $bc(G)$ 是平凡图
$G$ $bc(G)$ $G$ 的只含一个割点的块

例：

连通度和边连通度

定义 48： $G$ $V^{'}$ $V(G)$ $G-V^{'}$ $V^{'}$ $G$ 顶点割 $k$ $G$ $k$ 顶点割 $G$ 中点数最少的顶点割称为最小点割

注意

$G$ $v$ $G$ $\{v\}$ $G$ 的 1 顶点割
完全图没有顶点割，实际上也只有以完全图为生成子图的图没有顶点割

例： $V_1=\{u\},V_2=\{u,v\},V_3=\{u,v,w\}$ $G_1$ $V_1$ $V_2$ $V_3$ $G_2$ 没有顶点割

定义 49： $n$ $G$ $G$ $G$ $G$ 连通度 $n-1$ $G$ $\kappa(G)$ $\kappa$ $0$

注：连通度也可描述为 “使图不连通或成为平凡图，最少需要删去的点数”

例： $\kappa(K_n)=n-1；\kappa(C_n)=2$ $C_n$ $n$ $n \ge 3$

例：求下列各图的连通度

$\kappa(G_1)=1；\kappa(G_2)=3；\kappa(G_3)=1；\kappa(G_4)=2$

定义 50：至少 $k$ ，则称该图是 $k$ 连通的

注意

$\rightarrow K_2$ 连通度为 1
$G$ $G$ 连通、无割点且至少含有 3 个点
$K_2$ 连通、无割点，但连通度为 1

定义 51： $G$ $G-E^{'}$ $G$ $E^{'}$ $G$ 边割 $k$ 条边的边割称为 $k$ 边割。边数最少的边割称为最小边割

$G$ $e$ $G$ $\{e\}$ $G$ 的 1 边割

定义 52： $G$ $M$ $G$ $|M|$ $G$ 边连通度 $\lambda(G)$ $\lambda$ 。非连通图或平凡图的边连通度定义为 0

注：边连通度也可描述为 “使图不连通或成为平凡图，最少需要删去的边数”

例： $\lambda(K_n)=n-1；\lambda(C_n)=2$ $C_n$ $n$ $n \ge 2$

例：求下列各图的边连通度

$\lambda(G_1)=1；\lambda(G_2)=3；\lambda(G_3)=2；\lambda(G_4)=3$

定义 53：至少 $k$ ，则称该图是 $k$ 边连通的

注意

$\rightarrow K_2$ 边连通度为 1
$G$ $G$ $\rightarrow$ 2 个点的圈
$K_2$ 连通、无割点，但边连通度为 1

连通度的性质

定理 34： $G$ $\kappa (G) \le \lambda (G) \le \delta(G)$

证明： $G$ $\kappa(G)=\lambda(G)=0$ $G$ 为非平凡连通图
$u\in V(G)$ $u$ $G$ $\lambda(G) \le \delta(G)$
$\lambda(G)$ $\kappa(G) \le \lambda(G)$
$\lambda(G)=1$ $\kappa(G)=\lambda(G)=1$
$\lambda(G) < k \ (k \ge 2)$ $G$ $\kappa(G) \le \lambda(G)$ 成立
$G$ $k$ 的任意一个图
$E^{'}$ $G$ $k$ $e \in E^{'}$
$H=G-e$ $\lambda(H)=k-1$ $\kappa(H) \le \lambda(H) = k-1$
$H$ $G$ $\kappa(G)=|V(G)|-1=|V(H)|-1=\kappa(H) \le k-1 < k = \lambda(G)$
$H$ 的任意生成子图均不为完全图
$S$ $H$ $\kappa(H)$ $|S|\le k-1$
$G-S$ $\kappa(G) \le |S| \le k-1 <k =\lambda(G)$
$G-S$ $H-s$ $e$ $G-S$ 的割边
$G-S$ $|V(G)|=|S|+2$
$\kappa(G) \le |V(G)| - 1 = |S| +1 \le k=\lambda(G)$
$G-S$ $G-S$ $v$ $S\cup\{v\}$ $G$ $\kappa(G) \le |S\cup\{v\}| \le k = \lambda(G)$
$\kappa(G) \le \lambda(G)$

例： $\kappa(G) < \lambda(G) < \delta(G)$ $\kappa(G)=1,\lambda(G)=2,\delta(G)=3$

定理 35： $G$ $m$ $n$ $\kappa (G) \le \left \lfloor 2m/n \right \rfloor$

证明： $2m = \sum d(v) \ge n\delta(G) \ge n\kappa(G)$
$\kappa (G) \le \left \lfloor 2m/n \right \rfloor$

例： $n$ $k$ $\left\lceil kn/2 \right\rceil$ 条边

解释： $k$ $\rightarrow \kappa(G)=k$
$m\ge \left\lceil kn/2 \right\rceil$

引理： $G$ $n$ $\delta(G) \ge \left\lfloor n/2 \right\rfloor$ $G$ 必连通

证明： $G$ $G$ $H$ $|V(H)|\le\left\lfloor n/2 \right\rfloor$
$G$ $\Delta(H) \le \left\lfloor n/2 \right\rfloor -1 < \left\lfloor n/2 \right\rfloor$
$\delta(G) \le \delta(H) \le \Delta(H) < \left\lfloor n/2 \right\rfloor$
$G$ 必连通

定理 36： $G$ $n$ $k<n$ $\delta(G) \ge \frac{n+k-2}{2}$ $G$ $k$ 连通的

证明： $G$ $k-1$ $H$ $\delta(H)\ge\delta(G)-(k-1)\ge\frac{n+k-2}{2}-k+1=\frac{n-k}{2}$
$\delta(H)$ $\delta(H) \ge \left\lceil \frac{n-k}{2} \right\rceil=\left\lfloor \frac{n-k+1}{2} \right\rfloor$
$n-k+1$ $H$ $H$ 是连通的
$G$ $k$ 连通的

定理 37： $G$ $n$ $\delta(G) \ge \left\lfloor n/2 \right\rfloor$ $\lambda(G)=\delta(G)$

证明： $G$ 是连通的
$\lambda(G)\neq\delta(G)$ $\lambda(G)<\delta(G)$
$G$ $M$ $|M|=\lambda(G)<\delta(G)$ $G-M$ $G_1$ $G_2$ 所构成
。。。。。。。。。。。。。。。。。

Menger 定理

定义 54： $(x,y)$ 路称为内部不相交独立的 $x$ $y$ 是其公共点

定义 55： $x$ $y$ $G$ $x$ $y$ $G$ $(x,y)$ 路

例： $\{u_1,u_3\}$ $a$ $b$ $\{u_1b,u_2u_3,u_3u_5\}$ $a$ $b$

定理 38：

$x$ $y$ $G$ 不相邻点 $G$ $x$ $y$ $(x,y)$ 路的最大数目
$x$ $y$ $G$ $G$ $x$ $y$ $(x,y)$ 路的最大数目

例： $(u,v)$ $u$ $v$ $\{u_1,u_2\}$ ，包含 2 个顶点

$(u,v)$ $u$ $v$ $\{u_1v,u_2v,u_2u_3\}$ ，包含 3 条边

定理 39：

$G$ $k \ (k\ge2)$ $G$ $k$ 条独立的路
$G$ $k \ (k\ge2)$ $G$ $k$ 条边不重的路

$k$ $\rightarrow$ $k$ 条独立的路」

例： $G$ $k$ $S$ $G$ $k$ $H$ $G$ $w$ $w$ $S$ $H$ $k$ 连通的

证明： $G$ $k$ 个点
$w$ $G$ $S$ $k$ 个点
$H$ $k$ $H$ $k$ 条独立的路
$H$ $k$ $H$ $k$ 连通的

推论： $G$ 是阶树至少为 3 的图，则以下三个命题等价

$G$ 是 2 连通的无环图
$G$ 无环且任意两点都位于同一个圈上
$G$ 无孤立点且任意两条边都在同一个圈上

证明：
$G$ $\Rightarrow$ $G$ 无环且任意两点都位于同一个圈上
$G$ $G$ $P_1$ $P_2$ $P_1$ $P_2$ 构成包含这两个顶点的一个圈

$G$ $\Rightarrow$ $G$ 无孤立点且任意两条边都在同一个圈上
$G$ 中显然没有孤立点
$e_1$ $e_2$ $G$ $e_1$ $e_2$ $u$ $v$ $H$ $H$ 是 2 连通图
$H$ $u$ $v$ $H$ $e_1$ $e_2$ $G$ 的一个圈上

$G$ $\Rightarrow$ $G$ 是 2 连通的无环图
$G$ 显然无环，因为环和任意一条边不在同一个圈上。
$u$ $v$ $G$ $G$ $e_1,e_2$ $u,v$ 相关联
$e_1,e_2$ $u$ $v$ $u$ $v$ $G$ 是 2 连通的

应用

问题：如何构造出在给定可靠性的条件下使成本尽量低的系统？

图论模型： $G$ $G$ $k$ 连通生成子图

注意

$k=1$ ，此问题即为求最小生成树的问题
$k>1$ ，这是一个还未解决的困难问题

$G$ $n$ $k$ $G$ -> click

$H_{k,n}$ 的构造： $V(H_{k,n})=\{0,1,2,\cdots,n-1\}$

$k$ 为偶 $k=2r$ $0$ $1,2,\cdots,r$ $1$ $2,3,\cdots,r+1$ $\cdots$ $n-1$ $0,1,\cdots,r-1$ $H_{4,8}$ 所示
$k=2r+1，n$ 为偶 $H_{2r,n}$ $i$ $(i+n/2)$ $i(i+n/2) \ (0 \le i < n/2)$ $H_{5,8}$ 所示
$k=2r+1，n$ 为奇 $H_{2r,n}$ $0$ $(n-1)/2，(n+1)/2$ $i$ $i+(n+1)/2 \ (1 \le i < (n-1)/2)$ $H_{5,9}$ 所示

图的宽距离和宽直径

问题背景：

分析评价互联网络的性能指标有多个指标，其中包括传输延迟

传输延迟，又称时间延迟，是指信息从信息源传到目的地所需要的时间

如果度量网络的传输延迟？？

信息从信息源到目的地需要经过若干中间站存储和转发
因此，信息传输延迟可以用图的顶点间距离来度量。每条边的长度可以定义为 1
网络的最大通信延迟可以通过图的直径来度量

宽直径：

定义 56： $x$ $y$ $G$ $C_w(x,y)$ $G$ $w$ $(x,y)$ 路构成的路族，称之为 $x-y$ 容器容器 $w$ 宽度 $C_w(x,y)$ 长度 $l(C_w(x,y))$

例： $G$ $u-v$ $C_3(u,v)=\{P_1,P_2,P_3\}$ $l(C_3(u,v))=l(P_3)=4$

定义 57： $x,y \in V(G)$ $x$ $y$ $w$ $x$ $y$ $w$ 宽距离 $d_w(x,y)$ $d_w(x,y)=\min\{l(C_w(u,v)):\forall C_w(u,v)\}$

例： $u$ $v$ $d_3(x,y)=\min\{l(C_3(u,v)):\forall C_3(u,v)\}=3$

定义 58： $G$ $w$ $G$ $w$ $G$ $w$ 宽直径 $d_w(G)$ $d_w(G)=\max\{d_w(x,y)):x,y \in V(G)\}$

注意

1 宽距离就是普通距离，1 宽直径就是普通直径
$G$ $k$ $G$ $k$ $k$ 连通图的 $k$ 宽直径 $k-1$ 宽直径 $\cdots$ ，1 宽直径均存在

例： $n$ $C_n$ $n$ $K_n$ $n\ge 3$

解：
$d_1(C_n)=\left\lfloor n/2 \right\rfloor$
$C_n$ $x$ $y$ $n-1$ $d_2(C_n)=n-1$
$d_1(K_n)=1$
$w \ (2\le w\le n-1)$ $w$ 宽距离为 2
$d_w(K_n)=2 \ (2\le w \le n-1)$

定理 40： $G$ $G$ $d(G)=d_1(G)\le d_2(G)\le\cdots\le d_w(G)$

定理 41： $G$ $n$ $w$ $(w\ge 2)$ $2 \le d_w(G) \le n-w+1$ ，而且上界和下界都能达到

第四章 Euler 图 & Hamilton 图

欧拉图

定义 59： $G$ $Euler$ (闭)迹 $Euler$ $Euler$ 图 $E$ $Euler$ 闭迹又称为 $Euler$ 回路

注意

闭迹的起点和终点必须相同
若能遍历完所有的边但是没法回到起始点，称为非欧拉图但是有 $Euler$ 迹

例： $a,b$ $c,d$ $e,f$ 不是欧拉图，也无欧拉迹

定理 42： $G$ 是一个连通图，则下列命题等价：

$G$ 是欧拉图
$G$ 的每个点的度数是偶数
$G$ 的边集能划分为边不重的圈的并

证明：
$G$ $\Rightarrow$ $G$ 的每个点的度数是偶数
$C$ $G$ $Euler$ 闭迹
$G$ $C$ $G$ $C$ $C$ 中出现的次数的两倍，所以是一个偶数
$G$ $\Rightarrow$ $G$ 的边集能划分为边不重的圈的并
$G$ 的边数归纳证明。
$G$ $G$ 只能是自环，结论显然成立
$G$ $v$
$v$ $v$ 的通路构成一个圈
$G$ 中移去得到的圈，则得到的每个连通分支是一个满足条件，边数较少的图
由归纳假设知，结论显然成立
$G$ $\Rightarrow$ $G$ 是欧拉图
$C_1$ $G$ $G$ 显然是欧拉图
$C_2$ $C_2$ $C_1$ $v$
$v$ $C_1$ $C_2$ 相连组成的通道是含有这两个圈中各条边的一条闭迹
$G$ $G$ 是欧拉图

推论： $G$ $Euler$ $G$ $Euler$ $Euler$ 图）

证明： $G$ $Euler$ 闭 $G$ 有零个奇点
$G$ $Euler$ $C$ $u$ $v$ $C$ 的起点和终点
$C$ $u$ $v$ $e$ $C+e$
$C+e$ $Euler$ $C+e$ $C$ $G$ 仅有两个奇点
$G$ $u$ $v$ 的连通图
$u$ $v$ $e$ $G+e$ $G+e$ 没有奇点
$G+e$ $Euler$ $G$ $Euler$ 迹
综上，结论成立

一笔画问题：画一个图形，在笔不离纸，每条边只画一次而不允许重复的情况下，画完该图

注意

一笔画问题本质就是一个图是否存在 $Euler$ 迹 的问题
$G$ 为欧拉图，则能够一笔画完该图，并且又回到出发点
$G$ 只存在非封闭的欧拉迹，则能够一笔画完该图，但回不到出发点

例：在平台内，右图是否可以在三笔之内画成？

解：假设可以三笔画成，不妨用下图表示：
也就是说，在原图上添加三条边，可使其变成欧拉图
但原图有 8 个度数为奇数的顶点，添加三条边最多可以使 6 个顶点的度数变为偶数
因此，原图不能三笔画成

例： $G$ $2k$ $k$ $Q_1,Q_2,\cdots,Q_k$ $E(G)=E(Q_1)\bigcup E(Q_2) \bigcup \cdots \bigcup E(Q_k)$

证明： $G$ 是连通图进行证明
$v_1,v_2,\cdots,v_k,v_{k+1},\cdots,v_{2k}$ $G$ 的所有奇度点
$v_i$ $v_{i+k}$ $e_i$ $G^* \ (1 \le i \le k)$ $G^*$ 是欧拉图
$G^*$ $C$
$C$ $e_i \ (1 \le i \le k)$ $k$ $Q_i \ (1 \le i \le k)$ $E(G)=E(Q_1)\bigcup E(Q_2)\bigcup \cdots \bigcup E(Q_k)$

思考题：

$n$ $K_n$ 是欧拉图？ $\rightarrow \ \ n$ 为奇数
$n$ $n$ $Q_n$ 是欧拉图？ $\rightarrow \ \ n$ 为偶数
$K_{a,b}$ $a$ $b$ 需满足什么条件？ $\rightarrow \ \ a,b$ 均为偶数

思考题： $G$ $G$ 变为欧拉图，最少需要添加几条边？ $\rightarrow$ 最少需要添加 2 条边

思考题：欧拉图是否存在割边？ $\rightarrow$ 不存在

例：能否将一副多米诺骨牌排成一行，使得对于任意相邻的两块牌，他们的接触面具有相同的点数？

解：存在满足条件的排列方式
$(a,b)$ $0\le a \le b \le 6$ $(3,4)$ 表示骨牌
$0,1,2,\cdots,6$ $K_7$ $G$ 来表示
$G$ $3$ $(3,3)$
$G$ 是否为欧拉图
$G$ $G$ 是欧拉图

Fleury 算法

算法思想： 从任一点出发按以下方法来描画一条边不重复的迹，使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画

Fleury 算法

$v_0$ $w_0=v_0$
$w_i=v_0e_1v_1\cdots e_iv_i$ $E|\{e_1,e_2,\cdots,e_i\}$ $e_{i+1}$ ：使
- $e_{i+1}$ $v_i$ 相关联
- 除非没有别的边可选择 $e_{i+1}$ $G-\{e_1,e_2,\cdots,e_i\}$ 的割边
当第 2 步不能再执行时，算法停止

例： $e$ $g$ $g$ $e$ $g$ 处离开的路线

解： $e$ $g$ $e$ $g$ 的欧拉迹
$G$ $e$ $g$ $e$ $g$ $m$ ，如图所示
$e\ g\ c\ f\ a\ b\ c\ h\ b\ d\ h\ g\ d\ j\ i\ e\ j\ g \$ $m\$ $e$ $e\ g\ c\ f\ a\ b\ c\ h\ b\ d\ h\ g\ d\ j\ i\ e\ j\ g$

中国邮递员问题

问题描述：邮递员从邮局出发，递送邮件，然后返回邮局，要求辖区每条街至少走一遍且走过的总路程最短，应如何选择路线？

图论模型： $G$ 中找到一条包含每条边（允许重复）且边权之和最小的闭途径，称之为最优环游

注意

$G$ $G$ 的欧拉回路即可
$G$ $G^*$ $G^*$ 的欧拉回路

定理 43： $G^*$ $G$ $G^*$ 具有最小权值的充要条件是：

$G$ 的每一条边最多被添加一次
$G^*$ 的每个圈来说，该圈新添加的边的总权值不超过该圈总权值的一半

证明：必要性
$G$ $G^*$ $G$ 为生成子图的欧拉图
$G^*$ 总权值最小” 相矛盾，因此每条边最多被添加一次
$G^*$ $C$
$G^*$ $C$ 上新添加的边全部去掉，然后将原圈未添加新边的边都添加一条重复边
$G^*$ 总权值最小” 相矛盾

充分性：我们将证明「满足条件的任何两个图都具有相同的总权值」
$Y_1$ $Y_2$ $G_1$ $G_2$ 中添加的边的集合
$G_1$ $G_2$ $Y_1 \setminus Y_2$ $Y_2 \setminus Y_1$ 的权值
$Y=(Y_1\setminus Y_2)\bigcup (Y_2\setminus Y_1)$
$Y$ $G[Y]$
$G[Y]$ 的每个顶点的度数必然为偶数
$G$ $v$ $d_G(v)$ $Y_1$ $Y_2$ $v$ 关联的边数均为奇数
$d_Gj(v)$ $Y_1$ $Y_2$ $v$ 关联的边数均为偶数
$Y_1$ $Y_2$ $v$ $y_1$ $y_2$ $y_0$ $Y$ $v$ $y_1-y_0 + (y_2-y_0)=y_1+y_2-2y_0$
$Y$ $v$ $G[Y]$ 的每个顶点的度数必然为偶数
$G[Y]$ $G[Y]$ 可以作圈分解
$Y=E(C_1)\bigcup E(C_2)\bigcup \cdots \bigcup E(C_k)$
$i$ $\sum\limits_{e\in Y_1 \bigcap E(C_i)} w(e)=\sum\limits_{e\in Y_2 \bigcap E(C_i)} w(e)$
事实上，因为：
$\begin{matrix} \sum_{e \in Y_{1} ⋂ E (C_{i})} w (e) = \sum_{e \in E (C_{i}) ∖ Y_{1}} w (e), (i = 1, 2, \dots, k) \\ \sum_{e \in Y_{2} ⋂ E (C_{i})} w (e) = \sum_{e \in E (C_{i}) ∖ Y_{2}} w (e), (i = 1, 2, \dots, k) \end{matrix}$
又因为：
$E (C_{i}) ∖ Y_{1} = Y_{2} ⋂ E (C_{i}) E (C_{i}) ∖ Y_{2} = Y_{1} ⋂ E (C_{i})$
$i$ ，成立
$\begin{matrix} \sum_{e \in Y_{1} ⋂ E (C_{i})} w (e) \leq \sum_{e \in E (C_{i}) ∖ Y_{1}} w (e) = \sum_{e \in E (C_{i}) ⋂ Y_{2}} w (e) \\ \sum_{e \in Y_{2} ⋂ E (C_{i})} w (e) \leq \sum_{e \in E (C_{i}) ∖ Y_{2}} w (e) = \sum_{e \in E (C_{i}) ⋂ Y_{1}} w (e) \end{matrix}$
因此
$\sum_{e \in Y_{1} ⋂ E (C_{i})} w (e) = \sum_{e \in Y_{2} ⋂ E (C_{i})} w (e)$
$G_1$ $G_1$ 具有相同的权值

$Euler$ 图求最优环游的方法：

$G$ $G^{'}$
$G^{'}$ $C$ $C$ $G^*$ $G^*$ 中每个圈上重复边的总权值不大于该圈权值的一半
$G^*$ $Euler$ 回路

例： $G$ 如图 (a) 所示(各边权值为 1)，它有 10 个奇度点。任意添一些边得到一个欧拉多重图 (b)

(b) 中有色圈中重复边的数目为 5，大于圈长 8 的一半，在这个圈上交换重复边和不重复边，得到 (c)

例： $G$ 的一个最优欧拉环游

解：

例： $G$ $k$ $G$ $k/2$ $G$ 具有欧拉回路

例： $G$ $u$ $v$ ，设计一个求其最优欧拉环游的算法

解：
$u$ $v$ $P$ ；（最短路算法）
$P$ $G$ $G^*$
$G^*$ 中用 Fleury 算法求出一条欧拉回路
证明算法的合理性
$u$ $v$ $G$ $G^*$ $G$ 的任意一个欧拉多重图
$G^*[E^*-E]$ $u$ $v$ $G^*[E^*-E]$ $(u,v)$ $P^*$
$\sum\limits_{e\in E^*-E} w(e) \ge w(P^*) \ge w(P)$

例：求出下图的一条最优欧拉环游

$x\ u\ y\ w\ v\ z\ w\ y\ x\ u\ w\ v\ x\ z\ y\ x$

权值：37

哈密尔顿图

1857 年，哈密尔顿发明了一个游戏 (Icosian Game)。它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上 (钉子)，由此可以获得旅程的直观表示

该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题

定义 60：经过图中每个点的路称为 Hamilton 路，简称 $H$ 路

定义 61：经过图中每个点的圈称为 Hamilton 圈，简称 $H$ 圈

定义 62：存在 Hamilton 圈的图称为 Hamilton 图，简称 $H$ 图

例：正十二面体图是 Hamilton 图

思考

$n \ge 3$ $K_n$ 是否为哈密尔顿图？ $\rightarrow \ \$ 是
$n\ge 2$ $n$ $Q_n$ 是否为哈密尔顿图？ $\rightarrow \ \$ 是
$K_{a,b}$ $a$ $b$ 需满足什么条件？ $\rightarrow \ \ a=b\ge 2$

思考：是否存在一个具有奇数个顶点的连通图，它既是二部图，也是哈密尔顿图？ $\rightarrow \ \$ 不存在，否则二部图中出现了奇圈 $\rightarrow \ \$ 定理 9

思考： $G$ $(X,Y)$ 满足什么条件？ $\rightarrow \ \ |X|=|Y|$

定理 44： $G$ $H$ $V$ $S$ $\omega(G-S)\le|S|$

证明： $C$ $G$ $H$ 圈
$V$ $S$ $\omega(C-S)\le|S|$
$\omega(G-S)\le\omega(C-S)\le|S|$
注：上述定理只是必要条件，而非充分条件

例： $H$ 图，但满足定理中的条件

证明：可以直接验证彼得森图满足定理中的条件
$H$ 图
$H$ 图，对其顶点进行标号，如下图所示
$C$ $1a,2b,3c,4d,5e$ $acebda$ ，然后再沿着另一条辐轴边回到外面的圈 123451
$C$ 必然经过 2 条或者 4 条辐轴边
情况 1：
经过 2 条辐轴边
$1a$
$ac$ $ad$ $C$ $ad$
$ac$ $C$ $3c$ $C$ 上
$2b,4d,5e$ $C$ 上
$C$ 上
$C$ 上，矛盾！
情况 2：
经过 4 条辐轴边
$5e$
$1a$ $C$ $C$ $C$ 上
$eb$ $ec$ $C$ 上
$3c$ $ce$ $eb$ $b2$ 已经构成一个圈，矛盾
利用定理可以说明某些图不是哈密尔顿图

例： $G$ 是否为哈密尔顿图？

解： $S=\{2,6,7\}$ $\omega(G-S)=4>3=|S|$
$G$ 不是哈密尔顿图

例： $G$ $G$ 不是哈密尔顿图

证明： $G$ $G$ $v$
$\omega(G-v)\ge 2>1=|\{v\}|$
$G$ 不是哈密尔顿图
哈密尔顿简单图中一定不存在割点

例： $G$ $V(G)$ $S$ $\omega(G-S)\le|S|+1$

证明： $P$ $G$ 的哈密尔顿路
$\omega(G-S)\le\omega(P-S)\le|S|+1$

定理 45 (Dirac 1952)： $n \ge 3$ $G$ $G$ $\delta(G)\ge \frac{n}{2}$ $G$ $H$ 图

证明：

定理 46 (Ore 1962)： $n \ge 3$ $G$ $G$ $u$ $v$ $d(u)+d(v) \ge n$ $G$ $H$ 图

例： $G$ $K_{l+1}$ $K_{l+1}$ $G$ $u$ $v$ $d(u)+d(v)=2l=n-1$ $G$ 不是 Hamilton 图

定义 63： $n$ $G$ $d(u)+d(v)\ge n$ $u$ $v$ $G$ 是闭图

$d(u)+d(v)\ge n \ \ \rightarrow u \ adj \ v$

定理 47： $G_1$ $G_2$ $V$ $G=G_1\bigcap G_2$ 是闭图

证明： $w\in V$ $d_G(w)\le d_{G_1}(w)，d_G(w)\le d_{G_2}(w)$
$d_G(u)+d_G(v)\ge n$ $d_{G_1}(u)+d_{G_1}(v)\ge n，d_{G_2}(u)+d_{G_2}(v)\ge n$
$G_1$ $G_2$ $u$ $v$ $G_1$ $G_2$ $u$ $v$ $G$ $G$ 是闭图

$\bigcup$ ) 不一定是闭图

例： $G_1$ $G_2$ 是闭图，但其并不是闭图！！

定义 64： $G$ $\hat G$ $G \subset \hat G$ $\hat G$ $H$ $G\subset H \subset \hat G$ $H$ $\hat G$ $G$ 的闭包

$G$ $G$ 的极小闭图

图的闭包的构造方法：将图中度数之和至少是图的顶点个数的非邻接顶点对递归地连接起来，直到不再有这样的顶点对存在为止

例：下图给出了 6 个顶点的图的闭包的构造过程

注：一个图的闭包不一定是完全图。比如下图中 (a)、(b) 两个均不是完全图，但它们却是自己的闭包

定理 48： $G$ 的闭包是唯一的

证明： $\hat G_1$ $\hat G_2$ $G$ $G \subset \hat G_1，G \subset \hat G_2$
$G \subset \hat G_1 \bigcap \hat G_2$
$\hat G_1 \bigcap \hat G_2$ $\hat G_1$ $\hat G_2$ 定理 47 $\hat G_1 \bigcap \hat G_2 \subset \hat G_1，\hat G_1 \bigcap \hat G_2 \subset \hat G_2$
$\hat G_1 = \hat G_1 \bigcap \hat G_2 = \hat G_2$ ？？？？？
$G$ 的闭包是唯一的

引理： $G$ $n$ $u$ $v$ $G$ $d(u)+d(v)\ge n$ $G$ $H$ $G+uv$ $H$ 图

证明：
$G$ $H$ $G+uv$ $H$ 图
$G+uv$ $H$ $C$ $H$ 圈
$C$ $uv$ $G=(G+uv)-uv$ $G$ $H$ 圈
$C$ $uv$ $C=uvv_3v_4\cdots v_nu$
$G_1=G+uv$ $d_{G_1(u)}=d_G(u)+1，d_{G_1}(v)=d_G(v)+1$
$d_{G_1}(u)+d_{G_1}(v)=d_G(u)+d_G(v)+2\ge n+2$
$i \ (3\le i \le n-1)$ $u$ $v_i$ $v$ $v_{i+1}$ 相邻
..........

定理 49 (Bondy)： $G$ $H$ $H$ 图

证明： $G$ $G$ 相同，结论显然成立
$G$ $G$ $e_i \ (1 \le i \le k)$ $G$ 的闭包而依次添加的所有边
$G$ $H$ $G+e_1$ $H$ $G+e_1$ $H$ $G+e_1+e_2$ $H$ $\cdots$ ，反复下去，可以得到定理结论

推论： $G$ $n\ge 3$ $G$ $G$ $H$ 图

推论： $G$ $n\ge 3$ 的简单图

$G$ $d(v) \ge n/2$ $G$ $H$ 图
$G$ $u$ $v$ $d(u)+d(v)\ge n$ $G$ $H$ 图

定理 50 (度序列判定法)： $G$ $(d_1,d_2,\cdots,d_n)$ $d_1\le d_2\le \cdots \le d_n$ $n\ge 3$ $k<n/2$ $d_k > k$ $d_{n-k} > n-k$ $G$ $H$ 图

证明：
$G$ $K_n$ $G$ $H$ 图
..........

例： $G$ $H$ 图

证明： $G$ $d_1=d_2=d_3=3，d_4=d_5=5，d_6=6，d_7=7，d_8=d_9=8$
$d_1 > 1，d_2 > 2，d_6 \le 6，d_4 > 4$ $G$ $H$ 图

例： $G$ $(d_1,d_2,\cdots,d_n)$ $d_1 \le d_2 \le \cdots \le d_n$ $(n+1)/2$ $m$ $d_m < m$ $d_{n-m+1} < n-m$ $G$ $H$ 路

证明： $G$ $v$ $G$ $G_1$
$G_1$ $d_1+1,d_2+1,\cdots,d_n,n$
$(n+1)/2$ $m$ $d_m + 1 \le m$ $d_{(n+1)-m}+1 < (n+1) - m$
$G_1$ $H$ $G$ $H$ 路

例： $G$ $n$ $d$ $n \ge 2d+2$ $d>1$ $G$ $H$ 图

证明： $G$ $n-1-d$ $(d_1,d_2,\cdots,d_n)=(n-1-d,n-1-d,\cdots,n-1-d)$
$n\ge 2d_2$ $n-1-d \ge d+1$
$k<n/2$ ，分两种情况讨论
$k<d+1$ $d_k=n-1-d \ge d+1>k$
$k \ge d+1$ $d_{n-k}=n-1-d\ge n-k$
$G$ $G$ 的补图是哈密尔顿图

应用

例： $3\times 3 \times 3$ $1\times 1 \times 1$ 的子立方体。如果它从一角上开始，然后依次走向未吃的立方体，问吃完时是否可以到达中心点

解： $H$ 路

例： $a,b,c,d,e,f,g$ $a$ $b$ $c$ $d$ $e$ $f$ $g$ 会讲法语和德语。是否存在一种排座方法，使每个人能够和他身边的人交流？并说明理由

解： $G$ 如下
$G$ 是否为哈密尔顿图
$G$ $H$ $a \ b \ d \ f \ g \ e \ c \ a$
$a \ b \ d \ f \ g \ e \ c$ 的方式就座可以使每个人都可以和身边的人互相交流

度极大的非 Hamilton 图

定义 65： $G$ $H$ 图 $H$ 图

定义 66： $1\le m \le n/2$ $C_{m,n}$ $C{m,n}=K_m \vee (\overline K_m+K_{n-2m})$

例： $C_{1,5}$ $C_{2,5}$ 如图

引理： $1\le m < n/2$ $C_{m,n}$ $H$ 图

证明： $S=V(K_m)$ $\omega(G-S)=m+1>|S|=m$ $H$ $G$ $H$ 图

定理 51 (Chvátal 1972)： $G$ $n\ge 3$ $H$ $G$ $C_{m,n}$ 图

证明： $G$ $(d_1,d_2,\cdots,d_n)$ $H$ $d_1 \le d_2 \le \cdots d_n$
$m<n/2$ $d_m\le m$ $d_{n-m} < n-m$
$G$ 的度序列必弱于如下序列：
$\overset{m}{\overset{⏞}{m, m, \dots, m}}, \overset{n - 2 m}{\overset{⏞}{n - m - 1, n - m - 1, \dots, n - m - 1}}, \overset{m}{\overset{⏞}{n - 1, n - 1, \dots, n - 1}}$
$C_{m,n}$ 的度序列

注意

$H$ $C_{m,n}$ $n$ $H$ 简单图的极图
$n$ $G$ $C{m,n}$ $G$ $H$ 图
定理的条件是必要条件而非充分条件

例： $5$ $C_5$ $(2,2,2,2,2)$ $C_{2,5}$ $(2,2,2,4,4)$ $C_5$ $H$ 图

例： $G$ $H$ 图

解： $G$ $(2,3,3,4,4)$ $C_{1,5}$ $(1,3,3,3,4)$ $C_{2,5}$ $(2,2,2,4,4)$ $G$ $H$ 图

推论： $G$ $n$ $n\ge 3$ 且

\begin{matrix} | E (G) | > (\begin{matrix} n - 1 \\ 2 \end{matrix}) + 1 \end{matrix}

$G$ $H$ $n$ $\begin{pmatrix}n-1 \\2\end{pmatrix}+1$ $H$ $C_{1,n}$ $C_{2,5}$

证明：

$C_5$

例： $G$ $n$ $n\ge 3$ 且

\begin{matrix} | E (G) | > (\begin{matrix} n - 1 \\ 2 \end{matrix}) + 1 \end{matrix}

$G$ 的闭包是完全图

证明：

旅行售货员问题

E 图和 H 图的联系

定义 67： $G$ 的 $L(G)$ 定义为

$V(L(G))=E(G)$
$(e_1,e_2)\in E(L(G))$ $e_1$ $e_2$ 中相邻

$G$ $n$ 次迭线图 $L^n(G)$ $L^n(G)=L(L^{n-1}(G))$

例：

定理 52：

$L(G)$ $G$ 的边数
$e=uv$ $G$ $e$ $L(G)$ $d_{L(G)}(e)=d_G(u)+d_G(v)-2$

定理 53： $G$ $n$ $m$ $L(G)$ $|E(L(G))|=-m+\frac{1}{2}\sum\limits_{v\in V(G)}d^2(v)$

证明： $L(G)$ $m$ 个顶点
$G$ $v$ $d(v)$ $L(G)$ $d(v)(d(v)-1)/2$
$L(G)$ 的边数为：
$\sum_{v \in V (G)} \frac{d (v) (d (v) - 1)}{2} = \sum_{v \in V (G)} \frac{d^{2} (v)}{2} - \sum_{v \in V (G)} \frac{d (v)}{2} = - m + \frac{1}{2} \sum_{v \in V (G)} d^{2} (v)$

定理 54：一个图同构于它的线图当且仅当它是圈

定理 55： $G_1$ $G_2$ $K_3$ $K_{1,3}$ $G_1$ $G_2$ 同构

定义 68： $S_n$ $G$ $n$ 次细分图 $G$ $n$ $2$ 度顶点

例：

定义 69： $L_n(G)=L(S_{n-1}(G))$

$L_n(G)\neq L^n(G)$

定理 56：

$G$ $E$ $L(G)$ $E$ $H$ 图
$G$ $H$ $L(G)$ $H$ 图

注：该定理的逆命题不成立

定理 57： $G$ $E$ $L_3(G)$ $H$ 图

例：

定理 58： $G$ $n$ $k\ge n-3$ $L^k(G)$ $H$ 图

例：

第五章匹配与因子分解

图的匹配

定义 70： $M$ $G$ $e\in M$ $e$ $M$ $M$ $G$ 匹配 $M$ $G$ $v\in V(G)$ $v$ $M$ $v$ $M$ 饱和点 $M$ 非饱和点

定义 71： $G$ $M$ $M$ $G$ 的完美匹配

定义 72： $M$ $G$ $M$ $G$ 的最大匹配

注意

完美匹配必是最大匹配，而最大匹配不一定是完美匹配
最大匹配必存在，但完美匹配不一定存在
$G$ $G$ 的点数必然是偶数

例： $G$ $G$ 的匹配有：

$M_1=\{v_1v_8\}$
$M_2=\{v_1v_3, v_8v_4, v_7v_5\}$
$M_3=\{v_1v_2, v_8v_3, v_7v_4, v_6v_5\}$

$M_2$ $v_1$ $v_2$ 是非饱和点

$M_3$ $v_1$ $v_3$ 均是饱和点

$M_1$ $M_2$ $M_3$ 是最大匹配，也是完美匹配

定义 73： $M$ $G$ $G$ $M$ 交错路 $G$ $M$ $M$ $M$ 可扩路 $M$ $M$ 交错路

例： $M=\{v_7v_8,v_3v_4\}$ $v_6v_7v_8v_3v_4$ $v_1v_7v_8v_2$ $M$ $v_1v_7v_8v_2$ $M$ 可扩路

Berge 定理

定理 59 (Berge 1957)： $G$ $M$ $G$ $M$ 可扩路

证明： $M$ $G$ $G$ $M$ 可扩路 $v_0v_1\cdots v_{2m+1}$
$M^* \subseteq E$ $M^*=M | \{v_1v_2,v_3v_4,\cdots v_{2m-1}v_{2m}\} \bigcup \{v_0v_1,v_2v_3,\cdots,v_{2m}v_{2m+1}\}$
$M^*$ $G$ $|M^*|=|M|+1$ $M$ 就不是最大匹配
反之。。。。。。。。。。

偶图的匹配与覆盖问题的提出

问题的提出

在日常生活、工程技术中，常常遇到求偶图的匹配问题。例如：

有 7 名研究生 A，B，C，D，E，F，G 毕业寻找工作。就业处提供的公开职位是：会计师（a），咨询师（b），编辑（c），程序员（d），记者（e），秘书（f）和教师（g）。每名学生申请的职位如下：

A: b,c B: a,b,d,f,g C: b,e D: b,c,d E: a,c,d,f F: c,e G: d,e,f,g

问：学生能找到理想工作吗？

$X=\{A,B,C,D,E,F,G\},Y=\{a,b,c,d,e,f,g\}$ $X$ $Y$ 中的顶点连线当且仅当学生申请了该工作

于是，得到反映学生和职位之间的状态图：

$X$ 中每个顶点的一个匹配！！！

需要解决的问题是：

匹配是否存在？
如何求出匹配？

偶图的匹配存在性判定定理

定义 74： $G$ $S$ $M(S)=\{v|\exists u\in S, \mathrm{s.t.} u \ adj \ v\}$ $N(S)$ $S$ 的邻集

例： $S=\{v_1,v_2\}$ $N(S)=\{v_8,v_3,v_2,v_1\}$

定理 60 (Hall 1935)： $G$ $(X,Y)$ $G$ $X$ $|N(S)|\ge |S|$ $S \subseteq X$ 成立

证明：

注意

$G=(X,Y)$ 存在 $X$ 每个顶点的匹配也常说成存在 $X$ $Y$ 的匹配
婚姻定理 $r$ $s$ $(1\le r \le s)$ $r$ $k \ (1\le k \le r)$ $k$ $k$ 个男生
Hall 定理是在偶图中求最大匹配算法的理论基础，即匈牙利算法基础

推论： $G$ $k$ $(k>0)$ $G$ 有完美匹配

证明： $G$ $(X,Y)$ $k$ 正则偶图
$G$ $k$ $k|X|=|E(G)|=k|Y|$ $|X|=|Y|$
$X$ $S$ ，令
$E_1=\{e | e \in E, \ 并且\ e\ 与\ S\ 的顶点关联\}$
$E_2=\{e | e \in E, \ 并且\ e\ 与\ N(S)\ 的顶点关联\}$
$S$ $N(S)$ $E_1\subseteq E_2$
$k|N(S)|=|E_2|\ge|E_1|=k|S|$ $|N(S)| \ge |S|$
$G$ $X$ $M$ $|X|=|Y|$ $M$ 是完美匹配

例：

$n$ $(n\ge 1)$
$K_{2n}$ $K_{n,n}$ 中不同的完美匹配的个数

证明： $n$ $n$ $2^n$ $n$ 的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同
$n$ $2^n$ $X$ $Y$
$X$ $Y$ $n$ 方体是偶图
$n$ $n$ $n$ $n$ 正则偶图
$n$ 方体存在完美匹配

证明： $K_{2n}$ $K_{n,n}$ 中不同的完美匹配的个数
$K_{2n}$ $2n-1$ 种不同的方法被匹配
$K_{2n}$ $(2n-1)K_{2n-2}$ $K_{2n}$ $(2n-1)!!$
$K_{n,n}$ $n!$

例：证明：非平凡树至多存在一个完美匹配

证明： $M_1$ $M_2$ $T$ $M_1 \Delta M_2 \ne \varnothing$
$T[M_1 \Delta M_2]$ $T$ 中有圈，矛盾！

点覆盖与 König 定理

定义 75： $G$ 覆盖 $V(G)$ $K$ $G$ $K$ 中

定义 76： $G$ $G$ 的最小覆盖

例：

$K$ $G$ $M$ $G$ $M$ $M$ $|M|$ $|M| \le |K|$

$M^*$ $\widetilde{K}$ $|M^*|\le |\widetilde{K}|$

定理 61： $M$ $K$ $|M|=|K|$ $M$ $K$ 是最小覆盖

证明： $M^*$ $\widetilde{K}$ $|M|\le|M^*|\le|\widetilde{K}|\le|K|$
$|M|=|K|$ $|M|=|M^*|$ $|\widetilde{K}|=|K|$

定理 62 (König 1931)：在偶图中，最大匹配中的边数等于最小覆盖中的点数

证明：

例： $(0,1)$ 矩阵中所有 1 的线的最小条数，等于具有性质「任意两个 1 都不在同一条线上」的 1 的最大个数

证明：

Tutte 定理与完美匹配

图的分支根据它有奇数个或偶数个顶点而分别称为奇分支偶分支 $o(G)$ $G$ 的奇分支的个数

定理 63 (Tutte)： $G$ $o(G-S)\le|S|$ $S\subset V$ 成立

推论 (Peterson)：每个没有割边的 3 正则图都有完美匹配

证明：

例：彼得森图满足推论的条件（即没有割边的 3 正则图），故它有完美匹配

注：有割边的 3 正则图不一定就没有完美匹配

例： $T$ $v\in T$ $o(T-v)=1$

证明：必要性
$T$ $o(T-v)\le 1$
$T$ $o(T-v) \ge 1$
$o(T-v)=1$

充分性
$T$ $v$ $T_v$ $T-v$ $T_v$ $v$ $uv$
$v\in T_v$
$u$ $u$ $T_u$ $uv$
$w$ ，按照上述方式可以找到唯一的一个顶点与之配对
$o(T-v)=1$ $T$ 具有偶数个顶点
$T$ 的所有顶点都可以两两配对

因子分解

定义 77： $G$ 因子 $G$ 的一条边的生成子图，即非空的生成子图就是一个因子

定义 78： $G$ 因子分解 $G$ 分解成若干个边不重的因子之并

注意

$G$ 的所有顶点 (生成子图)
$G$

定义 79： $k-$ 因子 $k$ 正则的因子

解释： $k-$ $k$ 正则图

例：

1-因子的边构成一个完美匹配
2-因子的连通分支为一个圈

定义 80： $k-$ 因子分解： $k-$ $G$ 本身是 $k-$ 可因子化的

1-因子分解

$G$ $G$ 的阶数是偶数。所以，奇数阶图不能 1-因子分解

定理 64： $K_{2n}$ 是 1-可因子化的

证明： $K_{2n}$ 的 1-因子分解
$K_{2n}$ $2n$ $1,2,\cdots,2n$ 。按照右图进行排列
$2n$ $2n-1$ $2n-1$ $K_{2n}$ 的 1-因子分解

例： $K_6$ 的 1-因子分解

定理 65： $k$ $(k>0)$ 是 1-可因子化的

证明：因正则偶图存在完美匹配，即 1-因子，从不断减去完美匹配的方式就可得到正则偶图的 1-因子分解

例： $K_{3,3}$ 作 1-因子分解

解： $X$ $1,2,3$ $Y$ $1^{'},2^{'},3^{'}$ $G$ $K_{3,3}$ $Y$ 的点之间的匹配关系，即
$\begin{matrix} G_{1} = (\begin{matrix} 1 & 2 & 3 \\ 1^{^{'}} & 2^{^{'}} & 3^{^{'}} \end{matrix}) G_{2} = (\begin{matrix} 1 & 2 & 3 \\ 2^{^{'}} & 3^{^{'}} & 1^{^{'}} \end{matrix}) G_{3} = (\begin{matrix} 1 & 2 & 3 \\ 3^{^{'}} & 1^{^{'}} & 2^{^{'}} \end{matrix}) \end{matrix}$
则：

定理 66：具有 Hamilton 圈的 3 正则图是 1-可因子化的

证明： $G$ $G$ 的阶数是偶数
具有偶数个顶点的圈可以分解为两个 1-因子的并，得证

注：1-可因子分解的 3 正则图不一定有 Hamilton 圈 (即：定理 66 返过来不一定成立)

例：下图是 3 正则图且可以 1-因子分解，但不存在 Hamilton 圈

定理 67：若 3 正则图有割边，则不可 1-因子分解

证明： $G$ $G$ 的不含割边的 1-因子后，途中每个点均为 2 度，从而每条边均在圈中，特别地割边也在圈中，矛盾！！

注：无割边的 3 正则图可能也没有 1-因子分解

例： $M_1,M_2,M_3$ 的并

13323316493959534JNrufimage-20220408133233114

证明： $M_1,M_2,M_3$ 的并
$M_1,M_2$ $M_3$ $123451$ ，否则存在两条相邻的边出现在同一个 1-因子中
$12 \in M_1$ $1a$ $2b$ $M_1$
$1a$ $M_1$ $ac$ $ad$ $M_1$
$be$ $bd$ $M_1$
$M_1$ $acebda$ 上的两条边
$M_2$ $M_3$ $acebda$ 上的两条边。矛盾！！！

例： $K_4$ 有唯一的 1-因子分解

证明： $K_4$ $K_4$ 的每个 1-因子分解包含 3 个不同的完美匹配，所以，其 1-因子分解唯一
$K_2$ $K_4$ $K_6$ $K_8$ $K_{10}$ $K_{12}$
1 1 6 6240 1225566720 252282619805368320
$K_{14}$ $98758655816833727741338583040$

$K_2$	$K_4$	$K_6$	$K_8$	$K_{10}$	$K_{12}$
1	1	6	6240	1225566720	252282619805368320

例： $k>1$ $k-$ $G$

解：

2-因子分解

由定义有：

每个 2-因子是边不重圈的并
$H$ 圈
$K_{2n}$ 不是 2-可因子化的

定理 68： $K_{2n+1}$ $n$ $H$ 圈的并

证明： $K_{2n+1}$ $n$ $H$ $v_1,v_2,\cdots,v_{2n+1}$
$v_1,v_2,\cdots,v_{2n}$ $n$ $P_i$ 如下：
$P_{i} = v_{i} v_{i + 1} v_{i - 1} v_{i + 2} v_{i - 2} \dots v_{i + (n - 1)} v_{i - (n - 1)} v_{i + n}$
$1,2,\cdots,2n \pmod{2n}$
$H_i$ $v_{2n+1}$ $P_i$ 的两个端点构成

例： $K_7$ $H$ 圈的并

解： $K_7$ $i$ $1,2,3,4,5,6$ $7$ 是中心
$H$ $H_1=v_7v_1v_2v_6v_3v_5v_4v_7$
$P_{1} = 1 (1 + 1) (1 - 1) (1 + 2) (1 - 2) (1 + 3) = 126354 (\mod 6)$
$1,2,3,4,5,6$ $H$ $H_2=v_7v_2v_3v_1v_4v_6v_5v_7$
$\begin{matrix} P_{2} = 2 (2 + 1) (2 - 1) (2 + 2) (2 - 2) (2 + 3) = 231465 (\mod 6) \\ P_{3} = 3 (3 + 1) (3 - 1) (3 + 2) (3 - 2) (3 + 3) = 342516 (\mod 6) \end{matrix}$
$H$ $H_3=v_7v_3v_4v_2v_5v_1v_6v_7$
$K_7=H_1 \cup H_2 \cup H_3$

定理 69： $K_{2n}$ $n-1$ $H$ 圈的并

证明： $V(K_{2n})=\{v_1,v_2,\cdots,v_{2n}\}$
$n-1$ 条路：
$P_{i} = v_{i} v_{i + 1} v_{i - 1} v_{i + 2} v_{i - 2} \dots v_{i + (n - 1)} v_{i - (n - 1)} v_{i + n}$
$1,2,\cdots,2n-1 \pmod{2n-1}$
$v_{2n}$ $P_i$ $n-1$ $H$ 圈
$n-1$ $H$ 圈后，剩下的边构成一个 1-因子

例： $K_6$ $H$ 圈的并

解：
$\begin{matrix} P_{1} = v_{1} v_{2} v_{5} v_{3} v_{4}, H_{1} = v_{6} v_{1} v_{2} v_{5} v_{3} v_{4} v_{6} \\ P_{2} = v_{2} v_{3} v_{1} v_{4} v_{5}, H_{2} = v_{6} v_{2} v_{3} v_{1} v_{4} v_{5} v_{6} \end{matrix}$
$K_6$ 可分解为

定理 70：每一个没有割边的 3-正则图是一个 1-因子和一个 2-因子的并

证明： $M$ $G-M$ 是一个 2-因子

例：彼得森图是一个 1-因子和一个 2-因子的并

注：若没有割边的 3-正则图中的 2-因子是一些偶圈，则该图也是 1-可因子化的

定理 71：一个连通图是 2-可因子化的当且仅当它是偶数度正则图

证明：

例： $G$ 的一种 2-因子分解

解：

森林分解

定义 81：把一个图分解为若干个边不重的森林因子的并，称为图的森林因子分解，简称森林分解

定义 82： $G$ $G$ 荫度 $\sigma(G)$

$G$

例： $\sigma(K_4)=2, \ \ \sigma(K_5)=3$

定理 72： $G$ $m_s$ $G$ $s$ $\sigma(G)=\max\limits_{s}\lceil \frac{m_s}{s-1} \rceil$ $K_n$ $\frac{m_s}{s-1}$ $s=n$ $\sigma(K_n)=\lceil \frac{n}{2} \rceil$ $K_{r,p}$ $\frac{m_s}{s-1}$ $s=n=r+p$

推论： $\sigma(K_n)=\lceil \frac{n}{2} \rceil , \ \ \sigma(K_{r,p})=\lceil \frac{rp}{r+p-1} \rceil$

完全图的森林分解方法

$n=2s$ $K_{2s}$ $s$ 条生成路

P_{i} = v_{i} v_{i + 1} v_{i - 1} v_{i + 2} v_{i - 2} \dots v_{i + (s - 1)} v_{i - (s - 1)} v_{i + s}

$n=2s+1$ $K_{2s}$ $v_{2s+1}$ $v_{2s+1}$ $2s$ 个点构成一个星形图

例： $K_7$ 为生成森林的最小分解如下图所示

(考过) 例： $n$ $\delta(G) \ge \frac{n}{2} + 1$ $n$ $G$ 有 3-因子

证明： $\delta(G) \ge \frac{n}{2} + 1$ Dirac 定理 $n$ $G$ $H$ $C$
$n$ $C$ 为偶圈
$C$ $G$ $F_1$
$G_1=G-F_1$ $\delta(G_1)\ge \frac{n}{2}$ $G_1$ $H$ $C_1$
$H=C_1 \bigcup F_1$ $H$ $G$ 的一个 3-因子

思考： $G$ $n$ $n$ $\delta(G) \ge \frac{n}{2} + 3$ $G$ 中存在 5-因子

思考： $n\ge 1$ $K_{4n+1}$ 可以 4-因子分解

最优匹配 & 匈牙利算法 (几乎不考)

人员分派问题： $n$ $x_1,x_2,\cdots,x_n$ $n$ $y_1,y_2,\cdots,y_n$ $x_i$ $k_i$ $(i=1,2,\cdots,n)$ 。问能否存在一种工作安排方案，使每个人都能分配到他所能胜任的一件工作（假定每件工作只能一人做）。若能，又如何安排？

图论模型： $x_i$ $y_i$ $G$ $G$ 中一个完美匹配。次问题实际上是 求偶图的完美匹配问题

$X$ $X$ 是工人的集合

进一步，若问：能否存在一种安排使尽可能多的人能分到他能胜任的工作或使尽可能多的工作被分配，则问题为 求偶图的最大匹配问题

匈牙利算法 (几乎不考)

算法思想： $M$ $M$ 可扩路 $M$ $M$ $M$ $M$ $M$ $M^{'}$ $M^{'}$ 重复上面过程

$X$ $M$ $X$ $M$ $M$ $M$ $Y$ $M$ 可扩路

定义 83： $M$ $G$ $u$ $X$ $M$ $H\subseteq G$ $u\in V(G)$ $H$ $v$ $H$ $(u,v)$ $M$ $H$ 是一棵 $u$ $M$ 交错树

$u$ $M$ $u$ $M$ $H$

$H$ $u$ 组成，而在以后的步骤中它都按以下方式生长：

$u$ $M$ 饱和点，如图 (a)
$H$ $u$ $M$ 饱和顶点，如图 (b)

$M$ $M$ 可扩路

$S=V(H)\cap X, \ T=V(H)\cap Y$ $T \subseteq N(S)$

$N(S)=T$ $S \setminus \{u\}$ $T$ $|T|=|S|-1$ $|N(S)|=|S|-1<|S|$
$G$ $X$ 中所有顶点的匹配
$T\subset N(S)$ $N(S) \setminus T$ $y$ $S$ $x$ 相邻
$x=u$ $u$ $M$ $xy\notin M$ $x \ne u$ $H$ $u$ $M$ $xy\notin M$
$y$ $M$ $yz \notin M$ $y$ $z$ $xy$ $yz$ $H$ ，然后回到情形 1
$y$ $M$ $y$ $xy$ $H$ ，结果得到情形 2

匈牙利算法步骤： $(X,Y)$ 的偶图

$M$
$X$ $M$ $M$ ；否则转 (3)
$X$ $u$ $S=\{u\}, \ \ T=\varnothing$
$N(S)=T$ $|T|=|S|-1$ $|N(S)|<|S|$ $X$ $u$ $M$ $y\in N(s)\setminus T$
$y$ 为饱和点，则转 (6)；否则转 (7)
$z \in X$ $yz\in M$ $S=S\cup\{z\}$ $T=T\cup\{y\}$ ，转 (4)
$u$ $y$ $M$ $\varGamma$ $M^{'}=(M\cup E(\varGamma))\setminus (M\cap E(\varGamma)), \ \ M=M^{'}$ ，转 (2)

例： $G$ $X=\{v_1,v_2,v_3,v_4,v_5\}$

$M=\{v_1u_1,v_3u_3,v_5u_5\}$ ，如图 (a) 的红色所示
$X$ $v_2$ $S=\{v_2\}, \ \ T =\varnothing$

最优匹配 (几乎不考)

$G=(X,Y)$ $X=\{x_1,x_2,\cdots,x_n\}$ $Y=\{y_1,y_2,\cdots,y_n\}$ $x_iy_j$ $w_{ij}=w(x_iy_j)$ $x_i$ $y_i$ 时的效率。最优分派问题指的是在赋权完全偶图中寻找一个具有最大权值的完美匹配，称为最优匹配

定义 84： $G=(X,Y)$ $l$ $x\in X, y\in Y$ $l(x)+l(y)\ge w(xy)$ $l$ $G$ 的可行顶点标号

$G$ $G$ 的可行顶点标号。事实上，设：

\begin{matrix} l = {\begin{matrix} l (x) = max_{y \in Y} w (x y) & , x \in X \\ l (y) = 0 & , y \in Y \end{matrix} \end{matrix}

$l$ $G$ 的一个可行顶点标号

定义 85： $l$ $G=(X,Y)$ $E_l=\{xy\in E(G) | l(x) + l(y) = w(xy)\}$ $E_l$ $G$ $G$ $l$ 的相等子图 $G_l$

例： $G$ $l$

定理 73： $l$ $G=(X,Y)$ $G_l$ $M^*$ $M^*$ $G$ 的最优匹配

证明： $M^*$ $G_l$ $w(M^*) = \sum \limits_{e\in M^*}w(e)=\sum\limits_{v\in V(G)}l(v)$
$M$ $G$ $w(M)=\sum\limits_{e\in M}w(e) \le \sum\limits_{v\in V(G)}l(v)$
$w(M^*)\ge w(M)$ $M^*$ $G$ 的最优匹配

算法基本思想： $l$ $G_l$ $G_l$ $M$ $G_l$ 中已找到一个完美匹配，则该匹配就是最优匹配。否则修改可行顶点标号，直到完美匹配在某个相等子图中找到为止

Kuhn-Munkres 算法： $l$ $G_l$ $M$

$X$ $M$ $M$ $u$ $M$ $S=\{u\}, \ \ T=\varnothing$
$T\subset N_{G_l}(S)$ $\alpha = \min\limits_{x\in S, \ y\notin T}\{l(x)+l(y)-w(xy)\}$
$\hat{l} \left\{\begin{matrix} l(v) - \alpha_l & , v \in S \\ l(v) + \alpha_l & , v \in T \\ l(v) &, other \end{matrix}\right.$ 给出新的可行顶点标号，在新标号下重新开始
$N_{G_L}(S)\setminus T$ $y$ $y$ $M$ $yz \in M$ $S=S\bigcup \{z\}, \ \ T=T\bigcup \{y\}$ $P$ $G_l$ $M$ $(u,y)$ $M=M \Delta E(P)$ ，转 1

例： $G$ 的权值矩阵，求其最优匹配

\begin{matrix} W = (\begin{matrix} 3 & 5 & 5 & 4 & 1 \\ 2 & 2 & 0 & 2 & 2 \\ 2 & 4 & 4 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 3 & 3 \end{matrix}) \end{matrix}

解：

匹配在矩阵理论中的应用

定理 74： $v$ $M=(a_{ij}$ $n \le v$ $M$ $n \times (v-n+1)$ 阶的子矩阵，它的所有元素均为零

证明：

第六章平面图

平面图的概念

定义 86： $G$ $G$ 可嵌入平面 $G$ 可平面图 $G$ $G$ 平面嵌入 $G$ 的平面嵌入表示的图称为平面图

注：可平面图概念和平面图概念有时可以等同看待

例：

平面图的性质

定义 87： $G$ $G$ $G$ 的面，无界的区域称为外部面无限面 $G$ $\Phi$ 表示

注：每个平面图有且仅有一个外部面

例：

定义 88： $f$ $G$ $f$ $f$ 次数 $deg(f)$

例： $f_1,f_2,f_3,f_4,f_5$

$deg(f_1)=1,deg(f_2)=2,deg(f_3)=3,deg(f_4)=6,deg(f_5)=10$

注意

$deg(f_4), deg(f_5)$ 中存在一条割边，需要计算两次
$\sum\limits_{1 \le i \le 5}deg(f_i) = 2m$

例：图不连通，其外部面的次数为 5 (存在割边)

定理 75： $G$ $m$ $\sum\limits_{f \in \Phi}deg(f) = 2m$

证明： $G$ $e$ $e$ $G$ $e$ 不是割边，那么它必然是某两个面的公共边，因此，由面的次数定义知，它也给总数贡献 2 次。于是结论成立

定理 76 (Euler 公式)： $G$ $n$ $m$ $\varphi$ $n-m+\varphi =2$

证明： $\varphi$ 用归纳法
$\varphi = 1$ $G$ $n= m + 1$
$n-m+\varphi =(m+1) - n + 1 = 2$
$\varphi = k$ 时，结论成立
$\varphi = k + 1$ $G$ $f$
$f$ $G^{'}$ $G^{'}$ $n^{'}$ $m^{'}$ $\varphi^{'}$ $G^{'}$ $k$ 个面
$n^{'} - m^{'} + \varphi^{'} = 2$
$n^{'} = n,\ m^{'}=m-1,\ \varphi^{'}=\varphi - 1$
$n^{'} - m^{'} + \varphi^{'}=2$ $n-m+\varphi = 2$

推论： $G$ $n$ $m$ $\varphi$ $k$ $n-m+\varphi = k + 1$

证明： $G$ $k$ $G_1,G_2,\cdots,G_k$ $G_i$ $n_i - m_i + \varphi_i = 2 \ \ \ (i=1,2,\cdots,k)$ $n_i,m_i,\varphi_i$ $G_i$ 的点数、边数和面数
$k$ $\sum\limits^k_{i=1}n_i - \sum\limits^k_{i=1}m_i + \sum\limits^k_{i=1}\varphi_i = 2k$
$\sum\limits^k_{i=1}n_i = n,\ \ \sum\limits^k_{i=1}m_i=m, \ \ \sum\limits^k_{i=1}\varphi_i = \varphi+(k-1)$
$n-m+\varphi = k + 1$

推论： $G$ $n$ $m$ $\varphi$ $k$ $G$ $f$ $deg(f)\ge l \ge 3$ $m \le \frac{l}{l-2}(n-2)$

证明： $2m = \sum\limits_{f\in \Phi}deg(f)\ge l \varphi \ \Rightarrow \ \varphi \le \frac{2m}{l}$
$\varphi = 2-n+m$
$\varphi = 2-n+m \le \frac{2m}{l}$
$m \le \frac{l}{l-2}(n-2)$

注意

$G$ $n$ $m$ $m > \frac{l}{l-2}(n-2)$ $G$ 是非可平面图
$G$ 是平面图」的必要条件，不是充分条件

例： $K_{3,3}$ 是非可平面图

证明： $k_{3,3}$ $l=4$
$\frac{l}{l-2}(n-2)=\frac{4}{2}(6-2)=8$
$m=9$ $m \le \frac{l}{l-2}(n-2)$ ，矛盾！
$K_{3,3}$ 是非可平面图

推论： $G$ $n$ $m$ $n\ge 3$ $m\le 3n-6$

证明： $G$ 连通
$G$ $m \le \frac{3}{3-2}(n-2)=3n-6$
$G$ 不连通
$G$ 存在至少有三个点的连通分支 $G$ $m_1\le 3n_1-6$
$G$ $m_2$ $n_2$
$m_2\le n_2 \le 3n_2$ $m_1 + m_2 \le 3(n_1+n_2)-6$
$m \le 3n - 6$
$G$ 没有多于两个点的连通分支 $m\le n$
$n\ge 3$ $n\le 3n -6$ $m \le 3n -6$

例： $K_5$ 是非可平面图

证明： $K_5$ $m=10,\ n=5$ $3n-6=9$ $m\le 3n - 6$ $K_5$ 是非可平面图

推论： $G$ $n$ $m$ $G$ $l$ $m(l-2)=l(n-2)$

定理 77： $G$ $\delta \le 5$

证明： $n=1,2$ 的情况，直接验证可知结论成立
$n \ge 3$ $\delta \ge 6$ $6n \le \sum\limits_{v\in V(G)} d(v)=2m \ \ \Rightarrow \ \ m > 3n - 6$
$m \le 3n - 6$ 」矛盾！

定理 78： $G$ $G$ 的每个面的边界是圈

证明：由于环不影响图的连通性与平面性，故假设所讨论的图无环
「必要性」
。。。。
「充分性」
。。。。。

推论：设一个平面图是 2 连通的，则它的每条边恰在两个面的边界上

平面嵌入概念的推广

定义 89： $G$ $S$ $G$ $S$ $G$ 的这样一种画法 (若存在的话) 称为 $G$ $S$ 嵌入

例： $K_5$ 的环面嵌入，其中矩形的两对对边相等同

注意

$K_5$ 不可嵌入平面，但能嵌入环面，也存在不可嵌入环面的图
$S$ $S$ 的图。另一方面每个图又存在可以嵌入的某个可定向的曲面

定理 79：一个图可嵌入平面当且仅当它可嵌入球面

证明：

凸多面体与平面图

$n$ $m$ $\varphi$ $G$ $G$ $n-m+\varphi = 2$ 。这个公式也称为欧拉公式

定理 80 (Platonic)：存在且只存在 5 种正多面体：正四面体、正六面体、正八面体、正十二面体和正二十面体

证明： $\varphi$ $A$ $A$ $n$ $m$ 条棱
$A$ $G$ $G$ $l$ $r$ 度简单正则图
$\varphi l =2m, \ nr=2m, \ l \ge 3, \ r \ge 3$
$m = \frac{nr}{2}, \ \varphi=\frac{2m}{l} = \frac{nr}{l}$
$n-m+\varphi =2$ $n - \frac{nr}{2} + \frac{nr}{l} = 2$
$2ln-lnr+2nr=4l$ $n(2l-lr+2r)=4l$
$n=4l(2l-lr+24)^{-1}$
$n$ $l$ $2l-lr+2r>0$ $2(l+r)>lr$
这样我们得到不等式组
$\begin{matrix} {\begin{matrix} 2 (l + r) \geq l r \\ l \geq 3 \\ r \geq 3 \end{matrix} \end{matrix}$
$\varphi$ 值，其结果见下表：
序号 $r$ $l$ $n$ $m$ $\varphi$ 相应的正对面体
1 3 3 4 6 4 正四面体
2 3 4 8 12 6 正六面体
3 3 5 20 30 12 正十二面体
4 4 3 6 12 8 正八面体
5 5 3 12 30 20 正二十面体

序号	$r$	$l$	$n$	$m$	$\varphi$	相应的正对面体
1	3	3	4	6	4	正四面体
2	3	4	8	12	6	正六面体
3	3	5	20	30	12	正十二面体
4	4	3	6	12	8	正八面体
5	5	3	12	30	20	正二十面体

极大平面图及其性质

定义 90： $G$ $G$ $K_i \ \ (1 \le i \le 4)$ $G$ $G$ 是极大可平面图。极大可平面图是平面嵌入称为极大平面图

例：

引理： $G$ $G$ $G$ $G$ 无割边

证明：

定理 81： $G$ $G$ $G$ 中各面次数均为 3 且为简单图

证明：

注：该定理可以简单记为「极大平面图的三角形特征」，即每个面的边界是三角形

推论： $G$ $n$ $m$ $\varphi$ $n\ge 3$ $m = 3n - 6$ $\varphi = 2n - 4$

$G$ $n$ $G$ $G$ 的结构框架也大体确定了
$n=4$ $G$ $K_4$ $n=6$ $G$ 为正八面体图
$n=9$ $G$ 有 21 条边，14 个面，其中一个结构如图所示：
$n=12$ $G$ 有 30 条边，20 个面，此时，其中一个为正二十面体图，另一个如图所示

注：顶点数相同的极大平面图并不唯一。顶点数相同的极大平面图的个数和结构问题仍在研究当中

与「极大可平面图」相对应地图是「极小不可平面图」

定义 91： $G$ $G$ 极小不可平面图 $K_5$ $K_{3,3}$

极大外平面图及其性质

定义 92：若一个可平面图存在一个所有顶点均在同一个面的平面嵌入，则称该图为外可平面图。外可平面图的任一外平面嵌入 (即所有顶点均在同一个面的嵌入) 称为外平面图

例：下图给出了一个外可平面图及两种外平面嵌入

注： $G$ $G$ 的顶点均在外部面的边界上

定义 93： $G$ $G$ $G$ $G$ 是极大外可平面图。极大外可平面图的外平面嵌入称为极大外平面图

注：极大外平面图的外部面的边界是由多边形组成，内部面均由三角形围成

定理 82： $G$ $n \ \ (n \ge 3)$ $G$ 是极大外平面图当且仅当其外部面的边界是圈，内部面是三角形

证明：

引理： $G$ $n \ \ (n \ge 4)$ $G$ 中存在两个度数均为 2 且不相邻的点

证明：

定理 83： $G$ $n \ \ (n \ge 3)$ $G$ $n-2$ 个内部面

证明：

例： $G$ $n \ \ (n \ge 4)$ $m$ $G$ $m \le (3n-4)/2$

证明： $G$ $G$ $n$ ，内部面的次数至少为 4
$G$ $\varphi$ $2m \ge 4 (\varphi - 1) + n$
$\varphi = 2 -n + m$
$m \le \frac{3n-4}{2}$

定理 84：每个至少有 7 个顶点的外可平面的补图不是外可平面图，且 7 是这个数目的最小者

对偶图

定义 94： $G$ $G$ 对偶图 $G^*$ 是如下构造的图：

$G$ $f_i$ $v_i^*$ $G^*$ 的顶点
$G$ $e$ $e$ $f_i$ $f_j$ $v_i^*$ $v_j^*$ $G^*$ $v_i^* v_j^*$ $v_i^* v_j^*$ $e$ $e$ $f_i$ $v_i^*$ $G^*$ $v_i^* v_i^*$ $v_i^* v_i^*$ $e$ 相交

例：在下图中，平面图如 (a) 所示，其对偶图如 (b) 所示，其构造过程如 (c) 所示

定理 85： $G$ $G^*$ 也是平面图，并且还有

$G^*$ $G$ 的面数
$G^*$ $G$ 的边数
$G^*$ $G$ $G$ 连通)
$d(v_i^*) = deg(f_i)$

$G$	$G^*$
点	面
边	边
环	割边
割边	环
回路	边割
边割	回路

定理 86： $G^*$ $G$ $G^*$ 必连通

注： $G$ $G^*$ $(G^*)^*$ $G$

定理 87： $G$ $(G^*)^*=G$ $G$ 是连通图

注：同构的平面图可以有不同构的对偶图

例：下图中的两个图是同构的，但它们的对偶图却不同构

$G_2$ $G_1$ 没有次数是 1 的面

例： $G$ $n = 10, m = 10, \varphi=3$ $G^*$ $\varphi^*$

解： $n^*=\varphi=3, \ \ m^*=m=10$
$n^*-m^*+\varphi^*=k+1=3$
$\varphi^*=10$

平面图的判定

定义 95： $G$ $G$ 在 2 度顶点内扩充 $G$ $G$ 在 2 度顶点内收缩

例：

定义 96： $G_1$ $G_2$ $G_1\cong G_2$ $G_1$ $G_2$ 同胚的 $G_1$ $G_2$ 在 2 度顶点内是同构的

例：下面三个图是两两同胚的

注：图的可平面性在同胚意义下不变

定理 88 (库拉托夫斯基定理)： $G$ $K_5$ $K_{3,3}$ 同胚的子图

注： $G$ $K_5$ $K_{3,3}$ 同胚的子图」

例： $G_1$ $G_2$ 为不可平面图

证明： $G_1$ $1,3,5,7,9$ $K_5$ $G_1$ $K_5$ $G_1$ 是不可平面图
$G_2$ 的一个子图：
$6,3$ $K_{3,3}$ $G_2$ 是不可平面图

例：判断下图是否为可平面图

解：取红色的边导出的子图得到该图的一个子图：
$K_{3,3}$ 同胚。因此，原图不是可平面图

思考： $G$ $K_5$ $G$ 中删去 1 条边才可能使其成为可平面图

定义 97： $G$ $G$ $G$ $G$ 的基础简单图

定理 89：

$G$ 是可平面图当且仅当其基础简单图是可平面图
$G$ 是可平面图当且仅当它的每个块是可平面图

定义 98： $uv$ $G$ $G$ 的初等收缩 $uv$ 的运算 $G/uv$

定义 99： $G$ $H$ $H$ $G$ 通过一系列初等收缩而得到

例： $G$ $G/e$ $H$

定理 90 (瓦格纳定理)： $G$ $K_5$ $K_{3,3}$ 的子图

例： $G_1$ $G_1$ $12,34,56,78,90$ $K_5$

例： $K_5$ ，故彼得森图是不可平面图

定理 91：至少有 9 个点的简单可平面图的补图是不可平面的，而 9 是这种数目中最小的一个

例：找出一个 8 个顶点的可平面图，使其补图也是可平面的

例： $G$ $n$ $n \ge 11$ $G$ $G$ 的补图中至少有一个是非可平面图

解：

例： $G_i$ $n_i$ $m_i$ $i=1,2$ $G_1$ $G_2$ $n_1 + m_2 = n_2 + m_1$

证明：

涉及平面性的不变量简介

定义 100： $k$ $G$ $k$ $G$ 亏格 $\gamma(G)$

例：

$G$ $\gamma(G) = 0$
同胚的图是亏格相等
$\gamma(K_5) = 1$

定理 92： $\gamma$ $n$ $m$ $\varphi$ $n-m+\varphi =2-2\gamma$

因多面体可对应一个连通图，故定理对连通图也成立

推论： $G$ $n$ $m$ $\gamma$ 的连通图，则：

$\gamma \ge m/6-(n-2)/2$
$G$ $\gamma\ge m/4 -(n-2)/2$
$G$ $m=3(n-2+2\gamma)$
$G$ $m=2(n-2+2\gamma)$

定理 93： $n$ 是正整数，则

γ (K_{n}) = ⌈ \frac{(n - 3) (n - 4)}{12} ⌉

定理 94： $m,n$ 是正整数，则

γ (K_{m, n}) = ⌈ \frac{(m - 2) (n - 2)}{4} ⌉

定义 101： $G$ $k$ $G$ $k$ $G$ 厚度 $\theta(G)$

注： $G$ $\theta(G)=1$

定理 95： $n \ \ (n \ge 3)$ $m$ 条边的简单图，有

θ \geq \frac{m}{3 n - 6}

定理 96： $n \ne 4 \pmod{6}$ $n \ne 9$ ，则

θ (K_{n}) = ⌊ \frac{n + 7}{6} ⌋

定理 97： $m,n$ 是正整数，则

θ (K_{m, n}) = ⌊ \frac{m n}{2 (m + n - 2)} ⌋, θ (K_{n, n}) = ⌊ \frac{n + 5}{4} ⌋

定义 102： $G$ $G$ 叉数 $\eta(G)$

注： $G$ $\eta(G)=0$

定理 98： $m,n$ 是正整数，则

\begin{matrix} η (K_{n}) \leq \frac{1}{4} ⌈ \frac{n}{2} ⌉ ⌈ \frac{n - 1}{2} ⌉ ⌈ \frac{n - 2}{2} ⌉ ⌈ \frac{n - 3}{2} ⌉ \\ η (K_{m, n}) \leq \frac{1}{4} ⌈ \frac{m}{2} ⌉ ⌈ \frac{m - 1}{2} ⌉ ⌈ \frac{n}{2} ⌉ ⌈ \frac{n - 1}{2} ⌉ \end{matrix}

定义 103： $G$ $G$ 糙度 $\zeta(G)$

定理 99：完全图的糙度由下式给出

\begin{matrix} ζ (K_{3 n}) = {\begin{matrix} (\binom{n}{2}) & , 3 n \leq 15 \\ (\binom{n}{2}) + ⌊ \frac{n}{5} ⌋ & , 3 n \geq 15 \end{matrix} \\ ζ (K_{3 n + 1}) = (\binom{n}{2}) + 2 ⌊ \frac{n}{3} ⌋, 3 n + 1 \geq 19 a n d 3 n + 1 \neq 9 r + 7 a n d r 是 面 数 \\ ζ (K_{3 n + 2}) = (\binom{n}{2}) + ⌊ \frac{14 n + 1}{15} ⌋ \end{matrix}

平面性算法

定义 104： $H$ $G$ $E(G)\setminus E(H)$ $\sim$ $e_1 \sim e_2$ $W$ $W$ $e_1$ $e_2$ $W$ $H$ 不相交

$\sim$ $E(G) \setminus E(H)$ 上的一个等价关系

$G-E(H)$ $H$ -片段 $H$ 的公共顶点称为附着顶点

由片段的定义可直接推出：

$B$ $H$ $B$ 是连通图
$B$ $H$ 的内部不相交的路相连接
$H$ $H$ -片段没有公共顶点

例： $B_1,B_2,B_3,B_4$

定义 105： $C$ $G$ $G$ $C$ $B_1$ $B_2$ 是冲突的，如果

$B_1$ $B_2$ $C$ 上有三个公共的附着顶点；或
$C$ $v_1,v_2,v_3,v_4$ $v_1,v_3$ $B_1$ $v_2,v_4$ $B_2$ 的附着顶点

例：

注：冲突的两个片段无法同时平面嵌入到同一个面中

定义 106： $C$ $G$ $G$ $C$ $C$ -片段是冲突的，把这样得到的图称为 $C$ 的冲突图

例： $K_5$ 的哈密尔顿圈的冲突图

定理 100： $G$ $G$ $C$ ，其冲突图是二部图

证明：

定义 107： $H$ $G$ $H^{'}$ $H$ $B$ $H$ $B$ $H$ $H^{'}$ $f$ $B$ $H{'}$ $f$ 中是可画入的不可画入的 $F(B,H)=\{f | f 是 H^{'} 的面且 B 在 f 中可画入\}$

例： $H^{'}$ $B_3$ $B_2$ $f_2$ $f_3$ $F(B_1,H^{'})=\{f_1,f_3\}$

平面性算法

$G$ $G$ $H_1$ $H_1$ $H_i$ $H_{i+1}$

$E(G)\setminus E(H_i) = \Phi$ $G$ $H_i$ 的所有片段
$B$ $F(B,H_i)$
$B$ $F(B,H_i)=\Phi$ $G$ $H_i$ $|F(B,H_i)|$ $B$ $f\in F(B,H_i)$
$B$ $H_i$ $P_i$ $P_i$ $H_i$ $f$ $H_{i+1}=H_i \cup P_i$
$i= i + 1$ ，转第 1 步

例： $G$ 的平面性

解：

例：证明：每个 5 连通的简单图可平面图至少有 12 个顶点

证明： $G$ $\delta \ge \kappa \ge 5$
$2m = \sum d(v) \ge 5n$
$G$ $m \le 3n - 6$
$2.5n\le m \le 3n-6$ $n \ge 12$

例： $G$ $\delta \ge 3$ $G$ $deg(f) \le 5$

证明： $2m = \sum deg(f) \ge 6 \varphi$
$\varphi = 2 - n + m \le \frac{m}{3}$
$2m \le 3n - 6$
$\delta \ge 3$ $2m \ge 3n \ge 3n - 6$
这样导出矛盾！！

例： $G$ $G\cong G^*$ $m=2n -2$

证明： $G^*$ $n^*$ $n^* = \varphi$
$G \cong G^*$ $n^*=n$ $\varphi=n$
$G$ ，欧拉公式成立
$n-m+\varphi = n - m + n = 2$ $m = 2n - 2$

例：证明：不存在有 5 个面，且任意两个面之间至少存在一条公共边的平面图

证明： $G$ $G^*$ $G^*$ $K_5 \subseteq G^*$
$G^*$ 不是平面图，矛盾！！

例： $n\ge 3, \ \ S=\{x_1,x_2,\cdots,x_n\}$ $S$ $3n-6$ 个点对，它们之间的距离恰好为 1

证明：

第七章图的着色

图的边着色

排课表问题： $m$ $n$ $x_i$ $y_i$ $p_{ij}$ 节课。求如何在最少节次排完所有课

图论模型： $X=\{x_1,x_2,\cdots,x_m\},\ \ Y=\{y_1,y_2,\cdots,y_n\}$ $x_i$ $y_j$ $p_{ij}$ $G=(X,Y)$ $G$ $E$ $p$ $p$ 最小

$G$ 中给每条边着色，相邻边着不同色，至少需要的颜色数

定义 108： $G$ $G$ $G$ 正常边着色 $k$ $G$ $G$ 是 $k$ 边可着色的

定义 109： $G$ $G$ $G$ 边色数 $\chi^{'}(G)$

例： $\chi^{'} = 3$

定义 110： $G$ 正常边着色时，着相同颜色的边集称为该正常边着色的一个色组

偶图的边色数

$\chi^{'} \ge \Delta$

例： $K_{m,n}$ $\Delta$ $\chi^{'}(K_{m,n})=\Delta$

证明：

例： $K_{3,4}$ 正常边着色

解：

定义 111： $\pi$ $G$ $u$ $i$ ，则称 $u$ $i$ 色

定理 101 (König)： $G$ $\chi^{'}=\Delta$

证明：

一般简单图的边色数

引理： $G$ $x$ $y$ $G$ $\pi$ $G$ $k$ $x,y$ $x$ $G+xy$ $k$ 边可着色的

定理 102 (Vizing)： $G$ $\chi^{'}=\Delta$ $\chi^{'}=\Delta + 1$

证明：

$\Delta$ $\Delta + 1$ 的图

几类特殊简单图的边色数

定理 103： $G$ $G$ $\Delta(G)$ $G$ $\Delta(G)$ $\chi^{'}(G)=\Delta(G)$

证明：

定理 104： $G=(V,E)$ $n$ $n=2k+1$ $m > k\Delta$ $\chi^{'}=\Delta + 1$

证明：

例：试确定图中所给出的 4 个 5 阶图的边色数

解： $G_1$ $n=5=2\times 2 + 1$ $m=9$ $\Delta=4$ $m=9 > 8 = 2 \times 4$ $\chi^{'}(G_1)=\Delta + 1 = 5$
$G_2,G_3,G_4$ $m > k\Delta$ $\chi^{'}(G_2)=\Delta=4,\ \chi^{'}(G_3)=4,\ \chi^{'}(G_4)=3$

引理： $G$ $\Delta$ $\Delta>0$ $\chi^{'}=\Delta + 1$

证明：

例： $n=2k+1, \ k > 0$ $\chi^{'}(C_n)$ $\chi^{'}(K_n)$ $C_n$ $n$ 圈

解： $C_n$ $K_n$ $(n-1)$ $\chi^{'}(C_n) = 2 + 1= 3$ $\chi^{'}(K_n)=(n-1)+1=n$

例：求彼得森图的边色数

解： $\chi^{'} \ge 4$
所以，彼得森图的边色数为 4

定理 105： $G$ $\mu$ $\chi^{'} \le \Delta + \mu$

例： $\Delta + \mu$ $\Delta=4, \ \mu=2$

边着色的应用

排课表问题：

比赛安排问题：

顶点着色

定义 112： $G$ $G$ $G$ 正常顶点着色 $k$ $G$ $G$ 是 $k$ 可着色的

定义 113： $G$ $G$ 的点色数色数 $G$ $\chi(G)$ 表示

例：证明右图的色数是 4

注：对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。着同一种颜色的顶点集合称为一个色组，它们彼此互不相邻，所有又称为点独立集

定义 114： $k$ 的图称为 $k$ 色数

关于色数的若干结论

定理 106： $G$ $\chi \le \Delta + 1$

证明：

着色算法

$G=(V,E)$ $V=\{v_1,v_2,\cdots,v_n\}$ $\pi$ $C=\{1,2,\cdots,\Delta+1\}$

$\pi (v_1) = 1,\ \ i = 1$
$i=n$ $C(v_{i+1})=\{\pi(v_j) \ | \ j \le i,\ \ 并且 v_j 与 v_{i+1} 相邻\}$
$k$ $C \setminus C(v_{i+1})$ $\pi(v_{i+1})=k$
$i = i + 1$ ，转 (2)

例：试用着色算法给下图顶点着色

解： $\pi$ $C = \{1,2,\cdots,5\}$ ，着色过程如下：
$\pi(v_1)=1, \ \ C(v_2)=\{1\}, \ \ C \setminus C(v_2)=\{2,\cdots,5\}$
$\pi(v_2)=2, \ \ C(v_3)=\{1, 2\}, \ \ C \setminus C(v_3)=\{3,\cdots,5\}$
$\pi(v_3)=3, \ \ C(v_4)=\{3\}, \ \ C \setminus C(v_4)=\{1,2,4,5\}$
$\pi(v_4)=1, \ \ C(v_5)=\{1\}, \ \ C \setminus C(v_5)=\{2,\cdots,5\}$
$\pi(v_5)=2, \ \ C(v_6)=\{1,2,3\}, \ \ C \setminus C(v_6)=\{4,5\}$
$\pi(v_6)=4$

定理 107 (Brooks)： $G$ $G$ $\chi \le \Delta$

$G$ $\Delta_2(G) = \max\limits_{u \in V(G)} \max\limits_{v\in N(u) \ \ d(v) \le d(u)} d(v)$ $N(u)$ $G$ $u$ 相邻的点构成的集合。

$V_2(G)=\{v \ | \ v\in V(G) ， N(v) 中存在点 u，满足 d(u) \ge d(v)\}$ $\Delta_2(G)=\max\{d(v) | v \in V_2(G)\}$

$\Delta_2(G)$ $\Delta_2$ $\Delta_2(G) \le \Delta(G)$ $\Delta_2(G)$ $G$ 的次大度

例： $G_1$ $V_2(G_1)=\{v_1,v_2,v_3,v_4\},\ \ \ \Delta_2(G_1)=\max\{d(v) | v\in V_2(G_1)\}=1$

$G_2$ $V_2(G_2)=\{v_1,v_2,v_3,v_5,v_8,v_6,v_9\},\ \ \ \Delta_2(G_2)=\max\{d(v) | v\in V_2(G_2)\}=3$

定理 108： $G$ $\chi(G) \le \Delta_2(G)+1$

$\chi \le \Delta + 1$ 的一个改进！！！

例：考察简单图

解： $\chi \le \Delta = 5$
$\chi \le \Delta_2 + 1 = 4$

引理： $G$ $G$ $\chi \le \Delta$

四色定理 && 五色定理

定理 109 (Heawood)： $\chi \le 5$

顶点着色的应用

课程安排问题：

交通灯的相位设置问题：

与色数有关的几类图

定理 110： $G$ $k$ $k\ge 2$ ，则

$\delta \ge k - 1$
$G$ $k$ $G$ 的任意两个色组的并导出的子图是连通的

注意

唯一 1 可着色图是空图
唯一 2 可着色图是连通的偶图
唯一 4 可着色可平面图都是极大可平面图

色多项式的概念

假定与记号

假定着色是正常的点着色
假定所给图是标号图，即图中若某特定点着不同色，则视为不同的着色法
$P_k(G)$ $G$ $k$ 着色数目

$G$ $k$ $P_k(G)$ 表示

$P_k(G)$ $k$ $G$ 的色多项式

$\chi(G)$ $P_k(G)$ 的定义，有

$k<\chi(G)$ $P_k(G)=0$ $\chi(G)=\min\{k|P_k(G)\ge 1\}$
$G$ $n$ $P_k(G)=k^n$
$P_k(K_n)=k(k-1)\cdots(k-n+1)$
$G$ $n$ $P_k(G)=k^nP_k(G^{'})$ $G^{'}$ $G$ $n$ 个孤立点后所得的图
$G$ $k$ 着色数目与原图一样
$G$ $n$ $P_k(G)=k(k-1)^{n-1}$

递推计数法 (掌握一种即可)

$G\cdot e$ $G$ $e$ $e$ 的端点后所得的图

定理 111： $G$ $G$ $e$ $P_k(G)=P_k(G-e)-P_k(G\cdot e)$

证明： $e=uv$ $G-e$ $k$ 着色可分为两类
$u$ $v$ $k$ $G$ $P_k(G)$ 个
$u$ $v$ $k$ $G\cdot e$ $P_k(G\cdot e)$ 个
$P_k(G-e)=P_k(G)+P_k(G\cdot e)$
$P_k(G)=P_k(G-e)-P_k(G\cdot e)$

推论： $e=uv$ $G$ $d(u)=1$ $P_k(G)=(k-1)P_k(G-u)$

注意

当图的边数较少时，使用减边递推法
当图的边数较多时，使用加边递推法

例： $G_1,G_2,G_3$ 如图所示，分别求其色多项式

解：为了方便起见，递推的中间过程直接由图表示
注：递推计数法的计算复杂度是指数型的

理想子图法 (必须掌握)

定义 115： $H$ $G$ $H$ $H$ $G$ 理想子图 $N_r(G)$ $G$ $r$ 个分支的理想子图的个数

例： $G$ 的全部理想子图

解：
$N_3(G)=2$
$N_4(G)=6$
$N_5(G)=5$
$N_6(G)=1$

定理 112： $G$ $n$ $m$ 条边的简单图，则有

$N_n(G)=1$
$N_{n-1}(G)=m$
$k < \omega(G)$ $N_k(G) = 0$

定理 113： $q_r(G)$ $G$ $V$ $r$ $q_r(G)=N_r(\overline G), \ \ r=1,2,\cdots,|V|$

$k$ $G$ 正常着色，可以这样来计算着色方式数：

$\cdots$ $n$ 的方式数

推论： $n$ $G$ $P_K(G)=\sum\limits^n_{i=1}N_i(\overline G)[k]_i$ $[k]_i=k(k-1)\cdots(k-i+1)$

定义 116： $G$ $N_i(G)=r_i$ $h(G,x)=\sum\limits^n_{i=1}r_ix^i$ $G$ 的伴随多项式

着色算法： $G$ $x^i$ $[k]_i$ $G$ $P_k(G)$

例： $G$ $P_k(G)$

解： $G$ 的补图为：
$h(\overline G,x)=\sum\limits^n_{i=1}r_ix^i=2x^3+6x^4+5x^5+x^6$
$x^i = [k]_i$ $P_k(G)$ ：
$\begin{aligned} P_{k} (G) & = 2 [k]_{3} + 6 [k]_{4} + 5 [k]_{5} + [k]_{6} \\ = 2 k (k - 1) (k - 2) + 6 k (k - 1) (k - 2) (k - 3) \\ + 5 k (k - 1) (k - 2) (k - 3) (k - 4) \\ + k (k - 1) (k - 2) (k - 3) (k - 4) (k - 5) \end{aligned}$

定理 114： $G$ $t$ $H_1,H_2,\cdots,H_t$ $H_i$ $h(H_i,x), \ \ i = 1,2,\cdot,t$ $h(G,x)=\prod\limits^t_{i=1}h(H_i,x)$

$G$ 的补图的伴随多项式时，可以分别求出它的每个分支的伴随多项式，然后将它们作乘积

例： $G$ $P_k(G)$

解： $G$ 的补图
求出补图中各个分支的伴随多项式
$h(H_1,x)=x$
$h(H_2,x)=x+x^2$
$h(H_3,x)=x+x^2$
$h(\overline G,x)=x(x+x^2)^2 = x^3+2x^4+x^5$
$G$ 的色多项式：
$\begin{aligned} P_{k} (G) & = k (k - 1) (k - 2) + 2 k (k - 1) (k - 2) (k - 3) \\ + k (k - 1) (k - 2) (k - 3) (k - 4) \\ = k (k - 1) (k - 2) (k^{2} - 5 k + 7) \end{aligned}$

色多项式的性质

定理 115： $n$ $G$ $P_k(G)$ $k$ $n$ $k^n$ ，常数项为零，并且各项系数的符号正负相间

证明：

注意

$k^4-3k^3+3k^2$ 便不是任何图的色多项式
$G_1$ $G_2$ $P_k(G_1)=P_k(G_2)=k^2(k-1)^2$

第八章 Ramsey 定理

独立集与覆盖

定义 117： $G = （V,E)$ $V$ $V_1$ $G$ 独立集 $V_1$ $G$ $G$ 最大独立集 $G$ 的点独立数独立数 $\alpha(G)$

例：

定义 118： $G = （V,E)$ $V$ $K$ $G$ 覆盖 $E$ $K$ 中

定义 119： $G$ $G$ 最小覆盖 $G$ $G$ 的点覆盖数覆盖数 $\beta(G)$

例：

定理 116： $G=(V,E)$ $S \subseteq V$ $S$ $G$ $V\setminus S$ $G$ 的覆盖

证明：

定理 117 (Gallai)： $n$ $G$ $\alpha(G) + \beta(G) = n$

边独立集与边覆盖

定义 120： $G = （V,E)$ $E$ $E_1$ $G$ 边独立集 $E_1$ $G$ $G$ 最大边独立集 $G$ 边独立数 $\alpha^{'}(G)$

例：

注：一个边独立集实际上就是图的一个匹配，一个最大边独立集就是图的一个最大匹配

定义 121： $G = （V,E)$ $E$ $L$ $G$ 边覆盖 $G$ $L$ $G$ $G$ 最小边覆盖 $G$ 边覆盖数 $\beta^{'}(G)$

例：

定理 118 (Gallai)： $n$ $G$ $\alpha^{'}(G) + \beta^{'}(G) = n$

证明：

例： $G$ $\alpha, \ \beta,\ \alpha^{'},\ \beta^{'}$

解： $K_4$ $\alpha(G) = 2$ $\beta(G)=5$
$G$ $G$ $\alpha^{'} \le 3$
$G$ $\alpha^{'}(G) \ge 3$
$\alpha^{'}(G) = 3$ $\beta^{'}(G) = 4$

定理 119: $G$ $G$ 中最大独立集包含的顶点数等于最小边覆盖包含的边数

Ramsey 数 R(m, n)

定义 122： $m$ $n$ $R(m,n)$ $\lambda$ $\lambda$ $m$ $n$ $R(m,n)$ 称为 $(m,n)$ Ramsey 数

$R(m,n)=R(n,m), \ \ R(1,n)=R(n,1)=1$

例： $R(2, n); \ \ R(3, 3)$

解： $R(2, n) = n; \ \ R(3,3) = 6$

定理 120: $m$ $n$ $m, n \ge 2$ $R(m, n) \le R(m, n - 1) + R(m - 1, n)$ $R(m, n -1)$ $R(m-1,n)$ 都是偶数，则上面不等式严格成立

例： $R(2, 5) = 5, \ \ R(3, 4) = 9$ $R(3, 5)$ $R(4,4)$

解： $R(3, 5) \le R(2, 5) + R(3, 4) = 14$
$R(4, 4) \le R(3, 4) + R(4, 3) = 18$

第九章有向图

有向图

定义 123：有向图 $V(D)$ $E(D)$ $(V(D), E(D))$ $D=(V(D), E(D))$ $D=(V,E)$ $V \cap E = \Phi$ $E$ $V$ $V$ 中的元素称为顶点点 $E$ 中的元素称为有向边或弧，也简称边

定义 124： $e$ $<u,v>$ $e=<u,v>$ $u$ $e$ 的始点起点 $v$ $e$ 的终点

定义 125： $D$ $<u, v>$ $uv$ $D$ 的基础图

定义 126： $G$ $G$ $uv$ $<u, v>$ $<v, u>$ $G$ 的定向图

注：有向图的基础图唯一，而一个图的定向图并不唯一

例：下图中，前两个为有向图，它们都是后一个的定向图

定义 127： $v$ $D$ $D$ $v$ $v$ 出 (入) $d^+(v) (d^-(v))$ $v$ $v$ 度 $d(v)$

例：对下图所示有向图，有

$d^+(a)=1, \ \ d^-(a)=2, \ \ d(a) = 3$
$d^+(b)=1, \ \ d^-(b)=2, \ \ d(b) = 3$

定理 121: $D=(V,E)$ $\sum\limits_{v\in V}d^+(v)=\sum\limits_{v\in V}d^-(v)=|E|$

定义 128： $n$ $n$ $n$ 重边 $n$ 称为这些边的重数。重数大于 1 的边也称为重边，重数等于 1 的边也称为单边。既无环又无重边的有向图称为简单有向图

定义 129： $D=(V,E)$ $V=\{v_1,v_2,\cdots,v_n\}, \ E=\{e_1,e_2,\cdots,e_m\}$

$A(D)=(a_{ij})_{n\times n}$ $D$ 邻接矩阵 $a_{ij}$ $v_i$ $v_j$ $1 \le i \le n,\ \ 1 \le j \le n$
$D$ $M(D)=(m_{ij})_{n \times m}$ $D$ 的关联矩阵，其中

\begin{matrix} m_{i j} = {\begin{matrix} 1 & , v_{i} 是 有 向 边 e_{j} 的 始 点 \\ - 1 & , v_{i} 是 有 向 边 e_{j} 的 终 点, 1 \leq i \leq n, 1 \leq j \leq m \\ 0 & , 其 他 \end{matrix} \end{matrix}

$A(D)$ $i$ $d^+(v_i)$ $d^-(v_i)$

例： $D_1$ $D_2$ $A(D_1)$ $M(D_2)$

解：

有向图的连通性

定义 130： $D$ 有向途径 $\varGamma = v_0e_1v_1e_2\cdots e_kv_k$ $1 \le i \le k$ $e_i$ $v_{i-1}$ $v_i$ $v_0$ $v_k$ $\varGamma$ 的起点终点 $k$ $\varGamma$ 的长度

定义 131：边不相同的有向途径称为有向迹

$A$ $D$ $A^m$ $i$ $j$ $D$ $v_i$ $v_j$ $m$ 的有向途径数目

定义 132： $u$ $v$ $D$ $D$ $(u,v)$ $D$ $u$ $v$ $u \rightarrow v$ $u \rightarrow u$

定义 133： $u \rightarrow v$ $v \rightarrow u$ $u$ $v$ 可互达 $u \leftrightarrow v$ $\leftrightarrow$ $V(D)$ 上的一个等价关系

定义 133： $D=(V,E)$ 为一个有向图：

$\forall u, v \in V$ $u$ $v$ $D$ 是强连通的
$\forall u, v \in V$ $u \rightarrow v$ $v \rightarrow u$ $D$ 是单向连通的
$D$ $D$ 是弱连通的，简称连通

注：强连通一定单向连通，单向连通一定弱连通

例： $D_1,D_2,D_3$ $D_1,D_2$ $D_1$ 为强连通图

定理 122: $D=(V,E)$ $D$ 中存在含有所有顶点的有向闭途径

例：判断下图是否为强连通图

解：该图是强连通的。因为该图存在经过所有顶点的有向闭途径 124651351

定义 134： $D^{'}$ $D=(V,E)$ $D^{'}$ $D$ $D^{'}$ $D^{'}$ $D$ 的一个强连通分支 (单向连通分支、弱连通分支)

例： $D$ 的强连通分支、单向连通分支

解： $D$ 的强连通分支：
$D$ $D$ 本身

定理 123: $D=(V,E)$ $D$ 的一个强 (弱) 连通分支中

$D$ $D$ 的若干个单向连通分支。因为单向连通关系不是等价关系

图的定向问题

定理 124: $G$ $G$ 存在强连通定向图

有向树、跟树

定义 135： $D$ $D$ 为有向树

例：

定义 136：恰有一个顶点的入度为 0，其余顶点的入度均为 1 的非平凡树称为根树。跟树中入度为 0 的顶点称为树根，出度为 0 的顶点称为树叶，其余点称为内点，内点和根统称为分支点

习惯是我们把根树的根画在最上方，并使有向边的方向均指向下方，对这种标准画法，有向边的箭头还可省去

例：

定义 137： $v$ $v$ 的层数，所有顶点的最大层数称为该树的高

定义 138： $u\ne v \ and \ u \rightarrow v$ $u$ $v$ 祖先 $v$ $u$ 后代 $<u, v>$ $u$ $v$ 父亲 $v$ $u$ 儿子 $n$ $n$ 个顶点称为兄弟

定义 139： $v$ $T$ $v$ 及其所有后代导出的子图为 $v$ 为根的子树

m 元树

定义 140： $T$ $m$ $T$ m 元树 $m$ $T$ 为 m 元完全树

例：

定理 125: $m$ $T$ $t$ $i$ $(m-1)i = t - 1$

证明： $T$ $t+i$ $T$ $t+i-1$ 条边
$m$ $m$ $T$ $mi$ 。再由有向图中所有顶点的出度之和等于边数可得：
$m i = t + i - 1 \Rightarrow (m - 1) i = t - 1$

例： $(m = 2)$ $i = t−1$ $m(T) = 2(t − 1)$ $h$ $h + 1$ 片叶子

最优树

定义 141： $T$ $t$ $T$ $t$ $w_1,w_2,\cdots,w_t$ $T$ 带权二元树 $w_i$ $l(w_i)$ $W(T) = \sum\limits^t_{i=1}w_il(w_i)$ $T$ 权 $w_1,w_2,\cdots,w_t$ $w_1,w_2,\cdots,w_t$ $W(T)$ 最小的二元树称为最优树

例： $T_1$ $T_2$ $T_3$ 如图所示，试求它们的权

解：由带权二元树的定义，有：
$\begin{matrix} W (T_{1}) = 1 \times 2 + 2 \times 2 + 3 \times 2 + 4 \times 2 = 20 \\ W (T_{2}) = 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 3 = 26 \\ W (T_{3}) = 1 \times 3 + 2 \times 3 + 3 \times 2 + 4 \times 1 = 19 \end{matrix}$
$T_3$ 是最优树

例：求带权 1，2，4，5，6，8 的最优二元树

解：求解过程如下
$T$ $W(T) = (1+2) \times 4 + 4 \times 3 + (5+6+8) \times 2 = 62$

图论

第一章 图的基本概念

图的定义

图的同构

完全图 & 偶图 & 补图

度 & 度序列

度的频序列

子图

图的运算

途径 & 迹 & 路 & 圈 & 距离 & 直径

图的连通性

偶图判断定理

赋权图

最短路问题

邻接矩阵

关联矩阵

邻接谱

图的邻接代数

图空间 (几乎不考)

l 部图的概念与特征

Turán 定理

Turán 定理应用

第二章 树

树的概念

树的性质

树的中心

树的形心

生成树的概念 & 性质

生成树的计数

回路系统简介

Kruskal 算法

破圈法

Prim 算法

第三章 图的连通度

割边及其性质

割点及其性质

块及其性质

连通度和边连通度

连通度的性质

Menger 定理

应用

图的宽距离和宽直径

第四章 Euler 图 & Hamilton 图

欧拉图

Fleury 算法

中国邮递员问题

哈密尔顿图

应用

度极大的非 Hamilton 图

旅行售货员问题

E 图和 H 图的联系

第五章 匹配与因子分解

图的匹配

Berge 定理

偶图的匹配与覆盖问题的提出

偶图的匹配存在性判定定理

点覆盖与 König 定理

Tutte 定理与完美匹配

因子分解

1-因子分解

2-因子分解

森林分解

完全图的森林分解方法

最优匹配 & 匈牙利算法 (几乎不考)

匈牙利算法 (几乎不考)

最优匹配 (几乎不考)

匹配在矩阵理论中的应用

第六章 平面图

平面图的概念

平面图的性质

平面嵌入概念的推广

凸多面体与平面图

极大平面图及其性质

极大外平面图及其性质

对偶图

平面图的判定

涉及平面性的不变量简介

平面性算法

第七章 图的着色

图的边着色

第一章图的基本概念

第二章树

第三章图的连通度

第五章匹配与因子分解

第六章平面图

第七章图的着色

第九章有向图