离散数学笔记（10.4）平面图

广东深圳

一、基本概念及性质

1.定义
在一个平面上，如果能够画出无向图 G 的图解，其中没有任何边的交叉，则称图 G 是个平面图；否则，称 G 是非平面图。
有些图从表面上看，它的某些边是相交的，但是不能就此肯定它不是平面图。
对于图(a)(b)中的无向图来说，加以重画之后，它将不包含任何边的交叉(e)(f)。(a)(b)是平面图，而(c)(d)是非平面图。


2.观察法
设 C=v_1v_2v_3v_4v_1 是图 G 中的任何基本回路，  x＝v_1v_3  和 x '＝v_2v_4  是图 G 中的任意两条基本路径。若 x 和 x ' 同时在 C 的同一侧，则两者必定发生交叉。


观察法可判断 K_{3,3} 不是平面图。给定 K_{3,3} 中有一个基本回路  C= v_1 v_6 v_3 v_5 v_2 v_4 v_1 ，考察三条边 \left\{ {v_1,v_5 } \right\} ， \left\{ {v_2,v_6 } \right\} ， \left\{ {v_3 ,v_4 } \right\} ，显然，三条边中至少有两条边同时处于 C 的同一侧，因此避免不了交叉。


3.库拉托夫斯基定理
库拉托夫斯基图：由观察法均可证明， K_{3,3} 与 K_5 都是非平面图， K_{3,3} 是边最少的非平面图， K_5 是结点最少的非平面图。


同胚操作：在原图的边上增加或者删除度数为 2 的结点，不会影响图的平面性。


同胚图：设 G_1  和 G_2 是两个无向图。如果  G_1  和 G_2  是同构的，或者通过同胚操作，能够把 G_1 和 G_2 转化成同构的图，则称 G_1 和 G_2 是同胚的。


库拉托夫斯基定理：设 G 是一个无向图。图 G 中不存在任何与 K_{3,3} 或 K_5 同胚的子图，当且仅当图 G 是平面图。
应用库拉托夫斯基定理，通过同胚操作，可证明下图均为非平面图。


二、多边形的图

1.多边形的图的归纳定义
① 单个基本回路的图，称为多边形。一个多边形是一个多边形的图。
② 设 G=\left<V,E,ψ\right>  是一个多边形的图；另设  P=(v_iu_1u_2…u_{l-1}v_j),(l≥1 ) 是任意基本路径，不与图 G 中任一路径交叉，且有  v_i,v_j∈V ， u_k ∉V 。
于是，由图 G 和 P 所构成的图  G'=\left<V',E',ψ'\right> 也是一个多边形的图，其中
V'=V\cup\left\{ u_1,u_2,\dots,u_{l-1} \right\}
E'=E\cup\left\{ \left\{ u_i,u_1 \right\},\left\{ u_1,u_2 \right\},\dots,\left\{ u_{l-1},v_j \right\} \right\}



多边形的图

2.多边形图的面
多边形图中的多边形能够把平面划分成数个区域，每一个区域都称为图 G 的面。
如果两个面共有一条边，则称这样的两个面是邻接的面。
如上图中的区域 F_1,F_2,\dots,F_9 是面， F_1,F_2就是邻接的面。
3.极大基本回路
包含有多边形的图 G 的所有面的边界的多边形，称为 G 的极大基本回路。
图中 (v_1v_2v_3v_4v_5v_6v_7v_1) ，就是该多边形的图的极大基本回路。
如果图 G 在平面上，其极大基本回路外侧的无限区域，称为  G  的无限面。
如果图 G 在球面上，则 G 的无限面等同其它的有限面。
4.欧拉公式
设  G=\left<V,E\right>  是个具有  k  个面（包括无限面）的多边形的图，则 \left| V \right| − \left| E \right| + k = 2
证明：对于面的数目 k，用归纳法证明
① 面的最少数目（包括无限面）是 k = 2 。在这种情况下，图 G 是个多边形，因而应有 \left| V \right|=\left| E \right|。这样，有 \left| V \right| − \left| E \right| + k = 2 。
② 假设对于具有 k-1 个面（包括无限面）的图来说，定理成立。
要证对于具有 k 个面（包括无限面）的图，定理亦成立。首先构造具有  k'= k-1 个面的的图  G'=\left<V',E'\right> ，然后附加上一条长度为  l≥1  的基本路径，它与  G' 恰有共有两个结点，则 \left| V \right|-\left| E \right|+k=(\left| V' \right|+l-1)-(\left| E' \right|+l)+(k′+1)=\left| V' \right|-\left| E' \right|+k'
根据归纳假设可知， \left| V' \right|-\left| E' \right|+k'=2
三、对偶图

设多边形的图 G=\left<V,E\right> ，其含有面 F_1 ,F_2,\dots,F_n ，包括有无限面，则可用一下方法构造 G  的对偶图 G^* ：
在 F_i 内画出每个 F_i 对应的结点 v^*_i  ，并且连通 v^*_i 和 v^*_j ，去交叉 F_i 和 F_j 所有公共的边。易知 G 和  G^* 是互为对偶的。
如果 G 与 G^*  同构，则称 G 是自对偶图。


推论：若平面图  G=\left<V,E\right>  是自对偶图，则 2\left| V \right|-\left| E \right|=2 。
证明：由于图 G 是自对偶图，则有 \left| V \right|=k ，由欧拉公式易证。
四、着色问题

对于地图的着色问题，可以化为其对偶图的结点的着色问题。
着色：对图  G  的每个结点指派一种颜色，使得相邻结点都有不同的颜色。
若可用  n  种颜色对图  G  着色，则称  G  是n-可着色的， n 的最小值记为 \chi (G) 。
四色定理：任何简单平面图都是 4-可着色的。
五色定理：任何简单平面图 G=\left<V ,E\right> ，均有\chi(G)\leq5。

邹彬

请问啥是平面图？

家栋

任意两线段最多在端点相交

二笔的节奏

有一点不是很明白。在1.定义 中，(b)--> (f) 的过程中。点的位置被移动了。这中操作也是允许的吗？如果点的位置可以移动。那么肯定可以找到不交叉的边了呀。

潇湘第一深情

首先，所有的边和点都在同一个平面内。这些点在同一个平面内是可移动的，而且不管点怎么动，边也必须连接相同的两个点，同时边允许在平面内任意延长和弯曲。如果在上述的条件下，能做到没有边相交，则这个图为平面图