图的概念Introduction-of-Graph-图的术语Graph.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 概念 Introduction of Graph 术语
- 资源描述:
-
,单击此处编辑母版标题样式,*,*,Graphs/图论,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.1 图的概念/Introduction of Graph,7.2 图的术语/Graph Terminology,7.3 图的表示与同构/,Representing Graph and Graph Isomorphism,7.4 连通性/Connectivity,7.5 欧拉道路与哈密尔顿道路/,Euler and Hamilton Paths,7.6 最短道路问题/Shortest Path Problem,7.7 平面图/Planar Graphs,7.8 图的着色/Graph Coloring,10/1/2026,1,7.4 连通性/Connectivity,定义道路/path:,当中相邻边的序列(,0,,,1,),(,1,,,2,),(,k-1,,,k,),称为一条,道路(通路),。此道路的长度为。也可以以(,0,,,1,,,k,)表示道路,,0,为起点,,k,为终点。,当,0,=,k,时,该道路称为,回路/circuit,。,10/1/2026,2,定义简单道路/Simple Path:,一条道路中没有两条边是相同的,称此道路为,简单道路,。当其是回路时,称为,简单回路,/Simple Circuit。,定义基本道路/Element Path:,一条道路中,除了起点和终点可以相同,没有其他相同顶点出现,称此道路为,基本道路,。当其是回路时,称为,基本回路,/Element Circuit。,10/1/2026,3,(,5,,,1,,,2,,,3,,,4,)是简单道路,不是基本道路,因为(,)中,均出现了两次。但(c,d,b,c)是基本道路。,10/1/2026,4,定义,连通性/connectivity:,设(,),(,0,,,1,,,k,)是G中的一条道路,则称,0,到,k,连通,/connective或,可达,/。,说明:对无向图而言,若,0,到,k,可达,则,k,到,0,也可达。对有向图而言则未必。,10/1/2026,5,定理1,任意一个连通无向图的,任两个不同顶点都存在一条简单道路。,定义,无向图的连通性:,若(,)中任两个不同顶点都连通,则称此无向图是,连通的/connected,。,10/1/2026,6,定义连通分图/connected components:,图可分为几个不相连通的子图,每一子图本身都是连通的。称这几个子图为的连通分图。,定义,无向图的连通性:,若(,)中任两个顶点都连通,则称此无向图是,连通的/connected,。,10/1/2026,7,定义有向图的连通性:,(1)弱连通:,若(,)对应的无向图是连通图,则称为,弱连通/weakly connected,。,(2)强连通:,若(,)中任两点间都有路,即对与,到可达,到可达,称为,强连通/strongly connected,。,10/1/2026,8,10/1/2026,9,10/1/2026,10,例:用图描述一台自动售货机,只用分,分二种硬币,满分后压按钮,选择一块巧克力,钱多了不找还。,10/1/2026,11,顶点:分边:投分,:分 :投分,:分 :压按扭动作,:分,表示已投入钱的状态 表示一种动作,自动售货机:有向加权图描绘得很清楚,(1)钱数不够,压按扭,不起作用,(2)钱数够了,压按扭,给过糖果回到分状态,(3)钱超过分,再加钱白加,10/1/2026,12,用邻接矩阵讨论图的连通性质:,在邻接矩阵中,若,ij,,表明,i,到,j,有一条边,即,i,到,j,可达;若,ij,不说明,i,到,j,没有道路,若通过其他点中转,也有可能连通。作邻接矩阵的普通矩阵乘法:,10/1/2026,13,ij,的值表示,i,到,j,路长为的道路条数,一般地,就有:,定理2,m,的元素,ij,表示,i,到,j,长度为的道路条数。,10/1/2026,14,定理3:,个顶点的图中,如果,i,到,j,(,i,j,)有道路,则其最短的道路长度。,定理4:个顶点的图中,A是G的,邻接矩阵。,i,、,j,是G的顶点,,B=A+A,2,+A,n-1,则,i,到,j,(,i,j,)连通当且仅当b,ij,非零。,10/1/2026,15,定义:个顶点的图中,A是G的,邻接矩阵。,B=A+A,2,+A,n-1,+A,n,称为G的可达性矩阵。,有向图的连通性(n,1,):,()B中元素全为,强连通,(2),T,的可达性矩阵元素全为,是弱连通的。,无向图的连通性(n,1,):,B中元素全为,连通,10/1/2026,16,7.5 Euler and Hamilton Path,Konigsberg(哥尼斯堡)七桥问题,问题:能否从河岸或小岛出发,通过每一座桥,而且仅仅通过一次回到原地。,10/1/2026,17,Euler(欧拉)1736年对这个问题,给出了否定的回答。将河岸和小岛作为图的顶点,七座桥为边,构成一个无向重图,问题化为图论中简单道路的问题:,定义,欧拉道路(回路):,(,),称包含中所有边的简单道路为,欧拉道路/Euler Path/E道路,。,包含中所有边的简单回路为,欧拉回路/Euler Circuit/E回路,。,10/1/2026,18,定理1(欧拉定理):,没有次为的孤立顶点的无向图存在欧拉道路的充要条件是:,(1)图是连通的;,(2)图中奇次顶点个数是个或2个。,10/1/2026,19,证明:,必要性:,若存在欧拉道路,且没有次顶点,则每个顶点都有边关联,而边又全在欧拉道路上,故所有顶点都连通。,除了起点,终点外,欧拉道路每经过一个顶点,使顶点的次增加,故只有起点和终点才可能成为奇次顶点,而一个奇次顶点是不可能的,当无奇次顶点时,是欧拉回路。,充分性:,若(1),(2)成立,构造欧拉道路.,10/1/2026,20,若图存在奇次顶点,任取一个作为起点,若不存在,则任取一个顶点作为起点。,若此图有条边,总次为。每进入或离开一个顶点,让此顶点的次减,由于除了两个(或没有)奇次顶点外,其余顶点次为偶数,只要进得去,一定出得来,直至进入另一个奇次顶点(或起点)作为终点。,这样构造的是简单道路,如果经过所有的边,即得到一条欧拉道路。,不然,记走过的简单道路为,1,,,1,上顶点集,1,,边集,1,,,1,(,1,,,1,)是的子图。,10/1/2026,21,若,2,(,2,,,2,)是,1,的关于的余图,,2,1,,但,1,2,,否则不连通,设,1,2,,从出发,用上面方法作,2,的简单回路,2,回到,这能做到。,因为作好,1,后,留下顶点的次都是偶次。若,1,2,经过所有边,则欧拉道路是,1,走到时,先把,2,走完,最后走完,1,的余下道路。,若,1,2,仍未经过所有边,将,1,2,视为,1,重复上述过程,由于边有限,故存在欧拉道路。,10/1/2026,22,例1:,(1)顶点的次:A(3),B(2),C(4),D(2),E(6),F(2),G(6),H(2),I(4),J(3)。其中奇次顶点A,J,(2)从A出发,走一条道路,(A,C,E,A,B,C,D,E,G,J),10/1/2026,23,(3),1,(,1,,,1,),1,A,B,C,D,E,G,J,1,(A,B),(B,C),(A,C),(C,D),(C,E),(D,E),(E,G),(G,J),2,(,2,,,2,),2,(E,F),(F,G),(E,J),,(G,H),(G,I),(I,J),(H,I),2,E,F,G,H,I,J,E(,1,2,),10/1/2026,24,(4)从E出发回到E的回路(E,F,G,I,J,E),加入到P,1,中,1,(A,C,E,F,G,I,J,E,A,B,C,D,G,J),(5)还有未经过的边,重复上述过程,从G出发,(G,H,I,G),再加入即得欧拉道路。,10/1/2026,25,说明:,哥尼斯堡七桥问题,由于四个顶点都是齐次的,不可能有欧拉道路。,应用与推广:,(1)一笔画问题;,(2)如果齐次顶点个数为2K个,此问题是K笔画问题。,10/1/2026,26,例,个顶点均为3次,至少要笔。,定理2(有向图的欧拉定理):,不含次为的孤立顶点的有向图具有欧拉道路的充要条件是:,(1)弱连通;,(2)除了可能有个顶点,一个入次比出次大,一个出次比入次大,其余顶点出次等于入次。,10/1/2026,27,除了起点,终点外,欧拉道路每经过一个顶点,使顶点的次增加,故只有起点和终点才可能成为奇次顶点,而一个奇次顶点是不可能的,当无奇次顶点时,是欧拉回路。,解:取A1,A2,个顶点均为3次,至少要笔。,1、一定连通,否则分为二个不连通的分图1,2,其中1有1个顶点,2有2个顶点,1中每个顶点次1,2中每个顶点次2,从1中取一个顶点,2中取一个顶点,这一对顶点之和1212,与定理的假设矛盾。,自动售货机:有向加权图描绘得很清楚,哥尼斯堡七桥问题,由于四个顶点都是齐次的,不可能有欧拉道路。,任意一个连通无向图的任两个不同顶点都存在一条简单道路。,哥尼斯堡七桥问题,由于四个顶点都是齐次的,不可能有欧拉道路。,将河岸和小岛作为图的顶点,七座桥为边,构成一个无向重图,问题化为图论中简单道路的问题:,中国邮递员问题,(,欧拉道路的应用)(加权图),问题:,邮递员从邮局出发,走遍投递区域的所有街道,送完邮件后回到邮局,怎样使所走的路线全程最短.,若街道图(街道的交叉口为顶点)存在欧拉道路,显然此路是全程最短.,10/1/2026,28,Hamilton(哈密顿)道路问题:,年发明的一种游戏。,在一个实心的正十二面体,20个顶点标上世界著名大城市的名字,要求游戏者从某一城市出发,遍历各城市一次,最后回到原地。,这就是“绕行世界”问题。即,找一条经过所有顶点(城市)的基本道路(回路)。,10/1/2026,29,定义哈密顿道路/回路:,(,),G中经过中所有顶点的基本道路称为,哈密顿道路/Hamilton Path,,简称,道路,。,(,),G中经过中所有顶点的基本回路称为,哈密顿回路/Hamilton Circuit,,简称,回路,。,10/1/2026,30,图 每个顶点都是奇次的,不存在欧拉道路,但有道路。图存在欧拉道路,不存在道路。,10/1/2026,31,定理3:设(,)是个顶点的简单图,如果任何一对顶点的次之和,则中一定有道路。,证明:,1、一定连通,否则分为二个不连通的分图,1,,,2,,其中,1,有,1,个顶点,,2,有,2,个顶点,,1,中每个顶点次,1,,,2,中每个顶点次,2,,从,1,中取一个顶点,,2,中取一个顶点,这一对顶点之和,1,2,1,2,,与定理的假设矛盾。,10/1/2026,32,2、用逐步递推构造法证明中存在道路:,(1)任取一条边(,1,,,2,),是含个顶,点的基本道路。,(2)如果已有个顶点的基本道路,(,1,,,2,,,p,),(),必能构造个顶点的基本道路。,)如果在,1,,,2,,,p,中存在与,1,或,p,相邻的顶点,则基本道路自然可以扩充一个顶点。,)如果,1,,,p,仅与,1,,,2,,,p,中顶点相邻,则,1,,,2,,,p,必可适当排列,形成回路。,10/1/2026,33,如果,1,与,p,相邻,显然成了环。不然,由于,1,,,p,仅与,1,,,2,,,p,中顶点相邻,,1,,,p,的次。不妨设,1,的次为,分别记相邻顶点为,i,1,,,i,2,,,i,k,,它们前面的顶点(指在基本道路,1,,,2,,,p,中的序)为 ,,p,必与,中某顶点相邻,否则,p,的次,,1,与,p,的次之和,与任一对顶点次之和矛盾。,不妨,p,与,j-1,相邻,,1,与,j,相邻。将,1,与,j,连起来,,p,与,j-1,连起来,并将,j-1,到,j,的边去掉,就形成一个环,如下图所示。,10/1/2026,34,又由的连通性,总可在,1,,,2,,,p,中找到一个点,x,,与,1,,,2,,,p,中某一顶相邻,不妨与,k,相邻,,k,1,,,k,p,,连上,x,与,k,的边,去掉,k-1,到,k,的边,可以从,k-1,为起点,一直走到,k,,再到,x,,这是一条个顶点的基本道路。,10/1/2026,35,如果,仍继续扩充基本道路内的顶点,直至达到。,注意:,此定理条件显然不是必要条件,如的边形,二个顶点次之和,,,而边形显然有道路。,定理4:,(,)是的简单图,若任何一对顶点的次之和,则必有哈密顿回路。,10/1/2026,36,由于定理4条件也必满足定理3条件,存在道路,可类似于定理一的方法找到一条回路。,定理5:,有向完全图一定存在道路。,10/1/2026,37,小 结,1、图中顶点的连通性/可达性,2、图的连通性,有向图、无向图,3、E图:简单道路+所有边,4、H图:基本道路+所有顶点,10/1/2026,38,进一步的思考,1、,图的连通性的计算机表示与实现,2、E图/H图的应用,3、E图/H图的判定,10/1/2026,39,要判别一个图不存在道路,回路,也不是很容易的,只能对无向图给出一些必要条件:,(1)道路存在必要条件:,)连通,)至多只能有二个顶点的次,其余顶点的次。,b,c,d,a,10/1/2026,40,(2)回路存在必要条件:,对的任一非空真子集,的连通分图个数|。,10/1/2026,41,解:取A,1,,A,2,10/1/2026,42,G存在3个分图,根据H道路存在的必要条件之二,可知:H道路不存在。,10/1/2026,43,应用问题之一:,Knights tour,应用问题之二:,Gray Code,应用问题之三:,Tower of Hanoi,10/1/2026,44,练 习,pp.473 1、2、12、31,pp.486 36、37、65,10/1/2026,45,(2)回路存在必要条件:,所有a到b的道路中长度最短的一条。,一条道路中,除了起点和终点可以相同,没有其他相同顶点出现,称此道路为基本道路。,若(,)对应的无向图是连通图,则称为弱连通/weakly connected。,定义无向图的连通性:,定理3:设(,)是个顶点的简单图,如果任何一对顶点的次之和,则中一定有道路。,若存在欧拉道路,且没有次顶点,则每个顶点都有边关联,而边又全在欧拉道路上,故所有顶点都连通。,Euler(欧拉)1736年对这个问题,给出了否定的回答。,称这几个子图为的连通分图。,1(A,B),(B,C),(A,C),(C,D),(C,E),(D,E),(E,G),(G,J),当0=k时,该道路称为回路/circuit。,6 最短道路问题/Shortest Path Problem,(2)回路存在必要条件:,(,),称包含中所有边的简单道路为欧拉道路/Euler Path/E道路。,7.6 最短道路问题,Shortest Path Problem,加权图/Weighted graph,G=(V,E,f),f:E,R,+,G满足简单连通无向,10/1/2026,46,Example:,Weighted Graphs Modeling,an Airline System,For SF,LS,DL,DV,CG,BT,NY Cities:,Mileage,Flight Times,Fares,10/1/2026,47,Example:,Weighted Graphs Modeling,a Computer Network,For SF,LS,DL,DV,CG,BT,NY Cities:,Distance,Response Time,Lease Rate(per month),10/1/2026,48,a到b的道路及其长度,:,道路中所有边的函数值之和。,a到b的,最短道路/shortest path:,所有a到b的道路中长度最短的一条。,10/1/2026,49,a到b的道路及其长度,:,道路中所有边的函数值之和。,求G中任意两个顶点a到b的,最短道路的方法:,Dijkstras 算法,10/1/2026,50,应用问题:,旅行商问题(TSP),Traveling Salesman Problem,问题:从某地出发,恰好一次经过个城市回到,原地,寻找最短的道路。,实质:无向简单加权图,寻找最短回路的问题。,说明:,(1)不一定存在,若无向图是完全图则存在。,(2)图是,连通的,两个城市间总有路,若以两城市间交通费用作为边的权,则是无向图的H回路问题.,10/1/2026,51,无向加权完全图的,最近邻域算法/Approximation,:,从任一顶点出发,记为,1,,找一个与,1,最近的顶点,2,,(,1,,,2,)为两个顶点的基本道路。,若找出有个顶点的基本道路,(,1,,,2,,,p,),在道路外找一个离,p,最近的顶点,记为,p+1,,将其加入则得到具有P+1个顶点的基本道路。,若,转,否则转。,闭合回路:即增加一条边(,n,,,1,),,则(,1,,,2,,,n,,,1,)为一条近似的最短回路。,10/1/2026,52,说明:,(1)找最近一个顶点不唯一时,按序取。,(2)不一定是最短回路.,例:,下,图是加权无向完全图,从a点出发,用最近邻域法求最短回路,并与实际的最短H回路做比较。,10/1/2026,53,最近邻域法所求为:(,),总长为,最短回路:(,),总长为。,10/1/2026,54,(2)以关联e,i,的两个顶点v,1,v,2,分别作为起点,用最近邻域法求最短H回路。,(3)再比较这两条回路的长度,以确定最短的一条。,如上例:,(,)边长为,最短。,以为起点:(,),总长为,以作起点:(,),总长为,改进:,(1)找一条最短的边e,i,。,10/1/2026,55,设(,)是个顶点的完全无向图,满足三角不等式(,)(,)(,),,0,是最短回路,0,的长度,是最近邻域法得到的回路的长度,则:,10/1/2026,56,练 习,pp.499 17,26,10/1/2026,57,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


图的概念Introduction-of-Graph-图的术语Graph.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14503010.html