第8章 几类特殊的图精选PPT.ppt

《第8章 几类特殊的图精选PPT.ppt》由会员分享，可在线阅读，更多相关《第8章 几类特殊的图精选PPT.ppt（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第8章 几类特殊的图第1页，本讲稿共121页8.1 Euler图图n n1.Euler图的有关概念第2页，本讲稿共121页n nDefinition 8-1 设G=(V,E)是任意图,G中经过所有边一次且仅一次的路称为Euler轨迹轨迹;n n G中经过所有边一次且仅一次的回路称为Euler回路回路;n n存在Euler回路的图称为Euler图图或简称为E图.第3页，本讲稿共121页n nEuler回路Euler轨迹,但反过来一般不成立.在图(a)中的图中存在Euler轨迹,但不存在Euler回路.第4页，本讲稿共121页n n2.Euler定理(本节主要定理)n nTheorem 8-1(E

2、uler定理定理)设G是连通无向图,则G是Euler图的充要条件是G的每节点度数为偶数.n nProof()显然.n n()设G是(n,m)图.对边数m归纳.第5页，本讲稿共121页n n1921年Fleury给出了一个求Euler回路的算法.n n类似于Euler定理有n nTheorem 8-2(P222)设G是弱连通有向图,则G是Euler图的充要条件是G的每节点的入度等于其出度.n nSee Figure 8-1(b).第6页，本讲稿共121页n n根据Euler定理容易得出n nTheorem 8-3 设G是连通无向图,则G中存在Euler轨迹的充要条件是G的度数为奇数的节点个数为0

3、或为2.根据该定理知根据该定理知,“,“七桥问题七桥问题”无解无解,甚至不存在甚至不存在EulerEuler轨迹轨迹.有趣的中国古老数学游戏有趣的中国古老数学游戏“一笔画问题一笔画问题”与该与该定理密切相关定理密切相关.所谓一个图能一笔画出是指从所谓一个图能一笔画出是指从图的某节点出发图的某节点出发,线可以相交但不能重合线可以相交但不能重合,不起不起笔就可以将图画完笔就可以将图画完(P223,3)(P223,3)多笔画多笔画(P223,4).(P223,4).P224,5,6.P224,5,6.第7页，本讲稿共121页n n同样,对于有向图有n nTheorem 8-4 设G是弱连通有向图,则

4、G中存在Euler轨迹的充要条件是n n(1)G的每节点的入度等于其出度,或者n n(2)G中存在一个节点出度比入度多1,存在一个节点入度比出度多1,而其余所有节点的入度等于其出度.第8页，本讲稿共121页n n3.中国邮递员问题(Chinese postman problem)n n一位邮递员从邮局选好邮件去投递,然后返回邮局,要求邮递员必须经过其负责的每一条街至少一次,为这位邮递员设计一条投递线路,使其所走的路最短.(P224,7)第9页，本讲稿共121页n n显然,若连通无向图有度数为奇数的节点,由于必须返回邮局,邮递员必须得重复走一些街道,问题是怎样才能使得完成投递任务所走的路最短.这

5、是一个允许添加多重边后求最短Euler回路的问题.n nP224,8?第10页，本讲稿共121页n n中国邮递员问题首次由中国图论专家管梅谷于1962年提出并研究,提出了“奇偶点图上作业法”,引起世界上不少数学家的关注.在1973年匈牙利数学家Edmonds和Johnson对中国邮递员问题给出了一种有效算法,另外在1995年王树禾研究了多邮递员中国邮路问题(k-Postman Chinese Postman Problem).n n作业 习题8.1 4,5,6,7,8.第11页，本讲稿共121页8.2 Hamilton 图图n n1859年爱尔兰数学家W.R.Hamilton发明了一个周游世界

