第四章 平面图与对偶图
4.1 平面图 4.2 平面图上的欧拉公式
4.3 对偶图
4.1 平面图
平面上的图(plane graph)：指的是画在平面上的一个图形，它的 所有的边都不相交（除顶点外）。
平面图(planar graph)：如果一个图经过重画之后，可以画成平面 上的一个边不相交的图形，则该图便称为平面图（可嵌入平面 (embeding)）。 Jordan curve：自身不相交的):
1）如果两个图能够从一个图G出发，通过在G的边上插入有限多 个2次顶点得到，则称这两个图是同胚。 2）如果两个图是同构的或通过反复插入或消去2次顶点后是同构 的，则称这两个图是同胚。 Th4.2：一个图为平面图当且仅当它不含与k5或k3.3同胚的子图。
Th4.3：一个图为平面图当且仅当它不含可以缩成k5或k3.3的子图。
4） G* 是连通的且为平面嵌入的。
Lemma4.10：设G为n，m和f且为平面上的连通图，其对偶图G*有n*， m*和f* n*= f， m= m*和n =f*。 Th4.11：设G为平面上的连通图，则G**≌G。 Th4.12：设G为平面上的连通图且G* 为G的对偶图，则G的边集构 成G的一个圈对应的G*的边集构成G*的一个割集。 Corollary4.13：设G为平面上的连通图且G* 为G的对偶图，则G的边 集构成G的一个割集对应的G*的边集构成G*的一个圈。
Th:一个图是可嵌入平面它是可嵌入球面。 Th4.4：设Ｇ是一个连通的平面上的图，n，m和f分别表示图Ｇ的顶 点数，边数和面数，则n-m+f=2。 Cor４.5：设Ｇ为具有n个顶点，m条边，f个面和k个分图的平面上的 图，则n-m+f=k+1。
Cor４.６：Ｇ<V,E>为简单连通平面图|V|=n（n>2）和|E|=m
Jordan closed curve： Jordan curve 两个端点重合。
Jordan curve theorem：C为在平面上的Jordan closed curve，平面 的其余部分被分成不相交的开集，分别称为C的外部和内部，则 连接内部和外部点的任何连续曲线必与C相交。 Th4.1：k5和k3.3不是平面图。
１）m≤3n-6； ２）如果G中不含三角形，则m ≤2n-4。
Cor４.7： k5和k3.3不是平面图。
Th4.8：每个简单平面图均包含一个次数最多为5的顶点。
下面内容见书： 一个图的厚度： Th4.9
4.3 对偶图
1. 对偶图(dual graph)： 任意一个平面上的图G， 如果：1）在G 的每个面Fi中选定一个点vi*作为顶点；
交叉数：为G画在平面上时，它的边出现相交的最少可能的数目。 记为：Cr(G)。
4.2 平面图上的欧拉公式
平面上的一个点x不与Ｇ相交的点：x既不是Ｇ的顶点也不是Ｇ的任 何一条边上的点。
Ｇ的包含ｘ的面：为平面上所有可以从ｘ出发通过一条不与Ｇ相交 的Jordan曲线而能达到的点的集合。
无穷面
Ｇ可嵌入曲面Ｓ：如果一个图Ｇ能够画在一张曲面Ｓ上，使得它的 边除了顶点外再无其它交点。
2）对应于G的每条边e，画一条线e*，它只与e相交，而不与 G的其它边相交，并且连接位于e两边的面Fi中的顶点vi*作为边。
这样构成的图称为图G的对偶图，记为G*。 Note:1）G中的每个悬点都产生G*的一个自环； 2）G中多于一条公共边的面，便产生多重边；
3）H G 但是H* G* 不一定；