文档介绍：该【平面图及图的着色 】是由【435638】上传分享，文档一共【73】页，该文档可以免费在线阅读，需要了解更多关于【平面图及图的着色 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第17章 平面图及图的着色
单击此处添加副标题
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。
演讲人姓名
本章说明
本章的主要内容
项目背景
单击此处添加正文
02.
项目概况
单击此处添加正文
Contents.
单击添加标题
本章所涉及到的图均指无向图。
Part 01.
1 平面图的基本概念
01
2 欧拉公式
02
3 平面图的判断
03
4 平面图的对偶图
04
5 图中顶点的着色
05
6 地图的着色与平面图的点着色
06
7 边着色
07
本章小结
08
习 题
09
作 业
10
平面图的基本概念
一、关于平面图的一些基本概念
1、 平面图的定义
G可嵌入曲面S——如果图G能以这样的方式画在曲面S上，即除顶点处外无边相交。
G是可平面图或平面图——若G可嵌入平面。
G的平面嵌入——画出的无边相交的平面图。
非平面图——无平面嵌入的图。
是（1）的平面嵌入，（4）是（3）的平面嵌入。
一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一定是指平面嵌入。
1
K5和K3,3都不是平面图。
2
设GG，若G为平面图，则G也是平面图。
3
设GG，若G为非平面图，则G也是非平面图。
4
推论 Kn(n5)和K3,n(n3)都是非平面图。
5
若G为平面图，则在G中加平行边或环所得图还是平面图。
6
即平行边和环不影响图的平面性。
7
几点说明及一些简单结论
二、平面图的面与次数（针对平面图的平面嵌入）
1、 定义
设G是平面图，
G的面——由G的边将G所在的平面划分成的每一个区域。
无限面（外部面）——面积无限的面，记作R0。
有限面（内部面）——面积有限的面 ，记作R1, R2, …, Rk。
面Ri的边界——包围面Ri的所有边组成的回路组。
面Ri的次数——Ri边界的长度，记作deg(Ri)。
2、几点说明
若平面图G有k个面，可笼统地用R1, R2, …, Rk表示，不需要指出外部面。
回路组是指：边界可能是初级回路（圈），可能是简单回路，也可能是复杂回路。特别地，还可能是非连通的回路之并。
平面图有4个面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。
R1
R2
R3
R0
平面图G中所有面的次数之和等于边数m的两倍，即
1
本定理中所说平面图是指平面嵌入。
e∈E(G)，
当e为面Ri和Rj(i≠j)的公共边界上的边时，在计算Ri和Rj的次数时，e各提供1。
当e只在某一个面的边界上出现时，则在计算该面的次数时，e提供2。
于是每条边在计算总次数时，都提供2，因而deg(Ri)=2m。
2
证明
3