6、游戏:在一个正12面体的20个顶点上标示世界上的20个大城市,若从一个城市出发,沿正12面体的棱旅行,经过每个城市一次且仅经过一次,最后回到原出发点,就算旅行成功.n n从这个游戏抽象出图论中一种非常重要的Hamilton图,且派生出至今为止仍具研究价值的TSP(Traveling Salesman Problem).第12页，本讲稿共121页n n1.Hamilton 图的有关概念n nDefinition 8-2 设G=(V,E)是任意图,G中经过所有节点一次且仅一次的路径称为H路径(Hamiltonian path);n nG中经过所有节点一次且仅一次(除起点重复一次外)的圈称为H回路(

7、Hamiltonian cycle);n n存在H回路的图称为Hamilton图(Hamiltonian graph)或简称为H图.第13页，本讲稿共121页n n例8-2(P225)第14页，本讲稿共121页第15页，本讲稿共121页n n由H回路可得到H路径,不返回出发点即可,但反过来一般不成立.n n在图(a)中的图中存在H路径,但不存在H回路.(b)中的图存在H回路,它是H图.第16页，本讲稿共121页n n判断一个图是否是Hamilton 图是非常困难的,虽然已经有一些图是Hamilton 图的充要条件,但到目前为止还没有一种方法可以有效地解决Hamilton 图的判断问题,这是一个

8、计算机科学中的一个NP难问题.n n下面分别介绍Hamilton 图的必要条件和Hamilton 图的充分条件.第17页，本讲稿共121页n n2.Hamilton 图的必要条件n nTheorem 8-5 设G=(V,E)是Hamilton无向图,则对于任意 W V,均有w(G-W)|W|.n nProof 根据已知条件,G中存在Hamilton回路C.显然,w(G-W)w(C-W)|W|.n n例8-3(P225)对于Petersen图,可以验证它满足上述定理的条件,但它不是Hamilton图.第18页，本讲稿共121页n n3.Hamilton 图的充分条件n n1960年Ore得到一个

9、Hamilton 图的充分条件.n nTheorem 8-6(Ore,1960)设G=(V,E)是n(n 3)阶简单无向图,若对于任意的不相邻节点u,v V,有deg(u)+deg(v)n,则G是Hamilton图.n n课堂 P228,7.第19页，本讲稿共121页n nProof G是连通的.n nKey:在G中选取一条最长路径n n(a)v1与vp邻接?n n(b)v1与vp不邻接?最长路径法!第20页，本讲稿共121页n n例8-4(P227)Ore定理的条件不是必要的.n nOre的上述结果推广了1952年Dirac的结果.n nCorollary(Dirac,1952)设G=(V,

10、E)是n(n 3)阶简单无向图,若对于任意节点v V,有deg(v)n/2,则G是Hamilton图.n n类似于定理8-6有n nTheorem 8-7 设G=(V,E)是n(n 3)阶简单无向图,若对于任意的不相邻节点u,v V,有deg(u)+deg(v)n-1,则G中存在H路径.第21页，本讲稿共121页n n在定理8-6的证明过程中,使用了“最长路径法”技巧.下面再举一个例子说明该方法的使用.n n例8-5 设G=(V,E)是n(n 3)阶连通无向图,证明:中存在两个节点,将它们删除后得到的图仍是连通的.n nHint 选取最长路径,使用反证法即可.第22页，本讲稿共121页n n4

11、.旅行商问题(TSP)n n有n个城镇,其中任意两个城镇间都有道路(若没有则规定该边上的权为+),一个售货员要去这n个城镇售货,从某城镇出发,依次访问其余n-1个城镇且每个城镇只能访问一次,最后又回到原出发地.问售货员要如何安排经过个城镇的行走路线才能使他所走的路程最短.这就是“货郎担问题货郎担问题”或旅行商问题旅行商问题(TSP,Traveling Salesman Problem).第23页，本讲稿共121页n n求解TSP就是要在一个赋权图中,找出一条权最小的Hamilton回路.这是一个比判断一个图是否是Hamilton图更困难的问题.n n求解TSP,可以先将所有的Hamilton回

12、路找出来,再比较其权的大小,求出权最小的H回路即可.但对于阶数较大的赋权图这样计算的工作量太大.n n课堂 P229 11.n n作业 习题8.2 3,4,5,6,7.第24页，本讲稿共121页8.3 无向树无向树n n树是图论中的重要内容之一(研究独立)(1)1847年Kirchhoff电路网络;(2)A.Cayley 1857同分异构体.n n树分为无向树和有向树.本节仅讨论无向树.n n树在各个领域都有重要应用,特别是在计算机科学中.第25页，本讲稿共121页n n1.无向树的定义n nDef 8-3(1)不含有圈的(2)连通无向图称为无向树无向树(tree=undirected tre

13、e).每个连通分支均是无向树的无向图称为森林森林(forest).第26页，本讲稿共121页n n无向树在图论中称为树,也可以称为自由树.n n含n(n 1)个节点的树称为n阶树.不含任意节点的图称为空树.n n不同构的1阶无向树、2阶无向树、3阶无向树见图8-18(a)(b)(c),4阶无向树见例8-7?n n课堂:P233,1.第27页，本讲稿共121页n n2.无向树的性质n n(1)无向树的基本性质n n性质1 n(n 1)阶无向树恰有n-1条边.n nProof 对n使用数学归纳法.n=1?n n假设n 1阶无向树恰有n 2条边(n 2).n n设G是n阶无向树.由于n 2,于是v

