9 有向图 - Kloudy Shape

重点概念

1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图

图
简单图
图的度序列
注：度序列的判定问题是重点.
图的图序列
注：图序列的判定问题是重点.
子图 (生成子图和导出子图)
图的同构
补图与自补图
注：要求掌握自补图的性质.
联图
(Cartesian)积图, 字典积图(合成图)
最短路算法 (Dantzig 或 Dijkstra 算法)
二部图(偶图)
注: 掌握偶图的判定 (1.3)、正则偶图的相关结果.
1. 若 $G$ 是 $k$ 正则二部图 ( $k > 0$ ), 则 $G$ 存在完美匹配. (5.2)
2. 若 $G$ 为 $k$ 正则二部图 ( $k \geq 2$ ), 则 $G$ 无割边. (3.1)
图的矩阵表示: 邻接矩阵、关联矩阵、Laplacian矩阵、图的谱.
注: 掌握计算及的相关结果、邻接矩阵的谱 $S p e c (A)$
注: 要求熟练掌握两种矩阵的性质.

2、树、森林, 生成树, 最小生成树、根树、完全m元树

树、森林
树的中心与形心
生成树
生成树棵数的计算(包括递推计数和矩阵树定理).
最小生成树
注：要求熟练掌握最小生成树的求法.
根树
完全m元树
注：对于完全m元树, 要弄清其结构.
最优二元树的求法及其权值
注: 要求熟练掌握最优二元树的求法.

3、途径 (闭途径), 迹 (闭迹), 路 (圈), 最短路, 连通图, 连通分支, 点连通度与边连通度, 块, 块与 2-连通的关系.

注：上面概念分别在1和3章

割边, 割点和块
连通度

注：要求掌握相关性质及其证明.

4、欧拉图, 欧拉环游, 欧拉迹, 哈密尔顿圈, 哈密尔顿图, 哈密尔顿路, 中国邮路问题, 最优H圈, 度极大非H图

欧拉图与欧拉环游
欧拉迹
注: 中国邮递员问题是欧拉图的重要应用.
哈密尔顿图与哈密尔顿圈
注: TSP问题是哈密尔顿问题的重要应用.
哈密尔顿路
度极大非H图
E图与H图的联系——线图L(G)

5、匹配、最大匹配、完美匹配、最优匹配、因子分解

匹配
最大匹配与完美匹配
最优匹配
因子分解
注：要弄清楚因子分解和完美匹配之间的联系与区别.
注: 要弄清楚因子分解,完美匹配,边色数之间的联系与区别.

6、平面图、极大平面图、极大外平面图、平面图的对偶图

平面图
极大平面图
极大外平面图
平面图的对偶图

7、边色数、点色数、色多项式

边色数
点色数
色多项式

8、强连通图、单向连通图、弱连通图

强连通图
弱连通图
单向连通图

9、Ramsey 数

Ramsey 数的定义
简单 Ramsey 数的计算

重要结论

1、握手定理及其推论

图 $G = (V, E)$ 中所有顶点的度的和等于边数 $m$ 的 $2$ 倍, 即:

∑v∈V(G)d(v)=2m\sum_{v \in V(G)} d(v)=2m

推论 1: 在任何图中, 奇度点的个数为偶数.

推论 2: 正则图的阶数和度数不同时为奇数.

2、Turán 定理 (托兰定理, 图兰定理)

若 $n$ 阶简单图 $G$ 不包含 $K_{l+1}$ , 则 $G$ 度弱于某个完全 $l$ 部图 $H$ , 且若 $G$ 具有与 $H$ 相同的度序列, 则:

G≅HG\cong H

若 $G$ 是简单图, 并且不包含 $K_{l+1}$ , 则:

m(G)≤m(Tl,n)m(G)\leq m(T_{l,n})

仅当 $G≅Tl,nG\cong T_{l,n}$ 时, 有 $m(G) = m(T_{l,n})$ .

(不包含 $K_{l+1}$ 的 $n$ 个顶点的简单图中, Turán 图 $T_{l,n}$ 边数最大)

