图的基本概念

单击此处编辑母版标题样式,下,回,停,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版标题样式,2024年9月21日,图与网络方法,(,Methods of Graphs and network,),数学建模培训,-,图论部分,Who am I?,姓名,:,王艳宁,E-mail:,Phone,：,Office,：理学楼,310,性别： 男,1.,图论的基本概念,1),图的概念,2),赋权图与子图,3),图的矩阵表示,4),图的顶点度,5),路和连通,1),图的概念,定义,一个,图,G,是指一个二元组,(V(G),E(G),，其中,:,其中元素称为图,G,的,顶点（节点）,.,组成的集合，即称为,边集,其中元素称为,边,.,定义,图,G,的,阶,是指图的顶点数,|,V(G)|,用,来表示；,图的边的数目,|,E(G)|,用,来表示,.,也用,来表示边,是非空有限集，称为,顶,点集,，,1),2),E(G,),是顶点集,V(G),中的无序或有序的元素偶对,表示图，,简记,用,定义,若一个图的顶点集和边集都是有限集，则称,其为,有限图,.,只有一个顶点的图称为,平凡图,，其他的,所有图都称为,非平凡图,.,双语 ：,Graph Vertex Edge,定义,若,图,G,中的边均为有序偶对,称,G,为,有向,边 为,无向边,，称,e,连接,和 ，顶点 和 称,图,.,称边,为,有向边,或,弧,称,是从,连接,，称 为,e,的,尾,，称 为,e,的,头,.,若图,G,中的边均为无序偶对 ，称,G,为,无向图,.,称,为,e,的,端点,.,既有无向边又有有向边的图称为,混合图,.,常用术语,1),边和它的两端点称为互相,关联（,Incident,）,.,2),与同一条边关联的两个顶点称为,相邻（,adjacent,）,的顶点，,与同一个顶点,点关联的两条边称为,相邻,的边,.,3),端点重合为一点的边称为,环,(loop),，,端点不相同的边称为,连杆,(link),.,4),若一对顶点之间有两条以上的边联结，则这些边,称为,重边,5),既没有环也没有重边的图，称为,简单图,常用术语,6),任意两顶点都相邻的简单图,称为完全图,.,记为,K,v.,7),若 ，,，,且,X,中任意两顶点不,，,相邻，,Y,中任意两顶点不相邻，则称为,二部图,或,偶图,；若,X,中每一顶点皆与,Y,中一切顶点相邻,称为,完全二部图,或,完全偶图,记为,(,m=|X|,n=|Y|,),8),图 叫做,星,.,二部图,2),赋权图,定义 若图 的每一条边,e,都赋以,一个实数,w(e),，称,w(e),为边,e,的,权,，,G,连同边上的权,称为,赋权图,.,相应的图为,赋权无向图,或,赋权有向图,。,2),子图,定义,设 和 是两个图,.,1),若,称 是 的一个,子图,记,2),若 ， ，则称 是 的,生成子图,.,都是,G,的子图，,都不是,G,的生成子图,3),若 ，且 ，以 为顶点集，以两端点,均在 中的边的全体为边集的图 的子图，称,4),若 ，且 ，以 为边集，以 的端点,集为顶点集的图 的子图，称为 的,由 导出的,边导出的子图,，记为,.,为 的,由 导出的子图,，记为,.,3),图的矩阵表示,邻接矩阵,:,1),对无向图 ，其邻接矩阵 ，其中：,(,以下均假设图为简单图,).,Adjacent Matrix,2),对有向图,其邻接矩阵,其中：,其中：,3),对有向赋权图,其邻接矩阵,对于无向赋权图的邻接矩阵可类似定义,.,有时定义为：,对有向赋权图,其邻接矩阵,在使用别人的代码时，注意其 定义,3),图的矩阵表示,邻接数组 三元组,1),对无向图 ，其邻接矩阵 ，其中：,关联矩阵,1),对无向图 ，其关联矩阵,其中：,2),对有向图 ，其关联矩阵,其中：,4),图的顶点度,定义,1),在无向图,G,中，与顶点,v,关联的边的数目,(,环,算两次,),称为顶点,v,的,度,或,次数,，记为,d(v),或,d,G,(v,).,称度为奇数的顶点为,奇点,，度为偶数的顶点为,偶点,.,2),在有向图中，从顶点,v,引出的边的数目称为顶点,v,的,出度,，记为,d,+,(v),，从顶点,v,引入的边的数目称为,v,的,入度,，记为,d,-,(v),.,称,d(v)= d,+,(v)+d,-,(v),为顶点,v,的,度,或,次数,定理,的个数为偶数,推论,任何图中奇点,A,B,C,D,哥尼斯堡七桥示意图,哥尼斯堡七桥,(,Knigsberg Bridges,),问题,在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来,.,问题是,:,要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。,欧,拉,(Euler),解决了这个问题,！,将问题用图表示,四快被分开的区域作为点,连结它们的桥作为边,原来是一笔画问题！,图论起源,图论（,Graph Theory,）起源于,18,世纪。第一篇图论论文是瑞士数学家欧拉于,1736,年发表的,“,哥尼斯堡的七座桥,”,。,1847,年，克希霍夫为了给出电网络方程而引进了,“,树,”,的概念。,1857,年，凯莱在计数烷的同分异构物时，也发现了,“,树,”,。哈密尔顿于,1859,年提出,“,周游世界,”,游戏，用图论的术语，就是如何找出一个连通图中的生成圈。,近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。,图论中所谓的,“,图,”,(Graph),是指某类具体事物和这些事物之间的联系。,如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定联系，就得到了描述这个,“,图,”,的几何形象。,图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。,田,一笔画？,5),路和连通,定义,1),无向图,G,的一条,途径,（或,通道,或,链,）是指,一个有限非空序列 ，它的项交替,地为顶点和边，使得对 ， 的端点是 和,称,W,是从 到 的一条,途径,，或一条,途径,.,整,数,k,称为,W,的,长,.,顶点 和 分别称为的,起点,和,终点,而 称为,W,的,内部顶点,.,2),若途径,W,的边互不相同但顶点可重复，则称,W,为,迹,或,简单链,.,3),若途径,W,的顶点和边均互不相同，则称,W,为,路,或,路径,.,一条起点为,终点为 的路称为,路,记为,Walk,Trail,Path,定义,1),途径 中由相继项构成子序列,称为途径,W,的,节,.,2),起点与终点重合的途径称为,闭途径,.,3),起点与终点重合的的路称为,圈,(,或,回路,),，长,为,k,的圈称为,k,阶圈,，记为,C,k,.,4),若在图,G,中存在,(,u,v,),路，则称顶点,u,和,v,在图,G,中,连通,.,5),若在图,G,中顶点,u,和,v,是连通的，则顶点,u,和,v,之,之间的,距离,d,(,u,v,),是指图,G,中最短,(,u,v,),路的长；若没,没有路连接,u,和,v,，则定义为无穷大,.,6),图,G,中任意两点皆连通的图称为,连通图,7),对于有向图,G,，若 ，且 有,类似地，可定义,有向迹,，,有向路,和,有向圈,.,头 和尾 ，则称,W,为,有向途径,.,例,在右图中：,途径或链：,迹或简单链：,路或路径：,圈或回路：,例,一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东,.,由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处,.,给出渡河方法,.,解,：用四维,0-1,向量表示,(,人,狼,羊,菜,),在河西岸的状态,(,在河西岸则分量取,1,否则取,0),共有,2,4,=16,种状态,.,在河东岸的状态类似记作,.,由题设,状态,(0,1,1,0),(0,0,1,1),(0,1,1,1),是不允许的,从而对应状态,(1,0,0,1), (1,1,0,0), (1,0,0,0),也是不允许的,.,以可,允许的,10,个,状态,向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图,.,根据此图便可找到,渡河方法,.,(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0),(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,1,0,0),(0,1,0,1),(0,1,0,1),(0,1,0,0),(0,0,1,0),(0,0,0,1),(0,0,0,0),(1,0,1,0),(1,0,1,1),(1,1,0,1),(1,1,1,0),(1,1,1,1),河西,=(,人,狼,羊,菜,),河东,=(,人,狼,羊,菜,),将,10,个顶点分别记为,A,1,A,2, ,A,10,则,渡河问题化为在该图中求一条从,A,1,到,A,10,的,路,.,从图中易得到两条,路,：,A,1,A,6,A,3,A,7,A,2,A,8,A,5,A,10,;,A,1,A,6,A,3,A,9,A,4,A,8,A,5,A,10,.,3,最短路问题及算法,最短路问题是图论应用的基本问题，很多实际,问题，如线路的布设、运输安排、运输网络最小费,用流等问题,都可通过建立最短路问题模型来求解,.,最短路的定义,最短路问题的两种方法：,Dijkstra,和,Floyd,算法,.,1),求赋权图中从给定点到其余顶点的最短路,.,2),求赋权图中任意两点间的最短路,.,2),在赋权图,G,中，从顶点,u,到顶点,v,的具有最小权,定义,1),若,H,是赋权图,G,的一个子图，则称,H,的各,边的权和 为,H,的,权,.,类似地，若,称为路,P,的,权,若,P,(,u,v,),是赋权图,G,中从,u,到,v,的路,称,的路,P*,(,u,v,),，称为,u,到,v,的,最短路,3),把赋权图,G,中一条路的权称为它的,长,，把,(,u,v,),路的最小权称为,u,和,v,之间的,距离,，并记作,d,(,u,v,).,1),赋权图中从给定点到其余顶点的最短路,假设,G,为赋权有向图或无向图，,G,边上的权均非,负若 ，则规定,最短路是一条路，且最短路的任一节也是最短路,求下面赋权图中顶点,u,0,到其余顶点的最短路,Dijkstra,算法：,求,G,中从顶点,u,0,到其余顶点的最短路,设,G,为赋权有向图或无向图，,G,边上的权均均非负,.,对每个顶点，定义两个标记（,l(v),，,z(v),），其中,:,l(v),：,表从顶点,u,0,到,v,的一条路的权,z(v),：,v,的先驱点，用以确定最短路的路线,.,l(v),为从顶点,u,0,到,v,的最短路的权,算法的过程就是在每一步改进这两个标记，使最终,S,：具有永久标号的顶点集,.,输入,:,G,的带权邻接矩阵,w(u,v),Dijkstra,算法,算法步骤：,l(v),u,0,v,l(u),u,w(u,v),首先写出带权邻接矩阵,例 求下图从顶点,u,0,到其余顶点的最短路,因,G,是无向图，故,W,是对称阵,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,Dijkstra,算法,:,求,G,中从顶点,u,0,到其余顶点的最短路,.,1),置 ，对 ， ， 且,.,2),对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3),若 ，则停止；若 ，则用,i+1,代,替,i,，并转,2),.,定义,根据顶点,v,的标号,l(v),的取值途径，使 到,v,的最短路中与,v,相邻的前一个顶点,w,，称为,v,的,先驱,点,，记为,z,(,v,),即,z,(,v,)=,w,.,先驱点可用于追踪最短路径,.,例,5,的标号过程也,可按如下方式进行：,首先写出左图带权邻接矩阵,因,G,是无向图，故,W,是对称阵,结构程序设计之父,第 七位图 灵 奖,(1972,年,),获 得 者 。,E. W. Dijkstra 1930,年,5,月,11,日出身于,the Netherlands(,荷兰,)Rotterdam.,去世于,2002,年,8,月,6,日于,Nuenen, the Netherlands.,年轻时代，,Dijkstra,在,University of Leiden, the Netherlands. Leiden,大学是荷兰最古老的大学。,学习理论物理，但很快他就意识到其兴趣不,在于理论物理虽然获得了其数学和理论物理,的学位。后来，,Dijkstra,获得了其博士学位从,University of Amsterdam.,1952,年,-1962,年，,E. W. Dijkstra,是,Materematisch Centrum, Amsterdam,的一,个程序员。,1962,年,-1984,年，作为一个数学教授任职于,Eindhoven Unviersity of Technology.,1984,年至,1999,年，作为计算机系系主任任职与美国,UT Austin,分校，并于,1999,年退休。,2002,年,8,月,6,日在荷兰,Nuenen,自己的家中与世长辞,Dijkstra,最短路径算法被广泛的应用在网络协议方面，如,OSPF,。,Edsger Dijkstra,是,1950,年代,ALGOL,语言的一个主要贡献者。,ALGOL,高级编程语言已经成为结构清晰，数学基 础严谨的一个典范。,E. W. Dijkstra,是现代编程语言的主要贡献者之一，为我们理解程序语言的结构，表示方法与实现做出了巨大的贡献。,E. W. Dijkstra 15,年的学术著作覆盖了图论的理论工作，教育手册，解释文章和编程语言领域的哲学思考。,2),求赋权图中任意两顶点间的最短路,算法的基本思想,（,I,）求距离矩阵的方法,.,（,II,）求路径矩阵的方法,.,（,III,）查找最短路路径的方法,.,Floyd,算法：求任意两顶点间的最短路,.,举例说明,算法的基本思想,（,I,）求距离矩阵的方法,.,（,II,）求路径矩阵的方法,.,在建立距离矩阵的同时可建立路径矩阵,R,（,III,）查找最短路路径的方法,.,然后用同样的方法再分头查找若：,（,IV,）,Floyd,算法：求任意两顶点间的最短路,.,例,求下图中加权图的任意两点间的距离与路径,.,插入点,v,1,，,得：,矩阵中带“,=,”,的项为经迭代比较以后有变化的元素,.,插入点,v,2,，,得：,矩阵中带“,=,”,的项为经迭代比较以后有变化的元素,.,插入点,v,3,，,得：,插入点,v,4,，,得：,插入点,v,5,，,得：,插入点,v,6,，,得：,故从,v,5,到,v,2,的最短路为,8,由,v,6,向,v,5,追溯,:,由,v,6,向,v,2,追溯,:,所以从到的最短路径为：,见,Matlab,程序,-,Floyd.doc,