特殊图

一、树

1、树的基本概念及性质

定义：连通而不含回路的无向图称为无向树，简称树，常用$T$表示树。

一些概念：
(1)树中度数为1的结点称为叶；
(2)度数大于1的结点称为分支点或内部结点；
(3)每个连通分支都是树的无向图，或者不含回路的无向图称为森林；
(4)平凡图（仅含一个结点的零图）称为平凡树。

注意：树中没有环和平行边，因此一定是简单图。

性质：设无向图$G=\langle V,E \rangle$，$| V | =n$，$| E | =m$，下列各命题是等价的：
(1)$G$连通而不含回路(即G是树)
(2)$G$中无回路，且$m = n-1$
(3)$G$是连通的，且$m = n-1$
(4)$G$中无回路，但在$G$中任二结点之间增加一条新边，就得到唯一的一条基本回路
(5)$G$是连通的，但删除$G$中任一条边后，便不连通$(n\ge 2)$
(6)$G$中每一对结点之间有唯一一条基本通路$(n\ge 2)$

特点：在结点给定的无向图中，树是边数最多的无回路图，树是边数最少的连通图；由此可知，在无向图$G = (n, m)$中，若$m＜n-1$，则$G$是不连通的，若$m＞n-1$，则$G$必含回路。

定理：任意非平凡树$T = (n, m)$都至少有两片叶。

2、生成树

定义：给定图$G=\langle V,E \rangle$，若$G$的某个生成子图是树，则称之为$G$的生成树(Spanning Tree)，记为$T_G$。生成树$T_G$中的边称为树枝(Branch)，$G$中不在$T_G$中的边称为弦(Chord)，$T_G$的所有弦的集合称为生成树的补。

题型：判断某个子图是否为生成树

生成树的判断：首先判断该子图是否为树，再判断是否为生成子图。

生成树存在定理：一个图$G=\langle V,E \rangle$存在生成树$T_G=\langle V,E_T \rangle$的充分必要条件：$G$是连通的。

生成树算法：
求连通图$G=\langle V,E \rangle$的生成树的破圈法：每次删除回路中的一条边，直到图中不含回路，其删除的边的总数为$m-n+1$。

求连通图$G=\langle V,E \rangle$的生成树的避圈法：每次选取$G$中一条与已选取的边不构成回路的边，直到再选取一条边就构成回路，选取的边的总数为$n-1$。

求连通图$G=\langle V,E \rangle$的生成树的广度优先搜索算法：
(1)任选$s\in V$，将$s$标记为$0$，令$L=\{ s \}$，$V=V-\{ s \}$，$k = 0$；
(2)如果$V = \emptyset$，则转(4)，否则令$k = k+1$；
(3)依次对$L$中所有标记为$k-1$的结点$v$，如果它与$V$中的结点$w$相邻接，则将$w$标记为$k$，指定$v$为$w$的前驱，令$L=L\cup \{ w \}$，$V=V- \{ w \}$，转(2)；
(4)$E_G = \{(v, w)\mid w∈L - \{ s \} ，v为w的前驱 \}$，结束。

题型：利用破圈法、避圈法、广度优先算法求生成树

最小生成树：设$G=\langle V,E \rangle$是连通的赋权图，$T$是$G$的一棵生成树，$T$的每个树枝所赋权值之和称为$T$的权(Weight)，记为$w(T)$。$G$中具有最小权的生成树称为$G$的最小生成树(Minimal Spanning Tree)。

注意：如果$G$不是树，那么它的生成树就不是唯一的，最小生成树也可能不是唯一的。

Kruskal算法：
(1)在$G$中选取最小权边$e_1$，置$i = 1$。
(2)当$i = n-1$时，结束，否则转(3)。
(3)设已选取的边为$e_1, e_2, \cdots , e_i$，在$G$中选取不同于$e_1, e_2, \cdots , e_i$的边$e_{i+1}$，使$\{ e_1, e_2, …, e_i, e_{i+1} \}$中无回路且$e_{i+1}$是满足此条件的最小权边。
(4)置$i = i+1$，转(2)。

注意：选取边$e_{i+1}$时必须优先考虑不与先前的边集构成回路，然后再考虑最小权边。

