离散数学 7-5 平面图7-6对偶图与着色

韦尔奇·鲍威尔（WelchPowell）给出了一种对图的着色 方法，步骤如下：
（1）将图G中的顶点按度数递减次序排列。 （2）用第一种颜色对第一顶点着色，并将与已着色顶点不
邻接的顶点也着第一种颜色。 （3）按排列次序用第二种颜色对未着色的顶点重复（2）。
用第三种颜色继续以上做法，直到所有的顶点均着上色为 止。
4
5
6
定义1 ：设G=<V,E>是一个无向图，如果能够把G的所 有结点和边画在平面上，且使得任何两条边除了端点外 没有其它的交点，就称G是一个平面图。
判断一个图是否为平面图的简单方法是观察法： 找出基本循环，将交叉的边分别放置在基本循环内或 外而避免交叉。如下图所示：
但并非所有的图经过处理之后都可变为平面图。
2. 着色问题 在地图上，相邻国家涂不同的颜色，最少需要多少种 颜色？100多年前，有人提出了“四色猜想”，即只 用四种颜色就能做到，但一直无法证明，直到1976年 美国数学家才用电子计算机证明了这一猜想。 地图着色自然是对平面图的面着色，利用对偶图，可 将其转化为相对简单的顶点着色问题，即对图中相邻 的顶点涂不同的颜色。
设m=k-1（k≥1）时公式成立，现在考虑m=k时的 情况。因为在连通图上增加一条边仍为连通图， 则有三种情况：
（1）所增边为悬挂边，此时G的面数不变，顶点 数增1，公式成立。 （2）在图的任意两个不相邻点间增加一条边，此 时G的面数增1，边数增1，但顶点数不变，公式 成立。
（3）所增边为一个环，此时G的面数增1，边数增 1
于是有 r 2 m n 2m l
故 m l (n 2)
l2
(r为G的面数)
推论1:设图G是一个包含n个结点,m条边的连通简单平 面图，若n≥3,则m≤3n-6。

二、欧拉公式 1 定义6.2（面/外部面/内部面）
平面图G嵌入平面后将Ğ分成若干 个连通闭区域，每一个连通闭区域称为G 的一个面。
恰有一个无界的面，称为外部面。 其余的面称为内部面。
6.1 平面图与欧拉公式
2 欧拉公式 （1）定理6.1
若连通平面图G有n个顶点，e条边和f 个面，则
n-e+f=2 称为欧拉公式。 证明方法：归纳法
球面等，如果图G能画在曲面S上使得它 的边仅在端点处相交，则称G可嵌入曲面 (embeddable in the surface) S。
2. 定理6A.
图G可嵌入球面S
面P。
G可嵌入平
/*证明基于球极平面射影。*/ /*图嵌入平面与球面是一回事。*/
二、平面图
1 边界和度数
1）定义6A：
证明：
（1）归纳基础：一条边，欧拉公式成立；
（2）归纳步骤：假设m-1条边，欧拉公式成立；
考察m条边的连通平面图：
1）若有度数为1的顶点，则删去该顶点及其关联边， 便得到连通平面图G’，G’满足欧拉公式，再将删去 的点和边加回G’得到G也满足欧拉公式；
2）若没有度数为1的顶点，则删去有界面边界上的 任一边，便得到连通平面图G’， G’满足欧拉公式， 再将删去的边加回G’得到G也满足欧拉公式。
设G是有n个顶点，e条边，f个面的连 通平面图；又设G的几何对偶G*有n*个 顶点，e*条边，f*个面，则n*=f, e*=e, f*=n。
证明方法：前两个关系式直接由G*的定义 给出，第3个关系式由欧拉公式推出。
3 定理6.5 G是连通平面图G**同构于G。
6.1 平面图与欧拉公式（补充）
一、球面与平面 1. 嵌入曲面 设S是一个给定的曲面，比如平面，

定理4.6.6
f (Tn , t ) t (t 1)n1.
这由 (Tn ) 2即可得证。当 t 2时，f (Tn ,t) 2.
色数与色数多项式
定理 4.6.7
设i,j是G的不相邻结点，则
_
0
—0
f (G, t) f (Gij , t) f (Gij , t). 其中Gij ，Gij 由定义4.6.3给出
d0
，因此
(G' ) d0
1．即
d0
1 种颜
色可以对G '的结点着色，放回结点 vi 恢复成Ｇ，由
于d (vi ) d0 ，所以比有一种与 vi邻点都不同的颜色可
对vi 着色．
色数与色数Байду номын сангаас项式
定理 4.6.3 对于任意一个图G. γ(G) <= 1 + maxδ(G’) 其中δ(G’)是G的导出子图G’中结点的最小度, 极大是对所有的G’而言.
定理 4.5.4 若任何一个3-正则平面图的域可四着色,则任何 一个平面的域也可以四着色.
4.6 色数与色数多项式
定义 4.6.1 给定图G,满足相邻点结点着以不同颜色的最少 颜色数为G的色数,记为γ(G).
定义 4.6.2 给定图G,满足相邻边着以不同颜色的最少颜色 数目称为G的边色数,记为β(G).
色数与色数多项式
定理 4.6.1 一个非空图,γ(G) = 2,当且仅当它没有奇回路.
证明：充分性：在Ｇ中确定一个林 T '，其每个连通子
图都是树Ｔ， (T ) 2．由于每个回路都是偶回路．所
以加入每一条余树边都不会使结点着色发生变化，因
此 (G) 2．
必要性：如果Ｇ中有奇回路，则 (G) 3 ．矛盾．

则称G1与G2是同构的，记作G1 G2
怎样定义有向图的同构？
第 七 章
图
论
2/12/2021
28
离
散 例7、
数 学
a
d
第 七 章
图
论
2/12/2021
a' (b)
b
d ' (d)
c
c' (a)
b' (c)
29
离
散
数
学
1
2
6
10
7
9 8
2
5
3
第
3
4
七 章
彼得松图(petersen)
图
论
2/12/2021
1
5
6
10 7 8
9
4
30
离 散 数 学
第 七 章
图
论
2/12/2021
31
离 散 数 学
两个图同构必有： （1）结点数相同；
但不是充分条件
（满足这三个条件的两图 不一定同构）
第 （2）边数相同；
七
章 （3）度数列相同
图
论
2/12/2021
32
离 例8、 画出K4的所有非同构的生成子图。
散 数
七 章
边，构成一个无向重图，问题化为图论中简单道路
的问题。
图
论
2/12/2021
3
离 一、图的基本概念
散 数 学
旧金山
丹佛
洛杉矶
第 七 章
图
论
2/12/2021
底特律
芝加哥
纽约 华盛顿
4
离
散 设A、B是两个集合，称