离散数学平面图(精选)

i 1
i 1
i 1
i 1
经整理得 n-m+r = k+1。
2、 与欧拉公式有关的定理
定理17.8 设G为连通的平面图，且每个面的次数至少为 l(l3)，则 G的边数与顶点数有如下关系：
m l (n 2) l2
证明
由定理17.3（面的次数之和等于边数的2倍）及欧拉公式得
r
2m deg(Ri ) l r l(2 m n)
由于n3, 又G必为简单平面图，可知，G每个面的次数均3。
因为G为平面图，又为极大平面图。可证G不可能存在次数>3 的面。
假设存在面Ri的次数deg(Ri)=s≥4， 如图所示。
s
S-1
在G中，若v1与v3不相邻，在Ri内加边(v1,v3)不破坏平面性，这 与G是极大平面图矛盾，因而v1与v3必相邻，由于Ri的存在， 边(v1,v3)必在Ri外。
Microsoft Office PowerPoint，是微 软公司的演示文稿软件。用户可以在投影仪 或者计算机上进行演示，也可以将演示文稿 打印出来，制作成胶片，以便应用到更广泛 的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿，还可 以在互联网上召开面对面会议、远程会议或 在网上给观众展示演示文稿。 Microsoft Office PowerPoint做出来的东西 叫演示文稿，其格式后缀名为：ppt、pptx ；或者也可以保存为：pdf、图片格式等
(u,v)，称为在G中消去2度顶点w。
2、图之间的同胚 若两个图G1与G2同构，或通过反复插入或消去2度顶点后
是同构的，则称G1与G2是同胚的。
上面两个图分别与K3,3, K5同胚 。

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

本章说明
本章的主要内容
–平面图的基本概念 –欧拉公式 –平面图的判断 –平面图的对偶图
本章所涉及到的图均指无向图。
17.1 平面图的基本概念
17.2 欧拉公式
17.3 平面图的判断
17.4 平面图的对偶图
本章小结
习题
作业
17.1 平面图的基本概念
一、关于平面图的一些基本概念 1、 平面图的定义 定义17.1 G可嵌入曲面S——如果图G能以这样的方式画在曲面S上，
类似地，v2与v4也必相邻，且边(v2,v4)也必在Ri外部，于是必 产生(v1,v3)与(v2,v4)相交于Ri的外部，这又矛盾于G是平面图， 所以必有s＝3，即G中不存在次数大于或等于4的面，所以G的
每个面为3条边所围，也就是各面次数均为3。
只有右边的图为极大平面图。 因为只有该图每个面的次数都为3。
K5和K3,3都不是平面图。 定理17.1 设GG，若G为平面图，则G也是平面图。
设GG，若G为非平面图，则G也是非平面图。
由定理可知， Kn(n5)和K3,n(n3)都是非平面图。
定理17.2 若G为平面图，则在G中加平行边或环所得图还是 平面图。 即平行边和环不影响图的平面性。
二、平面图的面与次数（针对平面图的平面嵌入） 1、 定义 定义17.2 设G是平面图， G的面——由G的边将G所在的平面划分成的每一个区域。 无限面（外部面）——面积无限的面，记作R0。 有限面（内部面）——面积有限的面 ，记作R1, R2, …, Rk。 面Ri的边界——包围面Ri的所有边组成的回路组。 面Ri的次数——Ri边界的长度，记作deg(Ri)。
2、极大平面图的主要性质
定理17.4 极大平面图是连通的，并且n(n3)阶极大平面图 中不可能有割点和桥。