Prim算法：
(1)在$G$中任意选取一个结点$v_1$，置$V_T=\{ v_1 \}$, $E_T=\emptyset$，$k = 1$；
(2)在$V-V_T$中选取与某个$v_i\in V_T$邻接的结点$v_j$，使得边$(v_i, v_j)$的权最小，置$V_T = V_T\cup \{ v_j \}$, $E_T = E_T\cup \{ (v_i, v_j) \}$，$k = k+1$；
(3)重复步骤(2)，直到$k = |V|$。

题型：利用Kruskal算法和Prim算法求最小生成树

二、根树

1、根树的概念与分类

有向树：一个有向图，若略去所有有向边的方向所得到的无向图是一棵树，则这个有向图称为有向树(Directed Tree)。

根树：一棵非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称之为根树(Root Tree)或外向树(Outward Tree)。

一些概念：
(1)入度为0的结点称为根(Root)；
(2)出度为0的结点称为叶(Leaf)；
(3)入度为1，出度大于0的结点称为内点(Interior Point)；又将内点和根统称为分支点(Branch Point)；
(4)在根树中，从根到任一结点v的通路长度，称为该结点的层数(Layer Number)；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高(Height)；
(5)若从结点$v_i$到$v_j$可达，则称$v_i$是$v_j$的祖先(Ancestor)，$v_j$是$v_i$的后代(Descendant)；
(6)若$\langle v_i, v_j \rangle$是根树中的有向边，则称$v_i$是$v_j$的父亲(Father)，$v_j$是$v_i$的儿子(Son)；
(7)如果两个结点是同一个结点的儿子，则称这两个结点是兄弟(Brother)；
(8)如果在根树中规定了每一层上结点的次序，这样的根树称为有序树(Ordered Tree)。一般地，在有序树中同一层中结点的次序为从左至右。有时也可以用边的次序来代替结点的次序。

k元树：设$T$为根树。
(1)若$T$的每个分支点至多有k个儿子，则称$T$为k元树（或k叉树）（k-ary Tree）；
(2)若$T$的每个分支点都恰有k个儿子，则称$T$为完全k元树（Complete k-ary Tree）；
(3)若$T$是k元完全树且每个叶结点的层数均为树高，则称$T$为满k元树（Full k-ary Tree）；
(4)若k元树$T$是有序的，则称$T$为有序k元树（Ordered k-ary Tree）；
(5)若k元完全树$T$是有序的，则称$T$为有序完全k元树（Ordered Complete k-ary Tree）；
(6)若$T$是满k元树且是有序的，则称$T$为有序满k元树（Full Ordered k-ary Complete Tree）。

子树：在根树$T$中，任一结点$v$及其所有后代导出的子图$T’$称为$T$的以$v$为根的子树(Subtree)。当然，$T’$也可以有自己的子树。有序2元树的每个结点$v$至多有两个儿子，分别称为$v$的左儿子(Left Son)和右儿子(Right Son)。有序2元树的每个结点$v$至多有两棵子树，分别称为v的左子树(Left Subtree)和右子树(Right Subtree)。

注意：区分以$v$为根的子树和$v$的左(右)子树，$v$为根的子树包含$v$，而$v$的左(右)子树不包含$v$。

k元完全树中分支点与叶结点数目之间的关系定理：在k元完全树中，若叶数为$t$，分支点数为$i$，则有：$(k-1)×i = t-1$。

常用的数量关系（$n$表示结点数，$m$表示边数，$i$表示分支点数，$t$表示叶数）：
(1)树：$m=n-1$；$n=i+t$；
(2)完全k元树：$m=2i$；$(k-1)×i = t-1$；

2、根树的遍历

遍历：对于根树，一个十分重要的问题是要找到一些方法，能系统地访问树的结点，使得每个结点恰好访问一次，这就是根树的遍历(Ergode)问题。k元树中，应用最广泛的是2元树。由于2元树在计算机中最易处理，下面先介绍二元树的3种常用的遍历方法，然后再介绍将任意根树转化为二元树。

二元树的先根次序遍历算法：
(1)访问根
(2)按先根次序遍历根的左子树
(3)按先根次序遍历根的右子树

二元树的中根次序遍历算法：
(1)按中根次序遍历根的左子树
(2)访问根
(3)按中根次序遍历根的右子树

二元树的后根次序遍历算法：
(1)按后根次序遍历根的左子树
(2)按后根次序遍历根的右子树
(3)访问根

题型：按照三种算法写出二元树的遍历

