当前位置：文档之家 › 第六章 平面图1 图论及其应用课件

第六章 平面图1 图论及其应用课件

  • 格式：ppt
  • 大小：1.19 MB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

图论及其应用

图论及其应用
χ（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个边不相交的对集，并且

图论及其应用

图论及其应用

图和子图 图和简单图图 G = (V, E)V ---顶点集，ν---顶点数12ε E ---边集， ε---边数例。

左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。

真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。

不过今后对两者将经常不加以区别。

称 边 ad 与顶点 a (及d) 相关联。

也称 顶点 b(及 f) 与边 bf 相关联。

称顶点a 与e 相邻。

称有公共端点的一些边彼此相邻，例如p 与af 。

环（loop ，selfloop ）：如边 l 。

棱（link ）：如边ae 。

重边：如边p 及边q 。

简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。

一条边的端点：它的两个顶点。

记号：νε()(),()().G V G G E G ==。

习题1.1.1 若G 为简单图，则εν≤⎛⎝ ⎫⎭⎪2 。

1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。

同构在下图中， 图G 恒等于图H , 记为 G = H ⇔ VG)=V(H), E(G)=E(H)。

图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。

记为 G ≅F。

注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。

de f G = (V , E )yz w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。

完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。

V’ ( ⊆ V) 为独立集 ⇔ V’中任二顶点都互不相邻。

图论课件-PPT课件

图论课件-PPT课件

学习方法
目的明确
态度端正 理论和实践相结合
充分利用资源
逐步实现从知识到能力到素质的深化和
升华
课程考核
平时成绩 （30%-40%）
闭卷考试 （60%-70%）
图论模型
为了抽象和简化现实世界，常建立数学模型。图是关 系的数学表示，为了深刻理解事物之间的联系，图 是常用的数学模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢 化合物 用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。
E={w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5}代表每个仓库和每个 零售店间的关联。则图模型图形为： w1 w2 w3
r1
r2
r3
r4
r5
29
(3) 最短航线问题 用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。 例如：令V={a, b, c, d, e}代表5个城市} E={a b, ad, b c , be, de}代表城市间的直达航线 则航线图的图形为： a 320 500 d 370 b 140 430 e c

图论学科简介 （2）
19世纪末期，图论应用于电网络方程组
和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论 用来求解生产管理、军事、交通运输、 计算机和网络通信等领域中的离散性问 题 物理学、化学、运筹学、计算机科学、 电子学、信息论、控制论、网络理论、 社会科学、管理科学等领域应用
七桥问题
近代图论的历史可追溯到18世纪的七桥问题:
穿过Kö nigsberg城的七座桥，要求每座桥通过 一次且仅通过一次。

图论及其应用

图论及其应用

Prim算法及思想
• • • • • 首先我们将V分成两部分U,S U∩S=∅ U∪S=V 一开始S中只有任意以个节点 每次我们枚举每条U，S之间的边权最小的边S中 这条边的端点 删除并加入U • 我们可以每次更新S中点的这个值不需要每次枚 举边复杂度O(n^2) • 如果使用堆优化可以做到O(nlogn+nlogm)
tarjan算法
tarjan算法
拓扑排序
• 每次选择一个入度为0的点加入队列，然后 删掉这个点的所有出度
小试身手
• APIO2009 atm • 有一个城市有若干条有向道路 • 一个小偷从一个点出发想偷这个城ATM机， 他从一个点出发，最后偷完之后需要到一 个酒吧庆祝，给定道路情况，每个路口atm 的钱数和有没有酒吧，求最多能偷多少钱。 • n<=100000
小试身手
对于n<=1000我们依然可以直接暴力建出图 来进行Dijsktra算法但是对于n<=10000的测 试点，所有边一共有10^10条，我们无法存下 来但是我们发现，只有x坐标相邻和y坐标相 邻的边才有意义(为什么？)，然后就可以建出 图来用堆优化的Dij或者spfa过掉
小试身手
• 给你一个n个点的图，小Q有q个询问，每次 询问任意两点之间的最短路 • n<=200,q<=4000000
Байду номын сангаас
最短路算法
• 如果我们需要知道所有的点对之间的最短 路，可以使用floyed的传递闭包方法。 • floyed算法思想： • 我们每次选择一个中间点，然后枚举起点 和终点，用通过中间点的最短路径更新起 点和终点之间的最短路径时间复杂度O(n^3)
floyed代码实现
• 代码非常简单 • 注意枚举顺序

图论课件第六章平面图

图论课件第六章平面图

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页
通过尝试，可以把上图画为：

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

图论-总结PPT课件

