当前位置:文档之家› 第十七章 平面图及图的着色

第十七章 平面图及图的着色


若e为G中的桥且在面Ri 的边界上,则e*是以Ri 中G*的顶点v*i为端点的环,即e*=(v*i,v*i).
下图实线边图为平面图,虚线边图为其对偶图.
练习:求下图的对偶图
二、平面图与对偶图的阶数、边数与面数之间 的关系. 定理17.17 设G*是连通平面图G的对偶图,n*, m*, r*和n, m, r分别为G*和G的顶点数、边数和 面数,则 (1)n*= r (2)m*=m (3)r*=n ( 4 ) 设 G* 的 顶 点 v*i 位 于 G 的 面 Ri 中 , 则 dG*(v*i)=deg(Ri)
例:
图(2),(3)都是图(1)的平面嵌入,图(2)中, R0)=3,图(3)中,deg(R0) =4,它们虽然形 状不同,但都与(1)同构。
定理17.4 平面图各面次数之和等于边数的两倍.
证明: 因为任何一条边,或者是两个面的公 共边,或者在一个面中作为边界被重复计算两 次,故面的次数之和等于其边数的两倍。
R2的边界:v1v2v3v1 ,deg(R2)=3 ;
R0 的边界为复杂回路: v1v2v3v4v5v6v5v4v1, deg(R0)=8 。
注意: (1) 一个平面图的无限面只有一个。 (2) 同一个平面图可以有不同形状的平面 嵌入 (互相同构)。 (3) 不同的平面嵌入可能将某个有限面变 成无限面,而将无限面变成有限面。
定理17.12:设G是n(n≥3)阶m条边的简单平面 图,则m≤3n-6
证明:设G有k个连通分支。若G为树或森林, 因为(3n-6)-(n-k)=2n-6+k ≥0,所以m=n-k ≤3n-6 (n≥3)。若G不是树也不是森林,则G中必含圈, 又因为G为简单图,所以各圈的长度均大于或 等于3,因各面的次数至少为l,又
1、韦尔奇· 鲍威尔法(Welch Powell)
⑴将图G的顶点按照度数的递减次序进行排列。 (这种排列可能并不是唯一的,因为有些点有 相同的度数)。 ⑵用第一种颜色对第一点进行着色,并且按排 列次序,对前面着色点不邻接的每一点着上同 样的颜色。 ⑶用第二种颜色对尚未着色的点重复⑵,用第 三种颜色继续这种做法,直到所有的点全部着 上色为止。
三、自对偶图
定义17.8 设G*是平面图G的对偶图,若G*G,则 称G为自对偶图。
四、着色问题
从对偶图的概念,可以看到,对于地图的着色问题, 可以归纳为对于平面图的顶点着色问题,因此四色 问题可以归结为要证明对于任何一个平面图,一定 可以用四种颜色,对于它的顶点进行着色,使得邻 接的顶点都有不同的颜色。 着色数 x(G):对图G着色时,需要的最少颜色数。
3 10 (5 2 ) 9 3 2
这是个矛盾,所以K5不是平面图. 同理,若K3,3 是平面图,由于K3,3 中圈的长度 l≥4,所以边数9应满足
4 9 ( 6 2) 8 42
这是个矛盾,所以K3,3不是平面图.
定理17.11 :设G是有k个连通分支的平面图, 各面的次数至少为l(l≥3),则边数m与结点数n 应满足如下关系:
l 2
证明:由于平面图各面次数之和等于边数的两 倍,所以 2m r deg( R ) l r (1)

i 1
i
由欧拉公式可知 r=2+m-n (2) 将 (2)代入(1)得2m≥l(2+m-n) 整理得:
l m ( n 2) l 2
推论 K5, K3,3不是平面图.
证明:若K5是平面图,由于K5中无环和平行边, 所以每个面的次数均大于或等于l≥3,根据定理 17.10可知边数10应满足
l m ( n k 1) l 2
证明:由于平面图各面次数之和等于边数的两 r 倍,所以 2m deg( R ) l r (1)

