大学精品课件:7-图与路径规划.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《大学精品课件:7-图与路径规划.ppt》由用户(罗嗣辉)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学 精品 课件 路径 规划
- 资源描述:
-
1、第四章第四章 图与路径规划图与路径规划图与网络的基本知识图与网络的基本知识树树最短路问题最短路问题网络最大流问题网络最大流问题q18世纪,哥尼斯堡城中有一世纪,哥尼斯堡城中有一条河叫普雷格尔河,河中有条河叫普雷格尔河,河中有两个小岛,河上有七座桥。两个小岛,河上有七座桥。q问题:问题:q一个散步者能否走过七座桥,一个散步者能否走过七座桥,且每座桥只走过一次,最后回且每座桥只走过一次,最后回到出发点?到出发点?哥尼斯堡七桥问题哥尼斯堡七桥问题q1736年,欧拉年,欧拉“依据几何位置依据几何位置的解题方法的解题方法”将此问题归结为将此问题归结为图图10-1(b)的一笔画问题。的一笔画问题。图图10
2、-1(b)图图10-1(a)q能否从某一点开始一笔画出这能否从某一点开始一笔画出这个图形,最后回到原点,而不个图形,最后回到原点,而不重复?重复?q基本概念基本概念q定义定义1 1一个一个图图是由点集是由点集V=vi和和V中元素的无序对的一个集中元素的无序对的一个集合合E=ek所构成的二元组,记为所构成的二元组,记为G=(V,E),V中的元素中的元素vi叫做叫做顶点,顶点,E中的元素中的元素ek叫做边叫做边(无向边无向边)。1图与网络的基本知识图与网络的基本知识无向图无向图q定义定义11一个一个有向图有向图是由点集是由点集V=vi和和V中元素的有序对的一中元素的有序对的一个集合个集合A=ek所
3、构成的二元组,记为所构成的二元组,记为D=(V,A),V中的元素中的元素vi叫做顶点,叫做顶点,A中的元素中的元素ek叫做弧叫做弧(有向边有向边)。e4e2e1e3e5e6v1v2v3v4v5G=(V,E),V=v1,v2,v3,v4,v5,E=e1,e2,e3,e4,e5,e6,其中,其中e1=v1,v1,e2=v1,v2,e3=v1,v3,e4=v2,v3,e5=v2,v3,e6=v3,v4。记号:记号:m(G)=|V|表示图表示图G的顶点数,的顶点数,n(G)=|E|表示图表示图G的边数。的边数。环环多重边多重边悬挂点悬挂点悬挂边悬挂边孤立点孤立点q基本概念基本概念(续续)q定义定义2
4、2不含环和多重边的图称为不含环和多重边的图称为简单图简单图,含有多重边的图,含有多重边的图称为称为多重图多重图。(a)(b)(c)(d)q定义定义3 3每一对顶点都有边相连的无向简每一对顶点都有边相连的无向简单图称为单图称为完全图完全图。有。有n个顶点的无向完全个顶点的无向完全图记作图记作Kn。q有向完全图是指每一对顶点间有且仅有一有向完全图是指每一对顶点间有且仅有一条有向边的简单图。条有向边的简单图。q定义定义4 4图图G=(V,E)的点集的点集V可以分为两个可以分为两个非空子集非空子集X,Y,即,即X Y=V,X Y=,使得使得E中的每一条边的两个端点必有一端中的每一条边的两个端点必有一端
5、点属于点属于X,另一端点属于,另一端点属于Y,则称,则称G为二部为二部图图(偶图偶图),有时另记作,有时另记作G=(X,Y,E)。v1v2v3v4v5v6v1v3v2v4q顶点的次顶点的次q定义定义5 5以点以点v为端点的边数叫做为端点的边数叫做点点v的的次次,记作,记作deg(v),简记为,简记为d(v)。q定理定理1 1任何图中,顶点次数的总和任何图中,顶点次数的总和等于边数的等于边数的2倍。倍。由于每条边必与两个顶点关联,在计由于每条边必与两个顶点关联,在计算点的次时,每条边均被计算了两次,算点的次时,每条边均被计算了两次,所以顶点次数的总和等于边数的所以顶点次数的总和等于边数的2倍。倍
6、。q定理定理2 2任何图中,次为奇数的顶点必为偶数个。任何图中,次为奇数的顶点必为偶数个。证明证明 设设V1和和V2分别表示图分别表示图G中奇点与偶点的集合中奇点与偶点的集合(V1 V2=V)由定理由定理1知,知,e4e2e1e3e5e6v1v2v3v4v5 mvdvdvdVvVvVv221 2m为偶数,为偶数,2Vvvd是若干个偶数之和,亦为偶数,是若干个偶数之和,亦为偶数,1Vvvd所以,所以,必为偶数,即必为偶数,即|V1|为偶数。为偶数。q有向图顶点的次有向图顶点的次q定义定义6 6有向图中,以点有向图中,以点v为始点的边数称为点为始点的边数称为点v的的出次出次,用,用d+(v)表示,
7、以点表示,以点v为终点的边数称为点为终点的边数称为点v的的入次入次,用,用d-(v)表示。表示。v点的出次与入次之和就是该点的次。点的出次与入次之和就是该点的次。q有向图中,所有顶点的入次之和等于所有顶点的出次之和。有向图中,所有顶点的入次之和等于所有顶点的出次之和。q子图子图q定义定义7 7图图G=(V,E),若,若E是是E的子集,的子集,V是是V的子集,且的子集,且E中的边仅与中的边仅与V中的顶点相关联,则称中的顶点相关联,则称G=(V,E)是是G的的子图子图。特别,若特别,若V=V,则,则G称为称为G的的生成子图生成子图(支撑子图支撑子图)。q网络网络q点或边带有某种数量指标的图称为网络
8、。点或边带有某种数量指标的图称为网络。4692q定义定义8 8无向图无向图G=(V,E),若图,若图G中某些点与边的交替中某些点与边的交替序列可以排列成序列可以排列成连通图连通图 kkkiiiiiiivevevev,12110 的形式,的形式,且且 tttiiivve,1 ,则称这个点边序列为连接,则称这个点边序列为连接kiivv 与0的一条的一条链链(道路道路),链长为,链长为k。点边列中没有重复的点和重复的边者为点边列中没有重复的点和重复的边者为初等链初等链。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10S=v6,e6,v5,e7,v1,e8,v5,e7,v1,e9,v
9、4,e4,v3S1=v6,e6,v5,e5,v4,e4,v3q定义定义9 9无向图无向图G中,连接中,连接kiivv 与0的一条链,当的一条链,当kiivv 与0是同一个点时,称此链为是同一个点时,称此链为圈圈(回路回路)。圈中既无重复点圈中既无重复点也无重复边者为也无重复边者为初等圈初等圈。S2=v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1S3=v1,e2,v2,e10,v4,e5,v5,e6,v6,e1,v1q定义定义1010一个图中任意两点间至少有一条链相连,则一个图中任意两点间至少有一条链相连,则称此图为称此图为连通图连通图。任何一个不连通图都可以分为若干任何一个
10、不连通图都可以分为若干个连通子图,每一个称为原图的一个个连通子图,每一个称为原图的一个分图分图。q定义定义1111网络网络(赋权赋权图图)G=(V,E),其边,其边vi,vj有权有权wij,构构造矩阵造矩阵A=(aij)nxn,其中:,其中:图的矩阵表示图的矩阵表示 其他0,Evvwajiijij称矩阵称矩阵A为网络为网络G的的权矩阵权矩阵。v1v2v3v4v5938672445 0650760844580320430974290Aq定义定义1212对于图对于图G=(V,E),|V|=n,构造矩阵,构造矩阵A=(aij)nxn,其中:其中:其他0,1Evvajiij称矩阵称矩阵A为图为图G的的
11、邻接矩阵邻接矩阵。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10q定义定义1212连通连通图图G中,若存在一条道路,中,若存在一条道路,经过每边一次且仅一次,则称这条路为经过每边一次且仅一次,则称这条路为欧拉道路欧拉道路。若存在一条回路,经过每边。若存在一条回路,经过每边一次且仅一次,则称这条回路为一次且仅一次,则称这条回路为欧拉回欧拉回路路。q具有欧拉回路的图称为具有欧拉回路的图称为欧拉图欧拉图(E(E图图)。欧拉回路与道路欧拉回路与道路图论中的欧拉定理图论中的欧拉定理q定理定理3 3无向连通图无向连通图G G是欧拉图,当且仅当是欧拉图,当且仅当G G中无奇点。中无奇点。
12、证明证明必要性:无向连通图必要性:无向连通图G G是欧拉图是欧拉图 G G中无奇点中无奇点 G是欧拉图,则存在一条回路,经由是欧拉图,则存在一条回路,经由G中所有的边,中所有的边,在这条回路上,顶点可能重复出现,但边不重复。在这条回路上,顶点可能重复出现,但边不重复。对于图中的任一顶点对于图中的任一顶点v v,只要在回路中出现一次,只要在回路中出现一次,必关联两条边,即这条回路沿一边进入该点,再沿另一必关联两条边,即这条回路沿一边进入该点,再沿另一边离开该点。边离开该点。所以所以v点虽然可在回路中重复出现,但点虽然可在回路中重复出现,但deg(v)必为必为偶数。偶数。充分性:充分性:G中无奇点
13、中无奇点 G是欧拉图是欧拉图G中无奇点,从任一点出发,如从中无奇点,从任一点出发,如从v1点出发,经关点出发,经关联边联边e1 “进入进入”v2,由于由于v2是偶点,则必可由是偶点,则必可由v2经关联经关联边进入另一点边进入另一点v3,如此继续,每边仅取一次。如此继续,每边仅取一次。由于由于G图中点数有限,则必可走回图中点数有限,则必可走回v1,得到一条回得到一条回路路c1。1)若回路若回路c1经过经过G G的所有边,则的所有边,则c1就是欧拉回路。就是欧拉回路。2)若否,从若否,从G中去掉中去掉c1后得到子图后得到子图G,则,则G中每个中每个顶点的次仍为偶数。顶点的次仍为偶数。因为图因为图G
14、 G是连通的,所以是连通的,所以c1与与G至少有一个顶点至少有一个顶点vi重合,在图重合,在图G中从中从vi出发,重复出发,重复c1的方法,得到回路的方法,得到回路c2。把把c1与与c2组合在一起,如果恰是图组合在一起,如果恰是图G,则得到欧拉则得到欧拉回路。回路。否则重复否则重复2)可得回路可得回路c3,如此继续如此继续由于图由于图G中边数有限,最终可得一条经过图中边数有限,最终可得一条经过图G所有所有边的回路,即欧拉回路。边的回路,即欧拉回路。欧拉定理充分性欧拉定理充分性(续续)q 推论推论1 1无向连通图无向连通图G G是欧拉图,当且仅当是欧拉图,当且仅当G G的边集可划的边集可划分为若
15、干个初等回路。分为若干个初等回路。q 推论推论2 2无向连通图无向连通图G G有欧拉道路,当且仅当有欧拉道路,当且仅当G G中恰有两中恰有两个奇点。个奇点。欧拉回路与道路欧拉回路与道路(续续)deg(A)=5,deg(B)=deg(C)=deg(D)=3欧拉回路与道路欧拉回路与道路(续续)q定理定理4 4连通有向图连通有向图G G是欧拉图,当且仅当它每是欧拉图,当且仅当它每个顶点的出次等于入次。个顶点的出次等于入次。q连通有向图连通有向图G有欧拉道路,当且仅当这个图中有欧拉道路,当且仅当这个图中除去两个顶点外,其余每个顶点的出次等于入除去两个顶点外,其余每个顶点的出次等于入次,且这两个顶点中,
16、一个顶点的入次比出次次,且这两个顶点中,一个顶点的入次比出次多多1,另一个顶点的入次比出次少,另一个顶点的入次比出次少1。q一个邮递员,负责某一地区的信件投递。他每天要从一个邮递员,负责某一地区的信件投递。他每天要从邮局出发,走遍该地区所有街道再返回邮局,问应如邮局出发,走遍该地区所有街道再返回邮局,问应如何安排送信的路线可使所走的总路程最短?何安排送信的路线可使所走的总路程最短?q图论语言描述:图论语言描述:q给定一个连通图给定一个连通图G,每边有非负权,每边有非负权l(e),试求一条回路过每,试求一条回路过每边至少一次,且满足总权最小。边至少一次,且满足总权最小。qG无奇点无奇点qG是欧拉
17、图是欧拉图qG有奇点有奇点q在连通图在连通图G=(V,E)中,求一个边集中,求一个边集E1 E,把,把G中属于中属于E1的边均的边均变为二重边得到图变为二重边得到图G*=G+E1,使其满足,使其满足G*无奇点,且无奇点,且中国邮递员问题中国邮递员问题(1962年,管梅谷年,管梅谷)最小。11EeelELq定理定理5 5已知图已知图G*=G+E1无奇点,则无奇点,则 奇偶点图上作业法奇偶点图上作业法 11EeelEL最小的充分必要条件为:最小的充分必要条件为:1)每条边最多重复一次;每条边最多重复一次;2)2)对图对图G中每个初等圈来讲,重复边的长度和不超过中每个初等圈来讲,重复边的长度和不超过
18、圈长的一半。圈长的一半。求解中国邮递员问题实例求解中国邮递员问题实例v1v2v3v4v5v6v7v8v9559624444433v1v2v3v4v5v6v7v8v9559624444433v1v2v3v4v5v6v7v8v9559624444433v1v2v3v4v5v6v7v8v9559624444433奇点两两配对奇点两两配对每对选一条路每对选一条路检查图中每个初等检查图中每个初等圈是否满足定理圈是否满足定理5的条件的条件2,调整圈,调整圈v1,v2,v5,v4,v1调整检查图中每调整检查图中每个初等圈是否满个初等圈是否满足定理足定理5的条件的条件2调整圈调整圈v2,v3,v6,v9,v8
19、,v5,v2q树是图论中结构最简单但又十分重要的图,在自然科树是图论中结构最简单但又十分重要的图,在自然科学和社会的许多领域都有广泛的应用。学和社会的许多领域都有广泛的应用。q举例:举例:q网球比赛抽签后,可用图表示相遇情况。网球比赛抽签后,可用图表示相遇情况。二、树二、树运动员AB CDEFGHIJKLMNq定义定义1414连通连通且不包含圈的无向图称为且不包含圈的无向图称为树树。树中次。树中次为为1的点称为的点称为树叶树叶,次大于,次大于1的点称为的点称为枝点枝点。q定理定理6图图T=(V,E),|V|=n,|E|=m,则下列关于树的说则下列关于树的说法是等价的。法是等价的。1)T是一个树
20、。是一个树。2)T无圈,且无圈,且m=n-1。3)T连通,且连通,且m=n-1。4)T无圈,但每加一新边即得唯一一个圈。无圈,但每加一新边即得唯一一个圈。5)T连通,但任舍去一边就不连通。连通,但任舍去一边就不连通。6)T中任意两点,有唯一链相连。中任意两点,有唯一链相连。树的概念和性质树的概念和性质q1)1)2)2)(T是一个树是一个树T无圈,且无圈,且m=n-1)由树的定义知,由树的定义知,T连通且无圈。往证:连通且无圈。往证:m=n-1。归纳法:当归纳法:当n=2时,显然时,显然m=1,即,即m=n-1。假设假设n=k-1命题成立,即有命题成立,即有k-1个顶点时,个顶点时,T有有k-2
21、条边。条边。当当n=k时,因为时,因为T连通且无圈,连通且无圈,k个顶点中至少有一个点个顶点中至少有一个点u,其次为,其次为1。不妨设不妨设(u,v)为悬挂边。为悬挂边。从从T中去掉中去掉(u,v),得到图,得到图T,T连通且无圈,为只有连通且无圈,为只有k-1个顶点的树,个顶点的树,从而有从而有k-2条边。条边。故故T有有k-1条边。条边。q2 2)3)3)(T无圈,且无圈,且m=n-1 T连通,且连通,且m=n-1)反证法。设反证法。设T不连通,可以分为不连通,可以分为s个连通分图个连通分图(s 2),设第,设第i个分图有个分图有ni个顶点,个顶点,ni=n。第第i个分图是树个分图是树(?
22、),所以有,所以有ni-1条边;条边;s个分图共有总边数为个分图共有总边数为 (ni 1)=n-sn-1,矛盾。,矛盾。树树若干定义的等价性证明若干定义的等价性证明q3)3)4)4)(T连通,且连通,且m=n-1 T无圈,但每加一新边即得唯一一个圈无圈,但每加一新边即得唯一一个圈)反证法。若反证法。若T中有圈中有圈C。可去掉。可去掉C的一边,并不影响的一边,并不影响T的连通性。的连通性。如果剩余图中仍有圈,可继续去掉该圈的一边如果剩余图中仍有圈,可继续去掉该圈的一边。如此继续去掉如此继续去掉k条边条边(k 1)后,得到一个无圈的连通图后,得到一个无圈的连通图T,T有有m-k条边。条边。无圈连通
23、图无圈连通图T是树是树,其顶点个数与,其顶点个数与T相同,所以相同,所以T有有n-1条边。条边。但由但由3),m-k=n-1-k n-1,矛盾。即,矛盾。即T无圈。无圈。加新边得唯一圈显然。加新边得唯一圈显然。q4 4)5)5)(T无圈,但每加一新边即得唯一一个圈无圈,但每加一新边即得唯一一个圈T连通,但任舍去连通,但任舍去一边就不连通一边就不连通)反证法。若反证法。若T不连通,由连通性的定义知,存在两点不连通,由连通性的定义知,存在两点u,v之间无路可通。之间无路可通。加上一条边也不会形成圈,与加上一条边也不会形成圈,与4)矛盾。矛盾。再证:每舍一边便不连通。再证:每舍一边便不连通。若若T中
24、有一边中有一边(u,v),其舍去后图,其舍去后图T-(u,v)仍然连通,则仍然连通,则T=T-(u,v)是树,是树,但但T加一边加一边(u,v)后得后得T仍无圈,与仍无圈,与4)矛盾。矛盾。q5 5)6)6),6 6)1)1)显然显然树树若干定义的等价性证明若干定义的等价性证明(续续)q定义定义1515若若图图G的生成子图是一棵的生成子图是一棵树树,则称该树为,则称该树为G的生成树的生成树(支撑树支撑树)。图。图G的树。的树。图的生成树图的生成树q定理定理7 7图图G=(V,E)有生成树的充分必要条件为有生成树的充分必要条件为G是是连通图。连通图。q寻找连通图的生成树:每步选出一条边使它与已选
展开阅读全文