当前位置：文档之家 › 图论平面图

图论平面图

  • 格式：pdf
  • 大小：284.26 KB
  • 文档页数：27

下载文档原格式

  / 27

合集下载

图论 平面图与对偶图

图论 平面图与对偶图
第四章 平面图与对偶图
4.1 平面图 4.2 平面图上的欧拉公式
4.3 对偶图
4.1 平面图
平面上的图(plane graph)：指的是画在平面上的一个图形，它的 所有的边都不相交（除顶点外）。
平面图(planar graph)：如果一个图经过重画之后，可以画成平面 上的一个边不相交的图形，则该图便称为平面图（可嵌入平面 (embeding)）。 Jordan curve：自身不相交的):
1）如果两个图能够从一个图G出发，通过在G的边上插入有限多 个2次顶点得到，则称这两个图是同胚。 2）如果两个图是同构的或通过反复插入或消去2次顶点后是同构 的，则称这两个图是同胚。 Th4.2：一个图为平面图当且仅当它不含与k5或k3.3同胚的子图。
Th4.3：一个图为平面图当且仅当它不含可以缩成k5或k3.3的子图。
4） G* 是连通的且为平面嵌入的。
Lemma4.10：设G为n，m和f且为平面上的连通图，其对偶图G*有n*， m*和f* n*= f， m= m*和n =f*。 Th4.11：设G为平面上的连通图，则G**≌G。 Th4.12：设G为平面上的连通图且G* 为G的对偶图，则G的边集构 成G的一个圈对应的G*的边集构成G*的一个割集。 Corollary4.13：设G为平面上的连通图且G* 为G的对偶图，则G的边 集构成G的一个割集对应的G*的边集构成G*的一个圈。
Th:一个图是可嵌入平面它是可嵌入球面。 Th4.4：设Ｇ是一个连通的平面上的图，n，m和f分别表示图Ｇ的顶 点数，边数和面数，则n-m+f=2。 Cor４.5：设Ｇ为具有n个顶点，m条边，f个面和k个分图的平面上的 图，则n-m+f=k+1。
Cor４.６：Ｇ<V,E>为简单连通平面图|V|=n（n>2）和|E|=m

图论平面图

图论平面图

AD
f4
B D f2 DC
f1 F D
f3
DD
f1 : 边界:ABCDFDA f2 : 边界:ABCA f3 : 边界:ACDA f4 : 边界:ADA
deg(f1)=6 deg(f2)=3
deg(f3)=3 deg(f4)=2
欧拉公式
定理4.2 G是个连通的平面图, 设n、m、r分别表示G中
结点数、边数、面数, 则有 n-m+r=2. 称此式为欧拉公式.
的 extJ ，使得同一
类中的任意一对点能用 一条不与 J 相交的曲线 相连，而连接一对属于 不同类点的任意曲线必 须与 J 相交。
Jordan曲线定理: Jordan曲线把平面分为2部分， 连接内部与外部点的任意曲线必然与Jordan曲线 相交.
¾ 说明： 该定理看似无可置疑的明显结论。 该定理是 C.Jordan（1838－1933）首先提出， 并给出了（长而复杂又有缺陷）的证明，但后来 发现Jordan的证明有缺陷。 第一个严格的证明相当复杂，对于训练有素的数 学家来说，也是很难理解的。 对于多边形的Jordan曲线，证明是简单的。
u1
上的一条Jordan曲线，
C
设 v3 ∈ int C ,于是 (u1, v3), (u2, v3) 连同C将
v1
v2
u2 (2)
平面分成三个两两不
相交的的区域，而 u3 应落入这三个区域中的
某一个区域，不妨假设 u3 ∈ extC ，则由定理
知 (u3,v3)必须与C相交，故 K3,3 是非可平面图。
说明： 一个可平面图与其平面嵌入图拓扑同构， 因此我们将一个可平面图的平面嵌入也称为平面 图。
例如右图.就是
v1 D

图论课件--平面图的判定与涉及平面性的不变量