根树转化为二元树算法：
(1)从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线。
(2)兄弟间用从左向右的有向边连接。
(3)按如下方法确定二元树中结点的左儿子和右儿子：直接位于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依此类推。

有序森林转化为二元树算法：
(1)先把森林中的每一棵树都表示成二元树；（注意：即使某些树已经是二元树，也要执行上面的算法）
(2)除第一棵二元树外，依次将剩下的每棵二元树（注意：从最右边的树开始依次向左）作为左边二元树的根的右子树，直到所有的二元树都连成一棵二元树为止。

题型：将根树和森林转化为二元树

3、最优树与哈夫曼算法

在计算机与通信中，哈夫曼算法是一种常用的数据压缩编码方式。例如，可用00、01、10、11分别表示字母A、B、C、D。如果字母A、B、C、D出现的频率是一样的，传输100个字母用200个二进制位。
但实际上字母出现的频率很不一样，如A出现的频率为50％，B出现的频率为25％，C出现的频率为20％，D出现的频率为5％。能否用不等长的二进制序列表示字母A、B、C、D，使传输的信息的二进制位尽可能少呢？事实上，可用000表示字母D，用001表示字母C，00表示B，1表示A。这样表示，传输100个字母所用的二进制位为3×5+3×20+2×25+1×50 = 175。
这种表示比用等长的二进制序列表示法好，节省了二进制位。但当我们用1表示A，用00表示B，用001表示C，用000表示D时，如果接收到的信息为001000，则无法辨别它是CD还是BAD。导致这一问题的原因是B的编码成为了C的编码的前缀"00"。因而，不能用这种二进制序列表示A、B、C、D，要寻找另外的表示法。

前缀：设$a_1a_2\cdots a_{n-1}a_n$为长度为$n$的符号串，称其子串$a_1$，$a_1a_2$，$\cdots$ ，$a_1a_2\cdots a_{n-1}$分别为$a_1a_2\cdots a_{n-1}a_n$的长度为$1$、$2$、$\cdots$、$n-1$的前缀（Prefix）。例如，上面提到的"00"就是"001"的长度为$2$的前缀。

前缀码：设$A=\{ b_1,b_2,\cdots ,b_m \}$是一个符号串集合，若对任意$b_i, b_j\in A$，$b_i \ne b_j$，$b_i$不是$b_j$的前缀，$b_j$也不是$b_i$的前缀，则称$A$为前缀码（Prefixed Code）。若符号串$b_i(i = 1, 2,\cdots, m)$中，只出现0和1两个符号，则称A为二元前缀码。

用二元树产生前缀码：前缀码中元素互不为前缀的优点使其适合用作编码，且不会产生歧义，可以通过二元树来确定前缀码。给定一棵二元树$T$，假设它有$t$片树叶。设$v$是$T$任意一个分支点，则$v$至少有一个儿子至多有两个儿子。若$v$有两个儿子，则在由$v$引出的两条边上，左边的标上0，右边的标上1；若$v$只有一个儿子，在v引出的边上可标0也可标1。设$v_i$为$T$的任意一片树叶，从树根到$v_i$的通路上各边的标号组成的符号串放在$v_i$处，$t$片树叶处的$t$个符号串组成的集合为一个二元前缀码。$v_i$中的符号串的前缀均在$v_i$所在的通路上，因而所得集合为二元(0和1组成)前缀码。若$T$存在带一个儿子的分支点，则由$T$产生的前缀码不唯一，但$T$若为完全二元树，则$T$产生的前缀码就是唯一的了。

解决了歧义问题后，当知道了传输的符号出现的频率时，如何选择前缀码，使传输的二进制位尽可能地少呢？

最优二元树：设有一棵二元树，
(1)若对其所有的t片叶赋以权值$w_1$、$w_2$、$\cdots$ 、$w_t$，则称之为赋权二元树(Power Binary Tree)；
(2)若权为$w_i$的叶的层数为$L(w_i)$，则称$W(T)=\sum_{i=1}^{t} w_i\times L(w_i)$为该赋权二元树的权；
(3)而在所有赋权$w_1$、$w_2$、$\cdots$ 、$w_t$的二元树中，$W(T)$最小的二元树称为最优树(Optimal Tree)。

