《图论与网络优化》学习笔记（第6-8章）-Toy模板网

这篇具有很好参考价值的文章主要介绍了《图论与网络优化》学习笔记（第6-8章）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

《图论与网络优化》学习笔记（第6-8章）

上课时间：2023年10月——2024年1月
上课地点：国防科技大学
授课老师：戴丽
教材：戴丽.《图论与网络优化》
注：部分笔记根据自己的理解进行改动，可能不是很严谨，但便于理解。

第六章独立集及其算法

6.1 独立集和覆盖

独立集：设 $S\subseteq V(G)$ ，若 $S$ 中任意两个顶点在 $G$ 中都不相邻，则称顶点子集 $S$ 是 $G$ 的一个顶点独立集，简称独立集。含有 $k$ 个顶点的独立集称为 $k$ 独立集。
团：设 $S\subseteq V(G)$ ，若 $S$ 中任何两个相异顶点都相邻，则 $S$ 称为团，含有 $k$ 个顶点的团成为 $k$ 团。
极大独立集：设 $S$ 是图 $G$ 的独立集，但是任意增加一个顶点就不再是独立集，则称 $S$ 为极大独立集。
最大独立集： $G$ 中顶点数最多的独立集，称为是 $G$ 的最大独立集。最大独立集中所包含的顶点数称为 $G$ 的独立数，记作 $\alpha(G)$ 。

覆盖：图 $G$ 的覆盖是指 $G$ 的顶点集的一个子集，它包含 $G$ 的每一条边的至少一个端点。若顶点 $u$ 是边 $e$ 的端点，则称顶点 $u$ 覆盖边 $e$ 。
极小覆盖：若 $K$ 是 $G$ 的覆盖，但对于任何 $v\in K$ ，都不是覆盖，则称 $K$ 为极小覆盖。
最小覆盖：顶点数最少的覆盖成为最小覆盖。 $G$ 的最小覆盖的顶点数称为 $G$ 的覆盖数，记作 $\beta(G)$ 。

定理1 设 $S\subset V(G)$ 为顶点子集，集合 $S$ 是 $G$ 的独立集的充要条件是 $\bar{S}$ 为 $G$ 的覆盖。

定理2 对于任何图 $G$ ，有 $\alpha(G)+\beta(G)=\nu(G)$ 。

算法：极大独立集的计算

定理3 独立集与连通度的关系
设 $G$ 是 $\nu(\nu\ge2)$ 阶简单图，且对 $G$ 中任何不相邻的相异顶点 $x$ 和 $y$ ，均有 $d(x)+d(y)\ge\nu$ ，则 $\alpha(G)\le\kappa(G)$ 。（独立数小于连通度）

6.2 Ramsey数

Ramsey数：给定正整数 $k$ 和 $l$ ，若存在一个正整数 $n$ ，使得任何 $n$ 阶简单图或者含有 $k$ 团，或者含有 $l$ 独立集，记之为 $n\rightarrow(k,l)$ 。使 $n\rightarrow(k,l)$ 成立的最小正整数 $n$ 为Ramsey数，记作 $r (k, l)$ 。

定理1（Ramsey） 对于任何正整数 $k$ 和 $l$ ，有 $r (k, l)$ 都存在。

定理2 Ramsey数的上界 对于任何正整数 $k\ge2$ 和 $l\ge2$ ，有 $r(k,l)\le r(k-1,l)+r(k,l-1)$ ，并且若 $r (k - 1, l)$ 和 $r (k, l - 1)$ 都是偶数，则有 $r(k,l)\le r(k-1,l)+r(k,l-1)-1$
定理3 Ramsey数的上界 对于任何正整数 $k$ 和 $l$ ，都有 $r(k,l)\le \begin{pmatrix} k+l-2 \\ k-1 \end{pmatrix}$
定理4 Ramsey数的下界 对于任何正整数 $k$ ，有 $r(k,k)>k\cdot 2^{\frac{k}{2}-2}$
推论1 对任何正整数 $k$ 和 $l$ ，记 $m=min\{k,l\}$ ，则 $r(k,l)>m\cdot2^{\frac{m}{2}-2}$

**目前已知的Ramsey数：

《图论与网络优化》学习笔记（第6-8章）,学习笔记,图论,网络,学习