图论课件--平面图的判定与涉及平面性的不变量
证明 (3): 因为G的每个面是三角形，所以每条边是两 个面的公共边，得：3ф =2m。于是由定理4得：
m = 3 ( n 2 + 2)
对于完全图的亏格曾经是一个长期的，有趣的，困难 的和成功的努力。1890年希伍德提出如下猜想：
( n 3 ) ( n 4 ) ( K ) * ) ( n 1 2
n 7 n 4 ( m o d 6 ) 或 n 9 ,则： (Kn ) 6 m n (K ) mn , 2 n2 ) (m
(3) 对任意的单图G=(n, m),有：

m 3n 6
3、图的糙度
28
定义6 图G中边不相交的不可平面子图的最多数目称为 (G ) G的糙度，记为：
图 G1
图 G2
证明：对于G1来说，按G1在2度顶点内收缩后，可得 到K5。所以，由库拉托斯基定理知G1是非可平面图。
8
对于G2来说，先取如下子图
G2的一个子图
对上面子图，按2度顶点收缩得与之同胚子图K3,3:
K3,3
所以，G2是非可平面图。
9
例2 确定下图是否是可平面图。
u1
v1 v2
u2
y2 w2 x2
(K ) n ( n 3 ) ( n 4 ) 1 2
(K ) m ,n ( m 3 ) ( n 2 ) 4
27
2、图的厚度 定义5 若图G的k个可平面子图的并等于G，则称k的最 小值为G的厚度，记为 ( G ) 定理6 (1)若 (2)
H1 H2
又设H1与H2的顶点数分别为n1*和n2*,边数分别为m1*与 m2*。那么：
m * m P P n * n P P 1 1 1 2 1 1 1 2

图论及其应用

图论及其应用
χ（G）表示。若χ（G）=k，就称G是k-点可 色图。
顶点染色
定理：对于任何一个图χ（G）≤ω（G）。 ω（G）为图G的团数，用来描述χ（G）的下 界，其中ω（G）=max{k|Kk属于G}。
顶点染色
给定图G=（V，E）的一个k-点染色。用Vi表示G中染以 第i色的顶点集合（i=1,2，…，k），则每个Vi都是G 的独立集。因而G的每一个K-点染色对应V(G)的一个划 分[V1,V2,…,Vk]，其中每一个Vi是一个独立集。反之 ，给出V(G)的这样一个划分（V1,V2,…,Vk），其中每 一个Vi均是独立集（1≤i≤k），则相应得到G的一个k点染色，称V(G)的这样一个划分为G的一个色划分，每 一个Vi称为色类。因此，G的色数χ(G)就是使这种划 分成为可能最小自然数k。
推论：若G是p(G) 3且g(G) 3的平图，则 q(G) g(G) ( p(G) 2)。 g(G) 2
平面图的性质
推论：任何一个简单平面图G，有 q(G)≤3p(G)-6
推论：设G是简单平面图，则δ(G)≥6.
定理：仅存在5种正多面体，即正四面体、正 方体、正八面体、正十二面体和正二十面体。
定理：每一个平面的色数不超过5
边染色
定义：无环图G的一个正常染色k-边染色（简 称k-边染色）是指一个映射φ：E(G)→{1,2， …，k}，使对G中任意两条相邻的边e1和e2，有 φ(e1)≠φ(e2)。若G有一个正常k-边染色，则 称G是k-边染色的。G的边色数是指G为k-边染 色的最小整数k的值，记为
χ'(G)。若χ'(G)=k，则称G是k-边可色的。
边染色
设G有一个正常k-边染色，置Ei为G中所有染 以第i种颜色的边的全体，则E1，E2，…，Ek 是G的k个边不相交的对集，并且

图论课件第六章平面图

图论课件第六章平面图

A6
A2
A5
A3
A4
7
第7页，本讲稿共35页
例子3：3间房子和3种设施问题
问题：要求把3种公用设施(煤气，水和电)分别用煤气管 道、水管和电线连接到3间房子里，要求任何一根线或管道 不与另外的线或管道相交，能否办到？
上面问题可以模型为如下偶图：
G
W
E
H1
H2
H3
问题转化为，能否把上面偶图画在平面上，使得边与边 之间不会交叉？
1、平面图的次数公式
12
第12页，本讲稿共35页
定理1 设G=(n, m)是平面图，则：
deg(f )2m
f
证明：对G的任意一条边e, 如果e是某面割边，那么由面 的次数定义，该边给G的总次数贡献2次；如果e不是割边， 那么，它必然是两个面的公共边，因此，由面的次数定义 ，它也给总次数贡献2次。于是有：
19
第19页，本讲稿共35页
所以， l (n2)4(62)8
l2
2
而m=9，这样有：
m l (n 2) l 2
所以，由推论2，K3,3是非平面图。
推论3 设G是具有n个点m条边ф个面的简单平面图， 则：
m3n6
20
第20页，本讲稿共35页
证明：情形1，G连通。 因为G是简单图，所以每个面的次数至少为3，即l=3 。于是，由推论2得：
如果把每个景点分别模型为一个点，景点间连线，当且 仅当两景点间要铺设空调管道。那么，上面问题直接对应 的图为：
A1
A6
A2
A5 A3
A4
于是，问题转化为：能否把上图画在平面上，使得边不 会相互交叉？
6
第6页，本讲稿共35页
通过尝试，可以把上图画为：

[理学]图论第四章 平面图及着色

[理学]图论第四章 平面图及着色

v=2,e=1,r=1
v=1,e=1,r=2
(2)下用数学归纳法证明.
假设公式对n条边的图成立.设G有n+1条边. 若G不含圈,任取一点x,从结点x开始沿路行走.因G 不含圈,所以每次沿一边总能达到一个新结点,最后会 达到一个度数为1的结点,不妨设为a,在结点a不能再继 续前进.删除结点a及其关联的边得图G’,G’含有n条边. 由假设公式对G’成立,而G比G’多一个结点和一条边,且 G与G’面数相同,故公式也适合于G. 若G含有圈C,设y是圈C上的一边,则边y一定是两个 不同面的边界的一部分.删除边y得图G’,则G’有n条边. 由假设公式对G’成立而G比G’多一边和多一面,G与G’ 得顶点数相同.故公式也成立.
解:图K5有5个顶点10条边,而3*5-6=9,即10>9,由
推论1知,K5是非平面图. 显然K3,3没有长度为3的圈,且有6个顶点9条边, 因而9>2*6-4,由推论2知K3,3是非平面图. 推论3 设G是带v个顶点，e条边，r个面的平面 图，则 v- e+ r=1+w。其中w为G的连通分支数。 证明:由欧拉公式有: vi- ei+ ri=2(i=1,2,…,w) 从而有 vi- ei+ ri =2w 又 vi=v, ei=e, ri =r+(w-1)(外部面被重 复计算了w-1次.).所以有: V-e+r+(w-1)=2w 整理即得: v- e+ r=1+w.
定理2 对任何平面图G，面的度数之和是边数的二倍。 证明:对内部面而言,因为其任何一条非割边同时在两个 面中,故每增加一条边图的度数必增加2.对外部面的边 界,若某条边不同时在两个面中, 边必为割边,由于边界 是闭链,则该边也为图的度数贡献2.从而结论成立. 定理3 设G是带v个顶点，e条边，r个面的连通的平面 图，则 v-e+r=2。（欧拉公式） 证明:(1)当n=e=1时,如下图,结论显然成立.

图论平面图

图论平面图


本定理的用途:判定某图是非平面图。
说明：这是简单 图是平面图的必 要条件。
例如：K5中e=10，v=5，3v-6=9，从而e>3v-6， 所以K5不是平面图。
定理4.6.3的条件不是充分的。如K3,3图满 足定理4-6.3的条件（v=6，e=9，3v-6=12， e≤3v-6成立），但K3,3不是平面图。
4-6 平面图
重点：掌握欧拉定理及其证明。
一、平面图 1、定义4-6.1 如果无向图G=<V,E>的所有结点和 边可以在一个平面上图示出来，而使各边仅在顶点 处相交。无向图G称为平面图，否则称G为非平面 图。
有些图形从表面看有几条边是相交的，但是不 能就此肯定它不是平面图，例如，下面左图表面看 有几条边相交，但如把它画成右图，则可看出它是 一个平面图。
5.定理4-6.3 设G为一简单连通平面图，其顶点数 v≥3，其边数为e，那么 e≤3v – 6
证明思路：设G的面数为r,当v=3,e=2时上式成立,
若e=3,则每Hale Waihona Puke 面的次数不小于3,各面次数之和不小于
2e,因此
2e≥3r, r≤2e/3
代入欧拉公式: 2=v-e+r≤v-e+ 2e/3
整理后得: e≤3v – 6
定义4-6.3 设图G=<V,E>是一连通平面图,由图中 各边所界定的区域称为平面图的面(regions)。有界的 区域称为有界面，无界的区域称为无界面。界定各面 的闭的路径称为面的边界（boundary），面r的边界长 度称为面r的度（degree）记为deg (r) ，又称为面r的 次数 。
例如图
故 v-e+r=2成立。 （2）若G为一个边，即v=2，e=1，r=1，

第7章 图论 -5二部图、平面图

第7章 图论 -5二部图、平面图

第9章 图论
2）在G中求最大匹配 把边 (a2,b2) 从 M 中去掉，而把 (a1,b2) 和 (a2,b4) 添加到 M 中， 得到新的匹配M′=(a1,b2),(a2,b4),(a3,b3), (a5,b5)，如下图所示。 对于匹配M′= (a1,b2),(a2,b4),(a3,b3), (a5,b5)重复上述过程， 已找不到M′可扩路。所以M′就是最大匹配。
第9章 图论
在子图H中，任一结点至多与M中的一条边关联且与M1中 一条边关联。因而任一结点的度数是1或2。故H的连通分支是 一条路，或者是一个回路。 如果 H的连通分支是一条路 P，则它是 M 交替路，也是 M1 交替路。如果P的两个端点均与M中的边关联，则P是M1可扩路。 由假设知， M1 是最大匹配，所以，不存在 M1 可扩路，得到矛 盾。如果P的两个端点均与M1的边关联，那么P是一条M可扩路 与题设矛盾。故 P 只能是一个端点与 M 中的边关联，另一个端 点与M1中的边关联，这样P中属于M的边数与属于M1的边数相 等。 如果 H的连通分支是一个回路，回路中的边交替地属于 M 和M1，因而属于M的边数与属于M1的边数相等。 从上面可以看到，H中属于M的边与属于M1的边的数目相 等。再加上既属于M又属于M1的边，可以得出：M中的边数与 M1中的边数相等。所以，M是最大匹配。
第9章 图论
由上述讨论可见：利用可扩路可以增加匹配所含的边数。 不断地寻求G的可扩路，直到再也找不到新的可扩路，就可得 到一个最大匹配。将这个结论写成下列的定理。 定理 7.5.2 设 G=V1,V2,E是二部图， M为G的最大匹配的充分 必要条件是G中不存在M可扩路。 证明：设M为G的最大匹配，下证G中不存在M可扩路。 如果G中存在一条M可扩路，则可以得到比M的边数多1的 匹配，所以M 不是最大匹配，矛盾。所以G 中不存在M 可扩路。 设G中不存在M可扩路，下证M为G的最大匹配。 设M1是最大匹配，证明|M|=|M1|。 考察属于M而不属于M1和属于M1而不属于M中的边，由这 些边连同它们的端点一起构成G的子图H。

图论4-6 平面图

图论4-6 平面图

一个平面图。
有些图形不论怎样改画，除去结点外， 总有边相交。故是非平面图。
2、面、边界 定义4-6.2：设G是一连通平面图，由图中的边所 包围的区域，在区域内既不包含图的结点，也不包含 图的边，这样的区域称为G的一个面，包围该面的诸 边所构成的回路称为这个面的边界。面r的边界的长度 称为该面的次数，记为deg(r)。
证明 假设K3,3图是平面图。
在K3,3中任取三个结点，其中必有两个结点不
邻接，故每个面的次数都不小于4，
由4r≤2e，r≤e/2，即 v-e+e/2≥v-e+r=2， v-e/2≥2， 2v- e ≥ 4， 2v-4≥e。 在K3,3中有6个结点9条边， 2v-4=2×6-4=8<9,与 2v-4≥e 矛盾， 故 K3,3不是平面图。
则 v-e+r=2成立。
（3）设G为k条边时，欧拉公式成立，即 vk-ek+rk=2。
考察的情况。 因为在k条边的连通图上增加一条边，使它仍为连通图， 只有下述两种情况： ①加上一个新结点b，b与图上的一点a相 连，此时vk和ek两者都增加1，而面数rk没
变，故
（ vk +1）-（ ek +1）+ rk = vk-ek+rk=2。
在该面的度数中重复记了两次，故定理结论成立。
4、欧拉定理 定理4-6.2（欧拉定理）
式成立 v–e+r=2 证明
设G为一平面连通图，
v为其顶点数，e为其边数，r 为其面数，那么欧拉公
（1）若G为一个孤立结点，则v=1，e=0，r=1，
故 v-e+r=2成立。
（2）若G为一个边，即v=2，e=1，r=1，
4-6
平面图

图论6平图及着色

图论6平图及着色

• 定义３ 设G是一个平图，则G把平面划分 成若干个连通区域，每个连通区域的闭包 称为G的一个面，其中恰有一个无界的面， 称为外部面。
• 定理1 若G是连通平图，则 υ－ε＋f＝２， 其中，f是G的面数. (这个公式称为Euler公 式) • 证明 对G的边数ε用归纳法， ……
• 推论1 给定平面连通图G，则G的所有平 面嵌入有相同的面数。
平面图
• 定义1 如果一个图能画在平面上，使得它 的边仅在端点相交，则称这个图为平面图， 或说它是可平面嵌入的，平面图G的这样一 种画法，称为G的一个平面嵌入。
• 平面图G的平面嵌入称为平图。
• K3,，K4，K5
(a )
(b )
• 定义２ 一条连续的、自身不相交的封闭 曲线称为Jordon曲线。 • J的外部，extJ，外点，extJ与J之并称为extJ 的闭包，记为ExtJ；另一部分(不含曲线J)称 为J的内部，记为intJ，intJ的点称为J的内点， intJ与J之并称为intJ的闭包，记为IntJ。 • 引理 设J是一条Jordon曲线，任何连接J 的内点与外点的曲线必与J相交。
顶点着色
• 定义 设G是一个图，对G的每个顶点着色， 使得没有两个相邻的顶点着上相同的颜色， 这种着色称为图的正常着色 • 若图G的顶点可用k种颜色正常着色，称G为 k可着色的 • 使G是k可着色的数k的最小值称为G的色数， 记为χ(G)，如果χ(G)＝k，则称G是k色的。
(a )
(b )
• 假设G是简单连通图。 • 定理1 (1)对于完全图Kn，有χ(Kn)＝n，χ(～Kn)＝1。 (2)对于n个顶点构成的圈Cn，当n是偶数时， χ(Cn)＝2，当n是奇数时，χ(Cn)＝3。 (3)对于非平凡树T，有χ(T)＝２。 (4)G是二分图，当且仅当χ(G)＝２。

图论第6章-平面图

图论第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

图论第四章 平面图及着色

图论第四章 平面图及着色
是v-1阶极大平面图,由归纳假设,G’有平面表示 G~'
使 G~' 的每条边都是直线. (b)考和虑图(Gc~)')中.这边样P得z1到和的Pz图2,将G~它就分是裂G成的两平个面三表角示形,而(图 且每条边都是直线段.定理得证.
z3
z3
z3
z1
z2
x
x
y
(a)
y z1
(b)
p
z2
z1
z2
(c)
凸多面体
推论3 设G是带v个顶点，e条边，r个面的平面图， 则 v- e+ r=1+w。其中w为G的连通分支数。
证明:由欧拉公式有: vi- ei+ ri=2(i=1,2,…,w) 从而有 vi- ei+ ri =2w 又 vi=v, ei=e, ri =r+(w-1)(外部面被重复计算了
w-1次.).所以有:
例2 对哪些n,存在n条棱的凸多面体？
解:以多面体的顶点为图的顶点,以多面体的棱为图的边, 得到一个平面图G,若p(G),q(G),f(G)分别表示G的顶点数, 边数和面数,则p(G)4, f(G) 4,且每个面的度数是3,由 Euler公式易得q(G) 6,即没有棱小于6的凸多面体.四面 体是棱数为6的凸多面体.若有7条棱的凸多面体,则存在 满足上述条件, q(G) =7的平面图,由Euler公式p(G) +f(G)= q(G)+2=9,但G的每个面的度数至少是3,故 2q(G)=G(m) 3f(G)(m为G的面),
第四章 平面图
第一节 平面图
定义1 如果图G能画在曲面S上且使得它的边仅在端 点处相交，则称G可嵌入曲面S。如果G可嵌入平面 上，则称G是可平面图，已经嵌入平面上的图 G% 称为G的平面表示。

离散数学-图论-平面图

离散数学-图论-平面图
Scientific American数学 游戏栏目编辑
1975年4月1日,他发表 了声称只能用五色完成 的地图.
试试用四色?
18
作业
作业
P293: 2，5，6 P296: 2，5 b)，7, 5 a) c)
19
内部面.
例:面,边界,度,周线,相邻
边界为何不一定是圈?
因为割边的存在
面的度与边数
定理:平面图中面的度与图的边数m满足 fF(G) d(f ) = 2m
计算面的度时, 割边要算2次.
推论:平面图中奇度面数必为偶数.
欧拉公式
定理(欧拉1852):设G是连通平面图,它的顶点 数n, 边数m, 面数r 之间有 n–m+r=2
等号成立G是极大平面图 推论:简单平面图G中存在度小于6的顶点.
12
对偶图
定义:给定图G,如下构造的图G*,称为G的对偶 图(dual graph). 1.G中每个面Ri内放一个G*顶点v*i ; 2.对应面Ri和Rj的公共边e,作一条仅与e相交一 次的边e* (v*i,v*j) E(G*); 3.若割边e在面Ri的边界上,则作v*i上仅与e相交 一次的环e*.
例: K5是不可平面图.
K5是结点数最少的不可平面图.
例: K3,3是不可平面图.
K3,3是n6时边数最少的不可平面图.
8
Kuratowski定理
加细:在图的边上任意增加一些度为2的顶点.
原图与加细图称为同胚.
定理(Kuratowski):G是可平面图 G没有同胚 于K5和K3,3的子图.
平面图
1
平面图
定义:图G若能画在平面上,使任何两条边在顶 点之外都不相交, 就称G可嵌入平面,或称G是 可平面图.否则称不可平面图.