p –(q –1)+(r –1) = 2。整理即得 p – q + r = 2。
由归纳法原理，欧拉公式成立。
2019/11/11
离散数学
18
面等次平面图中边与点的关系
推论11.2.1：若简单平面图G (p, q, r)的每 个面的次数均为m , 则
q = m(p – 2) / (m – 2) 证明：由定理11.1.1，2q = d( fi ) = mr ，
此面之外，因而必相交, 此与G
的可平面性矛盾。
综合以上，知结论成立。
2019/11/11
离散数学
15
(充分性)若平面图G的每个面都是三角形， 则是G是极大平面图。
证明：设平面图G的每个面都是K3，若G不是 极 大 平 面 图 . 则 G 中 存 在 u 、 vV(G) ， 使 得 uvE(G)，且G+uv仍为平面图。
2019/11/11
离散数学
6
计算下图中各面的次数：
2
f0
4
1 f1
3
f0
f1
f2
(a)
d( f0 ) = 3 ; d( f1 ) = 5 。
(b)
d( f0 ) = 8 ; d( f1 ) = 3 ; d( f2 ) = 3 .
2019/11/11
离散数学
7
面的总次数为边数的两倍
定理11.1.1：对任何平面图G(p, q, r) ,有
下面我们对这三种情况分别予以讨论：
2019/11/11
离散数学
13
极大平面图的面都是三角形
证明：…
⑴若v1与v3不邻接，则v1v2v3v4v1 v1 所围成内部面，于是在该面内联

，m3n6为真. 否则G中含圈，每个面至少由l（l3）条边围成
，又
l 1 2
l 2 l 2
在l=3达到最大值，由定理17.11可知m3n6.
定理17.13 设G为n（n3）阶m条边的极大平面图，则m=3n6. 证明：由定理17.4, 欧拉公式及定理17.7所证。
定理17.14 设G 为简单平面图，则 (G)5. 证明： 阶数 n6，结论为真。 当n7 时，用反证法。否则会 推出2m6n m3n，这与定理17.12矛盾.
如上面的例子。
18
精选PPT
平面图与对偶图之间的关系
定理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中，则d(v*i)=deg(Ri) 证明： (1)、(2)平凡 (3) 应用欧拉公式 (4) 的证明中注意，桥只能在某个面的边界中，非桥边在两
20
精选PPT
自对偶图
定义：设G*是平面图G的对偶图，若G*G，则称G为自 对偶图. 概念： n阶轮图（ Wn ）、奇阶轮图、偶阶轮图 轮图都是自对偶图。 画出W6和W7的对偶图，并说明它们都是自对偶图。
21
精选PPT
第十七章 小结
❖ 主要内容 ▪ 平面图的基本概念 ▪ 欧拉公式 ▪ 平面图的判断 ▪ 平面图的对偶图
22
精选PPT
练习1
1. 设G是连通的简单的平面图，面数r<12，(G)3. (1) 证明G中存在次数4的面 (2) 举例说明当r=12时，(1) 中结论不真.
解 设G的阶数、边数、面数分别为n, m, r.

在23岁时，他发表了他还是一个17岁的孩子时作出的“奇怪的发 现”，…即《光线系统理论》第一部分，这是一篇伟大的杰作，它对于 光学，就象拉格朗日的《分析力学》之于力学。
哈密尔顿最深刻的悲剧既不是酒精，也不是他的婚姻，而是他顽固地
相信，四元数是解决物质宇宙的数学关键。…从来没有一个伟大的数学
家这样毫无希望地错误过。
2
1
3
4
(2) 有限面与无限面：面积有限的区域称为有 限面(或内部面)，否则为无限面(或外部面) 。 上图中，面4是无限面。
7/1/2020 9:05 PM
第四部分：图论（授课教师：向胜军）
24
(3) 面的次数等于面边界的边数(注意：悬挂边算2 次)，记为deg(R).
(4) 平面图中面的次数之和等于边数m的两倍，即
d(u)+d(v)≥n-1 则G是半哈密尔顿图。
注意:
此定理条件显然不是必要条件，如n≥6的n边形，对于 任意不相邻的顶点u, v, d(u)+d(v)=4，4<n-1，而n边形显 然有哈密尔顿通路。
7/1/2020 9:05 PM
第四部分：图论（授课教师：向胜军）
18
哈密尔顿图的充分条件
❖ 设G是n(n≥3)阶无向简单图，若G中 任意不相邻的顶点对u,v均满足： d(u)+d(v)≥n 则G是哈密尔顿图。
a
bc
d
e
f g
h
i j
k
l
ba
d
g
e j
f
l
b
a
c
d
g
j
i
e
h
f
k
7/1/2020 9:05 PM