$k$ 部图：若图 $G$ 的顶点集 $V$ 可以划分成 $V=V_i\cup V_2\cup...\cup V_k$ ，这里 $V_i\cap V_j=\varnothing(1\le i\le j\le k)$ ，且 $V_i$ 中任何两个顶点在 $G$ 中都不相邻，则称 $G$ 是 $k$ 部图。
完全 $k$ 部图：在 $k$ 部图中，若 $V_i\neq\varnothing(1\le i\le k)$ ，且 $V_i$ 中任一顶点与 $V_j$ 中任一顶点之间恰有一条边相连 $(1\le i\le j\le k)$ ，则称 $G$ 是完全 $k$ 部图。

定理5 若简单图 $G$ 不包含 $K_{K+1}$ ，则存在一个以 $V = V (G)$ 为顶点集的完全 $k$ 部图 $H$ ，使得 $d_G(x)\le d_H(x)(\forall x\in V)$ ，而且若 $d_G(x)=d_H(x)(\forall x \in V)$ ，则 $G\cong H$ 。

Turan图：设 $G$ 是 $\nu$ 阶完全 $k$ 部图，若 $\lfloor\frac{\nu}{k}\rfloor\le|V_i|\le\lceil\frac{\nu}{k}\rceil(1\le i\le k)$ ，则把 $G$ 记作 $T_{\nu,k}$ ，即 $T_{\nu,k}$ 中任何两个 $V_i$ ， $V_j$ 的顶点数最多相差1.

引理1 设 $G$ 是 $\nu$ 阶完全 $k$ 部图，则 $\epsilon(G)\le\epsilon(T_{\nu,k})$ 。并且若 $\epsilon(G)=\epsilon(T_{\nu,k})$ ，则 $G\cong T_{\nu,k}$ 。
定理6 Turan定理 $ex(\nu,K_{K+1})=\epsilon(T_{\nu,k})$ ，并且 $T_{\nu,k}$ 是不含 $K_{K+1}$ 且边数等于 $ex(\nu,K_{K+1})$ 的唯一的简单图（在同构意义下）。

6.3 顶点着色

色数的相关概念：
着色：设 $G$ 是无环图，若把 $G$ 的每个顶点都染上颜色，使任何一对相邻顶点的颜色都不相同，则称这种染色方法为正常顶点着色，简称为 $G$ 的着色。
$k$ 着色：若某一着色中所使用的着色种类不超过 $k$ k，则称这个着色为 $k$ 着色。
$k$ 可着色：若图 $G$ 有 $k$ 着色，则称 $G$ 是 $k$ 可着色的。
色数：使得 $G$ 是 $k$ 可着色的 $k$ 的最小值称为 $G$ 的色数，记作 $\chi(G)$ 。
$k$ 色图：若 $G$ ，则称 $G$ 是 $k$ 色图。特别地，图 $G$ 是1色图当且仅当 $G$ 是空图； $n$ 阶完全图是 $n$ 色图。

关于着色的几个结论：
1）对于着色只讨论简单图的着色问题，对于有环或有重边的图无意义。
2）着色问题等价于把顶点集 $V (G)$ 划分成多个独立集的问题。
3） $n$ 阶简单图一定存在 $k(k\ge n)$ 着色。
4） $n$ 阶简单图 $G$ 有 1 着色当且仅当 $G$ 是 $n$ 阶空图。

定理1 色数的上界
设简单图 $G$ 的顶点排序 $v_1,v_2,...,v_\nu$ 满足：每个 $v_j$ 最多与排在它前面的 $v_1,v_2,...,v_{j-1}$ 中 $k$ 个顶点相邻， $2\le j\le \nu$ ，则有 $\chi(G)\le k+1$ 。

推论1 对任意简单图 $G$ 均有 $\chi(G)\le\Delta(G)+1$ 。（其中 $\Delta$ 表示图 $G$ 中顶点的最大度）

推论2 对于设 $G$ 是简单图，则 $\chi(G)\le max(\delta(H))+1$ ，其中 $H$ 是取遍 $G$ 的所有顶点导出的子图。

推论3 设 $G$ 是简单连通图，且不是正则图，则有 $\chi(G)\le\Delta(G)$ 。

