图论复习(六)

G = 是一个无向图。 1.图G可嵌入平面：如果可以把图G的所有结点和边都画在平面上，同时除断点外连线之间没有交点，就称图G可嵌入平面。画出的无边相交的G’称G的平面嵌入。 2.可平面化：如果图G可以嵌入平面，就称图G可平面化。 3.G中边所包含的区域称作一个面。有界区域称为内部面，无界区域称为外部面，常记作R0，包围面的长度最短的闭链称为该面的边界，面R的边界的长度称为该面的度数，记作deg®。 4.面的度数计算中，含有割边和桥的度数为2，其余为1。

定理1：图G可嵌入球面当且仅当图G可嵌入平面。

定理2：G中各面的度数之和等于图G边数的两倍。

证明：设e为图G的两个面的公共边，再计算两个面的度数时候边数各提供1，当e不是公共边时候，也就是e为桥或者割边时候提供度数为2。因此，面的度数之和为边的两倍。

定理3：设R是图G的某个平面嵌入的一个内部面，则存在图G的一个平面嵌入使R为外部面。

定理4：设图G是简单的可平面图，如果G中任意两个不相邻的结点加边后所得到的为非可平面图。则称G是极大可平面图，极大可平面图的任何平面嵌入都称为极大平面图。极大平面图必是连通图

定理5：图G为n阶简单的连通的平面图，G为极大平面图当且仅当G的每一个面的度数为3。 定理说明结点数大于等于3的极大平面图的任何面都是由三角形组成。

结论1：K1,K2,K3,K4,K5-e(K5任意删去一条边）均为极大可平面图，他们的任何平面嵌入都是极大平面图；当阶数等于3时候，有割边或桥的平面图不可能是极大平面图。

结论2：无向完全图K5和无向完全二部图K3,3都是极小非可平面图（去掉一条边就成为可平面图）。

结论3：一个图是可平面图，那么他的子图也是可平面图； 一个图的子图是非可平面图，那么图本身也是非可平面图。

结论4：同一个图的平面嵌入中，外部面和内部面的度数可以不同。

centered 文本居中 定理1：欧拉公式：设图G是有n个结点、m条边和r个面的连通平面图，则它们满足：n - m + r = 2

推论1：设图G是有n个结点、m条边的连通平面简单图，其中n≥3，则有：m ≤ 3n - 6 证明：由图G的面度数之和为边数的二倍，即2m。又因为G是平面简单图每一个面的度数至少为3，则2m≥3r，由欧拉公式有： m ≤ 3n - 6

推论2：设图G是有n个结点、m条边的连通平面简单图，其中n≥3且没有长度为3的圈，则有：m ≤ 2n - 4

证明：G没有长度为3的圈也就没有度为3的面，G的每一个面的度数至少为4。所以2m≥4r，由欧拉公式有：m ≤ 2n - 4 对于推论1和推论2我们可以用定理进行判定它不是平面图。

例1：证明K5和K3,3是非平面图。

证明：在K5中，m应该小于等于3n - 6，即m≤9。而完全图K5具有10条边。所以是非平面图。

在K3,3中，没有长度大于3的圈，根据推论2可知，m≤2n-4，也就是m≤8，而K3,3含有9条边，所以是非平面图。

推论3： 证明：同理，有2m≥r x l，根据欧拉公式化简得： 2m ≥ l(m - n + 2)

推论4：

推论5： 证明过程与推论3类似，用到推论4的结论。

推论6：