离散数学平面图共47页文档

9
图的同构与平面图的同构
如果两个图是平面图同构，则必是两个同构的 图。可是两个同构的图不一定是平面图同构。
例1中图⑴与图⑵和图⑶是同构的图，但图⑴ 却不是平面图，因而不可能和它们平面图同构。
下面两个平面图是图同构，但不是平面图同构：
3
4
2020/1/22
2
3’ 2’
6
1 6’
1’
4’
5
由归纳法原理，欧拉公式成立。
2020/1/22
离散数学
18
面等次平面图中边与点的关系
推论11.2.1：若简单平面图G (p, q, r)的每 个面的次数均为m , 则
q = m(p – 2) / (m – 2) 证明：由定理11.1.1，2q = d( fi ) = mr ，
解出r，代入欧拉公式, 得
5
平面图的面
定义11.1.2：设G是一个平面图，平面被G的边 所围成的区域称为面，这些边称为该面的边界； 其中有限区域对应的面称为内部面，无限区域 对应的面称为外部面(用f0表示)。
用G(p, q, r)表示一个p个顶点，q条边以及r个面 的平面图。
一个面 f 所包含的边数称为 f 的次数，记为 d( f ) ，若边为割边，则计算两次。
证明：对面数r作归纳证明。
当r=1时，G是树，此时q = p – 1，结论成立。
假设对G (p, q, r-1)， r2，结论成立，设G是
有r个面的平面图，G至少有一条回路。设e是
某回路上的边，G –e仍是连通平面图，它有p
个顶点，q –1条边和r –1个面，由归纳假设有，
p –(q –1)+(r –1) = 2。整理即得 p – q + r = 2。

二、欧拉公式 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 ．矛盾．

离散数学图的基本概论
56、极端的法规，就是极端的不公。 ——西 塞罗 57、法律一旦成为人们的需要，人们 就不再 配享受 自由了 。—— 毕达哥 拉斯 58、法律规定的惩罚不是为了私人的 利益， 而是为 了公共 的利益 ；一部 分靠有 害的强 制，一 部分靠 榜样的 效力。 ——格 老秀斯 59、假如没有法律他们会更快乐的话 ，那么 法律作 为一件 无用之 物自己 就会消 灭。— —洛克
60、人民的幸福是至高无个的法。— —西塞 罗
16、业余生活要有意义，不要越轨。——华盛顿 17、一个人即使已登上顶峰，也仍要自强不息。——罗素·贝克 18、最大的挑战和突破在于用人，而用人最大的突破在于信任人。——马云 19、自己活着，就是为了使别人过得更美好。——雷锋 20、要掌握书，莫被书掌握；要为生