图论讲义第7章-平面图

图论讲义第7章-平面图

第七章 平面图§7.1 平面图的概念定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。

若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。

例如，下面是三个平面图及其平面嵌入。

根据定义，下列定理是显然的。

定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。

定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。

定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。

注：由以上定理知(1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。

(2) 环边和重边不影响图的平面性。

故以下讨论平面性时总假定图G 是简单图。

定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。

其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。

包围一个面的所有边称为该面的边界。

一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。

定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即其中R 1, R 2, … , R r 是G 的所有面。

证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。

可见每条边在计算总次数时，都提供2。

因而结论成立。

1deg()2().r ii R G ε==∑定义7.1.3设G为简单平面图，若在G的任意不相邻的顶点u, v之间加边uv 后，所得之图成为非平面图，则称G是极大平面图。

易见K1, K2, K3, K4, K5– e 都是极大平面图。

定义7.1.4 若非平面图G任意删除一条边后，所得之图都是平面图，则称G为极小非平面图。

图论平面图

图论平面图

3
5.1 平面图及其性质
[极大平面图] 设G=(V,E)为简单平面图，|V|3，若对 任意vi ,vjV，且 (vi ,vj) E，有G=(V, E{(vi ,vj)}) 为非平面图，则称G为一个极大平面图。
“极大性”乃针对固定顶点数的图的边的数目而
言。
4
5.1 平面图及其性质
[极大平面图的性质]
个域，则有m=3n-6，d=2n-4。
[证明] 将3d=2m代入欧拉公式。
[推论] 简单平面图G有 m 3n-6，d 2n-4。
[定理5-1-4] 简单平面图至少有一个顶点的度小于6。
[证明] 设任一点的度 6，得 m 3n，矛盾。
6
5.1 平面图及其性质
[二部图] 图G=(V, E)，若V可划分成V1和V2 两部分，
e3
e3
u3
11
5.2 Kuratowski 定理
[同胚] 设无向图 G和G，若存在G，使得G和G分别
经若干串联边置换后与G同构，则称G和G同胚.
与K5同胚的图，称为K(1)型图；与K3,3同胚的图，
称为K(2)型图； K(1)型图和K(2)型图统称K型图。 [定理5-2-1(Kuratowski)] 图 G=(V,E) 可平面当且仅当 G中不存在任何K型子图。( 证略) Kuratowski 定理的实际应用较为困难。
且deg(u2)=2，则称e1与e2串联。
[例 ] e1 u1
u2
e2 u3
10
5.2 Kuratowski 定理
[串联边置换] 将上述e1, e2 置换成 e3=(u1 , u3) ，并消去
可能的多重边的过程，称为串联边置换。
e1 u2 e2 e3

图论平面图

图论平面图

定理: K5是非可平面图 证明： 反证法 若G是与K5对应的平面图, v1 , v2 , v3 , v4 , v5 是G 的顶 点， 因为G是完全图，任意两点邻接， 所以 回路 C = v1v2 v3v1 是一个Jordan曲线，则 v4 ∈ int C 或 v4 ∈ extC 。
设 v4 ∈ int C ，（v4 ∈ extC 同理），那么边 (v4 , v1),(v4 , v2 ),(v4 , v3 ) int C1 , int C2 , int C3 这里 将 int C 分成3割区域： C1 = v1v4 v2 v1 , C2 = v2 v4 v3v2 , C3 = v3v4 v1v3 v5 一定在4个区域中的一个区域内，如果 v5 ∈ extC 那么因为 v4 ∈ int C 根据 Jordan定理，边(v4 , v5 ) 一定 与 C 相交， 这就与G是平面图的假设矛盾，对于 v5 ∈ int Ci 可以按照同样的方法处理。
v3*
证明：
若
D
v5
v2
D
D
F1 F2 Dv * 2
D v1 Dv1* D v3
F3
D v4ห้องสมุดไป่ตู้
9.2.10 举例说明下列命题： “平面图G有度 数为1 的顶点，则其对偶图G*含有环；若G有 度数为2的顶点，则G*含有重边。”的逆命题不 真。
9.2.10 举例说明下列命题： “平面图G有度 数为1 的顶点，则其对偶图G*含有环；若G有 度数为2的顶点，则G*含有重边。”的逆命题不 真。 提示：它的对偶图既含环又含重边。
定义:如果G1和G2是同构的,或者通过反复插入或删去度 数为2的结点, 使得它们变成同构的图, 称G1和G2 是在2 D 次结点内同构. D D D D D 例如右边3个图就是 D D D D D D 在2度结点内同构. 定理4.7 (Kuratowski定理)一个图是平面图的充分且必 要条件是它不含有任何与K5、K3,3在2次结点内同构的子 图. (此定理证明略.) 判断下面彼得森(Petersen)图: D v1 D v1 Dv6 v Dv6 v Dv1 Dv8 Dv9 v7 v 10 7 10 Dv3 v2 D D Dv4 D Dv5 v2 D D D Dv5 Dv10 Dv8 Dv9 Dv8 Dv9 Dv2Dv7 Dv6 Dv5 Dv3 Dv4 Dv3 Dv4

图论第6章 平面图

图论第6章 平面图
(4) 平面图在加环或平行边后还是平面图。
例： 立方体是平面图。
凸多面体
平面图的理论与多面体的研究密切相关:事实上,由于 每个凸多面体P可以与一个连通可平面图G对应,G的顶点 和边是P的顶点和棱,那么G的每个顶点的度至少为3.由于 G是一个平面图,则P的面就是G的面,并且G的每一条边落 在两个不同面的边界上. 一个多面体P的顶点,棱和面的数目分别用V,E和F来表 示,而且,这些分别是连通图G的顶点,边和面的数目.故欧 拉公式可写成V-E+F=2,这就是著名的Euler凸多面体公式. 为方便起见,用Vn和Fn分别表示凸多面体P的n度 点和n度面的数目,则n3且 2E nVn nFn
n3 n3
多面体的一些性质定理
定理 每个凸多面体都至少有一个n度面,其中 3n5.
证明:设F3=F4=F5=0,则: 即有F1/3E,又
n 6
2E nFn 6Fn 6 Fn 6F
n 6 n 6
2E nVn 3Fn 3V
n 3 n 3
定理：设H是G容许的，则对H的每一个片B，有
) FG ( B, H
~
~
这里
) { f f F (H ) , F (H )为H 的面集, 且B在f 内可画出} FG ( B, H
~ 是G容许的,则存在G的一个平面表示 证明:若 H ~ ~ ~ ~ 的子图 G, s.t. H G .显然,H的片B所对应的
i 1
定理： 设G是简单平面图，则G的最小度(G)≤5。 证明：设 G有n个结点，m条边。当n≤6，因为G是 简单图，因此， (G)≤(G)≤5。以下证n≥7的情况， 若 (G)≥6 ，即每个结点的度数大于等于 6n， G 中所有结 点度数之和大于等于6n。于是 2m= deg(vi ) i 1 ≥6n，m≥3n＞3n–6，即m＞3n–6，矛盾。

图论课件平面图的判定与涉及平面性的不变量

图论课件平面图的判定与涉及平面性的不变量

02
平面图的群论性质可以用来研究图的结构和性质，以及图的分
类和识别等问题。
群论在图论中有着广泛的应用，例如在化学分子结构、计算机
03
科学、交通运输等领域中都有重要的应用价值。
05 平面图的算法与复杂性
平面图的算法
欧拉路径与欧拉回路
通过遍历图中的边和顶点，寻找一条路径或回路，满足起点和终点是同一点，且路径或回 路上的所有边和顶点都不重复。
的路径，其中k为正整数。
平面图的边数与顶点数的关系
平面图中顶点数v和 边数e满足：ve+n=1，其中n为平 面的数量。
当平面图为连通图时， 顶点数v和边数e满足： v-e+1>0。
当平面图为简单图时， 顶点数v和边数e满足： v-e+1=0。
平面图的群论性质
01
平面图的群论性质是指平面图在群论中的表现形式，包括对称 性和置换群等。
应用
通过寻找是否存在哈密顿回路来判断一个图是否为平面图。如果存 在哈密顿回路，则该图是平面图。
限制
哈密顿回路判定法不适用于有向图和加权图。
03 平面性的不变量
欧拉路径与欧拉回路
欧拉路径
一个遍历图所有边且每条边只遍 历一次的路径。
欧拉回路
一个遍历图所有边且每条边只遍 历一次，且起点和终点是同一点 的路径。
图的着色问题
给定一个图，使用最少的颜色对图中的顶点进行着色，使得相邻的顶点颜色不同。这是一 个NP完全问题，可以使用贪心算法、回溯算法等求解。
最短路径问题
在图中寻找两个顶点之间的最短路径，可以使用Dijkstra算法、Bellman-Ford算法等求解 。
平面图问题的复杂性
平面图的判定问题

第14节 平面图

第14节 平面图
14/29
集合论 与图论
与欧拉公式有关的结论

推论5 K5与K3,3都不是可平面图. 证 如果K5是平面图，则5-10+f=2， 即f=7.
. 每个面至少三条边， 7个面至少需要21条边
考虑到每条边在两个面上， 2q≥3f，即 20≥21. 矛盾. 其实直接利用推论4，任意(p,q)平面图都满足 q≤3p-6，这里p≥3. q=10≤3p-6=9，这是不成立的. 所以K5不是可平面图.
集合论与图论429定义2平面图把平面分成了若干个区域这些区域都是单连通的称之为g的面其中无界的那个连通区域称为g的外部面其余的单连通区域称为g的内部面
集合论 与图论
第14节
主要内容：
平面图
平面图的基本概念 欧拉公式 平面图的判断(库拉托斯基定理) 平面图的对偶图
1/29
集合论 与图论
几点说明及一些简单结论
一般所谈平面图不一定是指平面嵌入. 但讨论 某些性质时，是指平面嵌入.
结论： (1) K5, K3,3都不是平面图(待证). (2) 设GG，若G为平面图，则G也是平面图. 由此可知，Kn(n≤4)，K2,n(n1) 都是平面图. (3) 设GG，若G为非平面图，则G也是非平面图. 由此可知，Kn(n5)，Km,n(m,n3) 都是非平面图. (4) 平行边与环不影响平面性.
10/29
集合论 与图论
欧拉公式
f≥2，G至少有一个内部面，从而G中有一个圈. 这个内部面是由这个圈围成的，从这个圈上去掉一 条边x，则打通了两个面.
G-x有p个顶点，q-1条边，f-1个面. 由归纳假设知： p-(q-1)+(f-1)=2 即：p-q+f=2 因此面数是f时也成立.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Jordan曲线定理: Jordan曲线把平面分为2部分， 连接内部与外部点的任意曲线必然与Jordan曲线 相交. ¾ 说明： 该定理看似无可置疑的明显结论。 该定理是 C.Jordan（1838－1933）首先提出， 并给出了（长而复杂又有缺陷）的证明，但后来 发现Jordan的证明有缺陷。 第一个严格的证明相当复杂，对于训练有素的数 学家来说，也是很难理解的。 对于多边形的Jordan曲线，证明是简单的。
v3*
证明：
若
D
v5
v2
D
D
F1 F2 Dv * 2
D v1 Dv1* D v3
F3
D v4
9.2.10 举例说明下列命题： “平面图G有度 数为1 的顶点，则其对偶图G*含有环；若G有 度数为2的顶点，则G*含有重边。”的逆命题不 真。
9.2.10 举例说明下列命题： “平面图G有度 数为1 的顶点，则其对偶图G*含有环；若G有 度数为2的顶点，则G*含有重边。”的逆命题不 真。 提示：它的对偶图既含环又含重边。
9.1.1 证明 K3,3 是非可平面图。 证明：令C表示图(1)中基本回路 v 1 u 1 v 2 u 2 v 1 , 在平面上的表示，如图（2），显然C是平面 上的一条Jordan曲线， 设 v3 ∈ int C ,于是 (u1 , v3 ), (u2 , v3 ) 连同C将 平面分成三个两两不 相交的的区域，而 u3 应落入这三个区域中的 某一个区域，不妨假设 u3 ∈ extC ，则由定理 知 (u3 , v3 )必须与C相交，故 K3,3 是非可平面图。
定理: K5是非可平面图 证明： 反证法 若G是与K5对应的平面图, v1 , v2 , v3 , v4 , v5 是G 的顶 点， 因为G是完全图，任意两点邻接， 所以 回路 C = v1v2 v3v1 是一个Jordan曲线，则 v4 ∈ int C 或 v4 ∈ extC 。
设 v4 ∈ int C ，（v4 ∈ extC 同理），那么边 (v4 , v1),(v4 , v2 ),(v4 , v3 ) int C1 , int C2 , int C3 这里 将 int C 分成3割区域： C1 = v1v4 v2 v1 , C2 = v2 v4 v3v2 , C3 = v3v4 v1v3 v5 一定在4个区域中的一个区域内，如果 v5 ∈ extC 那么因为 v4 ∈ int C 根据 Jordan定理，边(v4 , v5 ) 一定 与 C 相交， 这就与G是平面图的假设矛盾，对于 v5 ∈ int Ci 可以按照同样的方法处理。
deg(f1)=6 deg(f2)=3 deg(f3)=3 deg(f4)=2
欧拉公式 定理4.2 G是个连通的平面图, 设n、m、r分别表示G中 结点数、边数、面数, 则有 n-m+r=2. 称此式为欧拉公式. 证明: (对面数r归纳证明) ⑴ 设r＝1(一个面)，则图不含回路，图又是连通的，故必然是 一棵树，根据树的性质．有n-1=m ，因而 n-m+r=n-(n-1)+1=2于是结论成立. D D D D ⑵ 假设当G有r≤k-1个面时,结论成立. D D D D (3)当G有r=k 个面且是连通图时,当k≥2时, 至少有一个回路, 所以去掉此回路中的一条边后得到子图G’, G’ 中有k-1个面, 结点数同G中结点数, 由⑵得n-(m-1)+(k-1)=2 整理得 n-m+k=2 即 n-m+r=2 定理得证.
f1 , f 2 , f3 , f 4 , f5 , f 6 ,
面的边界:围成一个面r的所有边构成的回路,称之为 这个f面的边界. 此回路中的边数,称之为f面的次数, 记作deg(f).
BD f1 F D
AD f2
f4 DC f3
DD
f1 f2 f3 f4
: : : :
边界:ABCDFDA 边界:ABCA 边界:ACDA 边界:ADA
图 子图 K3,3
对偶图
对偶图的定义: 给定平面图G=<V,E>, 具有面F1,F2,F3,…,Fn. 如果 有图G*=<V*,E*>, 满足下面条件: ⑴对于G的任意面Fi 的内部有且仅有一个结点vi*∈V*. ⑵对于图G的面Fi与 Fj的公共边界ek ,有且仅有一条边 ek*∈E* ,使得 ek*=(vi*,vj*), 且ek*与ek相交.(vi*在Fi 内, vj*在Fj内) v3* ⑶当且仅当ek只是一个面Fi的 D 边界时,vi*上有且仅有一个环 F3 D v1 v5 D Dv * ek*∈E* 且与ek相交.则称图 F1 1 v2 D D v4 F2 Dv * G*是G的对偶图.可见G*中的 2 结点数等于G中的面数. D v3
推论 ：若G是简单连通平面图，则G至少有一个结点它的 次数小于等于5（ ） 证：用反证法，设G的所有结点的次数都大于等于6，则 结点次数和 deg(v) = 2m ≥ 6n
∑
v∈V
m ≥ 3n ，与定理（欧拉公式）矛盾，G不可 即 能所有结点的次数都在6以上，即至少有一结点的次数 小于等于5。
下面要介绍一个判定一个平面图的 充分且必要条件, 即Kuratowski(库拉托斯基)定理. 在 此之前先介绍一个新概念----在2度结点内同构(同胚). 在一个图中有2次结点, 则这些结点不影响平面的面数. v1 D 例如下面两个图: v1 D D v6 我们称这两个图是在 D v3 v2 D D v8 D v3 v2 D 2次结点内同构的图. D v7 D v5 v4 D D v9 D v5 v4 D
平面图
平面图 Jordan曲线定理 欧拉公式 对偶图
平面图 Plane Graph
在实际应用中,如高速公路设计、印刷电路设计, 都要求线路不交叉, 一个图能否画在一个平面上, 且任何边都不交叉, 这就是图的平面化问题. 近 些年来, 特别是大规模集成电路的发展进一步促 进了平面图的研究. 定义 一个图G，若可以将它画在平面上,使它的边 仅在顶点上才能相交，则称图G为可平面图 (planar graph)。图的这种平面画法称为平面嵌 入(plane embedding) 说明： 一个可平面图与其平面嵌入图拓扑同构， 因此我们将一个可平面图的平面嵌入也称为平面 图。
v1 D D v3 D v5 Df De Dd
4D
D6
Jordan曲线
Jordan曲线 平面上的简单闭曲线(自身不相交封闭曲 线) ¾ 若将平面看成一片任意变形的橡胶，图形保持什么 性质？ 平面上的一条简单闭曲线恰好将平面上的点分围两 类：分为两个区域：曲线内部的 int J ，曲线外部 的 extJ ，使得同一 类中的任意一对点能用 一条不与 J 相交的曲线 相连，而连接一对属于 不同类点的任意曲线必 须与 J 相交。
例如右图.就是 可平面化图. 下面是两个重要 的非平面图: K5和K3,3 v2 D v4 D 1D 2D D3 D5
ቤተ መጻሕፍቲ ባይዱ
v1 D v2 D v4 D v1 D D v3 D v5 aD bD cD Df De Dd bD cD v2 D v4 D aD D v3 D v5 v2 D v4 D
v1 D D v3 D v5
对偶图的特征: • 任何平面图的对偶图G*必然是连通图。（平面图只有 一个无限面，所以有限面中的结点与各有限面中的结 点必然是连通的。） • G和G *都是平面图。 当G是连通平面图时，G和G*互为对偶图。 若n,m,r分别表示G中的结点数、边数和面数，而 n*,m*,r* 别表示G*中对应的各数，则 m=m*,n=r*,r=n* • G中回路的边在G*中的对应边构成G*的割集，而G的割 集在G*中的对应边构成 G* 的回路，反之亦然，且对 应的割集和回路所含的边数相同。 • 一个给定的可平面图可以有不同的平面表示法，这些 平面表示图都是拓朴等价的，即彼此都是同构的，然 而按照构造它们的对偶图，各对偶图却不是同构的。
定义:如果G1和G2是同构的,或者通过反复插入或删去度 数为2的结点, 使得它们变成同构的图, 称G1和G2 是在2 D 次结点内同构. D D D D D 例如右边3个图就是 D D D D D D 在2度结点内同构. 定理4.7 (Kuratowski定理)一个图是平面图的充分且必 要条件是它不含有任何与K5、K3,3在2次结点内同构的子 图. (此定理证明略.) 判断下面彼得森(Petersen)图: D v1 D v1 Dv6 v Dv6 v Dv1 Dv8 Dv9 v7 v 10 7 10 Dv3 v2 D D Dv4 D Dv5 v2 D D D Dv5 Dv10 Dv8 Dv9 Dv8 Dv9 Dv2Dv7 Dv6 Dv5 Dv3 Dv4 Dv3 Dv4
定理: 图G 是可平面嵌入⇔图G是可球面嵌入 证明: 设 G 在球上的嵌入图为 G1 ,选择 G1 外的球 面上的点作为球极投影的投影中心 z ，则 G1 在球极投影的下的图像是 G 的平面嵌入图， 反之也成立.
欧拉公式
一个平面图 G 将平面分割成若干个连通区域，称这 些区域的闭包为图G的面. 有限面与无限面: 面的面积有限称为有限面, 反之 称为无限面. 所有平面图的外侧都有一个无限面.
球极投影 Stereographic Projection
曲面嵌入 (imbeddable on surface): 画在曲面上使得边与边不 在非顶点处相交, 如环面嵌入
球极投影 将一球S置于平面P上,球与平面的接触点称为球 的南极,通过南极的直径的另一端称为北极记为z 将平面P 的任意点与z相连， 连线一定与球面有 且仅有一个交点。 定义映射 π : S \{z} → P π ( s ) = p 当且仅当 z , s, p 是共线的， 该映射称为投影中 心为 z 的球极投影
定理4.13 一个图有对偶的充分必要条件是它 是平面图。
如果平面 G与它的对偶图G* 同构，则称G为自 对偶. D 自对偶图特点 D D DD (1)自对偶图的结点数与面数相等即 n=r D D (2)自对偶图的结点数与边数的关系为 D m＝2(n—1) (3)自对偶图如有自环和悬挂边，则它们的数目 相等。 (4)自对偶图如有平行边和串联边则它们一一对应 定义