3、树的性质

设 $T$ 是 $(n, m)$ 树, 则: $m = n - 1$ .

4、最小生成树算法

Kruskal 算法

破圈法

Prim 算法

5、偶图判定定理

(König, 1936) 一个图是二部图当且仅当它不包含奇圈.

图 $G$ 是偶图当且仅当 $G$ 中没有奇回路.

6、Menger 定理 (敏格尔定理)

(1) 设 $x$ 与 $y$ 是图 $G$ 中的两个不相邻点, 则 $G$ 中分离点 $x$ 与 $y$ 的最少点数等于内部不交 (独立的) $x, y$ 路的最大数目;

(2) 设 $x$ 与 $y$ 是图 $G$ 中的两个不同点, 则 $G$ 中分离点 $x$ 与 $y$ 的最少边数等于 $G$ 中边不重的 $x, y$ 路的最大数目.

7、欧拉图、欧拉迹的判定

下列陈述对于非平凡连通图 $G$ 是等价的:

(1) $G$ 是欧拉图;
(2) $G$ 的每个顶点的度均为偶数;
(3) $G$ 的边集能划分为边不交圈的并.

推论: 连通图 $G$ 是半欧拉图当且仅当 $G$ 中恰有两个顶点度数为奇数.

8、H 图的判定

必要条件

若 $G$ 为 H 图, 则对 $V (G)$ 的任一非空顶点子集 $S$ , 有:

ω (G - S) \leq ∣ S ∣

充分条件：Dirac 定理 (Dirac,1952)

(1) 对于 $n \geq 3$ 的简单图 $G$ , 如果 $G$ 中有:

δ (G) \geq n / 2

那么, $G$ 是 H 图.

(2) 设 $G$ 是 $2$ -连通的 $n \geq 3$ 阶图. 若 $G$ 的每个顶点的度都不小于 $k$ , 则 $G$ 中包含一条长度至少为 $2 k$ 的圈或 H 圈.

充分条件：Ore 定理 (Ore, 1960)

对于 $n \geq 3$ 的简单图 $G$ , 如果 $G$ 中的任意两个不相邻顶点 $u$ 与 $v$ , 有:

d (u) + d (v) \geq n

那么, $G$ 是 H 图.

闭包定理 (帮迪 Bondy-Chvátal, 1976)

图 $G$ 是 H 图当且仅当它的闭包是 H 图.

Chvátal 定理: 度序列判定法 (Chvátal, 1972)

设简单图 $G$ 的度序列是 $d_1,d_2, …,d_n)$ , 其中, $d_1 ≤ d_2 ≤ … ≤ d_n$ , 并且 $n \geq 3$ . 若对任意的 $1 \leq i < n / 2$ , 有 $d_i>i$ , 或 $d_{n−i} ≥ n−i$ , 则 $G$ 是 H 图.

(等价表述) 设简单图 $G$ 的度序列是 $d_1,d_2, …,d_n)$ , 其中, $d_1 ≤ d_2 ≤ … ≤ d_n$ , 并且 $n \geq 3$ . 若不存在 $1 \leq i < n / 2$ , 使得 $d_i≤i$ 并且 $d_{n−i} < n−i$ , 则 $G$ 是 H 图.

定理

设 $G$ 是 $n$ 阶简单图. 若 $n \geq 3$ 且 $∣E(G)∣>(n−12)+1|E(G)|>\binom{n-1}{2} +1$ , 则 $G$ 是 H 图;
并且, 具有 $n$ 个顶点, $(n−12)+1\binom{n-1}{2} +1$ 条边的非 H 图只有 $C_{1,n}$ 以及 $C_{2,5}$ .

9、偶图匹配与因子分解

Hall 定理

设 $G = (X, Y)$ 是二部图, 则 $G$ 存在饱和 $X$ 每个顶点的匹配的充要条件是: 对 $\forall S \subseteq X$ , 有 $∣ N (S) ∣ \geq ∣ S ∣$ . ( $N (S)$ 表示 $S$ 的邻点的集合)