哈夫曼算法（最优树算法）：
(1)初始：令$S=\{ w_1,w_2,\cdots ,w_t \}$；
(2)从$S$中取出两个最小的权$w_i$和$w_j$，画结点$v_i$，带权$w_i$，画结点$v_j$，带权$w_j$。画$v_i$和$v_j$的父亲$v$，连接$v_i$和$v$，$v_j$和$v$，令$v$带权$w_i+w_j$；
(3)令$S=( S-\{ w_i,w_j \} ) \cup \{ w_i+w_j \}$；
(4)判断$S$是否只含一个元素，若是，则停止，否则转(2)。

题型：设计哈夫曼编码

三、欧拉图

1、欧拉图的定义与判定

欧拉图：设$G$是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。平凡图是欧拉图。

欧拉图的特征：
(1)欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路；
(2)欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路；
(3)如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。

注意：只有存在欧拉回路的图才是欧拉图。

欧拉图的判定：无向图$G=\langle V,E \rangle$具有一条欧拉通路，当且仅当$G$是连通的，且仅有零个或两个奇度数结点。

推论：
(1)若连通的无向图有两个奇度数结点，则它们是$G$中每条欧拉通路的端点。
(2)无向图$G=\langle V,E \rangle$具有欧拉回路，当且仅当$G$是连通的，并且所有结点的度数均为偶数。
(3)有向图$G$具有欧拉通路，当且仅当$G$是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。
(4)有向图$G$具有欧拉回路，当且仅当$G$是连通的，且所有结点的入度等于出度。

	无向图	有向图
欧拉通路	$G$是连通的，且仅有零个或两个奇度数结点。	$G$是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。
欧拉回路	$G$是连通的，并且所有结点的度数均为偶数。	$G$是连通的，且所有结点的入度等于出度。

2、欧拉回路的计算

桥：设$G=\langle V,E \rangle$，$e\in E$，如果$p(G-e)＞p(G)$（$p(G)$表示$G$中的连通分支个数），称$e$为$G$的桥(Bridge)或割边(Cut edge)。显然，所有的悬挂边都是桥。

Fleury算法：
(1)任取$v_0\in V$，令$P_0 = v_0$，$i = 0$；
(2)按下面的方法从$E-\{ e_1,e_2,\cdots,e_i \}$中选取$e_{i+1}$：
$e_{i+1}$与$v_i$相关联；
除非无别的边可选取，否则$e_{i+1}$不应该为$G’ = G - \{ e1, e2, …, ei \}$中的桥；
(3)将边$e_{i+1}$加入通路$P_0$中，令$P_0 = v_0e_1v_1e_2\cdots e_iv_ie_{i+1}v_{i+1}, i = i+1$；
(4)如果$i=| E |$，结束，否则转(2)。

注意：选取$e_{i+1}$时，判断待选的边是否为桥时需要先去掉选过的边。$e_{i+1}$可能在$G$中不是桥，而在$G’ = G - \{ e1, e2, …, ei \}$中是桥。

题型：欧拉通路（回路）的判定与计算

四、哈密顿图

1、哈密顿图的定义

哈密顿图：经过图中每个结点一次且仅一次的通路（回路）称为哈密顿通路（回路）（Hamiltonian Entry/circuit）。存在哈密顿回路的图称为哈密顿图（Hamiltonian Graph）。平凡图为哈密顿图。

特征：
(1)哈密顿通路是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结点的基本通路。
(2)哈密顿回路是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路。
(3)如果我们仅用结点来描述的话，哈密顿通路就是图中所有结点的一种全排列，哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列。

注意：仅有哈密顿通路不一定是哈密顿图，只有存在哈密顿回路的图才是哈密顿图。

2、哈密顿图的判定

哈密顿图的必要条件：设无向图$G=\langle V,E \rangle$是哈密顿图，$V_1$是$V$的任意非空子集，则$p(G-V_1)\le | V_1 |$，其中$p(G-V_1)$是从$G$中删除$V_1$后所得到图的连通分支数。

推论：设无向图$G=\langle V,E \rangle$中存在哈密顿通路，则对$V$的任意非空子集$V_1$，都有$p(G-V_1)  \le  |V_1| + 1$。

注意：上述定理在应用中它本身用处不大，但它们的逆否命题却非常有用。我们经常利用其逆否命题来判断某些图不是哈密顿图，即：若存在$V$的某个非空子集$V_1$使得$p(G-V_1)> | V_1 |$，则G不是哈密顿图，即没有哈密顿回路；若存在$V$的某个非空子集$V_1$使得$p(G-V_1)> | V_1 |+1$，则$G$没有哈密顿通路。