14、V,deg(v)1.n n若v V,deg(v)2,由定理7-5知,G有圈,C!n nv V,deg(v)=1:G v?第28页，本讲稿共121页n n例8-6(P230)设G是一棵无向树且有3个3度节点,1个2度节点,其余均为1度节点.n n(1)求出该无向树共有多少个节点.n n(2)画出两棵不同构的满足上述要求的无向树.G-v:n-1阶无向图:(1)连通;(2)不含圈 G-v:是n-1阶无向树.第29页，本讲稿共121页n nSolution n n(1)设G有x个节点度数为1,则G的节点数为x+3+1=x+4.由无向树的性质1知,G恰有x+3条边.n n由握手定理,有33+12+x 1

15、=2(x+3),于是x=5.所以G有9个节点.n n(2)两棵不同构的满足上述要求的无向树见图8-19.第30页，本讲稿共121页n n性质2 n(n 2)阶无向树至少两片树叶.n nProof n 2:由性质1的证明知,至少1片树叶.n n若G只有1片树叶:第31页，本讲稿共121页n n例8-7 证明:不同构的4阶无向树仅为如图8-20(a)(b).n nProof 根据性质1,4阶无向树恰有3条边,由握手定理知,其所有节点度数之和为6.根据性质2,4阶无向树至少2片叶.n n若恰有2片叶,则其度数序列为2,2,1,1,此时为图8-20(a)中的图.第32页，本讲稿共121页n n若恰有3

16、片叶,则其度数序列为3,1,1,1,为图8-20(b)中图.第33页，本讲稿共121页n n(2)无向树的6个等价命题(无向树的一些性质).n nTheorem 8-8 以下关于(n,m)无向图G的6个命题等价.n n(a)G是一棵无向树.n n(b)G不含有圈且m=n-1.n n(c)G连通且m=n-1.n n(d)G不含有圈但增加一条新边后得到一个且仅一个圈.n n(e)G连通但删除任意一条边后便不连通.n n(f)G的每一对节点有且仅有一条路径.第34页，本讲稿共121页n nProof(a)(b)n n(b)(c)(反证)设G有k(k 2)个连通分支,它们都是无向树,其节点数分别为n

17、n(c)(d):先证G不含圈,对n归纳.n n再证,添加一条边必有圈?n n(d)(e):n n(e)(f):n n(f)(a):第35页，本讲稿共121页n n3.生成树n n左图中的无向图不是无向树,但可以得出其生成子图,它是无向树.第36页，本讲稿共121页n nDef 8-4 设G=(V,E)是无向图,是无向树的生成子图T称为G的生成树(spanning tree),T中的边称为树枝(branch),其余边称为关于生成树T的弦(chord).n nRemark 一个无向图的生成树不一定唯一,但不是任意无向图都存在生成树.第37页，本讲稿共121页n nTheorem 8-9 设G是无向

18、图,则G存在生成树的充要条件是G是连通图.n nProof()Clearly.n n()采用破圈法n nCorollary n(n 1)阶连通图至少n 1条边.n n基本回路;基本割集 线性空间.第38页，本讲稿共121页n n4.最小生成树n n设G是边赋权的连通无向图,在有些问题讨论中,不但要得出G的一棵生成树,而且要求生成树各边的权之和(生成树的权)最小.第39页，本讲稿共121页n nDefinition 8-5 设G是一个边赋权的连通无向图,G中权最小的生成树称为最小生成树最小生成树(minimal spanning tree).n n最最优优生成树生成树?n n下面分别介绍求边赋权

19、的连通无向图的最小生成树的几种算法.第40页，本讲稿共121页n n算法算法1 克鲁斯卡尔(Kruskal,1956)的避圈法n n先将图G的m条边,按权从小到大的顺序排列:e1,e2,em.按从左至右顺序n nStep 1 选取第一条边 ,只要 不是圈,令j 1.n nStep 2 若 j=n 1,则算法结束,否则转向Step 3.n nStep 3 假定已经选取了 ,再选取 ,只要 不构成圈.令j j+1,转向Step 2.第41页，本讲稿共121页n nKruskal的避圈法的基本思想是:以边的权从小到大的顺序,逐步选边,但必须去掉产生圈的边,即避开圈的产生,直至得到n-1条边为止.算法

