M05-1-图的模型和基本概念

*,/,28,*,第,5,章 图论模型及应用,Graph theory and its application,行 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,三、建模案例：最佳灾情巡视路线,2.1,哈 密 尔 顿 图,2.2,推 销 员 问 题,1.1,单源问题,1.2,每对顶点之间的最短路,哥尼斯堡“七桥问题”,给出了“一笔画”成立的一个等价判别条件：,欧拉,图中任意两点是连通的,每个点都与偶数条边相连,1,图的模型,一、概 论,1998,年全国大学生 数学模型竞赛,B,题,最佳灾情巡视路线,：,乡镇、村的公路网示意图,某县组织三路人从县政府所在地出发巡视全县各受灾乡（镇）、村，又回到县政府，设计总路程最短且各组尽可能均衡的路线,一、概 论,返回,2,图的基本概念,定义,图,G,是一个有序二元组,(,V,E,),，,其中,V=,v,1,，,v,2,，,，,v,n,是一个有限非空的集合。,一、概 论,V,中的元素称为,G,的,结点,V,称为图,G,的,结点集,常记作,V,(,G,);,E,是,V,中某些顶点的偶对的集合,E,中的元素称为,G,的,边,，,E,称为图,G,的,边集,常记作,E,(,G,).,在图,G,中，与,V,中顶点的有序偶对,(,vi,vj,),对应的边,e,称为图的,有向边,(,或,弧,),而与,V,中顶点的无序偶对,(,vi,vj,),对应的边,e,称为图的,无向边,。每一条边都是无向边的图,称为,无向图,;,每一条边都是有向边的图,称为,有向图,;,既有无向边又有有向边的图称为,混合图,。,一、概 论,图,G,中,如果任意两个不同的顶点都是相邻的,则称图,G,是,完全图,。,一、概 论,如果,则称图,H,为图,G,的,子图,，,记作,。特别的，如果 ，,则称图,H,为图,G,的,生成子图。,在无向图,G,中，若边,e,=(,vi,，,vj,)，,则称,vi,、,vj,为边,e,的,端点,，并称顶点,vi,与,vj,相邻,，,称边,e,与顶点,vi,、,vj,关联,；如果某,两条边至少有一个公共端点，则称这两条边在图,G,中,相邻,。,在有向图,G,中，若,e,=(,vi,，,vj,),，即箭头由,vi,指向,vj,，则称,vi,相邻到,vj,，,vi,称为,e,的,起点,，,vj,称为,e,的,终点,。,在无向图,G,中，与顶点,v,关联的边的数目称为,v,的,次数,，,记为,d,(,v,),。,例题,一、概 论,在有向图,G,中，从顶点,v,引出的弧的数目称为,v,的,出度,，,记为,d,+,(,v,),；从顶点,v,引入的弧的数目称为,v,的,入度,记为,d,-,(,v,),；,d,(,v,)=,d,+,(,v,)+,d,-,(,v,),称为,v,的,次数,。,点边交替序列,l,=,v,0,e,1,v,1,e,2,e,k,v,k,，,其中,v,j,V,（,G,），,0,j,k,，,e,i,E,（,G,），,0,i,k,，,e,i,与,v,i-,1,v,i,关联，称,l,是图,G,的一条,路径,，,k,为,路长,，顶点,v,0,和,v,k,分别称为,l,的,起点,和,终点,，而,v,1,v,2,v,k-,1,称为它的,内部顶点,。,若路径,l,的边不重复，则称,l,为,简单路径,（,或,迹,）；,若图,G,的两个顶点,u,、,v,间存在路径，则称,u,和,v,连通,。若图,G,的任两个顶点均连通，则称,G,为,连通图,。连通而无圈的图称为,树,。如果图,G,的生成子图,H,是树，则称,H,为图,G,的,生成树,。,例题,一、概 论,若路径,l,的顶点不重复，则称,l,为,基本路径,（,或,链,）。,起点和终点重合的路径称为,回路,；,起点和终点重合的简单路径称为,简单回路,；,起点和终点重合的基本路径称为,基本回路,（或,圈,）。,若将图,G,的每一条边,e,都对应一个实数,w,(,e,),，称,w,(,e,),为边,e,的,权,，并称图,G,为,赋权图,。,赋权图,G,中从顶点,u,到顶点,v,的一条路径上所有边的权之和,称为该路径的,权,，记作,d,(,u,v,).,赋权图,G,中从顶点,u,到顶点,v,的具有最小权的路径，称为,u,到,v,的,最短路,。,一、概 论,返回,例,图,G,如右图所示，是一个有向图,顶点集,V,v,1,v,2,v,3,v,4,v,5,边集,E,=,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,点,v,2,的出度,d,+,(,v,2,)=1,，入度,d,-,(,v,2,)=2,度,d,(,v,2,)=3,v,1,e,1,v,2,e,2,v,3,e,3,v,4,e,4,v,2,e,2,v,3,e,7,v,5,e,6,v,4,e,5,v,1,是一条回路，不是简单回路,v,1,e,1,v,2,e,2,v,3,e,7,v,5,e,8,v,3,e,3,v,4,e,5,v,1,是一条简单回路，不是基本回路,v,1,e,1,v,2,e,2,v,3,e,7,v,5,e,6,v,4,e,5,v,1,是一条基本回路,（圈）,一、概 论,返回,图,5.3,（,a,）,图,5.3,（,b,）是图,5.3,（,a,）的生成树,三、,图的矩阵表示,(1),邻接矩阵,图,G,=(,V,E,),的邻接矩阵,C,是一个,n,n,的,0-1,矩阵,即,(2),关联矩阵,图,G,=(,V,E,),的关联矩阵,B,是一个,n,m,的,矩阵，即,例题,一、概 论,返回,返回,例,一、概 论,1,单源问题,最短路的性质：最短路中的任一段子路径也是最短路。,迪克斯特拉,（,Dijkstra,）,算法,的,基本思想,：,按距起点,u,0,从近到远的顺序，依次求得,u,0,到,G,的各顶点的最短路径和距离，直至,G,中距起点,u,0,最远的顶点。,二、最短路问题,Dijkstra,算法的步骤：,l,(,v,),：,从顶点,u,0,到,v,的一条路的权,pri,(,v,),：,v,的前驱点，用以逆序查找最短路径,i,：,更新次数,v,*,：,中距离,u,0,最近的顶点,U,i,：,第,i,次更新确定其最短路的顶点,S,i,：,第,i,次更新时确定的顶点集,二、最短路问题,例,二、最短路问题,返回,2,每对顶点之间的最短路,Floyd,算法的基本思想,：,通过依次插入结点,v,1,v,2,v,k,v,n,，递推产生两个矩阵序列,D,0,D,1,D,k,D,n,，,path,0,path,1,path,k,path,n,，其中,D,k,(,i,，,j,),表示赋权图中从结点,v,i,出发仅通过,v,1,v,2,v,k,中的某些结点到达,v,j,的最短路径的长度，,path,k,(,i,，,j,),表示从,v,i,到,v,j,的当前最短路径中起点,v,i,的后继结点的标号。,计算时用迭代公式：,二、最短路问题,Floyd,算法的步骤,：,Step 1,初始化矩阵,D,、,path,，,令,Step 2,刷新,D,、,path,对,k,=1,2,，,n,重复,Step 3,和,Step 4,Step 3,刷新行,对,i,=1,2,，,n,重复,Step 4,Step 4,刷新,D,k,(,i,，,j,),、,path,k,(,i,，,j,),对,j,=1,2,，,n,Step 5,结束迭代,，,得到,D,k,即是各点之间的最短路径值矩阵,结束,Step 4,循环,结束,Step 3,循环,结束,Step 2,循环,二、最短路问题,例题,返回,例,某公司在六个城市中有分公司，从城市,c,i,到城市,c,j,的 直接航程票价如下表所示（,表示无直接航路），请帮助该公司设计一张城市间的票价最便宜的路线图。,票价,城市,1,城市,2,城市,3,城市,4,城市,5,城市,6,城市,1,0,50,40,25,10,城市,2,50,0,15,20,25,城市,3,15,0,10,20,城市,4,40,20,10,0,10,25,城市,5,25,20,10,0,55,城市,6,10,25,25,55,0,二、最短路问题,二、最短路问题,返回,二、最短路问题,D,6,(1,，,2)=35,，,故从,c,1,到,c,2,的最短距离为,35,path,6,(1,，,2)=6,，,c,1,的后继点是,c,6,；,又,path,6,(6,，,2)=2,，,c,6,的后继点是,c,2,；,故,c,1,到,c,2,的最短路径是,c,1,c,6,c,2,返回,二、最短路问题,三、哈密顿路径问题与推销员问题,1,哈密顿路径问题,哈密顿,(,Hamilton,),道路问题是,1859,年发明的一种游戏：在一个实心的正十二面体，,20,个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历所有城市仅一次，最后回到原地。这就是“绕行世界”问题。,哈 密 尔 顿 图,返回,定义,在加权图,G=(V,E),中，,（）权最小的哈密尔顿圈称为,最佳,H,圈,（）经过每个顶点至少一次的权最小的闭通路称为,最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H,回路，长,22,最佳推销员回路，长,4,无向赋权完全图，一种简单的构造,H,圈算法,最邻近算法,：,初步改进,:,Step 1,找一条最短的边,e,i,。,Step 2,以关联,e,i,的两个顶点,v,i,1,、,v,i,2,分别作为起点，用最邻,近算法求最佳,H,圈。,Step 3,再比较这两条回路的长度，以确定最短的一条。,Step 1,从任一顶点出发，记为,v,1,找一个与,v,1,最近的顶点,v,2,(,v,1,v,2,),为两个顶点的基本道路。,Step 2,若已找出有,p,个顶点的基本道路,(,v,1,v,2,v,p,),p,n,，,在道路外找一个离,v,p,最近的顶点,记为,v,p,1,，,将其加入则得到具有,p,+1,个顶点的基本道路。,Step 3,若,p,+1,=,n,，,转,step4,，,否则转,Step2,。,Step 4,闭合,回路：即增加一条边,(,v,n,v,1,),则,(,v,1,v,2,v,p,v,1,),为一条近似的最短,H,圈。,例题,三、哈密顿路径问题与推销员问题,返回,最邻近算法所求为：,(,a,，,c,，,e,，,d,，,b,，,a,),总长为,7,6,8,5,14=40,实际最佳,H,圈：,(,a,，,c,，,e,，,b,，,d,，,a,),总长为,7,6,9,5,10=37,改进,:,(,b,，,d,),边长为,5,，,是最短边。,以,b,作起点得：,(,b,，,d,，,e,，,c,，,a,，,b,),总长为,40,以,d,作起点得：,(,d,，,b,，,e,，,c,，,a,，,d,),总长为,37,例,三、哈密顿路径问题与推销员问题,返回,对已构造的,Hamilton,圈改良的算法,二次逐边修正法,：,Step 1,构造初始圈,C,v,1,v,2,v,n,v,1,。,Step 2,对于所有,i,、,j,，,1,i+,1,jn,，,构造新的,Hamilton,圈：,C,ij,v,1,v,2,v,i,v,j,v,j,-1,v,j,-2,v,i+,1,v,j,+1,v,j+,2,v,n,v,1,它是由,C,中,删去边,v,i,v,i+,1,和,v,j,v,j,+1,，,添加边,v,i,v,j,和,v,i+,1,v,j,+1,而得到的，如图所示。,若,w(,v,i,v,j,)+w(,v,i+,1,v,j+,1,)w(,v,i,v,i+,1,)+w(,v,j,v,j+,1,),，,则令,C,C,ij,，,C,ij,叫做,C,的改良圈。,Step 3,对更新的,C,重复步骤,2,，,直至对所有,i,、,j,都不存在改良圈,C,ij,，,停止。,注意：用二次逐边修正算法得到的结果一般不是最优解。可选择不同的初始圈，重复进行几次算法，再从中选优以求得较精确的结