哈密顿图的充分条件（无向图）：
(1)设$G=\langle V,E \rangle$是具有$n$个结点的简单无向图。如果对任意两个不相邻的结点$u, v\in V$，均有$deg(u) + deg(v) ≥ n - 1$，则G中存在哈密顿通路。
(2)设$G=\langle V,E \rangle$是具有$n$个结点的简单无向图。如果对任意两个不相邻的结点$u, v\in V$，均有$deg(u) + deg(v) ≥ n$，则G中存在哈密顿回路。
(3)设$G=\langle V,E \rangle$是具有$n$（$n ≥ 3$）个结点的简单无向图。如果对任意$v\in V$，均有$deg(v)\ge \frac{n}{2}$，则G是哈密顿图。

有向图的哈密顿通路的充分条件：设$G=\langle V,E \rangle$是有 $n$ ($n ≥ 2$)个结点的一个简单有向图。如果忽略$G$中边的方向所得的无向图中含生成子图$K_n$（$K_n$表示具有$n$个结点的无向完全图），则有向图$G$中存在哈密顿通路。

	无向图	有向图
哈密顿通路	任意两个不相邻的结点$u, v\in V$，均有$deg(u) + deg(v) ≥ n - 1$	忽略$G$中边的方向所得的无向图中含生成子图$K_n$
哈密顿回路（哈密顿图）	任意两个不相邻的结点$u, v\in V$，均有$deg(u) + deg(v) ≥ n$或者对任意$v\in V$，均有$deg(v)\ge \frac{n}{2}$（$n ≥ 3$）
没有哈密顿通路	存在$V$的某个非空子集$V_1$使得$p(G-V_1)> | V_1 |+1$
没有哈密顿回路（非哈密顿图）	存在$V$的某个非空子集$V_1$使得$p(G-V_1)> | V_1 |$

题型：哈密顿图的判定

五、偶图

1、偶图的定义

偶图：若无向图$G=\langle V,E \rangle$的结点集$V$能够划分为两个子集$V_1, V_2$，满足$V_1\cap V_2 = \emptyset$，且$V_1\cup V_2 = V$，使得$G$中任意一条边的两个端点，一个属于$V_1$，另一个属于$V_2$，则称$G$为偶图(Bipartite Graph)或二分图(Bigraph)。$V_1$和$V_2$称为互补结点子集，偶图通常记为$G=\langle V_1,E,V_2 \rangle$。偶图没有环。平凡图和零图可看成特殊的偶图。

完全偶图：在偶图$G=\langle V_1,E,V_2 \rangle$中，若$V_1$中的每个结点与$V_2$中的每个结点都有且仅有一条边相关联，则称偶图$G$为完全偶图(Complete Bipartite Graph)或完全二分图(Complete Bigraph)，记为$K_{i, j}$，其中，$i=| V_1 |$，$j=| V_2 |$。

2、偶图的判定

偶图的充分必要条件：无向图$G=\langle V_1,E,V_2 \rangle$为偶图的充分必要条件是$G$的所有回路的长度均为偶数。

注意：由于找到图中所有的回路较为复杂，实际应用中，我们常使用它的逆否命题来判断一个图不是偶图：无向图$G$不是偶图的充分必要条件是$G$中存在长度为奇数的回路。

3、匹配问题

匹配：在偶图$G=\langle V_1,E,V_2 \rangle$中，$V_1=\{ v_1,v_2,\cdots,v_q \}$，若存在$E$的子集$E’ = \{ (v_1, v_1’),(v_2, v_2’),\cdots,(v_q, v_q’) \}$，其中$v_1’, v_2’, \cdots, v_q’$是$V_2$中的$q$个不同的结点，则称$G$的子图$G’=\langle V_1, E’, V_2 \rangle$为从$V_1$到$V_2$的一个完全匹配(Complete Matching)，简称匹配。

注意：匹配的性质与单射类似，在偶图$G=\langle V_1,E,V_2 \rangle$中，若存在$V_1$到$V_2$的单射$f$，使得对任意$v\in V_1$，都有$(v, f(v))\in E$，则存在V1到V2的匹配。由单射性质知，不是所有偶图都有匹配，存在匹配的必要条件是$| V_1 | \le | V_2 |$。