20、的正确性是显然的.n n例8-10 使用Kruskal的避圈法,求出左中边赋权图的最小生成树.第42页，本讲稿共121页n n将边按权从小到大顺序排列:第43页，本讲稿共121页n n算法算法2 普里姆(Prim,1957)算法.n n算法算法3 管梅谷(1975)的破圈法.n n作业 习题8.3 1,2,5,6,8,9.第44页，本讲稿共121页8.4 有向树有向树n n在8.3节讨论的是无向树,本节讨论有向树,特别是根树的有关内容,它们在计算机算法设计及程序设计研究中都起着重要作用.n n1.有向树的定义n nDef 一个有向图,在不考虑边的方向时是一棵无向树,则该有向图称为有向树有向树(

21、directed tree).n n例子见书(P234).第45页，本讲稿共121页n n2.根树n n在有向树中,更常用的是根树,它能清楚地表示层次结构.在编译程序中,用于表示源程序的语法结构,在数据库系统中用于表示信息的组织形式.n nDef 8-7 一个有向树,若恰有一个节点入度为0,而其余节点入度均为1,则该有向树称为根根树树(rooted tree).n nSee Figure 8-27(a)(b).第46页，本讲稿共121页n n(a)在根树中,入度为0的节点称为树根树根(root),出度为0的节点称为树叶树叶(leaf),出度不为0的节点称为分枝节点分枝节点,将不是根的分枝节点称

22、为内点内点.n n根树的一般画法:根画在上方或下方(see Figure 8-27(a)(b).第47页，本讲稿共121页ABCDEFGKLHIJM第48页，本讲稿共121页n n(b)为了方便,可以借助于家族树称呼根树中的节点.若有向边(u,v)E,则称u是v的父节点父节点(parent),v是u的子节点子节点(child).同一个父节点的子节点称为兄弟节点(sibling).节点的祖先祖先(ancestor)是从根节点到该节点的路径上所经过的所有分枝节点.从一个节点可以到达的任意节点都称为该节点的后代后代(offspring,descendants).第49页，本讲稿共121页n n(c)

23、从根节点到任意节点有且仅有一条路径.从根节点到某个节点的路径的长度称为该节点的层层或级(level).其父节点在同一层的节点互为堂兄弟堂兄弟.根树中节点的最大层次,称为根树的高度高度(height)或深度深度(depth).n n在根树中,所有树叶的层数之和称为该根树的外部路径长度外部路径长度,记为E;所有内点的层数之和称为该根树的内部路径长度内部路径长度,记为I.第50页，本讲稿共121页n nRemark 关于根树中节点的层(level)的含义在有些数据结构中有所不同,它们将根节点称为第1层节点,其子节点称为第2层节点,依次类推.n n(d)Def 8-8 设G=(V,E)是一棵根树,v

24、V,由节点v及其所有后代导出的子图称为G的子根树子根树(rooted subtree),可以简称为子树子树(subtree).第51页，本讲稿共121页ABCDEFGKLHIJM第52页，本讲稿共121页n n3.m叉树(m-ary tree)n n在根树中,一个节点的出度可以称为元元,或更形象地称为叉叉.在数据结构中有称为“度”的,但容易与图论中节点的度数概念混淆.n n(1)m叉树的定义n nDef 1)根树;2)n n完全m叉树(complete m-ary tree):图8-27(a).n n正则m叉树=满m叉树(regular m-ary tree):图8-27(b).第53页，本讲

25、稿共121页ABCDEFGKLHIJM第54页，本讲稿共121页n n(2)m叉树的性质(Data Structure)n nProperty 1 m叉树的第i层的节点至多为mi(i 0).第55页，本讲稿共121页n nProperty 2 高度为h的m叉树至多有 mh+1-1(m 2)个节点.n nProperty 3 一棵有l片树叶的m叉树的高度至少为logml.第56页，本讲稿共121页n nProperty 4 若一棵完全m叉树有l片树叶,t个分枝节点,则(m 1)t=l 1.n nHint mt条边,t l个节点.n nProperty 5 若2叉树有l片树叶,则出度为2的节点有l