注: $S$ 是 $X$ 的任意子集, 故 $S$ 可以为空集.

推论

若 $G$ 是 $k$ 正则二部图 ( $k > 0$ ), 则 $G$ 存在完美匹配.

König 定理 (哥尼定理)

(König,Egerváry,1931) 在二部图中, 最大匹配的边数等于最小点覆盖的顶点数.

注: 在矩阵 (如布尔矩阵) 中的应用.

(Kőnig,1916) 设 $G$ 是无孤立点的二部图, 则 $G$ 中最大点独立集包含的顶点数等于最小边覆盖所包含的边数.

定理

$K_{2n}$ 可 $1$ 因子分解.

定理

具有 H 圈的三正则图可 $1$ 因子分解.

定理

$K_{2n+1}$ 可 $2$ 因子分解.

定理

$K_{2n}$ 可分解为一个 $1$ 因子和 $n - 1$ 个 $2$ 因子之和.

定理

每个没有割边的 $3$ 正则图是一个 $1$ 因子和 $1$ 个 $2$ 因子之和.

$3$ 正则无桥图存在完美匹配. (5.3)

每个至多包含 $2$ 条割边 (桥) 的三正则图都存在完美匹配. (5.3)

最优匹配算法

10、平面图及其对偶图

平面图的次数公式

设 $G = (n, m)$ 是平面图, 则:

∑f∈Φdeg⁡⁡(f)=2m\sum_{f\in \Phi}\deg⁡(f)=2m

平面图的欧拉公式

(Euler, 1752) 设 $G = (n, m)$ 是连通平面图, $ϕ\phi$ 是 $G$ 的面数, 则:

n−m+ϕ=2n-m+\phi=2

推论1

设 $G$ 是具有 $n$ 个点 $m$ 条边 $ϕ\phi$ 个面的连通平面图, 如果对 $G$ 的每个面 $f$ , 有: $deg⁡(f)≥l≥3\deg(f)≥l ≥3$ , 则:

m≤ll−2(n−2)m≤\frac{l}{l-2}(n-2)

推论2

设 $G$ 是具有 $n$ ( $n \geq 3$ ) 个点 $m$ 条边 $ϕ\phi$ 个面的简单平面图, 则:

m \leq 3 n - 6

设 $G$ 是具有 $n$ ( $n \geq 3$ ) 个点 $m$ 条边 $ϕ\phi$ 个面的简单平面二部图, 则:

m \leq 2 n - 4

推论3

设 $G$ 是具有 $n$ 个点 $m$ 条边的简单平面图, 则: $δ \leq 5$

注

掌握证明方法.

对偶图的性质

平面图 $G$ 的对偶图必然连通.

极大平面图的性质

设 $G$ 是 $n$ 阶 ( $n \geq 3$ ) 简单平面图, 则下面命题等价:

(1) $G$ 是极大平面图;
(2) $G$ 每个面的次数是 $3$ , 亦称作三角剖分 (triangulation);
(3) $G$ 有 $3 n - 6$ 条边.

设 $G$ 是至少有 $3$ 个顶点的平面图, 则 $G$ 是极大平面图, 当且仅当 $G$ 的每个面的次数是 $3$ 且为单图 (简单图).

11、着色问题

边着色

定理

$χ^′ (K_{m,n})=Δ$ .

定理

(哥尼 König, 1916) 若 $G$ 是二部图, 则 $χ^′(𝐺)=Δ$ .

Vizing 定理 (维津定理)

(Vizing[1964], Gupta[1966]) 若 $G$ 是简单图, 则:

χ′(G)=Δ+1χ^′ (G)=Δ \text{ 或 } χ^′ (G)=Δ+1

定理

设 $G$ 是简单图且 $Δ (G) > 0$ . 若 $G$ 中只有一个最大度点或恰有两个相邻的最大度点, 则: $χ^′ (G)=Δ(G)$ .

定理

设 $G$ 是简单图. 若顶点数 $n = 2 k + 1$ 且边数 $m > k Δ$ , 则: $χ^′ (G)=Δ(G)+1$ .