推论4 设 $G$ 是连通的正则简单图，且含有1顶点割，则 $\chi(G)\le\Delta(G)$ 。

推论5 设 $G$ 是连通的 $k(k\ge3)$ 正则简单图，不是完全图，且 $G$ 有2顶点割，则 $\chi(G)\le\Delta(G)$ 。

Brooks定理 设 $G$ 是连通简单图，且既不是奇圈，也不是完全图，则 $\chi(G)\le\Delta(G)$ 。

色多项式：设 $G$ 是顶点标号图，用 $k$ 种颜色对 $G$ 的顶点进行着色，用 $\pi(G,k)$ 表示图 $G$ 的所有不同的 $k$ 着色数目，这里 $\pi(G,k)$ 是关于颜色数目 $k$ 的多项式函数，称 $\pi(G,k)$ 为简单图 $G$ 的色多项式。
易知：
（1） $G$ 是 $k$ 可着色的当且仅当 $\pi(G,k)>0$ 。
（2）对于空图 $\overline{K_{\nu}}$ ， $\pi(\overline{K_{\nu}},k)=k^{\nu}$ 。
（3）对于完全图 $K_\nu$ ， $\pi(K_\nu,k)=k(k-1)...(k-\nu+1)$ 。

定理2 递推法计算色多项式（减少边 / 添加边）
对于简单图 $G$ 的任意一条边 $e$ ，有 $\pi(G,k)=\pi(G-e,k)-\pi(G\cdot e,k)$ ，或 $\pi(G,k)=\pi(G+e,k)+\pi((G+e)\cdot e,k)$ 。

定理3 色多项式的公式定义
设简单图 $G$ 有 $\nu$ 个顶点， $\epsilon$ 条边和 $\omega$ 个联通分支，则 $\pi(G,k)=a_0k^\nu-a_1k^{\nu-1}+...+(-1)^{\nu-\omega}a_{\nu-\omega}k^\omega$ ，其中 $a_0=1,a_1=\epsilon,a_i>0 (2\le i\le\nu-\omega)$ 。
注：根据公式可直接判断图 $G$ 的：边数 $\epsilon=a_1$ 、顶点数 $\nu=k的最高次幂$ 、连通分支个数 $\omega=k的最低次幂$ 。

定理4 树的色多项式
简单图 $G$ 是树，当且仅当 $\pi(G,k)=k(k-1)^{\nu-1}$ 。

定理5 二部图的色多项式
简单图 $G$ 是连通二部图，当且仅当 $\pi(G,k)$ 中的 $a_{\nu-1}$ 为奇数。

6.4 支配集

支配集：设简单图 $G = (V, E)$ ， $S\subseteq V$ ， $S\neq\varnothing$ ，若 $\forall v\in \overline{S}$ ，都存在 $S$ 中的顶点与 $v$ 相邻，则称 $S$ 是图 $G$ 的支配集。
极小支配集：若 $S$ 是图 $G$ 的支配集且 $S$ 的任何真子集都不再是支配集，则 $S$ 为极小支配集。
最小支配集：图 $G$ 中顶点个数最少的支配集为最小支配集。
支配数：最小支配集中所包含的顶点个数，称为 $G$ 的支配数，记作 $\gamma(G)$ 。
独立支配集：设 $S$ 是 $G$ 的支配集，若 $S$ 是独立集，则称 $S$ 为独立支配集。

关于独立集和支配集的结论：
（1） $S$ 是 $G$ 的独立支配集当且仅当 $S$ 是 $G$ 的极大独立集。
（2）若 $S$ 是 $G$ 的极大独立集，则 $S$ 也是 $G$ 的极小支配集。

定理1 支配集的性质
设 $S$ 为简单图 $G$ 的支配集，则 $S$ 为极小支配集当且仅当 $S$ 中的每个顶点 $v$ 满足下列性质之一：
（1）存在 $u\in\overline{S}$ ，使 $N(u)\cap S=\{v\}$ ；
（2） $S\cap N(v)=\varnothing$ 。

定理2 设 $G$ 是没有孤立顶点的简单图， $S$ 是 $G$ 的极小支配集，则 $\overline{S}$ 也是 $G$ 的支配集。

