当前位置：文档之家 › 图论第6章

图论第6章

  • 格式：ppt
  • 大小：1.11 MB
  • 文档页数：76

下载文档原格式

  / 76

合集下载

图论第5、6章

图论第5、6章

第5章 对集
算法用生长“以u为根的M交错树”的 方法 ，来系统地搜索M可扩路. 树中除 u外都是M饱和的，直到碰到第一个 M 不饱和的顶点时，即得一M可扩路.当树 不能再生长下去时，即有N(S)=T.
本算法是个‘好’算法： 从一个M到 下一个，至多进行X次搜索运算；M 至多扩大X次.
例：
5.5 最优分派问题
第5章 对集
构作一个具有二分类(X, Y)的偶图G，其中 X＝{X1, X2, …, Xn}，Y＝{Y1, Y2, …, Yn}， 并且Xi与Yj相连当且仅当工人Xi胜任工作Yj. 于是问题转化为确定G是否有完美对集的问 题.
下面给出的算法称为匈牙利算法，对任意 一个具有二分类(X, Y)的偶图G，它寻找G 的一个饱和X中所有顶点对集，或找到X的 一个子集S，使|N(S)| ＜ |S| .
第5章 对集
若G有正常的k边着色，则称G是k边可着色的. 每个无环图都是ε边可着色的； 若G是k边可着色的，则一定是k＋1边可着色的. 使G为k边可着色的最小整数k称为G的边色数， 记为χ’(G) . 若G的边色数为k，也称G是k边色的. 下图的边色数是多少？
第5章 对集
显然，在任何正常边着色中，和任一顶 点关联的边必须分配以不同的颜色，因 此
第5章 对集
定理5.2(Hall 1935) 设G是具有二分类(X,Y) 的偶图，则G包含饱和X的每个顶点的对集当 且仅当
|NG(S)|≥|S| 对所有S ⊆ X成立.
❖Hall定理是图论中最有用的定理之一，它 在数学及其他许多学科中都有应用.
Hall定理的证明
第5章 对集
必要性 假设G包含对集M，它饱和X的每个顶 点，并设S是X的子集. 由于S的顶点在M下和 N(S)中相异顶点配对，显然有|N(S)| ≥ |S| .

国科大中科院图论与网络流理论第6章答案

国科大中科院图论与网络流理论第6章答案

,Vk 是 G I 的一个正常 k -点染色，即 V1 ,V2 ,
V j ,
k i 1
,Vk 是 V (G I ) 的
一个划分，每个 Vi 非空， Vi
Vi V (G I ) 。从而
k i 1
Vi
I V (G ) ，且是
V1 ,V2 ,
因此构成 G 的一个 k 1 正常点染色， 故 (G) k 1 ， ,Vk , I 互不相交的独立集。
(G) (G I ) 1，即 (G) 1 (G I ) 。
结合式（1）得 (G I)
(G) 1 。
证明 2： G 是 k 色临界的，则 (G) k ，且 (G I ) k 1 。 另一方面，若 (G I ) r k 1，无妨设 G I 的一个 r 正常染色为 V1 ,V2 , 则 V1 ,V2 ,
即 (G I ) (G) 1 ，结合（2）式，得 (G I)
(G) 1 。
ห้องสมุดไป่ตู้
证明 4： 因 G 是色临界图， 故 (G I ) (G) 1 ， 另一方面， 假如 (G I ) (G) 2 ， 则 G I 是 (G) 2 色可染的，因 G I 是 G 的子图，对 G I 进行 (G) 2 色正常染色 后，再用第 (G) 1种色对 I 中的点染色，可得 G 的 (G) 1正常点染色，这与 G 的色数
证法 3：假如 (G) ，则由正则性， G 的每个点都与 种颜色的边相关联，从而去掉一 种颜色的边后所得之图 G 是 个顶点的 k 1 正则图。在 G 中看， 2
d (v )
vG

第六章图与网络分析

第六章图与网络分析