定理

设 $G$ 是奇数阶 $Δ$ 正则简单图, 若 $Δ > 0$ , 则: $χ^′ (G)=Δ(G)+1$ .

点着色

定理

对任意的图 $G$ , 有: $χ (G) \leq Δ (G) + 1$ .

Brooks 定理 (布鲁克斯定理)

(Brooks, 1941) 若 $G$ 是连通的简单图, 并且它既不是奇圈, 又不是完全图, 则: $χ (G) \leq Δ (G)$ .

色多项式

递推计数法

设 $G$ 为简单图, 则对任意 $e \in E (G)$ 有:

Pk(G)=Pk(G−e)−Pk(G⋅e)P_k(G) = P_k(G-e) - P_k(G \cdot e)

理想子图计数方法

用理想子图法求 $P_k(G)$ 的步骤如下:

(1) 画出 $G$ 的补图 $G‾\overline{G}$ .

(2) 求出关于补图的 $ri=Ni(G‾),(1≤i≤n)r_i=N_i (\overline{G}),(1≤i≤n)$ .

(3) 写出关于补图的伴随多项式 $h(G‾,x)=∑i=1nrixih(\overline{G},x) = \sum_{i=1}^n r_i x^i$ .

(4) 将 $x^i=[k]_i$ 代入伴随多项式中得到 $P_k(G)$ .

12、根树问题

定理

在完全 $m$ 元树 $T$ 中, 若树叶数为 $t$ , 分支点数为 $i$ , 则:

(m - 1) i = t - 1

图论应用

重点掌握如下两方面应用

1、偶图匹配问题

学生能找到理想工作吗 (5.2)

2、着色问题

边着色问题

排课表问题 (7.1)

比赛安排问题 (7.1)

点着色问题

课程安排问题 (7.2)

交通灯的相位设置问题 (7.2)

附录: 主要符号表

常见的图

符号	含义
$G$	无向图
$T$	树, 森林
$D$	有向图
$P_n$	$n$ 个点的路
$W$	途径
$C$	圈
$K_n$	完全图
$K_{m,n}$	完全二部图
$Q_n$	超立方体
$T_{l,n}$	Turán 图 (1.6)
$H_{k,n}$	哈拉里图 (3.2)
$C_{m,n}$	$C_{m,n}$ 图 (4.4)
$Ω(F)\Omega (\mathcal{F})$	集族的交图 (1.7)

图的集合

符号	含义
$V={v…}V=\{v \ldots\}$	顶点集
$E={e…}E=\{e \ldots\}$	边集
$\vert V\vert$	顶点数, 图的阶数
$\vert E \vert$	边数
$S$	顶点集的子集
$N (S)$	点子集 $S$ 的邻点的集合
$Φ={f…}\Phi=\{f \ldots\}$	平面图的面组成的集合
$ϕ\phi$	平面图的面数
$M$	匹配 (边子集)
$K$	覆盖 (点或边子集)
$B_i$	图的块 (3.1)
$B_i$	图的 $H$ -片断 ( $H$ 为 $G$ 的子图) (6.4)

图的属性

符号	含义
$d (v)$	顶点的度
$d^+(v)$	(有向图) 顶点的出度
$d^-(v)$	(有向图) 顶点的入度
$deg⁡(f)\deg( f )$	面的次数

$δ (G)$	图的最小度
$Δ (G)$	图的最大度
$κ (G)$	图的 (点) 连通度
$λ (G)$	图的边连通度
$t (G)$	图的坚韧度

$α(G)\alpha(G)$	图的 (点) 独立数
$β(G)\beta(G)$	图的 (点) 覆盖数
$α′(G)\alpha'(G)$	图的边独立数
$β′(G)\beta'(G)$	图的边覆盖数

