第二章图论模型

《第二章图论模型》由会员分享，可在线阅读，更多相关《第二章图论模型（90页珍藏版）》请在金锄头文库上搜索。

1、数学建模简明教程国家精品课程国家精品课程第二章第二章 图论模型图论模型一、一、问题引入与分析问题引入与分析二、二、图论的基本概念图论的基本概念三、三、最短路问题及算法最短路问题及算法 四、四、最小生成树及算法最小生成树及算法 五、五、旅行售货员问题旅行售货员问题六、六、模型建立与求解模型建立与求解目录下页返回上页结束1. 98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B题题“最佳灾最佳灾 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾. 为考察灾情、为考察灾情、 组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（

2、镇）、村巡视. 巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线. .情巡视路线情巡视路线”中的前两个问题是这样的：中的前两个问题是这样的： 一、问题引入与分析一、问题引入与分析目录下页返回上页结束 1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线. 2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35

3、公里公里/小时小时. 要在要在24小时内完成巡视，至少应小时内完成巡视，至少应分分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.目录下页返回上页结束公路边的数字为该路段的公里数公路边的数字为该路段的公里数. .目录下页返回上页结束2.2.问题分析：问题分析： 本题给出了某县的公路网络图，要求的是在不本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各镇、村之间的公路看作此图对应顶

4、点间的边，各次再回到点次再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.条公路的长度（或行驶时间）看作对应边上的权，条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点络图中寻找从给定点O出发，行遍所有顶点至少一出发，行遍所有顶点至少一目录下页返回上页结束 如第一问是三个旅行售货员问题，第二问是四如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸本题是旅行售货员问题的延伸-多

5、旅行售货员问题多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是本题所求的分组巡视的最佳路线，也就是m条条众所周知，旅行售货员问题属于众所周知，旅行售货员问题属于NP完全问题，完全问题，显然本问题更应属于显然本问题更应属于NP完全问题完全问题. 有鉴于此，有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）到最小的闭链（闭迹）.个旅行售货员问题个旅行售货员问题.即求解没有多项式时间算法即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实

6、的，对于规模较解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解大的问题可使用近似算法来求得近似最优解.目录下页返回上页结束二、二、图论的基本概念图论的基本概念目录下页返回上页结束1) 图的概念图的概念2) 赋权图与子图赋权图与子图3) 图的矩阵表示图的矩阵表示4) 图的顶点度图的顶点度5) 路和连通路和连通 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其，其中中: 其中元素称为图其中元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边. 定义定义 图图G的的阶阶是指图的顶点数是指图的

7、顶点数|V(G)|, 用用来表示；来表示；图的边的数目图的边的数目|E(G)|用用 来表示来表示. 也用也用来表示边来表示边是非空有限集，称为是非空有限集，称为顶点集顶点集，1)2) E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对表示图，表示图，简记简记 用用1) 图的概念目录下页返回上页结束定义定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图. 只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图都称为所有图都称为非平凡图非平凡图.目录下页返回上页结束 定义定义若图若图G中的边均

8、为有序偶对中的边均为有序偶对(vi,vj)，称，称G为为有向有向图图. 称边称边 为为有向边有向边或或弧弧,称称 是从是从连接连接 , 称称 为为e的的尾尾， 称称 为为e的的头头. 若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称为为e的的端点端点. 边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称 既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图.目录下页返回上页结束 常用术语常用术语1) 边和它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶

9、点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合为一点的边称为端点重合为一点的边称为环环， 端点不相同的边称为端点不相同的边称为连杆连杆.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5) 既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 目录下页返回上页结束常用术语常用术语6) 任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图. 记为记为Kv. 7) 若若 ， ，且且X 中任意两顶点不中任意两顶点不 相邻，相邻，Y 中任意两顶点不