q-p+1条弦。 (2) 若G是一个(p,q)连通图，则T至少有多少个圈?(q-p+1) 若G是一个(p,q)连通图，则T有多少个圈? 若G是一个(p,q)连通图，则T至少（多）有多少个生成树？
.
16
第三节 割点、桥和割集
3.1 割点和桥(割边)
定义1 设v是图G的一个顶点，若G-v的支数大于 G的支数，则称顶点v为图G的一个割点(如图)。
degu + degv≥p-1，
则G是连通的。[这个定理是一个充分条件]
定理3 设G=(V,E)是至少有一个顶点不是弧立顶 点的图。若对任意v∈V，degv为偶数，则G中 有回路。
定理4 若图G中的两个不同顶点u与v间有两条不 同的路联结，则G中有回路。
.
6
例1 若G是一个恰有两个奇度顶点u和v的无向图，则 G连通G+uv连通。
.
8
第五节 欧拉图(Euler)
5.1 欧拉图
定义1 设(G,V)是一个图，则包含图的所有顶 点和所有边的闭迹称为欧拉闭迹；存在一 条欧拉闭迹的图称为欧拉图。
定理1 图G是欧拉图当且仅当G是连通的且每 个顶点的度都是偶数。
(定理1对多重图也成立)
.
9
第六节 哈密顿图
6.1 哈密顿图 定义1 设G是一个图，则图G中包含G的所有顶
数称为顶点v的度，记为degv。 定理1 (握手定理)设G=(V,E)是一个具有p个顶点q条边的图,
则G中各顶点度的和等于边的条数q的两倍，即∑degv=2q。 推论1任一图中，度为奇数的顶点的数目必为偶数。
.
3
定义3 设G是图，若Δ(G)=δ(G)=r，即G的每个顶点的 度都等于r，则G称为r度正则图。

图论第6章


正八面体和正二十面体的一维骨架：
正八面体
正二十面体
26
如果将一个有n个顶点，m条棱和ф个面的凸多面 体的顶点作为顶点，棱作为边，则这个多面体可视 为一个图G，而且G可嵌入球面，从而可嵌入平面而 得到一个连通的平面图。 由定理2，凸多面体的顶点数，棱数与面数也满 足 n-m + ф =2。这个公式也称为欧拉公式 定理6（Platonic） 存在且只存在5种正多面体： 正四面体、正方体、正八面体、正十二面体和正二 十面体。 证明 任取一个正ф面体A ，设A 有n个顶点，m 条棱。将A 嵌入平面记所得的平面图为G。易知G 是一个每个面的次数均相同（设为l）的r 度简单 正则图。从而有
n m +
i
k
k
k
i
而
n
i =1
k
i =1
i =1
i
= 2k
i
(1.4)
i =1
i
= n,
m
i =1
k
i
= m,

i =1
k
=ф +（k-1）
因为外部面重复计算了k次，即多算了k-1次
13
将它们代入（1.4）式得 n – m +ф+ k-1 = 2k n – m +ф= k+1 定理4 设 G 是具有n 个点m 条边的连通平面图, Ψ 是G 中所有面的集合，若对 任意的 f ∈ Ψ 均有 deg( f )≥l ≥3，则
deg( f ) = 2m
f Ψ
（1.1）
证明 任取G 的一条边 e 。若 e 是两个面的公共 边，则在计算面的次数时，e 被计算两次。若 e 不 是公共边，则 e 是 G 的割边，由面的次数的定义， e 也被计算两次。所以所有面的次数之和是边数 的2倍，即（1.1）式成立。

图论平面图


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

第六章 平面图3 图论及其应用课件(共30张PPT)


H G
称 H 是G容许(róngxǔ)的。 例2 在G中，我们(wǒ men)取红色边导出的子图为HH, 并H取
G
G
容易知道： H 是G容许的。
6
第六页，共30页。
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
例3 在G中，我们(wǒ men)取红色边导出的子图为HH,并H取
B3 G[v4v5] F (B 3,H 4)f1,f5
B4 G[v5v8] F(B4,H 4)f1
B5 G[v6v8] F(B5,H4)f1
v5 v6 f3 v7
v8
第十八页，共30页。
f5
18
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
v8 v7
v3 v4
v6
v5 图G
v1
v2 f2 f1
v3 v4
H1
v5 v6 f3
v7 v8
15
第十五页，共30页。
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
B1 G[v1v4] F (B 1,H 2)f1,f3
B2 Gì)知H 道： 不 是G容许的。
定义4 设B是G中子(zhōngzǐ)图H的任意一座桥，假设B对H的所有
附着顶点都位于 H 的某个面f的边界上，那么称B在面 f 内可画入，
否那么，称B在面 f 内不可画入。
7
第七页，共30页。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