定理3 设 $G$ 是没有孤立顶点的 $\nu$ 阶简单图，则 $\gamma(G)\le\frac{v}{2}$ 。

极小支配集的计算
约定： $\phi_i$ 表示 $V_i$ 及其邻域

6.5 边独立集和边覆盖

边独立集：两两不相邻的边的集合，称为边独立集，又称匹配。
最大边独立集：边数最多的边独立集称为最大边独立集。最大边独立集中的边数称为边独立数，记作 $\alpha'(G)$ 。

边覆盖：设 $L$ 是图 $G$ 的边集 $E (G)$ 的一个子集，若 $L$ 中的每个顶点都是 $G$ 中某条边的端点，则称 $L$ 是 $G$ 的边覆盖。
最小边覆盖：边数最少的边覆盖，称为最小边覆盖。最小边覆盖中的边数称为边覆盖数，记作 $\beta'(G)$ 。

注意：边独立集的补集不一定是边覆盖

定理1 若简单图 $G$ 中没有孤立顶点，即 $\delta(G)>0$ ，则 $\alpha'+\beta'=\nu$ 。

完美匹配：若边集 $M$ 既是边独立集（匹配），又是边覆盖，则称 $M$ 为完美匹配。

6.6 边着色

边着色：设 $G$ 为无环图，如果把 $G$ 的每条边都染上颜色，使得相邻的边的颜色不同，则称这种染法为正常边着色，简称为边着色。
k边着色：如果某一边着色中所有的颜色数目不超过 $k$ ，则称该边着色为 $k$ 边着色。
$k$ 边可着色：如果图 $G$ 存在 $k$ 边着色，则称 $G$ 是 $k$ 边可着色的。
边色数：在 $G$ 的所有边着色中，所需最少颜色数目称为 $G$ 的边色数，记作 $\chi'(G)$ 。若 $\chi'(G)=k$ ，则称 $G$ 为 $k$ 边色的。

定理1 Vizing定理
设简单图 $G$ 的最大度 $\Delta$ ，则有 $\Delta\le\chi'(G)\le\Delta+1$ 。

定理2 二部图的边着色
设 $G$ 是二部图，则 $\chi'(G)=\Delta(G)$ 。

定理3 完全图的边着色
偶数阶的完全图 $K_{2n}$ 是第一类图 $\chi'(G)=\Delta(G)$ ，奇数阶的完全图 $K_{2n+1}$ 是第二类图 $\chi'(G)=\Delta(G)+1$ 。

第七章最大匹配

7.1 二部图的最大匹配

M饱和顶点：设 $M$ 是图 $G$ 的一个匹配， $v$ 是 $G$ 的一个顶点，若 $v$ 与 $M$ 中边关联，则称 $v$ 是 $M$ 饱和顶点，或称 $M$ 饱和 $v$ 。
配对：若 $G$ 中两个顶点 $u$ 和 $v$ 与 $M$ 中同一条边关联，则称 $u$ 和 $v$ 在匹配 $M$ 中配对。
最大匹配：最大边独立集又称为最大匹配。
完美匹配：若 $G$ 中存在边数为 $\frac{\nu}{2}$ 的匹配 $M$ ，即 $M$ 中每个顶点都是 $M$ 饱和顶点，则称 $M$ 为 $G$ 的完美匹配。

规律匹配 $M$ 是图 $G$ 的完美匹配，当且仅当 $M$ 是 $G$ 的边覆盖。

M交错链：设 $M$ 是图 $G$ 的一个匹配， $G$ 中一条 $M$ 交错链是指其边交替地属于 $\overline{M}$ （即 $\ M E(G) \backslash M$ ）和 $M$ 的一条链。
M增广链：两个端点都是 $M$ 非饱和点的 $M$ 交错链。

定理1 图 $G$ 中匹配 $M$ 是最大匹配当且仅当 $G$ 中不存在 $M$ 增广链。

定理2 Hall定理
设 $G = (X, Y, E)$ 是二部图，则 $G$ 中存在饱和 $X$ 的每个顶点的匹配，当且仅当 $|N(S)|\ge|S|,\forall S \subseteq X$ 。

推论1
设 $G$ 是 $k$ 正则二部图， $k > 0$ ，则 $G$ 有完美匹配。