10、相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称称为为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)8) 图图 叫做叫做星星.二部图二部图目录下页返回上页结束 定义定义 若图若图G=(V(G),E(G) 的每一条边的每一条边e 都赋以都赋以一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图. 1) 若若 ,称称 是是 的一个的一个子图子图,记记 2) 若若 ， ，则称，则称

11、是是 的的生成子图生成子图. 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 为为 的的由由 导出的子图导出的子图，记为，记为 .4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图,记为记为 . 2) 赋权图与子图赋权图与子图目录下页返回上页结束 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子

12、图，称的子图，称 4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的 边导出的子图边导出的子图,记为记为 . 为为 的的由由 导出的子图导出的子图，记为，记为 .目录下页返回上页结束1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： 邻接矩阵邻接矩阵: (以下均假设图为简单图以下均假设图为简单图).3) 图的矩阵表示图的矩阵表示目录下页返回上页结束2) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： 目录下页返回上页结束其中：其中：3) 对有向赋权图对有向赋权图 ,其邻接矩

13、阵其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义. 目录下页返回上页结束1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,其中：其中：关联矩阵关联矩阵目录下页返回上页结束2) 对有向图对有向图 ，其关联矩阵，其关联矩阵 ,其中：其中：目录下页返回上页结束目录下页返回上页结束定义定义 1) 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点. 2) 在有向图

14、中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度或或次数次数定理定理的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点4) 图的顶点度图的顶点度目录下页返回上页结束 定义定义1) 无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替 地为顶点和边，使得对地为顶点和边，使得对 ， 的端点是的

15、端点是 和和 ,称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径. 整数整数k称为称为W的的长长. 顶点顶点 和和 分别称为分别称为起点起点和和终点终点,而而 称为称为W的的内部顶点内部顶点. 2) 若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W为为迹迹或或简单链简单链. 3) 若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路记为记为5) 路和连通路和连通目录下页返回上页结束 定义定义 1) 途径途径 中由相继项构成子序列中由相继项构成子序列

16、 称为途径称为途径W的的节节. 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)

17、 图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈. 7) 对于有向图对于有向图G，若，若 ，且，且 有有头头 和尾和尾 ，则称，则称W为为有向途径有向途径. 例例 在右图中：在右图中： 途径或链：途径或链： 迹或简单链：迹或简单链： 路或路径：路或路径： 圈或回路：圈或回路：目录下页返回上页结束三、最短路问题及算法三、最短路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用

18、流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法 .1)1) 求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路. . . . 2) 求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.目录下页返回上页结束 2) 在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的具有最小权 定义定义 1) 若若H是赋权图是赋权图G的一个子图，则称的一个

19、子图，则称H的各的各边的权和边的权和 为为H的的权权. 类似地，若类似地，若称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3) 把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v). 目录下页返回上页结束1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路 解决上述问题的一个方法是由解决上述问题的一个方法是由Dijkstra于于1959年提出的算法，此算

20、法不仅能求出赋权图指定两点年提出的算法，此算法不仅能求出赋权图指定两点最短路最短路.目前它是求无负权图最短路的最好方法目前它是求无负权图最短路的最好方法. 间的最短路，而且能求出从指定点到其余各顶点的间的最短路，而且能求出从指定点到其余各顶点的 该算法基本原理该算法基本原理：若：若 是赋权图是赋权图G中从中从 到到 的最短路，则的最短路，则 必为从必为从 到到的最短路，则称的最短路，则称 是是 的的先驱点先驱点,记为记为 ,它可用于追踪最短路的路径它可用于追踪最短路的路径. 最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路目录下页返回上页结束 假设假设G为赋

21、权有向图或无向图，为赋权有向图或无向图，G边上的权均非边上的权均非负若负若 ，则规定，则规定 求下面赋权图求下面赋权图G中顶点中顶点v0到其余顶点的最短路到其余顶点的最短路输入：图输入：图G的带权邻接矩阵的带权邻接矩阵W. 目录下页返回上页结束Dijkstra算法算法: 求G中从顶点 到其余顶点的最短路.对每个顶点，定义两个标记（对每个顶点，定义两个标记（l(v),t(v)），其中），其中: l(v)表示从顶点到的一条路的权表示从顶点到的一条路的权t(v)表示的先驱点，它可用以确定最短路的路径表示的先驱点，它可用以确定最短路的路径.算法的过程就是在每一步改进这两个标记算法的过程就是在每一步改进