外可平面图
外平面图1
外平面图2
10
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
注：对外可平面图G来说，一定存在一种外平面嵌入， 使得G的顶点均在外部面的边界上。这由球极投影法可 以说明。
下面研究极大外平面图的性质。
定义3 设G是一个简单外可平面图，若在G中任意不邻 接顶点间添上一条边后，G成为非外可平面图，则称G是 极大外可平面图。极大外可平面图的外平面嵌入，称为极 大外平面图。
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
图论及其应用
任课教师：杨春 Email: yc517922@
应用数学学院
1
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
定义1 设G是简单可平面图，如果G是Ki (1≦i≦4),或 者在G的任意非邻接顶点间添加一条边后，得到的图均是
非可平面图，则称G是极大可平面图。
极大可平面图的平面嵌入称为极大平面图。
3
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
1
注：该定理可以简单记为是“极大平面图的三角形特 征”，即每个面的边界是三角形。
证明：“必要性”
由引理知，G是单图、G无割边且G的每个面的次数 至少是3。
假设G中某个面f的次数大于等于4。记f的边界是 v1v2v3v4…vk。如下图所示。
6
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
情形2 若G是2连通的。 考虑G的任意一种外平面嵌入。则G的外部面边界一 定是圈。否则，容易推出G有割点。
设C是G的外平面嵌入的外部面边界。若除C外，图 中没有其它的边，则G=C, 显然G中有不邻接点，度数 不超过2；
13
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
2mdeg(f)3 f
由欧拉公式：
2nm
所以得：
2m2nm 3
8
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
所以得： m3n6
又 mn2
所以： 2n4
注：顶点数相同的极大平面图并不唯一。例如：
正20面体
非正20面体
9
1
0 .5 n 0
1 0 .8
0 .6 0.4 x 0 .2
定理2 设G是一个有n (n≥3)个点，且所有点均在外部面 上的极大外平面图，则G有n-2个内部面。
证明：对G的阶数作数学归纳。
定理的充分性是显然的。
7
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
推论：设G是n个点，m条边和ф个面的极大平面图， 且n≥3.则：(1) m=3n-6; (2) ф=2n-4.
证明：因为G是极大平面图，所以，每个面的次数为3. 由次数公式：
1 0 .8
0 .6 0.4 x 0 .2
v1
vk
v2
f
v5
v3
v4
如果v1与v3不邻接，则连接v1v3，没有破坏G的平面性， 这与G是极大平面图矛盾。所以v1v3必须邻接，但必须在 f 外连线；同理v2与v4也必须在f外连线。但边v1v3与边 v2v4在 f 外交叉，与G是平面图矛盾！
所以，G的每个面次数一定是3.
极大外平面图
11
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
引理 设G是一个连通简单外可平面图，则在G中有 一个度数至多是2的顶点。
证明 我们对G的阶数n作数学归纳。
当n≦3时，引理结论显然成立；当n=4时，由于K4不 能是外可平面图，所以，四阶的外可平面图至少有一个 顶点度数不超过2。事实上，更强一点的结论是：当n=4 时，有两个不邻接顶点，其度数不超过2.
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4ቤተ መጻሕፍቲ ባይዱx 0 .2
下面证明极大平面图的一个重要性质。
定理1 设G是至少有3个顶点的平面图，则G是极大平 面图，当且仅当G的每个面的次数是3且为单图。
设当G是一个阶数小于n的简单连通外可平面图时， 存在两个不邻接顶点，其度数不超过2。
考虑G是一个阶数等于n的简单连通外可平面图。
情形1，如果G有割点x
12
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
x
由归纳假设，G-x的两个不同分支中分别有一个异于 x的顶点z与z1,使得度数不超过2。这说明G中有两个不邻 接顶点, 使得度数都不超过2；
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
还在研究中的问题是：顶点数相同的极大平面图的个 数和结构问题。
与极大平面图相对应的图是极小平面图。
2、极大外平面图及其性质
定义2 若一个可平面图G存在一种平面嵌入，使得其所 有顶点均在某个面的边界上，称该图为外可平面图。外可 平面图的一种外平面嵌入，称为外平面图。
本次课主要内容
特殊平面图与平面图的对偶图
(一)、一些特殊平面图
1、极大平面图及其性质 2、极大外平面图及其性质
(二)、平面图的对偶图
2
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00
1 0 .8
0 .6 0.4 x 0 .2
(一)、一些特殊平面图
1、极大平面图及其性质
对于一个简单平面图来说，在不邻接顶点对间加边， 当边数增加到一定数量时，就会变成非平面图。这样， 就启发我们研究平面图的极图问题。
0 .6 0.4 x 0 .2
若除C外，图中至少有边xy。如下图所示：
x
y
则在C上的两条xy路上的点在G中的两个导出子图H1 与H2是外平面图。
有归纳假设，在H1,H2中分别存在异于x ,y的点z与z1, 使得，它们的度数不超过2.
x
z
z1
y 14
1
0 .5 n 0
0 .5
1 2 1 .5 t1 0 .5 00