e3
v3
若链中所有的顶点也互不相同,这样的链称为路.
e4
v4
起点和终点重合的链称为圈. 起点和终点重合的路称为回路.
若图中的每一对顶点之间至少存在一条链, 称这 样的图为连通图, 否则称该图是不连通的. 第10页
完全图，偶图
任意两点之间均有边相连的简单图, 称为完全图. K n
K2
K3
K4
2 | E | Cn
第20页
6.2树图和图的最小部分树问题 Minimal tree problem 6.2.1树的概念
若图中的每一对顶点之间至少存在一条链, 称这样的图 为连通图. 树图(简称树Tree)： 无圈的连通的图，记作T(V, E)
组织机构、家谱、学科分支、因特网络、通讯网络及高压线路 网络等都能表达成一个树图 。
第13页
有向图 G ： (V,E)，记为 G=(V,E)
G 的点集合： V {v1 , v2 ,...,vn } G 的弧集合： E {eij } 且 eij 是一个有序二元组 (vi , v j ) ，记
为 eij (vi , v j ) 。下图就是一个有向图，简记 G 。 若 eij (vi , v j ) ，则称 eij 从 v i 连向 v j ，点 v i 称为 eij 的尾，v j 称为 eij 的头。 v i 称为 v j 的前继， v j 称为 v i 的后继。 基本图：去掉有向图的每条弧上的方向所得到的无向图。
有向图 G (V , E ) 的关联矩阵：一个 | V | | E | 阶矩阵
B (bik ) ，
1, 当 弧ek以 点i为 尾 其中 bik 1, 当 弧ek以 点i为 头 0, 否 则

图与网络分析

图与网络分析

end;
例 1 中 1 到 7 点的最短路是 1-2-5-7
查伴随矩阵 E 的第一行
1234567
10020255 19
hw
小结
• 最短路有广泛的应用 (P176案例) • 最短路的多种形式：无向图，有向图无循环圈，有向
图，混合图，无负边权，有负边权，有负回路，k-最 短路等 • 当存在负权值边时，Floyd算法比Dijkstra算法效率高， 且程序极简单。但Dijkstra算法灵活 • 若图是前向的，则Dijkstra算法也可以求两点间最长路 • 一般情况下，两点间最长路是 NP-complete，但最短 路是 P算法 • 两点间k-最短路：分为边不相交的和边相交的 求边不相交的k-最短路非常容易：先求最短路，将该 最短路中的边从网路删去，再用Dijkstra算法可求次最 短路，以此类推
hw
6.1.4 链，圈，路径，回路，连通图
• 走过图中所有边且每条边仅走一次的闭行走称为欧拉 回路
定理 2：偶图一定存在欧拉回路(一笔画定理) 6.1.4 连通图，子图，成分
• 设有两个图 G1(V1, E1), G2(V2, E2), 若V2 V1, E2 E1， 则 G2 是 G1 的子图
• 无向图中，若任意两点间至少存在一条路径，则称为 连通图(connected graph)，否则为非连通图( disconnected graph)；非连通图中的每个连通子图称为成分 (component)
线表示实体间的关联
A
A D
C
C
D
B
B
2
hw
6.1 图与网络的基本概念
6.1.1图与网络 • 节点 (Vertex)
– 物理实体、事物、概念 – 一般用 vi 表示

图论讲义第6章-染色应用

图论讲义第6章-染色应用