22、这两个标记(l(v),t(v),使最终使最终l(v)为从顶点为从顶点v0到到v的最短路的权的最短路的权S：具有永久标号的顶点集：具有永久标号的顶点集. 目录下页返回上页结束Dijkstra算法步骤算法步骤: 用上述算法求出的用上述算法求出的l(v)就是就是v0到到v的最短路的权的最短路的权, (1) 初始化操作初始化操作:置置S=v0,l(v0)=0,对每个对每个 ,令令 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点，即中的顶点，即 ，则令，则令 ， . 若若 ，停止，停止. 否则，转（否则，转（3）. (3)更新更新l(v)、t(v)：对每个：对每个 ，若，若l(v)l(u)

23、+w(u,v), 则令则令l(v)=l(u)+w(u,v),转转(2) .从从v的先驱点标记的先驱点标记t(v)追溯到追溯到v0, 就得到就得到v0到到v的最短的最短路的路径路的路径. (1) 初始化操作初始化操作:置置S=v0,l(v0)=0 ,对每个对每个令令停止停止. 否则，转（否则，转（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)取最小值的

24、取最小值的 中的顶点中的顶点,即即置置S=v0,l(v0)=0,方框把方框把0 0框起来框起来. . 给与给与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)= . (1) 初始化操作初始化操作:置置S=v0,l(v0)=0 ,对每个对每个令令停止停止. 否则，转（否则，转（3）. ,则令则令 ， .若若 , (3)更新更新l(v) 、t(v) :对每个对每个 ,若若l(v) l(u)+w(u

25、,v), 则则l(v)=l(u)+w(u,v),转转(2) . (2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即对每个对每个 记记t(v)=v0 ,即它们即它们的的先驱点均为先驱点均为v0。在在中取标号最小者中取标号最小者l(v1)=1.用方框把用方框把1框起来框起来.令令 (1) 初始化操作初始化操作:置置S=v0,l(v0)=0 ,对每个对每个令令停止停止. 否则，转（否则，转（3）. ,则令则令 ， .若若 , (3)更新更新l(v) 、t(v) :对每个对每个 ,若若l(v) l(u)

26、+w(u,v), 则则l(v)=l(u)+w(u,v),转转(2) . (2)设设v*是是使使l(v)取取最最小小值值的的 中中的的顶顶点点，即即的算法步骤的算法步骤(3)重新重新 (2)设设v*是使是使l(v)取最小值的取最小值的 中的顶点中的顶点,即即 令令用用Dijkstra的标号的标号l(v)、t(v) .经经计计改进顶点改进顶点算只有算只有v3满足条件满足条件:则给则给v3标以标以l(v3)=4. 令令 t(v3)=v1,此时其它此时其它点的两个标号点的两个标号l(v) 、t(v)保持不变。保持不变。 (1) 初始化操作初始化操作:置置S=v0,l(v0)=0 ,对每个对每个令令停止

27、停止. 否则，转（否则，转（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)取最小值的取最小值的 中的顶点中的顶点,即即 重复上面的做法，重复上面的做法，能在改进为止。能在改进为止。 直到所有顶点的两直到所有顶点的两个标号个标号l(v) 、t(v)不不目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束目录下页返回上页结束定义 根据顶点根据顶点v的