定理3
二部图 $G$ 的最大匹配的边数等于最小覆盖的顶点数，即 $\alpha'(G)=\beta(G)$ 。

推论2
设 $G$ 是无孤立点的二部图，则 $G$ 的独立数等于边覆盖数，即 $\alpha(G)=\beta'(G)$ 。

定理4
设 $K, M$ 分别为图 $G$ 的覆盖和边独立集，若 $∣ K ∣ = ∣ M ∣$ ，则 $K, M$ 分别是图 $G$ 的最小覆盖和最大边独立集。

求二部图的最大匹配：匈牙利算法（增广链的标号法）
基本思想：对于一直的匹配 $M$ ，从 $X$ 中的任意选定的 $M$ 非饱和点出发，用标号的方法寻找 $M$ 增广链，如果找到 $M$ 增广链，则 $M$ 就可以得到增广；否则，从 $X$ 的另一个 $M$ 非饱和顶点出发，继续寻找 $M$ 增广链。重复这个过程，直到 $G$ 中不存在 $M$ 增广链时，算法结束。

Tutte定理
定义有奇数个顶点的连通分支为奇分支。则图 $G$ 有完美匹配，当且仅当 $o(G-S)\le |S|$ $(\forall S\subset V(G))$ 。其中 $o (G)$ 为奇分支个数， $S$ 可以是空集。

推论1 每个 $k - 1$ 边连通的偶阶 $k$ 正则图 $G$ 都有完美匹配

7.2 最优匹配

最优匹配：设 $M$ 为图 $G$ 的最大匹配，若 $M$ 中所有边权和达最大，则称 $M$ 为最优匹配。

问题描述：