26、-1个.n nHint 由握手定理.第57页，本讲稿共121页n nProperty 6 有l片树叶的完全2叉树有2l-1个节点.n nProperty 7 若完全2叉树有t个分枝节点,则E=I+2t,其中E为外部路径长度,I为内部路径长度.第58页，本讲稿共121页n n(3)叶赋权m叉树n n下面讨论叶赋权m叉树.n nDefinition 设G=(V,E)是一棵m叉树,若G的每一片树叶上都赋予一个非负实数,则称G为叶赋权叶赋权mm叉树叉树.n n可以将树叶理解为苹果,树叶上所赋的权理解为苹果的重量(see below).第59页，本讲稿共121页ABCDEFGKLHIJM第60页，本讲稿

27、共121页n nDef 8-11 设G=(V,E)是一棵叶赋权m叉树,其l片树叶上的权分别为w1,w2,wl,记根节点到权为wi 的树叶节点的路径长度(即距离)为l(wi),称 为m叉树的权权,记为W(G),即n nW(G)可理解为该m叉树所承受的“力”,也可以参见后面的Huffman编码.第61页，本讲稿共121页ABCDEFGKLHIJM第62页，本讲稿共121页n n下面仅讨论最优2叉树问题,它在计算机解决某些判定问题时可以得到最佳判定算法.所得结论可以推广到一般的最优m叉树,参见数据结构等书.n nDef 8-12 设G=(V,E)是一棵叶赋权2叉树,其l片树叶上的权分别为w1,w2,

28、wl,在所有树叶数相同以及相应树叶上的权也相同的2叉树中,权最小的那棵2叉树称为最优最优2 2叉树叉树或HuffmanHuffman树树.第63页，本讲稿共121页第64页，本讲稿共121页n n赫夫曼(Huffman)在1952年首先给出一个求最优2叉树的有效算法,其基本思想是“将较轻的苹果挂远一点,而不是相反,否则可能折断树枝”:n n例8-11 计算有5片树叶,分别赋权1,2,3,4,5的Huffman树.第65页，本讲稿共121页1569334512第66页，本讲稿共121页n n4.有序树n n在根树中,对同一个节点的所有儿子节点是没有先后顺序的,这与家族树不完全一致.同时,在有些应

29、用问题中,需要对同一个节点的所有儿子节点规定一个先后顺序,通常是从左至右顺序,这就是有序树.第67页，本讲稿共121页n nDef 8-13 设G是一棵根树,若对同一个节点的所有儿子节点规定一个先后顺序,则称G为有序树有序树(ordered tree).n n在有序树中,一个节点的最左边的儿子常称为该节点的长子长子.在同一个父节点的所有子节点中,一个节点的右边第一个节点称为该节点的大弟大弟.n nSee above.第68页，本讲稿共121页n n如果一片森林中,每一棵根树都是有序树,且全体有序树的根也规定了先后顺序,则称该森林为有序森林有序森林(ordered forest),其中一棵有序树