28、标号的标号l(v)的取值途径，使的取值途径，使 到到v的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱点点，记为，记为t(v), 即即t(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径. 上例的标号过程也上例的标号过程也可按如下方式进行：可按如下方式进行：首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵因因G是无向图，故是无向图，故W是对称阵是对称阵目录下页返回上页结束目录下页返回上页结束见见Visual C+6.0程序程序-Dijkstra.cpp目录下页返回上页结束 （I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径

29、矩阵的方法.（III）查找最短路路径的方法）查找最短路路径的方法. Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路. 举例说明举例说明2) 求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路算法的基本思想算法的基本思想算法的基本思想算法的基本思想直接在图的带权邻接矩阵中用插入顶点的直接在图的带权邻接矩阵中用插入顶点的方法依次构造出方法依次构造出v个矩阵个矩阵D(1)、 D(2)、 、D(v)， 使最后得到的矩阵使最后得到的矩阵D(v)成为图的距离矩阵，同时成为图的距离矩阵，同时 也求出插入点矩阵以便得到两点间的最短路径也求出插入点矩阵以便得到两点间的最短路径目录下

30、页返回上页结束目录下页返回上页结束（I）求距离矩阵的方法）求距离矩阵的方法.设赋权图设赋权图G的顶点集为的顶点集为 .1）写出赋权图写出赋权图G的带权邻接矩阵的带权邻接矩阵W，把它作为距把它作为距离离矩阵的初值，即矩阵的初值，即2）对）对k=1,2,v，计算，计算 其中其中表示从表示从vi到到vj且中间点仅为且中间点仅为v1,v2,vk的的k个点个点的的所有路径中的最短路的长度。所有路径中的最短路的长度。 于是于是 中元素中元素 就是从就是从 到到 的的路径中间可插入任何顶点的路径中最短路的长度，路径中间可插入任何顶点的路径中最短路的长度，即即 就是所求距离矩阵就是所求距离矩阵.目录下页返回上

31、页结束在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R （II）求路径矩阵的方法）求路径矩阵的方法. 设设 ，这里，这里 的含义是从的含义是从 到到的最短路要经过点号为的最短路要经过点号为 的点的点.算法开始于算法开始于 ， ， 迭代到第迭代到第k步，步，即由即由 到到 迭代，若某个元素改变（变小），迭代，若某个元素改变（变小），则由则由 到到 迭代中，相应元素改为迭代中，相应元素改为k，表示到第，表示到第k次迭代次迭代,从从 到到 的最短路过点的最短路过点 比过原中间点更短比过原中间点更短. 在求得在求得 时求得时求得 ，可由，可由 来查找任何点对来查找任何点对之间最短

32、路的路径之间最短路的路径.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：（III）查找最短路路径的方法）查找最短路路径的方法.目录下页返回上页结束(IV) Floyd算法算法:求任意两顶点间的最短路求任意两顶点间的最短路.d(i,j)：i到到j的距离的距离r(i,j)：i到到j之间的插入点之间的插入点输入输入: 带权邻接矩阵带权邻接矩阵 .(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,

33、k)+d(k,j), r(i,j) k.(3)若若k=v，停止否则，停止否则k k+1，转，转(2)目录下页返回上页结束目录下页返回上页结束例例 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径. 目录下页返回上页结束插入点插入点 v1，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.插入点插入点 v2，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.目录下页返回上页结束插入点插入点 v3，得：得：目录下页返回上页结束插入点插入点 v4，得：得：插入点插入点 v5，得：得

34、：目录下页返回上页结束插入点插入点 v6，得：得：目录下页返回上页结束故从故从v5到到v2的最短路为的最短路为8 由由v6向向v5追溯追溯: 由由v6向向v2追溯追溯: 所以从到的最短路径为：所以从到的最短路径为： 见见Visual C+6.0程序程序Floyd.cpp如下。如下。目录下页返回上页结束四、最小生成树及算法四、最小生成树及算法目录下页返回上页结束1) 树的定义与树的特征树的定义与树的特征定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示. 树中的边称为树中的边称为树枝树枝. 树中度为树中度为1的顶点称为的顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡

35、树平凡树.平凡树平凡树目录下页返回上页结束1) G是树（是树（ G无圈且连通）；无圈且连通）；2) G无圈，且有无圈，且有n-1条边条边；3) G连通，且有连通，且有n-1条边；条边；4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6) G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.定理定理2 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又

36、是树它又是树,则称则称T是是G的的生成树生成树. 图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明: 必要性必要性是显然的是显然的.2）图的生成树）图的生成树目录下页返回上页结束充分性充分性：任取任取 ，令集合，令集合 ，这时生成树，这时生成树 的边集的边集 为空集为空集. 因为因为 是连通图，点集是连通图，点集 与与 之间必有边相连，设之间必有边相连，设 为这样的边，为这样的边， 目录下页返回上页结束 属于属于 而而 属于属于 。则得。则得 ， 。重复进行上述步骤，对于。重复进行上述步

37、骤，对于 , , , 仍能找到边仍能找到边 满足其一端在点集满足其一端在点集 ，另一端在点集，另一端在点集 中中. 由于由于 有一端在有一端在 之外，所以之外，所以 与与 中的中的 边不构成圈边不构成圈. 当当 时，得到时，得到 ， ，即图即图 有有 条边且无圈，由定理条边且无圈，由定理2知，知， 这是一棵树，且为图这是一棵树，且为图 的一棵生成树的一棵生成树.目录下页返回上页结束可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法 B 破圈法破圈法 （II）找图中生成树的方法）找图中生成树的方法目录下页返回上页结束 定理定理3的充分性的证明

38、提供了一种构造图的生的充分性的证明提供了一种构造图的生 成树的方法成树的方法.止止. . 这种方法可称为这种方法可称为“避圈法避圈法”或或“加边法加边法”成树的方法可分为两种：成树的方法可分为两种：深探法深探法和和广探法广探法.A 避圈法避圈法 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为 在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生目录下页返回上页结束a) 深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退

39、到标号为步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图10012345678910111213目录下页返回上页结束13a) 深探法深探法图1001234567

40、89101112步骤如下：步骤如下： 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为i) 在点集在点集V中任取一点中任取一点u,ii) 若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给给u以标号以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例用用深探法求出下图深探法求出下图10的一的一棵生成树棵生成树 目录下页返

41、回上页结束3b)广探法广探法步骤如下：步骤如下：i) 在点集在点集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未对所有未标标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端中的边端点点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.图10目录下页返回上页结束3b)广探法广探法步骤如下：步骤如下：i) 在点集在点

42、集V中任取一点中任取一点u,ii) 令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号. 对所有未对所有未标标号之点均标以号之点均标以i+1,记下这些记下这些 iii) 对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VVi中的边端中的边端点点边边.例例用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图101012213212234标号为止标号为止.显然图显然图10的生成树的生成树不唯一不唯一.目录下页返回上页结束意舍弃一条边，将这个圈破掉，重复这个步骤直意舍弃一条边，将这个圈破掉，重复这个

43、步骤直例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.B 破圈法破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”. 这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈，任任到图到图G中没有圈中没有圈为止为止.目录下页返回上页结束例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.B 破圈法破圈法不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的 . 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法. 3) 最小生成树与算法最小生成

44、树与算法目录下页返回上页结束目录下页返回上页结束步骤如下：步骤如下： 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i) 为无圈图，为无圈图， ii) 是满足是满足i)的尽可能小的权，的尽可能小的权， 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算法构作的任何生成树算法构作的任何生成树都是最小树都是最小树.A Kruskal算法（或避圈法）算法（或避圈法）目录下页返回上页结束例例10用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中

45、权值权值最小的边有最小的边有 任取一条任取一条 在在 中选取权值中选取权值最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选任取一条边任取一条边会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取 中选取中选取 . 但但 与与 都都目录下页返回上页结束算法算法2 步骤如下：步骤如下： 1) 从图从图G中任选一棵树中任选一棵树T1.2) 加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈. 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查