相关定义：
可行顶标：设完全二部图 $K_{n,n}=(X,Y,E)$ ， $X=\{x_1,x_2,...,x_n\}$ ， $Y=\{y_1,y_2,...,y_n\}$ ， $\omega_{ij}$ 是边 $x_iy_j$ 上的权。若映射 $l:V(K_{n,n,}\rightarrow R$ ，满足 $l(x_i)+l(y_j)\ge\omega_{ij}(\forall i,j\in\{1,2,...,n\})$ ，则称 $l$ 为 $K_{n,n}$ 的可行顶标，称 $l (v)$ 为顶点 $v$ 的标号。
$l$ 等子图：若 $E_l=\{x_iy_j|l(x_i)+l(y_j)=\omega_{ij}\}$ ，则称以 $G$ 为边集的 $E_l$ 的支撑子图为 $K_{n,n}$ 等子图。

定理1 设 $l$ 是 $K_{n,n}$ 的可行顶标，若 $l$ 等子图有完美匹配 $M$ ，则 $M$ 是 $K_{n,n}$ 的最优匹配。

最优匹配搜索算法 Kuhn-Munkres算法（KM算法）：
Step1 给出 $K_{n,n}$ 的一个可行顶标，如平凡顶标；
Step2 找出 $l$ 等子图 $K[E_l]$ ，在 $K[E_l]$ 中执行匈牙利算法；
Step3 若在 $K[E_l]$ 中找到完美匹配，这个完美匹配就是最优匹配，算法结束。否则修改可行顶标，修改方案为：设匈牙利算法终止于 $S\subset X,T\subset Y$ ，令 $\ T } a_l=min\{l(x_i)+l(y_i)-\omega_{ij}|x_i\in S,y_j\in Y\backslash T\}$ ，则定义新可行顶标 $l^{'}$ 为 $l'(u)=\begin{cases} l(u)-a_l & u\in S \\ l(u)+a_l & u\in T \\ l(u) & else \end{cases}$ 以 $l^{'}$ 代替 $l$ ，转Step2，继续寻找新的 $l$ 等子图。

第八章平面图及其算法

8.1 平面图

平面图：如果一个图能画在平面上，使得它的边仅仅只能在端点处相交，则称这个图可嵌入平面，或称它为平面图。
平面嵌入：将平面图 $G$ 画在平面上这样一种画法称为 $G$ 的一个平面嵌入。
平图：已经嵌入平面内的图称为平图。
面：平图 $G$ 的每个区域连同它的边界构成 $G$ 的一个面，记作 $f$ 。每个平图恰有一个面是无界的，这个面称为外部面，其他的面称为内部面。平图 $G$ 的所有面的集合记作 $F (G)$ ，平面数记作 $\Phi(G)$ 。
面的边界：由点和边交替组成，是两个面之间的边界，记作 $b (f)$ 。若 $G$ 连通，则 $b (f)$ 为一条闭途径，若 $b (f)$ 不含割边和环，则 $b (f)$ 是 $G$ 的圈。
面 $f$ 的度：面 $f$ 的边界 $b (f)$ 所含的边数称为面 $f$ 的度，记作 $d_G(f)$ 。
面相邻、关联：若平面图 $G$ 中的两个不同的面的边界有公共边 $e$ ，则称这两个面是相邻的，且这两个面同时与边 $e$ 关联。

对偶图：给定一个平图 $G$ ，定义另一个图 $G^*$ ： $G$ 的每个面 $f$ 对应 $G^*$ 的一个顶点 $f^*$ ， $G$ 的每条边对应 $G^*$ 的一条边 $e^*$ 。这样得到的图 $G^*$ 称为 $G$ 的对偶图。

平面图 $G$ 与它的对偶 $G^*$ 有下列性质：
（1） $\nu(G^*)=\Phi(G),\epsilon(G^*)=\epsilon(G)$
（2） $\forall f\in F(G),d_{G^*}(f^*)=d_G(f)$
（3）平图 $G$ 中所有面的度数和为 $2\epsilon(G)$ 。

定理1
对于任何平面图 $G$ 都有 $\sum_{f\in F(G)}d_G(f)=2\epsilon(G)$ 。

推论1
任何平图中度为奇数的面的个数为偶数。

定理2 Euler公式：描述顶点数、边数、面数三者的关系
设 $G$ 是连通平面图，则 $\nu(G)-\epsilon(G)+\Phi(G)=2$ 。

推论2
设平面图 $G$ 有 $\omega$ 个连通分支，则 $\nu(G)-\epsilon(G)+\Phi(G)=\omega+1$ 。

欧拉公式的应用：
（1）已知一个简单凸多面体的各个顶点都关联3条棱，求 $2\Phi-\nu$ 。

（2）用Euler公式证明：只有五个正多面体。

8.2 Kuratowski定理

围长：图 $G$ 中最短圈的长称为 $G$ 的围长，记作 $g$ 。

定理1 平面图的必要条件
设平面图 $G$ 的围长为 $g$ ， $g\ge3$ ，则 $\epsilon\le\frac{g}{g-2}(\nu-2)$ 。

推论1
设 $G$ 是简单平面， $\nu\ge3$ ，则 $\epsilon\le 3\nu-6$ 。

推论2
设 $G$ 是简单平面图，则 $\delta\le 5$ 。（其中 $\delta$ 为最小度）

推论3
$K_5$ 和 $K_{3,3}$ 都不是平面图。

极大平面图：设 $G$ 是简单平面图，若对于 $G$ 中任何不相邻的相异顶点 $u$ 和 $v$ ， $G + uv$ 不是平面图，则称 $G$ 为极大平面图。极大平面图的平面嵌入称为极大平图。

定理2 极大平面图的充要条件
$G$ 是 $\nu\ge3$ 的极大平面图，当且仅当 $G$ 的任何平面嵌入中每个面的边界都是3圈。

推论4
设 $G$ 是 $\nu\ge3$ 的简单平面图，则 $G$ 是极大平面图，当且仅当 $\epsilon=3\nu-6$ 。

外平面图：如果 $G$ 有一个平面嵌入 $\tilde{G}$ ，使得 $G$ 的所有顶点都在外部面的边界上，则称 $G$ 为外平面图。
极大外平面图：设 $G$ 是简单外平面图，若对于 $G$ 中任何不相邻的相异顶点 $u$ 和 $v$ ， $G + uv$ 不是外平面图，则称 $G$ 为极大外平面图。

定理3 外平面图的必要条件
$G$ 是 $\nu\ge3$ 的极大外平面图，当且仅当 $G$ 的外部面的边界是Hamilton圈，且每个内部面的边界是3圈。

定理4
设 $G$ 是 $\nu\ge3$ 的极大外平面图，则 $G$ 有 $\nu-2$ 个内部面。

推论5 三条结论
（1）若 $G$ 为极大外平面图， $\nu\ge3$ ，则 $\epsilon=2\nu-3$ 。
（2）若 $G$ 为简单外平面图， $\nu\ge3$ ，则 $\epsilon\le2\nu-3$ 。
（3）设 $G$ 是 $\nu\ge3$ 的简单外平面图，则 $G$ 是极大外平面图，当且仅当 $\epsilon=2\nu-3$ 。

剖分图：把图 $G$ 进行一系列边的剖分得到的图称为 $G$ 的剖分图。

引理1
若 $G$ 是（外）平面图，则 $G$ 的任何剖分图也都是（外）平面图。

引理2
若 $G$ 是（外）平面图，则 $G$ 的任何子图也是（外）平面图。

H分支：

引理3
设 $B$ 与 $B^{'}$ 是重叠的两个 $C$ 分枝，则他们或者是3等价的或者是偏斜的。

引理4
若 $G$ 不是平面图，则 $H_1$ 和 $H_2$ 中至少有一个不是平面图。

引理5
设 $G$ 不是平面图，且不含 $K_5$ 或 $K_{3,3}$ 的剖分图，并且有尽可能少的边数，则 $G$ 是3连通简单图。

定理1 Kuratowski定理（平面图的充要条件）
一个图是平面图，当且仅当它不含有 $K_5$ 和 $K_{3,3}$ 的剖分图。

定理2
图 $G$ 是外平面图，当且仅当 $G$ 不含 $K_5$ 或 $K_{2,3}$ 的剖分图。

面着色问题：
面着色：对于一个平图 $G$ ，如果能够把每个面染以给定的 $k$ 种不同颜色中的一种，使得任意相邻的两个面的颜色不同，则称这种染法为正常的 $k$ 面着色，简称为 $k$ 面着色，称 $G$ 是 $k$ 面可着色的。
面色数：使得 $G$ 是 $k$ 面可着色的最小 $k$ 值称为 $G$ 的面色数，记作 $\chi^*(G)$ 。

定理3 五色定理
每个简单平面图都是5可着色的。

8.3 平面性检测算法

容许的：设 $H$ 是平面图 $G$ 的一个子图， $\tilde{H}$ 是 $H$ 的平图。若存在 $G$ 的平图 $\tilde{G}$ 使 $\tilde{H}\subseteq\tilde{G}$ ，则称 $\tilde{H}$ 是 $G$ 容许的。

《图论与网络优化》学习笔记（第6-8章）,学习笔记,图论,网络,学习

面 $f$ 内可画出：设 $B$ 是 $G$ 的 $H$ 分枝， $f$ 是平图 $\tilde{H}$ 的面，若 $B$ 的所有接触点 $V_G(B,H)$ 都在面 $f$ 的边界上，则称 $B$ 在面 $f$ 内可画出。能使 $B$ 可画出的 $\tilde{H}$ 的面的集合记作 $F_G(B,\tilde{H})$ 。

DMP算法思想：从 $G$ 的一个可平面子图 $H$ 出发，先将 $H$ 嵌入平面，然后再边不交的添加 $H$ 分枝中的边，这样逐步建立越来越大的 $G$ 的可平面子图，最后扩张成 $G$ 的平面嵌入。
DMP算法：
（1）预处理：
a）若 $G$ 不连通，则分别检测每一个连通分支是否为平面图。
b）若 $G$ 有割点，则分别检测由割点切分的每一块是否为平面图。
c）删去 $G$ 中的环。
d）将 $G$ 中度为2的顶点删去，用一条边代替。（剖分运算不影响图的平面性）
e）删去 $G$ 中的重边。
（2）对预处理后的简单图进行简单判断：
a）若 $\nu<5$ ，则 $G$ 是平面图；
b）若 $\epsilon<9$ ，则 $G$ 是平面图；
c）若无圈，则 $G$ 是平面图；
d）若 $\epsilon>3\nu-6$ ，则 $G$ 不是平面图；
e）若 $\delta(G)>5$ ，则 $G$ 不是平面图；
f）若以上条件都不满足，则执行DMP算法。
（3）算法执行：

（4）例题：