图论基本知识

下回停1.问题引入与分析2.图论的基本概念3.最短路问题及算法图论模型4.最小生成树及算法5.旅行售货员问题6.模型建立与求解1.问题引入与分析1)98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线”中的前两个问题是这样的：1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数.2)问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条再回到点O，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条众所周知，旅行售货员问题属于NP完全问题，显然本问题更应属于NP完全问题.有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.2.图论的基本概念1)图的概念2)赋权图与子图3)图的矩阵表示4)图的顶点度5)路和连通1)图的概念定义一个图G是指一个二元组(V(G),E(G))，其中:其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.),(jivv定义图G的阶是指图的顶点数|V(G)|,用来表示；v图的边的数目|E(G)|用来表示.也用来表示边jivv).,(jivv},,,{)(21vvvGV是非空有限集，称为顶点集，1)2)E(G)是顶点集V(G)中的无序或有序的元素偶对).,(EVG))(),((GEGVG表示图，简记用定义若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.例设))(),((GEGVG，其中：},,,{)(4321vvvvGV，,,{)(21eeGE},,,6543eeee，111vve，322vve，313vve，414vve，435vve，436vve.（见图2）定义若图G中的边均为有序偶对,称G为有向),(jivv边为无向边，称e连接和，顶点和称图.称边为有向边或弧,称),(jivve是从),(jivveiv连接jv，称为e的尾，称为e的头.ivjv若图G中的边均为无序偶对，称G为无向图.称jivv为e的端点.jivveivjvivjv既有无向边又有有向边的图称为混合图.例设))(),((HEHVH，其中：},,,,{)(54321uuuuuHV，,,{)(21aaHE},,,,76543aaaaa，),(211uua，),(222uua，),(243uua，),(544uua，),(345uua，),(436uua，),(317uua.（见右图3）常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，端点不相同的边称为连杆.4)若一对顶点之间有两条以上的边联结，则这些边称为重边．5)既没有环也没有重边的图，称为简单图．常用术语6)任意两顶点都相邻的简单图,称为完全图.记为Kv.7)若，，且X中任意两顶点不YXGV)(YX，相邻，Y中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y中一切顶点相邻,称为完全二部图或完全偶图,记为(m=|X|,n=|Y|)．nmK,8)图叫做星.nK,1:X1x2x3x:Y1y2y3y4y二部图6K:X1x2x3x:Y1y2y3y4y4,1K4,3K2)赋权图与子图定义若图的每一条边e都赋以))(),((GEGVG一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图.定义设和是两个图.),(EVG),(EVG1)若,称是的一个子图,记EEVV,GG.GG2)若，，则称是的生成子图.VVEEGG3)若，且，以为顶点集，以两端点VVVV均在中的边的全体为边集的图的子图，称VG为的由导出的子图，记为.GV][VG4)若，且，以为边集，以的端点EEEEE集为顶点集的图的子图，称为的由导出的GGE边导出的子图，记为.][EG}],,[{321vvvG}],,,[{6543eeeeG3)若，且，以为顶点集，以两端点VVVV均在中的边的全体为边集的图的子图，称VG4)若，且，以为边集，以的端点EEEEE集为顶点集的图的子图，称为的由导出的GGE边导出的子图，记为.][EGGV][VG为的由导出的子图，记为.3)图的矩阵表示邻接矩阵:1)对无向图，其邻接矩阵，其中：G)(ijaA.,0,,1不相邻与若相邻与若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假设图为简单图).2)对有向图,其邻接矩阵,其中：)(ijaA),(EVG.),(,0,),(,1EvvEvvajijiij若若432143210100001000001110uuuuAuuuu其中：3)对有向赋权图,其邻接矩阵,)(ijaA),(EVG.),(,,0,),(,EvvjiwEvvwajiijjiijij若，为其权，且若43214321040608730uuuuAuuuu对于无向赋权图的邻接矩阵可类似定义.关联矩阵1)对无向图，其关联矩阵,),(EVG)(ijmM其中：.,0,,1不关联与若相关联与若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee2)对有向图，其关联矩阵,),(EVG)(ijmM.,0,,1,,1的头与尾不是若的头是若的尾是若jijijiijevevevm其中：43215432111000101100001101101uuuuMeeeee4)图的顶点度定义1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2)在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的度或次数．定理.2)(Vvvd的个数为偶数．推论任何图中奇点4)(1vd1)(3ud2)(3ud3)(3ud5)路和连通定义1)无向图G的一条途径（或通道或链）是指一个有限非空序列，它的项交替kkveevevW2110地为顶点和边，使得对，的端点是和,ki1ie1iviv称W是从到的一条途径，或一条途径.整0vkv),(0kvv数k称为W的长.顶点和分别称为的起点和终点,0vkv而称为W的内部顶点.121,,,kvvv2)若途径W的边互不相同但顶点可重复，则称W为迹或简单链.3)若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路0vkv),(0kvv记为).,(0kvvP定义1)途径中由相继项构成子序列kkvevevW...110称为途径W的节.jjiiivevev...112)起点与终点重合的途径称为闭途径.3)起点与终点重合的的路称为圈(或回路)，长为k的圈称为k阶圈，记为Ck.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，若，且有kkveevevW2110ie类似地，可定义有向迹，有向路和有向圈.头和尾，则称W为有向途径.iv1iv例在右图中：途径或链：迹或简单链：路或路径：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg3．最短路问题及算法最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解.•最短路的定义•最短路问题的两种方法：Dijkstra和Floyd算法.1)求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路.2)在赋权图G中，从顶点u到顶点v的具有最小权定义1)若H是赋权图G的一个子图，则称H的各边的权和为H的权.类似地，若)()()(HEeewHw称为路P的权．若P(u,v)是赋权图G中从u到v的路,称)()()(PEeewPw的路P*(u,v)，称为u到v的最短路．3)把赋权图G中一条路的权称为它的长，把(u,v)路的最小权称为u和v之间的距离，并记作d(u,v).1)赋权图中从给定点到其余顶点的最短路假设G为赋权有向图或无向图，G边上的权均非负．若，则规定)(),(GEvu.),(vuw最短路是一条路，且最短路的任一节也是最短路．求下面赋权图中顶点u0到其余顶点的最短路．Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且.0)(0ul0uv)(vl}{00uS0i2)对每个，用iSv)},()(),(min{vuwulvlii代替，计算，并把达到这个最小值的)(vl)}({minvliSv一个顶点记为，置1iu}.{11iiiuSS3)若，则停止；若，则用i+1代1i1i替i，并转2)..7,...,2,1,)(},{00juluSj01Su}10,min{)(1ulDijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且.0)(0ul0uv)(vl}{00uS0i2)对每个，用iSv)},()(),(min{vuwulvlii代替，计算，并把达到这个最小值的)(vl)}({minvliSv一个顶点记为，置1iu}.{11iiiuSS3)若，则停止；若，则用i+1代1i1i替i，并转2)..7,...,2,1,)(},{00juluSj01Su1)(1ul02SuDijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且.0)(0ul0uv)(vl}{00uS0i2)对每个，用iSv)},()(),(min{vuwulvlii代替，计算，并把达到这个最小值的)(vl)}({minvliSv一个顶点记为，置1iu}.{11iiiuSS3)若，则停止；若，则用i+1代1i1i替i，并转2)..7,...,2,1,)(},{00juluSj1)(1ul2)(2ul03Su)(3ulDijkstra算法:求G中从