46、完毕为止部弦检查完毕为止.例例11用破圈用破圈法求下图的最小树法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树. 加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；B破圈法破圈法 再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全全部的弦均已试过全部的弦均已试过,得最小树得最小树.目录下页返回上页结束五、旅行售货员问题五、旅行售货员问题 定义定义设设G=(V,E)是连通无向图，包含图

47、是连通无向图，包含图G的每个的每个顶点的路称为顶点的路称为G的的哈密尔顿路哈密尔顿路(Hamilton路路或或H路路). 包含图包含图G的每个顶点的圈，称为的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈(或或Hamilton圈圈或或H圈圈). 含含Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图(或或Hamilton图图或或H图图). 目录下页返回上页结束 一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各城镇之间的距离后，应怎样计划给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次他的旅行路线，使他能对每个城

48、镇恰好经过一次而总距离最小？而总距离最小？ 它可归结为这样的它可归结为这样的图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为称这种圈为最优最优圈圈. 但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前目前还还没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此只能找一种求出相当好（不一定最优）的解只能找一种求出相当好（不一定最优）的解.旅行售货员问题或货郎担问题.目录下页返回上页结束 是先求一个

49、是先求一个H圈圈,然后适当然后适当修改修改,以得到具有较小权的以得到具有较小权的另另一个一个H圈圈.一个可行的办法一个可行的办法 : : 设找到一个初始设找到一个初始H圈圈 ，则对所，则对所有有适合适合 的的 和和 ，总可得到一个新的，总可得到一个新的H 圈：圈： ，它是由，它是由C 删去边删去边 和和 ，以及添加边，以及添加边 和和而得到，如右图所示。而得到，如右图所示。目录下页返回上页结束定义 若对于某一对若对于某一对i和和j，有，有则圈则圈Cij将是圈将是圈C的一个的一个改进改进.二边逐次修正法二边逐次修正法: 在接连进行一系列修改之后在接连进行一系列修改之后,最后得一个圈最后得一个圈,

50、不不能能再用此方法改进了，这个最后的圈可能不是最优的再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个但是它是比较好的，为了得到更高的精度，这个程序可以重复几次，每次都以不同的圈开始程序可以重复几次，每次都以不同的圈开始. 这种这种方法叫做方法叫做二边逐次修正法二边逐次修正法.目录下页返回上页结束较优较优H圈圈:其权为其权为W(C3)=192例例 对下图对下图16的的K6,用二边逐次修正法求较优用二边逐次修正法求较优H圈圈.目录下页返回上页结束 分析分析: : 找出的这个解的好坏可用最优找出的这个解的好坏可用最优H圈的权圈的权的下界与其比较而得出的下界与其

51、比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界，圈的一个下界，方法如下方法如下： 设设C是是G的一个最优的一个最优H圈，则对圈，则对G的任一顶点的任一顶点v, C-v是是G-v的路，也的路，也G-v是的生成树是的生成树.如果如果T是是G-v的的最小生成树最小生成树,且且e1是是e2与与v关联的边中权最小的两条关联的边中权最小的两条边边,则则w(T)+w(e1)+w(e2)将是将是w(C)的一个下界的一个下界.取取v=v3,得得G-v3的一的一最小生成树最小生成树(实线实线),其其权权w(T)=122,与与v3关联关联的权最小的两条边为的权最小的两条边为w(T)+w(

52、v1v3)+w(v2v3)=178.故最优故最优H圈的权圈的权v1v3和和v2v3,故故w(C)应满足应满足178 w(C) 192.目录下页返回上页结束六、最佳灾情巡视路线的模型的建立与求解六、最佳灾情巡视路线的模型的建立与求解问题转化为在问题转化为在给定的加权网给定的加权网络图中寻找从络图中寻找从给定点给定点O出发出发,行遍所有顶点行遍所有顶点至少一次再回至少一次再回回到点回到点O ,使使得得总权总权(路程或时路程或时时间时间)最小最小,即即最佳旅行售货最佳旅行售货员问题员问题.目录下页返回上页结束最佳旅行售货员问题是最佳旅行售货员问题是NP完全问题完全问题,采用一种采用一种近似算法求其一