$χ (G)$	图的点色数
$χ^{'} (G)$	图的边色数
$c l (G)$	图的团数 (7.4)
$θ (G)$	图的完全数 (7.4)

$d (u, v)$	两点的距离
$e (v)$	点的离心率 (2.2)
$d (G)$	图的直径 (2.2, 1.3)
$r (G)$	图的半径 (2.2)
$ω(G)\omega(G)$	图的 (连通) 分支数
$o (G)$	图的奇分支数

$τ(G)\tau (G)$	图的生成树棵数
$w (e)$	(边赋权图) 边的权值
$W (H)$	图的权值
$h (G)$	图的哈密尔顿指数 (4.7)
$σ (G)$	图的荫度 (5.4)
$r (m, n)$	Ramsey 数 (8.2)

图的关系

符号	含义
$u \leftrightarrow v$	顶点 $u$ 与 $v$ 相邻或邻接
$ф_D$	(有向图) 关联函数
$≅\cong$	同构
$H \subseteq G$	$H$ 为 $G$ 的子图
$H \subset G$	$H$ 为 $G$ 的真子图

图的运算

符号	含义
$G‾\overline{G}$	图的补图
$G^*$	图的对偶图
$G[V^′]$	点导出子图
$G[E^′]$	边导出子图
$G-V^′, G-v$	图的删点运算
$G−E^′, G-e$	图的删边运算
$G_1-G_2$	图的差
$G_1∪G_2$	图的并
$G_1+G_2$	图的不交并
$G_1∩G_2$	图的交
$G1△G2G_1 \bigtriangleup G_2$	图的对称差, 异或
$G1∨G2G_1 \vee G_2$	图的联
$G1□G2G_1 \square G_2$	Cartesian 积图
$G_1 [G_2]$	图的合成, 字典积
$G_1×G_2$	图的张量积
$\cdot e$	收缩 (2.3)
$c (G)$	图的闭包 (4.3)
$L (G)$	图的线图 (4.7)
$L^n(G)$	图的 $n$ 次迭代线图 (4.7)
$S_n(G)$	图的 $n$ 次剖分图 (4.7)
$L_n(G)$	图的 $L_n(G)$ 图 (4.7)
$B (G)$	图的块割点树 (3.1)

图的矩阵

(1.5)

符号	含义
$A (G)$	图的邻接矩阵
$M (G)$	图的关联矩阵
$D (G)$	图的度矩阵
$L (G)$	图的 Laplacian 矩阵
$S p e c (G)$	图的邻接谱

涉及平面性的不变量

(6.3)

符号	含义
$g(Σ)g(\Sigma)$	曲面的亏格
$g (G)$	图的亏格
$c(Σ)c(\Sigma)$	闭曲面的欧拉示性数
$θ(G)\theta(G)$	图的厚度
$c r (G)$	图的交叉数

图的色多项式

(7.5)

符号	含义
$P_k(G)$	图的色多项式
$N_r(G)$	图的具有 $r$ 个分支的理想子图的个数
$q_r (G)$	将简单图的顶点集合划分为 $r$ 个不同色类的划分数
$x^i=[k]_i$	$k(k−1)(k−2)⋯(k−i+1)k(k-1)(k-2)\cdots(k-i+1)$
$h (G, x)$	图的伴随多项式

附录：一些前置知识

集合运算

差集 $A\BA \backslash B$ : (在集合 $A$ 中, 但不在集合 $B$ 中的所有元素)

排列组合

符号	含义
$(nm)\binom{n}{m}$	组合数 (从 $n$ 个不同元素中取出 $m (m \leq n)$ 个元素的所有组合的个数)
$C_{n}^{m}$	组合数
$A_{n}^{m}$	排列数

Anm=n(n−1)⋯(n−m+1)=n!(n−m)!Cnm=Anmm!=n!m!(n−m)!=Cnn−m\begin{aligned} A_{n}^{m} &=n(n-1)\cdots(n-m+1)=\frac{n!}{(n-m)!} \\ C_{n}^{m} &={\frac{A_{n}^{m}}{m!}}={\frac{n!}{m!(n-m)!}}=C_{n}^{n-m} \end{aligned}

等价关系

设 $R$ 是非空集合 $A$ 上的二元关系, 若 $R$ 是自反的、对称的、传递的, 则称 $R$ 是 $A$ 上的等价关系.