霍尔定理（婚姻定理）：偶图$G=\langle V_1,E,V_2 \rangle$中存在从$V_1$到$V_2$的匹配的充分必要条件是$V_1$中任意$k$个结点至少与$V_2$中的$k$个结点相邻，$k=1,2,\cdots,| V_1 |$，这一条件被称为相异性条件。

注意：判断一个偶图是否满足相异性条件需要从1检查到$| V_1 |$，通常比较复杂。因此，在考察相异性条件之前，应该先考察t条件。

t条件：设$G=\langle V_1,E,V_2 \rangle$是一个偶图。如果满足条件
(1)$V_1$中每个结点至少关联$t$条边；
(2)$V_2$中每个结点至多关联$t$条边；
则G中存在从$V_1$到$V_2$的匹配。其中$t$为正整数。

注意：判断t条件非常简单，只需要计算$V_1$中结点的最小度数和$V_2$中结点的最大度数即可，如果两个数相等，则存在匹配。

⚠️小心：t条件不是充分必要条件，如果不满足t条件，也不能说明不存在匹配，因为相异性条件比t条件更容易满足，一个偶图可能满足相异性条件而不满足t条件，此时它仍然存在匹配。

题型：匹配的判定

六、平面图

1、平面图的定义

平面图：如果能把一个无向图$G$的所有结点和边画在平面上，使得任何两边除公共结点外没有其他交叉点，则称$G$为平面图(Plane Graph)，否则称$G$为非平面图(Nonplanar Graph)。当且仅当一个图的每个连通分支都是平面图时，这个图是平面图。

注意：有些图从表面上看它的某些边是相交叉的，但是不能就此肯定它不是平面图。判定平面图通常采用观察法，通过改变边的形状或位置，使其尽量避免交叉。

2、欧拉公式

一些概念：在平面图G的一个平面表示中，

• 由边所包围的其内部不包含图的结点和边的区域，称为G的一个面(Surface)
• 包围该面的边所构成的回路称为这个面的边界(Bound)
• 面r的边界的长度称为该面的次数(Degree)，记为D®
• 区域面积有限的面称为有限面(Finite Surface)，区域面积无限的面称为无限面(Infinite Surface)
• 平面图有且仅有一个无限面

连通平面图中面和边界的计算：面是由边所包围的其内部不包含图的结点和边的区域，面的边界是包围该面的诸边所构成的回路。如果图中有桥（或割边），桥须在边界中走两次。

(握手？)定理：平面图中所有面的次数之和等于边数的2倍。

欧拉公式（与凸多面体的欧拉公式类似）：设$G=\langle V,E \rangle$是连通平面图，若它有$n$个结点、$m$条边和$r$个面，则有$n – m + r = 2$。

推论（由以上两个定理证明）：设$G$是一个$(n, m)$简单连通平面图，若$m＞1$，则有$m ≤ 3n – 6$。
该推论本身可能用处不大，但它的逆否命题却非常有用，可以用它来判定某些图是非平面图。即：一个简单连通图，若不满足$m ≤ 3n - 6$，则一定是非平面图。

推论：设$G$是一个$(n, m)$简单连通平面图，若每个面的次数至少为$k (k ≥ 3)$，则有$m\le \frac{k}{k-2}(n-2)$。
同样，该推论本身可能用处不大，但它的逆否命题却非常有用，可以用它来判定某些图是非平面图。即一个简单连通图，若每个面的次数至少为$k (k ≥ 3)$，若不满足$m\le \frac{k}{k-2}(n-2)$，则一定是非平面图。

3、库拉托夫斯基定理

库拉托夫斯基定理：一个图是平面图的充分必要条件是它的任何子图都不可能收缩为$K_5$（完全图）或$K_{3,3}$（完全偶图）。

推论：一个图是非平面图的充分必要条件是它存在一个能收缩为$K_5$或$K_{3,3}$的子图。$K_5$和$K_{3,3}$称为库拉托夫斯基图(Kuratowski Graph)。

是平面图	不是平面图
它的任何子图都不可能收缩为$K_5$或$K_{3,3}$	不满足$m ≤ 3n - 6$，
	不满足$m\le \frac{k}{k-2}(n-2)$
	它存在一个能收缩为$K_5$或$K_{3,3}$的子图

题型：平面图的判定