定理15.4 设G为任一平面图, 则(G)≤5. (五色定理)
用第一数学归纳法对G的顶点数n进行归纳: 显然, 当n≤5时, 有(G)≤5. 假设 n–1 (n≥6)时, (G)≤5成立.
显然, 平面图G中必有度数小于6的顶点u0. (因m≤3n-2) 将顶点u0从G中去掉(含u0邻接的边), 得G0=G – u0, 则G0仍是平面图且顶点数为n-1, 根据假设, 有(G0)≤5. 再从G0加入顶点u0及邻接的边, 还原为G. ⑴如果d(u0)≤4, 则与u0邻接顶点最多涂4色, 有(G)≤5成立. ⑵如果d(u0)=5, 令与u0邻接的顶点按顺时钟排为u1,u2,u3,u4,u5. 并设这5个顶点涂色为C1,C2,C3,C4,C5.
3
定义15.2 设G是一个平面图, 如果连接G的任意两个 不邻接顶点u和v, 都会使G+(u,v)变成非平 面图, 则称G为极大平面图. (边数极大)
极大平面图
K5非平面图
K3
定理15.2 设G是至少具有三个顶点的极大平面图, 则G的任何一个面都是K3.
假设G是极大平面图, 但有一个面不是K3面, 不妨设为{u1,u2,u3,u4,…,u1}, 考察: ⑴ (u1,u3)邻接, (u2,u4)邻接 两边会在圈外相交 ⑵ (u1,u3)不邻接 可加边(u1,u3), 仍是平面图 ⑶ (u2,u4)不邻接 可加边(u2,u4), 仍是平面图
6
§15.2 色数
1. 对偶图 定义15.3 设G是一个平面图, 具有k个面F1,F2,…,Fk, 其中包括无限面, 构造对偶图G*: ⑴ 在G的每个面Fi的内部取一点fi, 作为G*的顶点; ⑵ 对应于G的任意一条边e,
如果e是Fi和Fj的公共边, 则与e交叉连接fi和fj, 使(fi, fj)G* 如果e仅是Fj的悬挂边或桥, 则连一个自环, 使(fj, fj)G*

17-1 平面图 Plane Graph
1. 定义 设G是无向图, 如果能将G的所有结点和边都画
在一个平面上,且使得任何两条边除了端点外有 其它交点, 则称G是个平面图。 画出的没有边交 叉出现的图，称为G的平图。一个图表面上是个 非平面图, 如果通过改变边的位置就变成平面图, 称此图是可平面化的。
v1 v2 v7 v6 v10 v5
v8 v3
v9 v4
v1
v3 v8
v2 v7 v6
v8 v3
v9 v10 v4
v5
v9 v4
1
2 65
7
10
收缩边（1,6) (2,7)(3,8)
3 8 9 4 (4,9)(5,10)
16 5
16 5
去掉（1,3)
f*2
e*6 e*8
e*3
f*4
e*5 e*4 f*3
对偶图的性质
1. G*是唯一的, 且G*是连通的. 2. G*是平面图. 3. 若G是平面连通图, 则(G*)*=G. 4. m(G*)=m(G), n(G*)=r(G), d(v*)=d(f). 5. 设C是平面图G的一个圈, S*是G*中与C的各边ei对应的 G*的边集合 , 则S*是G*的一个割集. 证明: ∵ C把G的域分成两部分, ∴ E(G*)-S*把G*的点分成 不连通的两部分.
v3
v4
v5
a
b c
f e
d
二、对偶图 v7
1. 平面图的面、边界及面的次数
设G是个平面图, 图中
边围成的区域,其内部不 含有结点, 也不含有边,
v6
f5 f6 v8 f4
v1
f1 v4 v5
f2 f3 v2 v3