53、个近似最优解，来代替最优解近似算法求其一个近似最优解，来代替最优解.算法一算法一 求加权图的最佳旅行售货员回路近似算法求加权图的最佳旅行售货员回路近似算法: 1) 用图论软件包求出用图论软件包求出G中任意两个顶点间的最短路中任意两个顶点间的最短路, 构造出完全图构造出完全图2) 输入图输入图 的一个初始的一个初始H圈；圈；3) 用对角线完全算法（见用对角线完全算法（见3）产生一个初始圈）产生一个初始圈;4) 随机搜索出随机搜索出 中若干个中若干个H圈，例如圈，例如2000个；个；5) 对第对第2)，3)，4)步所得的每个步所得的每个H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优修正

54、法进行优化，得到近似最优H圈；圈；6) 在第在第5)步求出的所有步求出的所有H圈中，找出权最小的一个圈中，找出权最小的一个, 此即要找的最优此即要找的最优H圈的近似解圈的近似解.因二边逐次修正法的结果与初始圈有关因二边逐次修正法的结果与初始圈有关,故本算法故本算法第第2)，3)，4)步分别用三种方法产生初始圈，以保步分别用三种方法产生初始圈，以保证能得到较优的计算结果证能得到较优的计算结果. 问题一问题一 若分为三组巡视，设计总路程最短且各若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题此问题是多个售货员的最佳旅行售货员问

55、题.4)目录下页返回上页结束目录下页返回上页结束 此问题包含两方面：此问题包含两方面：a)对顶点分组对顶点分组, b)在每组中在每组中求求(单个售货员单个售货员)最佳旅行售货员回路最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法存在多项式时间内的精确算法.故故多多也不也不目录下页返回上页结束 而图中节点数较多，为而图中节点数较多，为53个，我们只能去寻求个，我们只能去寻求一种较合理的划分准则，对图一种较合理的划分准则，对图1进行粗步划分后进行粗步划分后,求求出各部分的近似最佳旅行售货员回路的权出各部分的近似最佳旅行

56、售货员回路的权,再进一再进一进一步进行调整，使得各部分满足均衡性条件进一步进行调整，使得各部分满足均衡性条件3). 从从O点出发去其它点，要使路程较小应尽量走点出发去其它点，要使路程较小应尽量走O点到该点的最短路点到该点的最短路. 故用软件包求出故用软件包求出O点到其余顶点的最短路点到其余顶点的最短路. 这些最短路构成一棵这些最短路构成一棵O为树根的树为树根的树.将从将从O点出发的树枝称为点出发的树枝称为干枝干枝.从从O点出发到其它点共有点出发到其它点共有6条干枝，它们的名称条干枝，它们的名称分别为分别为，. 在分组时应遵从准则：在分组时应遵从准则： 准则准则1 尽量使同一干枝上及分枝上的点分

57、在同一组尽量使同一干枝上及分枝上的点分在同一组.准则准则2 应将相邻的干枝上的点分在同一组；应将相邻的干枝上的点分在同一组； 准则准则3 尽量将长的干枝与短的干枝分在同一组尽量将长的干枝与短的干枝分在同一组.分组分组1极不均衡极不均衡,故考虑分组故考虑分组2.由上述分组准则，我们找到两种分组形式如下：由上述分组准则，我们找到两种分组形式如下：分组分组1:（，），（），（，），（），（，）分组分组2:（，），（），（，），（），（，）目录下页返回上页结束分组分组2:(,),(,),(,) 对分组对分组2中每组顶点的生成子图中每组顶点的生成子图,用算法一求出用算法一求出近似最优解及相应的巡视路线近