§6.5 染色应用举例—求图的边色数及色数的算法一、排课表问题—求二部图的正常)(G χ′边染色1. 问题： 有m 位教师m x x x ,,,21 ，n 个班级n y y y ,,,21 。

教师x i 每周需要给班级y j 上p ij 次（节）课。

要求制订一张周课时尽可能少的课程表。

2. 图论模型：构造二部图),(Y X G =，其中X ＝{m x x x ,,,21 }，Y ＝{n y y y ,,,21 }，顶点i x 与j y 之间连ij p 条边。

一个课时的安排方案对应于二部图G 的一个匹配。

排课表问题等价于：将E (G )划分成一些匹配，使得匹配的数目尽可能地少。

按)(G χ′的定义，这个最小的数目便是)(G χ′。

由定理6.2.1，()()G G χ′=Δ。

因此，排课表问题等价于：求二部图G 的边正常)(G Δ染色。

如§6.1中所述，虽然求简单图的正常（1+Δ）边染色存在多项式时间算法，但求简单图G 的边色数)(G χ′及其相应的正常边染色是一个NPC 问题[28]。

尽管如此，求二部图的边正常Δ染色却有多项式时间算法。

求图的边色数的近似算法可参考文献[29]~[51]。

[28] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Computing , 10: 4(1981), 718-720.[29] E. Petrank, The hardness of approximation: gap location, Computational Complexity , 4 (1994), 133-157.[30] D. Leven and Z. Galil, NP completeness of finding the chromatic index of regular graphs, J. Algorithms , 4(1983) 35-44.[31] P. Crescenzi, V . Kann, R. Silvestri, and L. Trevisan, Structure in approximation classes, SIAM J. Comp., 28 (1999), 1759-1782.[32] J. Misra and D. Gries, A constructive proof of Vizing's theorem. Inform. Process. Lett. 41 (1992), 131-133.[33] O. Terada, and T. Nishizeki, Approximate algorithms for the edge-coloring of graphs, Trans. Inst. Eletron. Commun. Engr. Japan J65-D , 11(1982), 1382-1389.[34] M. Chrobak, and T. Nishizeki, Improved edge-coloring algorithms for planar graphs, J. Algorithms , 11(1990), 102-116.[35] I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Perennes, P. Persiano and H. Rivano, Approximate constrained bipartite edge coloring, Discrete Applied Mathematics , 143(2004), 54-61[36] M. R. Salavatipour, A polynomial time algorithm for strong edge coloring of partial k -trees, Discrete Applied Mathematics , 143(2004), 285-291.[37] D.A. Grable, A. Panconesi, Nearly optimal distributed edge coloring in O (log log n ) rounds, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, January, (1997), 278–285.[38] Yijie Han, Weifa Liang and Xiaojun Shen, Very fast parallel algorithms for approximate edge coloring, Discrete Applied Mathematics, 108(2001), 227-238.[39] M. Fürer and B. Raghavachari, Parallel edge coloring approximation, Parallel Process. Lett. , 6 (1996), 321–329.[40] H.J. Karloff and D.B. Shmoys, Efficient parallel algorithms for edge coloring problems. J. Algorithms 8 (1987), 39–52.[41] W. Liang, Fast parallel algorithms for the approximate edge-coloring problem. Inform. Process. Lett. 56 (1995), 333–338.[42] W. Liang, X. Shen and Q. Hu, Parallel algorithms for the edge-coloring and edge-coloring update problems. J. Parallel Distrib. Comput. 32 (1996), 66-73.[43] R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms. J. Comput. System Sci. 49 (1994), 478-516.[44] D. Bertsimas, C-P. Teo, and R. V ohra, On dependent randomized rounding algorithms, Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization , Lecture Notes in Comput. Sci. 1084, Springer-Verlag, (1996), 330-344.[45] M.K. Goldberg, Edge-colorings of multigraphs: recoloring technique, J. Graph Theory , 8(1984), 123-127.[46] D.S. Hochbaum, T. Nishizeki and D.B. Shmoys, Better than “Best Possible” algorithm to edge color multi graphs, Journal of Algorithms , 7(1986), 79-104[47] T. Nishizeki and K. Kashiwagi, On the 1.1 edge-coloring of multigraphs, SIAM J. Disc. Math. , 3(1990), 391-410.[48] J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory (Ser. B ), 68(1996), 233-254.[49] X. Zhou H. Susuki, and T. Nishizeki, A linear algorithm for edge-coloring series-parallel multigraphs, J. Algorithms , 20(1996), 174-201.[50] X. Zhou H. Susuki, and T. Nishizeki, An NC parallel algorithm for edge-coloring series-parallel multigraphs, J. Algorithms , 23(1997), 359-374.[51] B. Berger and J. Rompel, Simulating (log c n )-wise independence in NC. J. ACM 38 (1991), 1026–1046.3. 求二部图),(Y X G =的边正常)(G Δ染色的算法z 算法思想：给G 添加必要的顶点使得||||Y X =，再添加必要的边使得G 成为)(G Δ正则二部图，所得图记为*G ，然后反复运用匈牙利算法求*G 的完美匹配。

第6-8章 图论2

第6-8章 图论2

5.设D是有向图，当且仅当D中有一条通过每个 D 结点的通路时，D为（ ）连通的。 答案：单向 6.设有向图D=<V，E>，V={a,b,c,d}, E={<a,b><a,d><d,c><b,d><c,d>},则D是 （ ）连通的，c的可达集为()，d(c,a)=()
6.设有向图D=<V,E>，V={a,b,c,d,}， E={<a,b>,<a,d>,<d,c>,<b,d>,<c,d>}, 则D是（ ）连通的，c的可达集为（ ），d(a,b)=（） 答案：单向 ｛c,d｝ 7.图６－１的点连通度为（），边连通度为（） 答案： １ １ 8.k5的点连通度为（），边连通度为（）。 答案： ４ ４
7.若无向图中恰有2个度数为奇数的结点，则这两个结 点必连通。（ ） 答案：T 8.在有向图中，结点间的可达关系是等价关系。（ ） 答案：F 9. 若有向图中有两个奇度结点，则它们中一个可达另 一个或互相可达。（ ） 答案：F
10.若图G不连通，则 G 必连通。（ ） 答案：T 11.有向图的每个结点恰位于一个单向分图中。（ ） 答案：F 12.图6-3为无强分图（ ） 答案：F 13.若图G的边e不包含在G的某简 图6-3 单回路中，则e是G的割边。（ ） 答案：T
22.设G= <V,E>为连通的简单平面图，若|V|>=3，则 所有结点v，有deg(v)<=5.（ ） 答案：F
第7章 树 章
树是图论中最重要的概念之一，它是基尔霍夫在解决 电路理论中求解联立方程时首先提出的。它又是图论 中结构最简单，用途最广泛的一种平面图，在计算机 科学的算法分析、数据结构等方面有着广泛的应用， 本章主要介绍树的基本概念、性质和若干应用。

《图论》第6章-图的着色

第七页，编辑于星期六：八点 一分。
6.1 色数
[定理6-1-1] k-临界图 G=(V, E), =min{deg(vi)|viV}, 则
k-1。
[证明]反证法：设 G 是一个 k-临界图且 <k-1。又设v0V， deg(v0)= 。由 k-临界图的定义，Gv0 是 (k1)可着色的， 在一种 k1着色方案下，Gv0 的顶点可按照颜色划分 成 V1,V2, …, Vk-1 共 k1块，块 Vi 中的顶点被涂以颜色 ci。由于deg(v0)< k1，v0 至少与其中一块 Vj 不邻接即与 Vj 中的任何顶点不邻接。此时可将 v0 涂以颜色 cj，
12
第十二页，编辑于星期六：八点 一分。
6.1 色数
[五色定理] (1890, Heaword) 任何简单平面图都是 5-可着色的。 [证明]设简单平面图 G=(V, E)，对 n=|V| 作归纳。
n 5时容易讨论结论成立。
设 n = k1时，结论成立。 当 n = k 时，由[定理5-1-8]简单平面图 G 至少有一个顶点的度 小于6。故可设 v0V，deg(v0) 5。设 G=Gv0，由归纳假设
何顶点的度不小于 k-1。又 G 为 k 色图，其中至少有 k 个顶点。
9
第九页，编辑于ቤተ መጻሕፍቲ ባይዱ期六：八点 一分。
6.1 色数
[推论2] 对 G=(V, E)， =max{deg(vi)|viV}，有 (G) +1。
[证明] 设 (G)=k，由推论1，有 vV，使得 deg(v) k-1
又： deg(v) 故： k-1 或 (G)-1 即： (G) +1
图所示。
13
第十三页，编辑于星期六：八点 一分。

图论讲义6染色理论

第六章 染色理论许多实际问题可以归结为求图的匹配或者独立集。

此外，在许多应用中，人们希望知道：一个给定的图，它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。

§6.1 点染色定义6.1.1 设G 是一个无环边的图。

G 的顶点正常k 染色(proper vertex k-colouring)π是指k 种颜色k ，，，L 21对于G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。

换句话说，G 的顶点正常k 染色π是一个映射},,2,1{)(:k G V L →π,使得)(1i −π是独立集或空集),,2,1(k i L =.注：设π是G 的一个顶点正常k 染色。

令})(|)({)(V 1i x G V x i i =∈==−ππ，（k i ,,2,1L =）。

则π实际上是对顶点集)(G V 的一种划分：),,,(21k V V V L =π，其中φ=j i V V I ，)(1G V Vki i==U ，且每个i V 是独立集或空集),,2,1(k i L =.例：定义6.1.2 若存在G 的一种顶点正常k 染色，则称图G 是点k 色可染的(vertex k-colourable)， 有时简称为k 色可染的或可k 染色的。

注：⑴ 每个图G 一定是)(G ν色可染的。

⑵ 若图G 是k 色可染的，则对任何正整数k m ≥，G 也m 色可染。

定义6.1.3 设G 是无环边的图，令G k G |min{)(=χ是k 色可染的}，称)(G χ为G 的点色数，有时简称为色数(chromatic number)。

若k G =)(χ，则称G 为k 色图(k-chromatic graph)。

注：（1） 若k G =)(χ（即G 是k 色图），则G 中任何点k 染色),,,(21k V V V L =π中每个i V 都是非空的独立集。

哈工大集合论与图论第六章作业题答案

第六章图的基本概念P习题2061．画出具有4个顶点的所有无向图(同构的只算一个)。

11个2．画出具有3个顶点的所有有向图(同构的只算一个)。

16个3．画出具有4个、6个、8个顶点的三次图。

略4．某次宴会上，许多人互相握手。

证明：握过奇数次手的人数为偶数(注意，0是偶数)。

把实际问题转化为图论问题，然后用握手定理的推论。

P习题2091．设u与v是图G的两个不同顶点。

若u与v间有两条不同的通道(迹)，则G 中是否有圈？若u与v间有两条不同的通道，G中无圈若u与v间有两条不同的迹，G中有圈2．证明：一个连通的(p，q)图中q≥p-1。

数学归纳法3．设G是一个（p，q）图，且2/)2>p-q，则G是连通的。

p)(1(-6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。

试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。

证明：把实际问题转化为图论问题，就和下面的题一样了。

8．设G是图。

证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。

这两个题和这个题一样的证明方法。

P习题2161．证明：若图G不是连通图，则G c 是连通图。

2．证明：每一个自补图有4n或4n+1个顶点。

P习题2281.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。

下图中任意一对不邻接的顶点u和v，均有：degu+degv≥9。

2．试求Kp中不同的哈密顿圈的个数。

(p-1)!/24．完全偶图Km，n为哈密顿图的充分必要条件是什么？10．证明具有奇数顶点的偶图不是哈密顿图。

图论第6章-平面图

n–m+r=( n′+1)–(m′ +1)+r′= n′-m′ +r′ =2。
若G不是树，则G中含有回路。设边e在G的 某个回路上。令G′=G-e(从G中删除边e，而得 到G′)，则G′仍然是连通图。设n′，m′和r′分别是 的结点数、边数和面数。则n′=n，m′=m-1=k， r′=r–1 。 于 是 n=n′ ， m=m′+1 ， r=r′+1 。 因 为 G′ 是连通图且m′=k，所以G′满足归纳假设的条件。 由归纳假设知：n′–m′＋r′=2，所以 n–m+r= n′–(m′+1)+(r′+1)= n′-m′+r′=2。
v1
v4
R0 R2 R1 v2
v3 v5
v6
又例：下图为非连通的平面图，有两个连
通分支， deg(R1)=3， deg(R2)=4， R0的 边界由两个初级回路v1 v2 v3v1 和v4 v5 v6 v7 v4围成， deg(R0)=7 。
v1
v4
v7
v2
R1 v3R0 v5
R2
v6
定理：设G=V,E是有限平面图，有r个面，
如下图G1,G2,G3是同胚的。
G1
G2
G3
定理 (库拉斯基定理) 一个图G是非平面的，当 且仅当它包含一个同胚于K3.3或K5的子图。
例 说明彼得森图不是平面图。
解:删去下图(a)皮得森图的结点b,得其子图
(b)H。a 而H胚于Kf 3,3,所以皮c 得森不是平f面图。d
j
f ejg baFra bibliotekd g
6
36
4
54 12
7
8
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

面的连通平面图，则有
n – m + ф =2
（1.2）
证明 对ф 用归纳法。
当ф =1时 ，G 无圈又连通，从而是树，有
于是
n =m+1 n -m+ф =（m+1）- m + 1= 2
设 ф = k 时，（1.2）式成立。
9
当 ф = k+1 时，此时 G 至少两个面，从而有 圈 C。删去 C 中一条边，记所得之图为 G ’ 。并 设 G ’ 的点数、边数和面数依次为 n’ , m’ 和 ф ’, 易知 G ’ 仍连通，但只有 k 个面，由归纳假设有
(1.7）
证明 只需在定理4的证明中将所有不等号改为等号即可得 (1.7)式。
例3 在右图所示的图中， m=12，n = 8，l = 4
有 12×(4-2) = 4×(8-2)， 满足（1.7）式。
例4 证明 K5 和 K 3,3 是不可平面图。
16
证明 若 K5 是可平面图，则因 K5 是至少三个点的简单图， 由推论1，K5 应满足 m≤3n -6。而 K5 中 m=10， n = 5，代
例1
=
平面图
可平面图
3
不可平面图
=
可平面图
不可平面图
4
= 可平面图
= 可平面图
5
定义： 设G 是一个平面图，G 将所嵌入的平 面划分为若干个区域，每个区域的内部连同边界 称为 G 的面，无界的区域称为外部面或无限面。 每个平面图有且仅有一个外部面。设 f 是 G 的一 个面，构成 f 的边界的边数（割边计算两次）称 为 f 的次数，记为 deg(f )。
y1
y2
y3
但如果在 x3 与y1 之间也要修一条铁路，则 可验证满足要求的方案不存在。
问题的解答
2
§ 6.1平面图
定义1 若图 G 可画在一个平面上使除顶点外边不交叉， 则称 G 可嵌入平面，或称 G 为可平面图。可平面图 G 的 边不交叉的一种画法称为 G 的一个平面嵌入，G 的平面 嵌入表示的图称为平面图。
于是
m1+m2≤ 3(n 1 + n 2 ) - 6，
从而有
m ≤3n - 6。
设G 没有大于两个点的连通分支。此时m≤ n 。因 n ≥ 3 时， n ≤3n - 6，所以有 m≤3n - 6。
15
推论2 设G是具有n个点m条边的连通平面图,若G中所有面
均由长度为 l 的圈围成，则
m (l-2) = l (n-2)
n - nr + nr = 2 2l
2ln – lnr+2nr = 4l
n (2l – lr+2r)= 4l
n = 4l(2l – lr+2r)-1
(1.8)
(1.9)
22
n = 4l(2l – lr+2r)-1
(1.9)
因n 和l 均为正，由（1.9）式得
2l – lr+2r＞0
2(l +r)＞lr
设n≥3。若G 存在割边 uv，则 G-uv 不连通，恰有两 个连通分支G1与G2。设u在G1中，v在G2中。因n≥3，所 以G1与G2中必有一个至少含两个点，不妨设G2至少含 两个点。
26
设 f 是 G1中含点u的面，将G2画在 f 内。因G2是简单 图，故在G2的外部面上存在不等于v的点t。在G中连接不 相邻点u和t，记所得的图为G*，易知G* 也是平面图，这 与G是极大平面图矛盾。所以G不含割边。
矛盾，所以 K 3,3 是不可平面图。
17
定理5 若 G 是简单平面图，则δ≤5.
证明 对点数 n =1，2，直接验证可知结论成立。
设n ≥3，若 δ≥6，则
6 n d (v) = 2m
n V ( G )
m ＞ 3n - 6
这与定理4的推论1矛盾。 所以δ≤5。
Байду номын сангаас18
平面嵌入概念的推广
v1 v2
f v3
v4
28
推论 设G是一个有n个点m条边ф个面的极大平面图， n≥3，则
（1）m = 3n-6； （2）ф= 2n-4。 证明留作习题。
推论表明对一个极大平面图G，当其点 数n给定时，G的边数和面数也就确定了 ，从而G的结构框架也大体确定了。例如 ，当n=4时，G为K4；当n=6时，G为正八 面体；当 n=9时，G 有21 条边14个面， 其中一个的结构如上图所示；当n=12时 ，G有30条边20个面，此时，其中的两个 G一个为正二十面体（图6-10），另一个 如图右所示。
x
y
O
图6-9
P
20
4. 如果将一个有n个顶点，m条棱和φ个面的凸多面体的 顶点作为顶点，棱作为边，则这个多面体可视为一个图 G，很明显G可嵌入球面，从而可嵌入平面而得到一个 连通的平面图。因而由定理2，凸多面体的顶点数，棱 数与面数也满足 n-m +φ=2。这个公式也称为欧拉公式 。 定理6（Platonic） 存在且只存在5种正多面体：正四 面体、正方体、正八面体、正十二面体和正二十面体。
19
3. 一个图可嵌入平面当且仅当它可嵌入球面
简证 将球面S放在一个平面P上，设切点为O，过O点 作垂直于P的直线，此直线与S的交点设为z。作映射
f : S - z P
定义 f（x）= y 为点 z，x与y共线。这样的映射f（如图6-9
所示）便称为球极平面射影。
z
通过球极平面射 影可将嵌入球面S 的图映射为嵌入 平面的图，反之 亦然。
n’ - m’ + ф ’ = 2
（1.3）
同时 n’ = n ， m’ = m - 1，ф ’ = ф - 1
代入（1.3）式得 n -（m-1）+（ф -1）= 2
即
n – m + ф =2
10
定理3 设G是具有ф个面k个连通分支的平面图，则 n - m +ф= k + 1
证明 设G的k个连通分支分别为G1, G2, …,Gk ,对每个G i 用欧拉公式可得：
27
若 v1与v3不相邻，则在 f 内连接v1与v3不破坏G的平面性 ，这与G为极大平面图矛盾。所以v1与v3必相邻。因面 f 内无边，故边v1v3必在 f 外。同理，v2与v4必相邻并且边 v2v4也在 f 外。这样边 v1v3 与边 v2v4 必相交（如图所示） ，这就与G是平面图矛盾。所以G中各面次数只能为3。
例1 下两图均为极大平面图。
25
引理 设G是极大平面图，则G必连通； 若G的点数n≥3 ，则G无割边。
证明 若G不连通，则G至少存在两个连通分支G1与G2。 显然G1与G2也是平面图。将G2画在G1的外部面内，并分 别在G1与G2的外部面上各取一个点u和v。很明显， u与v 不相邻。连接u和v，记所得的图为G* 。易知G*也是平 面图，这与G是极大平面图矛盾，所以G连通。
3
m≤
(n - 2) =3n - 6
3-2
14
设G 不连通。若G 存在至少有三个点的连通分支， 因对G 的这些分支均满足（1.6）式，将各不等式相 加也得类似不等式，设为m1 ≤3n 1 - 6。
再设G 的所有少于3个点的连通分支的总边数为 m2，总点数为n 2。此时有 m2≤ n 2 ≤3n 2 ，
6
例2
f1 f5
f2 f3
f4
有5个面：f1，f2，f3，f4，f5 （ f5 为外部面）
deg(f1) =1 deg(f2) =2
deg(f3) = 3 deg(f4) = 6 deg(f5)= 10
相加为22，正好是 边数11的2倍
图不连通，其外部面的次数为5
7
定理1 设具有m 条边的平面图G 的所有面的集合为 Ψ, 则
29
从以上例子可以看出：点数相同的极大平面图不唯一 ，但究竟有多少个？其结构如何？这还是一个待解决 的问题之一；当极大平面图是正则图时它便是一个正 多面体。
定义2 如果在不可平面图G中任意删去一条边所得的图 为可平面图，则称G为极小不可平面图。
例 K5与K3，3均为极小不可平面图。
定义3 若一个可平面图存在一个所有顶点均在同一个面 的平面嵌入，则称该图为外可平面图。外可平面图的任 一外平面嵌入（即所有顶点均在同一个面的嵌入）称为 外平面图。
5
5 3 12 30 20
正八面体和正二十面体的平面表示为
相应的正多面体 正四面体 正方体 正十二面体 正八面体 正二十面体
正八面体
正二十面体
24
§6.2 一些特殊平面图及平面图的对偶图 一、一些特殊平面图
定义1 设G是简单可平面图，如果在G中任意两个不 相邻的顶点之间添加一条边所得到的图均为不可平面 图，则称G为极大可平面图。极大可平面图的平面嵌 入称为极大平面图。
证明 任取一个正φ面体A ，设A 有n个顶点，m条棱。 将A 嵌入平面记所得的平面图为G。易知G是一个每个 面的次数均相同（设为l）的r 度简单正则图。从而有
21
φl = 2m，nr = 2m，l≥3，r≥3
m = nr , Φ= 2m = nr
2
ll
将上两式代入Eular 公式n-m+φ=2 得
第六章 平面图
电子科技大学应用数学 张先迪
1
问题：假定有三个仓库 x1，x2，x3 和三个车站 y1，y2，y3。 为了便于货物运输，准备在仓库与车站间修筑铁路，如图(a) 所示, 其中边代表铁路。问是否存在一种使铁路不交叉的路 线设计方案，以避免修建立交桥。
x1
x2
x3
x1
x2
x3
y1
y2
y3
?
i=1
11
将它们代入（1.4）式得 n – m +ф+ k-1 = 2k