是指对它的每一个结点指定一种颜色，使得没 有两个邻接的结点有同一种颜色。如果图在着 色时用了n种颜色，我们称G为n-色的图。 3、色数：对于图G着色时，需要的最少颜色数 称为G的色数，记作x(G)。
证明一个图的色数为n，首先 必须证明用n种颜色可以着色该 图，其次证明用少于n种颜色不 能着色该图。
4、对点着色的鲍威尔方法： 第一步：对每个结点按度数递减次序进行排列(相 同度数的结点次序可随意) 第二步：用第一种颜色对第一个结点着色，并按次
颜色即可对地图着色的猜想，1879年肯普(Kempe) 给出了这个猜想的第一个证明，但到1890年希伍德
(Hewood)发现肯普证明是错误的，但他指出肯普
的方法 虽不能证明地图着色用四种颜色就够了，但 可证明用五种颜色就够了，即五色定理成立。

此后四色猜想一直成为数学家感兴趣而未能解 直到1976年美国数学家阿佩尔和黑肯宣布：他
(2)归纳假设：设G有k个结点时结论成立。即G是最多可5-着色 的。 (3)归纳推理：需要证明G有k+1个结点时结论仍成立。 先在G中删去度数小于5的结点u,根据归纳假设，所得的图G-{u} 有k个结点,结论成立。然后考虑在G-{u}中加上一个结点的情况。 若加入的结点满足deg (u)<5，则可以对u正常着色。若加入的结 点满足deg (u)=5，则与它邻接的5个结点可以用4种颜色着色。 分两中情况证明： . 对调v1,v3两个结点的颜色后，给着v1的颜色。 .对调v2,v4两个结点的颜色后，给着v2的颜色。
r=8，则e=2r=16。
5.定理7-5.3 设G为一简单连通平面图，其顶点数 v≥3，其边数为e，那么 e≤3v – 6 证明思路：设G的面数为r,当v=3,e=2时上式成立, 若e≥3,则每一面的次数不小于3。由欧拉定理，各面 次数之和不小于2e。因此 2e≥3r, r≤2e/3 代入欧拉公式: 2=v-e+r≤v-e+ 2e/3 整理后得: e≤3v – 6

15
18.4 点着色
定义17.9 (1) 图G的一种点着色——给图G的每个顶点涂上一种颜色，
使相邻顶点具有不同颜色 (2) 对G进行k着色（G是k-可着色的）——能用k种颜色给G
的顶点着色 (3) G的色数(G)=k——G是k-可着色的，但不是(k1)-可着色
的.
16
关于顶点着色的几个简单结果
定理17.19 (G)=1当且仅当G为零图 定理17.20 (Kn)=n 定理17.21 若G为奇圈或奇阶轮图，则(G)=3，若G为偶阶轮 图，则(G)=4. 定理17.22 若G的边集非空，则(G)=2当且仅当G为二部图.
路径 (7) M的交错圈——由M与EM中的边交替出现构成的G中圈
上图中，只有第一个图存在完美匹配
8
可增广路径及交错圈
(1)
(2)
(3)
设红色边在匹配M中，绿色边不在M中，则图(1)中的两条路 径均为可增广的交错路径；(2)中的全不是可增广的交错路 径；(3)中是一个交错圈. 不难看出，可增广交错路径中，不在M中的边比在M中的边 多一条. 交错圈一定为偶圈.
立集 (3) 最大点独立集——元素最多的点独立集 (4) 点独立数——最大点独立集中的元素个数，记为0
(1)
(2)
在图中，点独立数依次为2, 2, 3.
(3)
2
极大独立集与极小支配集
定理18.1 设G=<V,E>中无孤立点，则G的极大点独立集都是 极小支配集. 证明线索： (1) 设V*为G的极大点独立集，证明它也是支配集.
定理17.28 偶圈边色数为2，奇圈边色数为3. 定理17.29 (Wn) = n1, n4. 定理17.30 二部图的边色数等于最大度. 定理17.31 n为奇数（n1）时，(Kn)=n；