58、似最优解及相应的巡视路线. 在每个子图所构造的完全图中在每个子图所构造的完全图中,取一个尽量包含取一个尽量包含上图中树上的边的上图中树上的边的H圈作为其第圈作为其第2)步输入的初始圈步输入的初始圈.分组分组2的近似解的近似解 目录下页返回上页结束因为该分组的均衡度因为该分组的均衡度.所以此分法的均衡性很差所以此分法的均衡性很差. 为改善均衡性，将第为改善均衡性，将第组中的顶点组中的顶点C,2,3,D,4分给第分给第组（顶点组（顶点2为这两组的公共点），重新分为这两组的公共点），重新分分组后的近似最优解见表分组后的近似最优解见表2.目录下页返回上页结束因该分组的均衡度因该分组的均衡度 所以这种分

59、法的均衡性较好所以这种分法的均衡性较好. 问题二问题二 当巡视人员在各乡（镇）、村的停留当巡视人员在各乡（镇）、村的停留停留时间一定停留时间一定,汽车的行驶速度一定汽车的行驶速度一定,要在要在24小时小时内内完成巡视完成巡视,至少要分几组及最佳旅行的巡视路线至少要分几组及最佳旅行的巡视路线.目录下页返回上页结束 由于由于T=2小时小时,t=1小时小时,V=35公里公里/小时小时,需访需访问问的乡镇共有的乡镇共有17个，村共有个，村共有35个个. 计算出在乡计算出在乡(镇镇)及及村的总停留时间为村的总停留时间为17 2+35=69小时，要在小时，要在24小时小时内完成巡回，若不考虑行走时间，有内

60、完成巡回，若不考虑行走时间，有: 69/i24(i为为分的组数分的组数). 得得i最小为最小为4，故，故至少要分至少要分4组组. 由于该网络的乡由于该网络的乡(镇镇)、村分布较为均匀、村分布较为均匀,故有可故有可能找出停留时间尽量均衡的分组能找出停留时间尽量均衡的分组,当分当分4组时各组停组时各组停停留时间大约为停留时间大约为69/4=17.25小时，则每组分配在路小时，则每组分配在路路途上的时间大约为路途上的时间大约为24-17.25=6.75小时小时.而前面讨而前面讨论过论过,分三组时有个总路程分三组时有个总路程599.8公里的巡视路线，公里的巡视路线，分分4组时的总路程不会比组时的总路程

61、不会比599.8公里大太多公里大太多,不妨以不妨以599.8公里来计算公里来计算.路上约用路上约用599.8/35=17小时小时,若平若平均分配给均分配给4个组个组,每个组约需每个组约需17/4=4.25h6.75h,故分成故分成4组是可能办到的组是可能办到的.目录下页返回上页结束 现在尝试将顶点分为现在尝试将顶点分为4组组.分组的原则：除遵从分组的原则：除遵从前面准则前面准则1、2、3外，还应遵从以下准则：外，还应遵从以下准则： 准则准则4 尽量使各组的停留时间相等尽量使各组的停留时间相等. 用上述原则在下图用上述原则在下图上将图分为上将图分为4组，同组，同时计算时计算各组的停留时间各组的停

62、留时间,然后用算法一算出各组的近似最然后用算法一算出各组的近似最最佳旅行售货员巡回，得出路线长度及行走时间最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间从而得出完成巡视的近似最佳时间. 用算法一用算法一计计计算时，初始圈的输入与分三组时同样处理计算时，初始圈的输入与分三组时同样处理.这这4组的近似最优解见表组的近似最优解见表3.目录下页返回上页结束表表3符号说明：加有底纹的表示前面经过并停留过符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留此次只经过不停留;加框的表示此点只经过不停留加框的表示此点只经过不停留. 可看出可看出,表表3分组的均衡度很好分组的均衡度很好,且完全满足且完全满足24小时完成巡视的要求小时完成巡视的要求. 该分组实际均衡度该分组实际均衡度 4.62% 再见目录下页返回上页结束