30、的右边第一棵有序树的根是前一棵有序树的根的大第大第.n n例8-12 用有序树表示一个代数表达式?关键是注意先后位置.n n命题公式第69页，本讲稿共121页n n作为根树相同(同构),而作为有序树是不同的!-/|cba/c-ba|第70页，本讲稿共121页n n5.定位2叉树n n对于2叉有序树,每个分枝节点至多两个儿子.若对这两个儿子,包括只有一个儿子的情形,还根据实际情况确定了其左右位置,分别称为左儿子和右儿子,这就是定位2叉树.n n(1)定义n nDef 8-14 设G是一棵有序2叉树,若对同一个节点的所有儿子(至多2个!)节点确定一个左右位置,则称G为定位定位2 2叉树叉树(pos

31、itional binary tree).第71页，本讲稿共121页定位定位2 2叉树是数据结构中的叉树是数据结构中的2 2叉树叉树(binary tree.(binary tree.(1)(1)左儿子左儿子和和右儿子右儿子.(.(无右儿子或左儿子的理解无右儿子或左儿子的理解?)(2)(2)左子树和右子树左子树和右子树.第72页，本讲稿共121页n n(2)Huffman编码n n在定位2叉树中,与Huffman树密切相关的是Huffman编码.n nHuffman编码是数据文件压缩的一个十分有效的编码方法,其压缩率在20%90%.n n 现给出前缀及前缀码的定义.第73页，本讲稿共121页n

32、 nDef 8-15设 是长度为n的符号串,则称子串 分别为 的长度为1,2,n-1的前缀前缀.设 是符号串组成的集合,若对于任意i j均有 与 互不为前缀,则称A为前缀码前缀码(prefix code).若 中只出现0或1两个符号,则称A为二元前缀码二元前缀码(binary prefix code).第74页，本讲稿共121页n n用二进制对计算机及通讯中使用的符号进行编码:n n(1)保证编码没有歧义,不会将字母传错;n n(2)二要保证码长要尽可能地短;n n(3)电文总长最短.n n为了使电文总长尽可能地短,使用Huffman编码即可.第75页，本讲稿共121页n nHuffman编码

33、是使得电文(EFGGHHADEC BBB)总长最短的2进制前缀编码,其叶上的权为传输各符号的频率,所得到的Huffman树的权为传输一个符号需要使用的二进制数字的个数.n n例8-14 将7个符号按其出现的频率0.2,0.19,0.18,0.17,0.15,0.1,0.01构造出其Huffman编码.第76页，本讲稿共121页DABEGFC第77页，本讲稿共121页n n(3)遍历方式n n遍历定位2叉树(traversing binary tree)有3种方式:n n(a)前序遍历:根节点左子树右子树.n n(b)中序遍历:左子树根节点右子树.n n(c)后序遍历:左子树右子树根节点.n n

34、(see below)第78页，本讲稿共121页n n(a)前序遍历:n n(b)中序遍历:n n(c)后序遍历:第79页，本讲稿共121页n n数据结构(如何遍历?):-+/a*efb-cd第80页，本讲稿共121页n n(4)有序森林与定位2叉树之间的转换n n由于定位2叉树结构简单,经常将有序森林,特别是有序树,转换成定位2叉树(Data Structure).我们以有序森林与定位2叉树之间的转换作为结束.n n在有序森林与定位2叉树之间根据自然转换规则建立一一对应:n n(1)在F中u是v的长子,则在B中u是v的左儿子;n n(2)在F中u是v的大弟,则在B中u是v的右儿子.n n例8

35、-15 将图8-36(a)中的有序森林转换成定位2叉树.第81页，本讲稿共121页第82页，本讲稿共121页n nRemark 若u只有一个的长子v,则v是u的长子.n n作业 n n习题8.4:2,8,9,11,12.第83页，本讲稿共121页8.5 平面图平面图 n n本节仅讨论无向图本节仅讨论无向图.n n对于一个无向图来说，怎样将其图形画出来本身是对于一个无向图来说，怎样将其图形画出来本身是无关紧要的，只要与原来的图同构皆可无关紧要的，只要与原来的图同构皆可.但有些实但有些实际问题要求把图画在一个平面上，同时使得图的边际问题要求把图画在一个平面上，同时使得图的边仅仅在节点处才相交仅仅在

36、节点处才相交.例如单层印刷电路版、集成例如单层印刷电路版、集成电路的布线等问题就需要满足上面的要求电路的布线等问题就需要满足上面的要求.n n虽然在现实生活中出现了交通立交桥、多层电路版，虽然在现实生活中出现了交通立交桥、多层电路版，但平面图问题仍然是一个基本问题但平面图问题仍然是一个基本问题.例如在上章例如在上章7.17.1节提到的节提到的“3 3户户3 3井问题井问题”就是判定一个图是否是就是判定一个图是否是平面的问题平面的问题.n n平面图与地图着色问题密切相关平面图与地图着色问题密切相关.第84页，本讲稿共121页n n1.平面图的有关概念n nDef 设G是无向图,若可将G画在一个平

37、面上,同时使得任意两条边仅仅在节点处才相交,则称G是可平面图可平面图(planar graph)或简称G为平面图平面图(plane graph).n n设G是平面图,则可在一个平面上将图G画出来且使得其任意两条边仅仅在节点处才相交,这样画出的图称为平面图G的平面嵌入(embedding)或平面表示.由于一个平面图与其平面表示是同构的,因此平面图通常是指其平面表示.第85页，本讲稿共121页n n两个重要的非平面图的例子:n n(1)K5.n n(2)K3,3.第86页，本讲稿共121页n n极大平面图?K K5 5-e e(True);(True);K K3,33,3-e e(False).(

38、False).n n极小非平面图?K K5 5;K K3,33,3.第87页，本讲稿共121页n nDef 8-19 设G是平面图,由G的若干条边所围成的连通区域称为图G的面面(face),围成面的(回路所在的)边称为面的边界边界(boundary).n n一个区域是连通的,是指其内部不包含该图的任何边.n nFigure 8-38(b)?围墙?第88页，本讲稿共121页n n特别注意,任何平面图都有一个由若干条边往外围成的一个面,它是唯一的一个无限面.n n求一个平面图的面可以这样做,在一张较大的纸上将平面图画上,然后用剪刀将图的所有边剪破,这张纸被分成的每一部分就是一个面.n n平面图的两

39、个面相邻是指这两个面有公共的边界.第89页，本讲稿共121页n n2.Euler公式公式n nEuler在1750年研究多面体时发现,多面体的面数等于多面体的棱数减去顶点数加2,后来发现连通平面图的面数与其节点数、边数之间也有同样的关系.n nTheorem(Euler公式公式)任意(n,m)连通平面图的面数r=m n+2.n nProof 对面数r归纳.r=1.n n r 2 圈C.去掉C上的一条边e.G e.第90页，本讲稿共121页n nRemark 在Euler公式中,“连通”的条件是必不可少的.n nCorollary 1 任意(n,m)简单平面图,若n 3,则m 3n-6.n nn

40、 3(?):n n不妨设G连通(?),否则考虑其连通分支.n n由于对于n2(n7!)的简单图有m 3n,若存在连通分支的节点个数n 3,就有边数m 3n 6,结论成立.假设每个连通分支的节点个数均 2.第91页，本讲稿共121页n n若存在两个连通分支的节点个数为2,则这两个连通分支的边数2 34 6,结论也会成立.n n若节点个数为2的连通分支仅一个或没有,结论也成立.n n例8-16 证明:K5不是平面图.n nHint 反证.10 35 6?第92页，本讲稿共121页n nCorollary 2 任意(n,m)简单平面图,若G不含K3子图且n 3,则m 2n-4.n nSimilar

41、to the proof of Corollary 1:n n例8-17 证明:K3,3不是平面图.n nHint 反证.9 26 4?n n更一般的结论:P246 7?第93页，本讲稿共121页n n下面的定理是证明“五色定理”的关键.n nTheorem 8-11(P244)任何简单平面图必存在一个度数 5 的节点.n nProof 不妨设n 3.假设vV,deg(v)6.第94页，本讲稿共121页n n3.Kuratowski定理n n先介绍同胚的定义.n nDef 若两个图是同构的,或者通过反复进行以下操作(见图8-42)使得它们同构,则称这两个图同胚同胚(homeomorphism)

42、:第95页，本讲稿共121页n nTheorem(Kuratowski,1930)无向图G是平面图的充要条件是G无同胚于K5和K3,3的子图.n n例8-18 证明:Petersen图不是平面图.第96页，本讲稿共121页n nP246 5(利用Euler公式证明)第97页，本讲稿共121页n n4.平面图的对偶图n n对平面图G的面的研究可以转换为对其对偶图G*的节点的研究.第98页，本讲稿共121页n n根据定义知,任意平面图的对偶图是平面图且是连通的.设G是(n,m)平面图,有r个面,则G*是(r,m)平面图,有n个面.n n对于连通平面图G,其对偶图为G*,这时G*的对偶图G*为本身.

43、对于非连通平面图G,可能G与G*不同构.n n作业 习题8.5 26,9,11,13,15,17.第99页，本讲稿共121页8.6 平面图的面着色平面图的面着色n n“四色猜想”(4CC,Four Color Conjecture).n n1879年伦敦数学会会员A.B.Kemple给出了四色猜想的第一个证明,10年后P.J.Heawood指出了Kemple证明过程中存在一个不可克服的漏洞,并沿用Kemple的方法证明了五色定理,即五种颜色足够.第100页，本讲稿共121页n n4CC成了会下金蛋的鹅.在1976年,美国的Kenneth Appel和Wolfgang Haken与John Ko

44、ch合作,用了1260个小时证明了“四色猜想”,它开启了定理机器证明的新篇章,四色猜想变成四色定理了.1999年又给出了一些改进,缩短了计算机的运行时间.n n至今为止还没有发现4CC的纯数学证明.n n本节主要内容是平面图的面着色问题,顺便介绍任意无向图的节点着色以及边着色等有关内容.第101页，本讲稿共121页n n1.平面图的面着色n nDef 设G是平面图,若对G的每个面涂上一种颜色且相邻的面出现不同的颜色,则称对该平面图的面着色面着色(face coloring),所需颜色的最少种数称为面着色数面着色数(region chromatic number).n nFigure 8-47(

45、see below)n nRemark 任意平面图均有无限面.第102页，本讲稿共121页第103页，本讲稿共121页n n2.图的节点着色n n(1)任意图的节点着色n nDef 设G是任意无向图,若对G的每个节点涂上一种颜色且相邻的节点出现不同的颜色,则称对该图的节点着色节点着色(vertex coloring),简称着色着色(coloring),所需颜色的最少种数称为节点着色数,简称着色数着色数(chromatic number),记为n n 第104页，本讲稿共121页第105页，本讲稿共121页n nTheorem 8-13 G无loop,则n n可以利用韦尔奇鲍威尔(Welch P

46、owell)算法对图的节点着色,进而求出的上界.n nStep 1 将节点按度数从大到小的顺序排列.n nStep 2 用第一种颜色对第一个节点着色,并且按照其余未着色节点顺序,对不邻接的每一个节点着上同样的颜色.n nStep 3 用第二种颜色对尚未着色的节点重复Step 2,继续下去,直到所有的点都着色为之.n n例子?第106页，本讲稿共121页n n(2)平面图的节点着色n n平面图的节点着色与一般无向图的节点着色是相同的.值得注意的是,平面图的面着色,可以转换为其对偶图(也是平面图)的节点着色.于是,五色定理为n nTheorem 8-14 设G是简单平面图,则n nHint 对G的

47、节点个数n归纳.第107页，本讲稿共121页n n3.任意图的边着色n nDef 设G是任意无向图,若对G的每条边涂上一种颜色且相邻的边出现不同的颜色,则称对该图的边着色边着色(edge coloring),所需颜色的最少种数称为边着色数边着色数(edge-chromatic number).n n图中的两条边相邻是指它们有公共的节点.第108页，本讲稿共121页第109页，本讲稿共121页n n对图的边着色问题不做更深入讨论,最后对与Ramsey理论密切相关的图的边“涂色”的问题进行简单说明.n nRamsey问题问题(Ramsey problem)任给一群人,其中有p个人彼此认识或有q个人

48、彼此不认识,这种人群至少多少人?n nRamsey问题中的答案记为R(p,q).n n例8-20(P250)证明:任意6个人中,有3个人彼此认识或有3个人彼此不认识.第110页，本讲稿共121页n nR(3,3)=6(1930),其他Ramsey数?n n作业 习题8.6 1,3,5,7,9.第111页，本讲稿共121页8.7 二部图及其匹配二部图及其匹配n n在诸如人员分配、资源分配等问题的讨论中,经常涉及到二部图及其匹配.n n本节仅对简单无向图进行讨论.n n1.二部图n nDefinition V划分为V1和V2,任意边关联的两个节点中一个在V1中,一个在V2中.第112页，本讲稿共1

49、21页n nRemark 互补节点集合不是唯一的.第113页，本讲稿共121页n n下面的定理给出了简单无向图是二部图的充要条件.n nTheorem 8-15 设G为阶数 2的简单无向图,则G是二部图的充要条件是G中任意圈的长度为偶数.n nProof()n n()取v V,令V1=u|u V,d(u,v)是偶数,V2=V-V1.n n显然,任意无向树是二部图.n n三部图?有向二部图(petri net)?第114页，本讲稿共121页n n2.匹配匹配n nDef 设G=(V,E)是任意简单无向图.若 M E且中任何两条边都不相邻,则称M为G的一个匹配匹配(matching)或边独立集边独

50、立集(independent set of edges),M中每条边的两个节点在M中匹配.第115页，本讲稿共121页n nab,fh,idn nab,fi,cd,hjn naf,bg,ch,di,ej第116页，本讲稿共121页n nG=(V,E),W V.n n(1)W中任意两个节点均不邻接:点独立集.n n极大点独立集;最大点独立集合.n n(2)GW是完全图:团(clique)n n极大团;最大团.n n王晓东,计算机算法设计与分析,电子工业出版社,2001.n nCh5回溯法,Ch6分支界限法:最大团问题.第117页，本讲稿共121页n n(a)边数最多的匹配称为最大匹配最大匹配(m