i 1
i
由欧拉公式的推广可知 r=k+1+m-n (2) 将 (2)代入(1)得2m≥l(k+1+m-n) 整理得:
l m ( n k 1) l 2
例: 用韦尔奇· 鲍威尔法对下图着色
解: ⑴根据递减次序排列各点A5,A3,A7,A1, A2,A4,A6,A8。 ⑵第一种颜色对A5着色,并对不相邻的结点A1 也着第一种颜色。 ⑶对A3结点和它不相邻的结点A4,A8着第二种 颜色。 ⑷对A7结点和它不相邻的结点A2,A6着第三种 颜色。 因此图G是三色的。所以x(G)=3。
(2)无限面或外部面:(可用R0表示)面积无限的面。
(3)有限面或内部面(可用R1, R2, …, Rk等表示):面 积有限的面 。 (4)面Ri的边界:包围Ri的回路组。
(5)面Ri的次数:Ri边界的长度,用deg(Ri)表示 。
例:
v1 R1
v4
v6 R0
R2
v2 v3
v5
此平面图,共有3 个面:R0,R1,R2 ; R1 的边界: v1v3v4v1,deg(R1) =3;
定义:设G为简单平面图,若在G的任意不相 邻的结点u,v之间加边(u,v),所得图为非平 面图,则称G为极大平面图。 例:K1,K2,K3,K4,K5-e都是极大平面图。 定理17.5:极大平面图是连通的。 定理17.6:设G为n(n≥3)阶极大平面图,则G 中不可能存在割点和桥。 定理17.7:设G为n(n≥3)阶简单连通的平面图, 极大平面图当且仅当G的每个面的次数均为3。
(2)是(1)的平面嵌入;
(1)
(2)
例:
(1)即K4 图,(2)是(1)的平面嵌入,故(1)是平面图. (4)是(3)的平面嵌入,故(3)是平面图。 (5)即K5 图,无论怎样画,都不可能将交叉的边 全去掉,(6)是(5)的一种画法。 (7)即K3,3 图,无论怎样画,也不可能将交叉的 边全去掉;(8)是(7)的一种画法。 故 K5和 K3,3都不是平面图。 注意: 有些图形从表面上看有几条边是相交的,但不 能就此肯定它不是平面图。
若G不是树,则G中含有圈,设边e在G的某个圈 上,令G’=G-e,则G’仍连通,且m’=m-1=k, 由归纳假设有n’-m’+r’=2,而n’=n,r’=r-1,于 是 n-m+r=n’-(m’+1)+(r’+1)= n’-m’+r’=2
定理17.9 (欧拉公式的推广)设G是具有k(k2) 个连通分支的平面图,则nm+r=k+1 。 证明:设G的连通分支分别为G1,G2,…,Gk ,并 设 Gi 的 结 点 数 , 边 数 和 面 数 分 别 为 ni,mi,ri,i=1,2,…,k。由欧拉公式可知 ni-mi+ri=2 (1) 又m=∑mi, n=∑ni,由于每个Gi有一个外部面, 而G只有一个外部面,所以
若G是树,则G是非平凡的,因而G中至少有2 片树叶,设v为树叶,令G’=G-v,则G’仍然连 通,且G’的边数m’=m-1=k,由归纳假设可知 n’-m’+r’=2 ( n,m’,r ‘分别为G’的结点数、 边数和面数),所以 n-m+r=(n’+1)-(m’+1)+r’= n’-m’+r’=2 。
第十七章 平面图及图的着色
在一张纸上画几何模型时常常会发 现,不仅需要允许各边在结点处相交, 而且还应该允许各边在某些非结点处相 交。但是,有些图形是不允许边交叉的, 例如大家熟悉的印制电路,除了结点外, 它的导线是不允许交叉的,这就是本章 要学习的平面图。
本章的主要内容
平面图的基本概念
欧拉公式
2、相关结论
定理:对于n个结点的完全图Kn,有 x(Kn)=n。 定理:任意平面图G至多是5-色的。
例:某大学计算机专业三年级学生总共 选n门选修课,期末考试前必须提前将这 n门选修课程考完。要求每天每人在下午 考一门课,问至少需要几天考完这n门课? 若设n=5,并且课程1与2,1与3,1与4, 2与5,3与4,3与5均有人同时选,问至 少需要几天考完这5门课程?
f
g
h
证明:在左图中将边(a,f), b (b,g),(c,h),(d,i),(e,j)收缩 所得的图为K5,由于K5不是 平面图,所以彼得松图不是 平面图。
c
17.2 图的着色
问题的提出:这个问题最早起源于地图的着色,一个 地图的相邻的两个国家着于不同的颜色,那么最少需 用多少种颜色?一百多年前,英国格色里(Guthrie)提 出了用四种颜色即可对地图着色的猜想,1879年肯普 (Kempe)提出了这个猜想的第一个证明,但到1890年希 伍德(Hewood)发现肯普的证明是错误的,但他指出肯 普的方法,虽不能证明地图着色用四种颜色就够了, 但可证明用五种颜色就够了。此后四色猜想一直成为 数学家感兴趣而未能解决的难题。直到1976年美国数 学家阿佩尔和黑肯宣布:他们用电子计算机证明了四 色猜想是成立的。所以从1976年以后就把四色猜想这 个名词改为“四色定理”了。
平面图的判断
平面图的对偶图 图的着色
17.1 平面图
一、关于平面图的一些基本概念
1. 平面图的定义(定义17.1 ) (2)G是可平面图或平面图——G可嵌入平面。 (3)平面嵌入——画出的无边相交的平面图。
(1)G可嵌入曲面S:若能将G除顶点外无边相交地画在S上。
(4)非平面图——无平面嵌入的无向图。
4、两个判定定理 定理17.15 G是平面图 G中不含与K5或K3,3同胚 的子图. 定理17.16 G是平面图 G中无可收缩为K5或K3,3 的子图
例: 证明下图所示二图均为非平面图.
两个图的子图如下,分别与K3,3, K5同胚.
例:证明彼得松(Prterson)图不是平面图。
a
e
j i d
l 2 1 l2 l2
在l=3时达到最大值3,由定理17.11知
l m (n k 1) 3( n 2) 3n 6 l 2
定理17.13:设G是n(n≥3)阶m条边的极大平 面图,则m=3n-6。
相关主题