数学图论模型学习教案.pptx

会计学1数学图论数学图论(t ln)模型模型第一页，共90页。1.98年全国大学生数学建模竞赛年全国大学生数学建模竞赛(jngsi)B题题“最佳最佳灾灾 今年今年(jnnin)(1998年年)夏天某县遭受水灾夏天某县遭受水灾.为考察为考察灾情、灾情、组织自救组织自救(zji)，县领导决定，带领有关部门负责，县领导决定，带领有关部门负责人到人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视.巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线.情巡视路线情巡视路线”中的前两个问题是这样的：中的前两个问题是这样的：一、问题引入与分析一、问题引入与分析目录下页返回上页结束第2页/共90页第二页，共90页。1）若分三组（路）巡视）若分三组（路）巡视(xnsh)，试设计总，试设计总路程最路程最短且各组尽可能均衡短且各组尽可能均衡(jnhng)的巡视路线的巡视路线.2）假定巡视）假定巡视(xnsh)人员在各乡（镇）停留人员在各乡（镇）停留时间时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时小时.要在要在24小时内完成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.目录下页返回上页结束第3页/共90页第三页，共90页。公路边的数字公路边的数字(shz)(shz)为该路段的公为该路段的公里数里数.目录下页返回上页结束第4页/共90页第四页，共90页。2.2.问题问题(wnt)(wnt)分析：分析：本题本题(bnt)给出了某县的公路网络图，要求的是在给出了某县的公路网络图，要求的是在不不同的条件下，灾情巡视的最佳同的条件下，灾情巡视的最佳(zu ji)分组方案和路分组方案和路线线.将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各镇、村之间的公路看作此图对应顶点间的边，各次再回到点次再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.条公路的长度（或行驶时间）看作对应边上的权，条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点络图中寻找从给定点O出发，行遍所有顶点至少一出发，行遍所有顶点至少一目录下页返回上页结束第5页/共90页第五页，共90页。如第一问是三个旅行售货员问题如第一问是三个旅行售货员问题(wnt)，第二问是，第二问是四四本题是旅行售货员问题本题是旅行售货员问题(wnt)的延伸的延伸-多旅行多旅行(lxng)售货员问售货员问题题.本题所求的分组巡视的最佳路线，也就是本题所求的分组巡视的最佳路线，也就是m条条众所周知，旅行售货员问题属于众所周知，旅行售货员问题属于NP完全问题，完全问题，显然本问题更应属于显然本问题更应属于NP完全问题完全问题.有鉴于此，有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）到最小的闭链（闭迹）.个旅行售货员问题个旅行售货员问题.即求解没有多项式时间算法即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解大的问题可使用近似算法来求得近似最优解.目录下页返回上页结束第6页/共90页第六页，共90页。二、图论二、图论(t ln)的基本概念的基本概念目录下页返回上页结束1)图的概念图的概念(ginin)2)赋权图与子图赋权图与子图3)图的矩阵图的矩阵(j zhn)表示表示4)图的顶点度图的顶点度5)路和连通路和连通第7页/共90页第七页，共90页。定义定义 一个一个(y)图图G是指一个是指一个(y)二元组二元组(V(G),E(G)，其中，其中:其中元素称为其中元素称为(chn wi)图图G的顶点的顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|,用用来表示；来表示；图的边的数目图的边的数目|E(G)|用用 来表示来表示.也用也用来表示边来表示边是非空有限集，称为是非空有限集，称为顶点集顶点集，1)2)E(G)是顶点集是顶点集V(G)中的无序中的无序(w x)或有序的元素或有序的元素偶对偶对表示图，表示图，简记简记 用用1)图的概念目录下页返回上页结束第8页/共90页第八页，共90页。定义定义定义定义 若一个若一个若一个若一个(y(y )图的顶点集和边集都是有限集，则称图的顶点集和边集都是有限集，则称图的顶点集和边集都是有限集，则称图的顶点集和边集都是有限集，则称 其为有限其为有限(yuxin)图图.只有一个顶点的图称为平凡图，其他只有一个顶点的图称为平凡图，其他的的 所有所有(suyu)图都称为非平凡图图都称为非平凡图.目录下页返回上页结束第9页/共90页第九页，共90页。定义定义(dngy)(dngy)若图若图GG中的边均为有序偶对中的边均为有序偶对(vi,vj)(vi,vj)，称，称GG为有向为有向图图.称边称边 为为有向边有向边或或弧弧,称称 是从是从连接连接 ,称称 为为e的的尾尾，称称 为为e的的头头.若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称为为e的端点的端点(dun din).边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称 既有无向边又有有向边的图称为既有无向边又有有向边的图称为(chn wi)混混合图合图.目录下页返回上页结束第10页/共90页第十页，共90页。常用(chn yn)术语1)边和它的两端点称为边和它的两端点称为(chn wi)互互相关联相关联.2)与同一条边关联的两个与同一条边关联的两个(lin)端端点称点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边.3)端点重合为一点的边称为端点重合为一点的边称为环环，端点不相同的边称为端点不相同的边称为连杆连杆.4)若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5)既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 目录下页返回上页结束第11页/共90页第十一页，共90页。常用常用(chn yn)术语术语6)任意两顶点任意两顶点(dngdin)都相邻的简单图都相邻的简单图,称为完全图称为完全图.记为记为Kv.7)若若 ，且，且X 中任意中任意(rny)两两顶点不顶点不 相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称称为为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)8)图图 叫做叫做星星.二部图二部图目录下页返回上页结束第12页/共90页第十二页，共90页。定义定义(dngy)(dngy)若图若图G=(V(G),E(G)G=(V(G),E(G)的每一条边的每一条边e e 都赋以都赋以一个实数一个实数w(e)，称，称w(e)为边为边e的权，的权，G 连同连同(lintng)边边上的权上的权称为称为(chn wi)赋权图赋权图.定义定义 设设 和和 是两个图是两个图.1)若若 ,称称 是是 的一个的一个子图子图,记记 2)若若 ，则称，则称 是是 的的生成子图生成子图.3)若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 为为 的的由由 导出的子图导出的子图，记为，记为 .4)若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图,记为记为 .2)赋权图与子图赋权图与子图目录下页返回上页结束第13页/共90页第十三页，共90页。3)若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 4)若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图,记为记为 .为为 的的由由 导出的子图导出的子图，记为，记为 .目录下页返回上页结束第14页/共90页第十四页，共90页。1)对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中：邻接矩阵邻接矩阵:(以下均假设图为简单图以下均假设图为简单图).3)图的矩阵图的矩阵(j zhn)表示表示目录下页返回上页结束第15页/共90页第十五页，共90页。2)对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中：目录下页返回上页结束第16页/共90页第十六页，共90页。其中其中(qzhng)：3)对有向赋权图对有向赋权图 ,其邻接矩阵其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似对于无向赋权图的邻接矩阵可类似(li s)定义定义.目录下页返回上页结束第17页/共90页第十七页，共90页。1)对无向图对无向图 ，其关联矩阵，其关联矩阵 ,其中其中(qzhng)：关联矩阵关联矩阵目录下页返回上页结束第18页/共90页第十八页，共90页。2)对有向图对有向图 ，其关联矩阵，其关联矩阵 ,其中其中(qzhng)：目录下页返回上页结束第19页/共90页第十九页，共90页。目录下页返回上页结束定义定义 1)在无向图在无向图G中，与顶点中，与顶点v关联关联(gunlin)的边的数的边的数目目(环环算两次算两次),称为顶点称为顶点(dngdin)v的度或次数，记为的度或次数，记为d(v)或或 dG(v).称度为奇数称度为奇数(j sh)的顶点为奇点，度为偶数的顶点的顶点为奇点，度为偶数的顶点为偶点为偶点.2)在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d-(v).称称d(v)=d+(v)+d-(v)为顶点为顶点v的的 度度或或次数次数定理定理的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点4)图的顶点度图的顶点度第20页/共90页第二十页，共90页。目录下页返回上页结束 定义定义(dngy)1)无向图无向图G的一条途径（或通道或链）的一条途径（或通道或链）是指是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替 地为顶点和边，使得对地为顶点和边，使得对 ，的端点是的端点是 和和 ,称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径.整数整数k称为称为W的的长长.顶点顶点 和和 分别称为分别称为起点起点和和终点终点,而而 称为称为W的的内部顶点内部顶点.2)若途径若途径W的边互不相同的边互不相同(xin tn)但顶点可重但顶点可重复，则称复，则称W为迹或简单为迹或简单(jindn)链链.3)若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径.一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路记为记为5)路和连通路和连通第21页/共90页第二十一页，共90页。目录下页返回上页结束 定义定义(dngy)1)途径途径 中由相继项构成子序列中由相继项构成子序列 称为途径称为途径W的的节节.2)起点与终点起点与终点(zhngdin)重合的途径称为闭途重合的途径称为闭途径径.3)起点与终点重合起点与终点重合(chngh)的的路称为圈的的路称为圈(或或回路回路)，长，长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck.4)若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通.5)若在图若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之之间的之间的距离距离d(u,v)是指图是指图G中最短中最短(u,v)路的长；若没路的长；若没没有路连接没有路连接u和和v，则定义为无穷大，则定义为无穷大.第22页/共90页第二十二页，共90页。目录下页返回上页结束 6)图图G中任意两点皆连通中任意两点皆连通(lintng)的图称为连通的图称为连通(lintng)图图 类似类似(li s)地，可定义有向迹，有向路和有向圈地，可定义有向迹，有向路和有向圈.7)对于有向图对于有向图G，若，若 ，且，且 有有头头 和尾和尾 ，则称，则称W为为有向途径有向途径.例例 在右图中：在右图中：途径途径(tjng)或链：或链：迹或简单链：迹或简单链：路或路径：路或路径：圈或回路：圈或回路：第23页/共90页第二十三页，共90页。目录下页返回上页结束三、最短路问题三、最短路问题(wnt)及算法及算法 最短路问题是图论应用的基本最短路问题是图论应用的基本(jbn)问题，很问题，很多实际多实际问题，如线路的布设问题，如线路的布设(b sh)、运输安排、运输网络最、运输安排、运输网络最小费小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.第24页/共90页第二十四页，共90页。目录下页返回上页结束 2)在赋权图在赋权图G中，从顶点中，从顶点(dngdin)u到顶点到顶点(dngdin)v的具有最小权的具有最小权 定义定义(dngy)1)若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的的各各边的权和边的权和 为为H的的权权.类似地，若类似地，若称为称为(chn wi)路路P的权的权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3)把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v).第25页/共90页第二十五页，共90页。目录下页返回上页结束1)1)求赋权图中从给定点到其余顶点求赋权图中从给定点到其余顶点(dngdin)(dngdin)的最短路的最短路 解决上述问题的一个解决上述问题的一个(y)方法是由方法是由Dijkstra于于1959年提出年提出(t ch)的算法，此算法不仅能求出赋权图指定的算法，此算法不仅能求出赋权图指定两点两点最短路最短路.目前它是求无负权图最短路的最好方法目前它是求无负权图最短路的最好方法.间的最短路，而且能求出从指定点到其余各顶点的间的最短路，而且能求出从指定点到其余各顶点的 该算法基本原理该算法基本原理：若：若 是赋权图是赋权图G中从中从 到到 的最短路，则的最短路，则 必为从必为从 到到的最短路，则称的最短路，则称 是是 的的先驱点先驱点,记为记为 ,它可用于追踪最短路的路径它可用于追踪最短路的路径.最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路第26页/共90页第二十六页，共90页。目录下页返回上页结束 假设假设(jish)G为赋权有向图或无向图，为赋权有向图或无向图，G边上边上的权均非的权均非负若负若 ，则规定，则规定 求下面赋权图求下面赋权图G中顶点中顶点v0到其余到其余(qy)顶点的最顶点的最短路短路第27页/共90页第二十七页，共90页。输入输入(shr)：图：图G的带权邻接矩阵的带权邻接矩阵W.目录下页返回上页结束Dijkstra算法算法:求G中从顶点 到其余顶点的最短路.对每个顶点对每个顶点(dngdin)，定义两个标记（，定义两个标记（l(v),t(v)），），其中其中:l(v)表示从顶点表示从顶点(dngdin)到的一条路的权到的一条路的权t(v)表示的先驱点，它可用以确定最短路的路径表示的先驱点，它可用以确定最短路的路径.算法的过程就是在每一步改进这两个标记算法的过程就是在每一步改进这两个标记(l(v),t(v),使最终使最终l(v)为从顶点为从顶点v0到到v的最短路的权的最短路的权S：具有永久标号的顶点集：具有永久标号的顶点集.第28页/共90页第二十八页，共90页。目录下页返回上页结束Dijkstra算法算法(sun f)步骤步骤:用上述用上述(shngsh)算法求出的算法求出的l(v)就是就是v0到到v的最短路的最短路的权的权,(1)初始化操作初始化操作:置置S=v0,l(v0)=0,对每个对每个 ,令令 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点，即中的顶点，即 ，则令，则令 ，.若若 ，停止，停止.否则，转（否则，转（3）.(3)更新更新l(v)、t(v)：对每个：对每个 ，若，若l(v)l(u)+w(u,v),则令则令l(v)=l(u)+w(u,v),转转(2).从从v的先驱点标记的先驱点标记(bioj)t(v)追溯到追溯到v0,就得到就得到v0到到v的的最短最短路的路径路的路径.第29页/共90页第二十九页，共90页。(1)初始化操作初始化操作:置置S=v0,l(v0)=0,对每个对每个令令停止停止(tngzh).否则，转（否则，转（3）.,则令则令 ，.若若 ,(3)更新更新l(v)、t(v):对每个对每个 ,若若l(v)l(u)+w(u,v),则令则令l(v)=l(u)+w(u,v),转转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即置置S=v0,l(v0)=0,方框方框(fn kun)(fn kun)把把0 0框起来框起来.给与给与(i y)v0相邻的顶点相邻的顶点 分别标以分别标以l(v1)=w(v0v1)=w011,l(v2)=2,l(v4)=7,l(v6)=4,l(v7)=8.v1,v2,v4,v6,v7,其余顶点均标以其余顶点均标以 ,即即l(v3)=,l(v5)=.第30页/共90页第三十页，共90页。(1)初始化操作初始化操作:置置S=v0,l(v0)=0,对每个对每个令令停止停止(tngzh).否则，转（否则，转（3）.,则令则令 ，.若若 ,(3)更新更新l(v)、t(v):对每个对每个 ,若若l(v)l(u)+w(u,v),则则l(v)=l(u)+w(u,v),转转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即对每个对每个 记记t(v)=v0,即它们即它们(t men)的的先驱先驱(xinq)点均为点均为v0。在。在中取标号最小者中取标号最小者 l(v1)=1.用方框把用方框把1框起来框起来.令令 第31页/共90页第三十一页，共90页。(1)初始化操作初始化操作:置置S=v0,l(v0)=0,对每个对每个令令停止停止(tngzh).否则，转（否则，转（3）.,则令则令 ，.若若 ,(3)更新更新l(v)、t(v):对每个对每个 ,若若l(v)l(u)+w(u,v),则则l(v)=l(u)+w(u,v),转转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即的算法步骤的算法步骤(bzhu)(3)重新重新 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即 令令用用Dijkstra的标号的标号(bioho)l(v)、t(v).经计经计改进顶点改进顶点算只有算只有v3满足条件满足条件:则给则给v3标以标以l(v3)=4.令令 t(v3)=v1,此时其它此时其它点的两个标号点的两个标号 l(v)、t(v)保持不变。保持不变。第32页/共90页第三十二页，共90页。(1)初始化操作初始化操作:置置S=v0,l(v0)=0,对每个对每个令令停止停止(tngzh).否则，转（否则，转（3）.,则令则令 ，.若若 ,(3)更新更新l(v)、t(v):对每个对每个 ,若若l(v)l(u)+w(u,v),则则l(v)=l(u)+w(u,v),转转(2).(2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即 重复上面重复上面(shng min)的做法，的做法，能在改进能在改进(gijn)为止。为止。直到所有顶点的两直到所有顶点的两个标号个标号l(v)、t(v)不不目录下页返回上页结束第33页/共90页第三十三页，共90页。目录下页返回上页结束第34页/共90页第三十四页，共90页。目录下页返回上页结束第35页/共90页第三十五页，共90页。目录下页返回上页结束定义 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点(dngdin)w，称为，称为v的的先驱先驱点点，记为，记为t(v),即即t(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径(ljng).上例的标上例的标号过程也号过程也可按如下可按如下(rxi)方方式进行：式进行：首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵因因G是无向图，故是无向图，故W是对称阵是对称阵第36页/共90页第三十六页，共90页。目录下页返回上页结束第37页/共90页第三十七页，共90页。目录下页返回上页结束见见Visual C+6.0程序程序(chngx)-Dijkstra.cpp第38页/共90页第三十八页，共90页。目录下页返回上页结束（I）求距离矩阵）求距离矩阵(j zhn)的方法的方法.（II）求路径矩阵）求路径矩阵(j zhn)的方法的方法.（III）查找最短路）查找最短路(dunl)路径的方路径的方法法.Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.举例说明举例说明2)求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路算法的基本思想算法的基本思想第39页/共90页第三十九页，共90页。算法算法(sun f)的基本思想的基本思想直接直接(zhji)在图的带权邻接矩阵中用插入在图的带权邻接矩阵中用插入顶点的顶点的方法依次方法依次(yc)构造出构造出v个矩阵个矩阵D(1)、D(2)、D(v)，使最后得到的矩阵使最后得到的矩阵D(v)成为图的距离矩阵，同时成为图的距离矩阵，同时 也求出插入点矩阵以便得到两点间的最短路径也求出插入点矩阵以便得到两点间的最短路径目录下页返回上页结束第40页/共90页第四十页，共90页。目录下页返回上页结束（I）求距离矩阵）求距离矩阵(j zhn)的方法的方法.设赋权图设赋权图G的顶点集为的顶点集为 .1）写出赋权图）写出赋权图G的带权邻接矩阵的带权邻接矩阵W，把它作为，把它作为(zuwi)距离距离矩阵的初值，即矩阵的初值，即2）对）对k=1,2,v，计算，计算 其中其中表示从表示从vi到到vj且中间点仅为且中间点仅为v1,v2,vk的的k个点的个点的所有所有(suyu)路径中的最短路的长度。路径中的最短路的长度。于是于是 中元素中元素 就是从就是从 到到 的的路径中间可插入任何顶点的路径中最短路的长度，路径中间可插入任何顶点的路径中最短路的长度，即即 就是所求距离矩阵就是所求距离矩阵.第41页/共90页第四十一页，共90页。目录下页返回上页结束在建立在建立(jinl)距离矩阵的同时可建立距离矩阵的同时可建立(jinl)路径矩阵路径矩阵R（II）求路径矩阵）求路径矩阵(j zhn)的方法的方法.设设 ，这里，这里 的含义是从的含义是从 到到的最短路要经过点号为的最短路要经过点号为 的点的点.算法开始于算法开始于 ，迭代到第迭代到第k步，步，即由即由 到到 迭代，若某个元素改变（变小），迭代，若某个元素改变（变小），则由则由 到到 迭代中，相应元素改为迭代中，相应元素改为k，表示到第，表示到第k次迭代次迭代,从从 到到 的最短路过点的最短路过点 比过原中间点更短比过原中间点更短.在求得在求得 时求得时求得 ，可由，可由 来查找任何点对来查找任何点对之间最短路之间最短路(dunl)的的路径路径.第42页/共90页第四十二页，共90页。然后用同样然后用同样(tngyng)的方法再分头查找若：的方法再分头查找若：（III）查找）查找(ch zho)最短路路径的最短路路径的方法方法.目录下页返回上页结束第43页/共90页第四十三页，共90页。(IV)Floyd算法算法:求任意求任意(rny)两顶点间的最短路两顶点间的最短路.d(i,j)：i到到j的距离的距离(jl)r(i,j)：i到到j之间的插入之间的插入(ch r)点点输入输入:带权邻接矩阵带权邻接矩阵 .(1)赋初值赋初值:对所有对所有i,j,d(i,j)w(i,j),r(i,j)j,k 1.(2)更新更新d(i,j),r(i,j):对所有对所有i,j,若若d(i,k)+d(k,j)d(i,j),则则 d(i,j)d(i,k)+d(k,j),r(i,j)k.(3)若若k=v，停止否则，停止否则k k+1，转，转(2)目录下页返回上页结束第44页/共90页第四十四页，共90页。目录下页返回上页结束例例 求下图中加权图的任意求下图中加权图的任意(rny)两点间的距离两点间的距离与路径与路径.第45页/共90页第四十五页，共90页。目录下页返回上页结束插入插入(ch r)点点 v1，得：，得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的项为经迭代比较以后有变化(binhu)的的元素元素.第46页/共90页第四十六页，共90页。插入插入(ch r)点点 v2，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后的项为经迭代比较以后(yhu)有变化的元有变化的元素素.目录下页返回上页结束第47页/共90页第四十七页，共90页。插入插入(ch r)点点 v3，得：，得：目录下页返回上页结束第48页/共90页第四十八页，共90页。插入插入(ch r)点点 v4，得：，得：插入插入(ch r)点点 v5，得：，得：目录下页返回上页结束第49页/共90页第四十九页，共90页。插入插入(ch r)点点 v6，得：，得：目录下页返回上页结束第50页/共90页第五十页，共90页。故从故从v5到到v2的最短路的最短路(dunl)为为8 由由v6向向v5追溯追溯:由由v6向向v2追溯追溯:所以从到的最短路径为：所以从到的最短路径为：见见Visual C+6.0程序程序(chngx)Floyd.cpp如下。如下。目录下页返回上页结束第51页/共90页第五十一页，共90页。四、最小生成四、最小生成(shn chn)树及算法树及算法目录下页返回上页结束1)树的定义树的定义(dngy)与树的特征与树的特征定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为(chn wi)树常用树常用T表表示示.树中的边称为树中的边称为树枝树枝.树中度为树中度为1的顶点称为的顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡树平凡树.平凡树平凡树第52页/共90页第五十二页，共90页。目录下页返回上页结束1)G是树（是树（G无圈且连通）；无圈且连通）；2)G无圈，且有无圈，且有n-1条边条边；3)G连通连通(lintng)，且有，且有n-1条边；条边；4)G无圈，但添加任一条无圈，但添加任一条(y tio)新边恰好产生一个新边恰好产生一个圈圈;5)G连通连通(lintng)，且删去一条边就不连通，且删去一条边就不连通(lintng)了（即了（即G为最为最最小连通图最小连通图）；）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.定理定理2 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：第53页/共90页第五十三页，共90页。定义定义(dngy)若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它它又是树又是树,则称则称T是是G的生成的生成(shn chn)树树.图图G中不在生成中不在生成(shn chn)树的边叫做弦树的边叫做弦.定理定理(dngl)3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是是连连 通的通的.证明证明:必要性必要性是显然的是显然的.2）图的生成树）图的生成树目录下页返回上页结束充分性充分性：任取任取 ，令集合，令集合 ，这时生成树，这时生成树 的边集的边集 为空集为空集.因为因为 是连通图，点集是连通图，点集 与与 之间必有边相连，设之间必有边相连，设 为这样的边，为这样的边，第54页/共90页第五十四页，共90页。目录下页返回上页结束 属于属于 而而 属于属于 。则得。则得 ，。重复进行上述步骤，对于。重复进行上述步骤，对于 ,仍能找到边仍能找到边 满足其一端在点集满足其一端在点集 ，另一端在点集，另一端在点集 中中.由于由于 有一端在有一端在 之外，所以之外，所以 与与 中的中的 边不构成圈边不构成圈.当当 时，得到时，得到 ，即图即图 有有 条边且无圈，由定理条边且无圈，由定理2知，知，这是一棵树，且为图这是一棵树，且为图 的一棵生成树的一棵生成树.第55页/共90页第五十五页，共90页。目录下页返回上页结束可分为可分为(fn wi)两种：避圈法两种：避圈法和破圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法破圈法（II）找图中生成）找图中生成(shn chn)树的方树的方法法第56页/共90页第五十六页，共90页。目录下页返回上页结束 定理定理3的充分性的证明提供的充分性的证明提供(tgng)了一种构了一种构造图的生造图的生 成树的方法成树的方法(fngf).止止.这种方法这种方法(fngf)(fngf)可称为可称为“避圈法避圈法”或或“加边法加边法”成树的方法可分为两种：成树的方法可分为两种：深探法深探法和和广探法广探法.A 避圈法避圈法 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为 在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生第57页/共90页第五十七页，共90页。目录下页返回上页结束a)深探法深探法 若这样若这样(zhyng)的边的另一端均已有标号，就的边的另一端均已有标号，就退到标号为退到标号为步骤步骤(bzhu)如如下：下：i)在点集在点集V中任取一点中任取一点(y din)u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图10012345678910111213第58页/共90页第五十八页，共90页。目录下页返回上页结束13a)深探法深探法图100123456789101112步骤步骤(bzhu)如下：如下：若这样若这样(zhyng)的边的另一端均已有标号，就退的边的另一端均已有标号，就退到标号为到标号为i)在点集在点集V中任取一点中任取一点(y din)u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给给u以标号以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用用深探法求出下图深探法求出下图10的一的一棵生成树棵生成树 第59页/共90页第五十九页，共90页。目录下页返回上页结束3b)广探法广探法步骤步骤(bzhu)如下：如下：i)在点集在点集V中任取一点中任取一点(y din)u,ii)令所有令所有(suyu)标号标号i的的点集为点集为是否均已标号是否均已标号.对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.图10第60页/共90页第六十页，共90页。目录下页返回上页结束3b)广探法广探法步骤步骤(bzhu)如下：如下：i)在点集在点集V中任取一点中任取一点(y din)u,ii)令所有令所有(suyu)标号标号i的点的点集为集为是否均已标号是否均已标号.对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.显然图显然图10的生成树的生成树不唯一不唯一.第61页/共90页第六十一页，共90页。目录下页返回上页结束意舍弃一条边，将这个意舍弃一条边，将这个(zh ge)圈破掉，重复这个圈破掉，重复这个(zh ge)步骤直步骤直例例 用破圈法求出用破圈法求出下图的一棵生成下图的一棵生成(shn chn)树树.B 破圈法破圈法 相对相对(xingdu)于避圈法，还有一种求生成树的方法于避圈法，还有一种求生成树的方法叫做叫做“破圈法破圈法”.这种方法就是在图这种方法就是在图G中任取一个圈，任中任取一个圈，任到图到图G中没有圈中没有圈为止为止.第62页/共90页第六十二页，共90页。目录下页返回上页结束例例 用破圈法求出下图的另一棵生成用破圈法求出下图的另一棵生成(shn chn)树树.B 破圈法破圈法不难发现，图不难发现，图的生成的生成(shn chn)树不是树不是唯一的唯一的.第63页/共90页第六十三页，共90页。介绍介绍(jisho)最小树的两种算法：最小树的两种算法：Kruskal算法（或避圈法）和破圈法算法（或避圈法）和破圈法.3)最小生成最小生成(shn chn)树与算法树与算法目录下页返回上页结束第64页/共90页第六十四页，共90页。目录下页返回上页结束步骤步骤(bzhu)如下：如下：1)选择选择(xunz)边边e1，使得，使得w(e1)尽可能尽可能小；小；2)若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)的尽可能小的权，的尽可能小的权，3)当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止(tngzh).