图论模型[行业知识]

1、下下 回回 停停 1. 问题引入与分析问题引入与分析 2. 图论的基本概念图论的基本概念 3. 最短路问题及算法最短路问题及算法 第二讲第二讲 图论模型图论模型 4. 最小生成树及算法最小生成树及算法 5. 旅行售货员问题旅行售货员问题 6. 模型建立与求解模型建立与求解 1. 问题引入与分析问题引入与分析 1) 98 1) 98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题“最佳灾最佳灾 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾. 为考察灾情、为考察灾情、 组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视

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

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

4、总权（路程或时间）最小. 公路的长度（或行驶时间）看作对应边上的权，所公路的长度（或行驶时间）看作对应边上的权，所 给公路网就转化为加权网络图，问题就转化图论中给公路网就转化为加权网络图，问题就转化图论中 一类称之为旅行售货员问题，即在给定的加权网络一类称之为旅行售货员问题，即在给定的加权网络 图中寻找从给定点图中寻找从给定点O出发，行遍所有顶点至少一次出发，行遍所有顶点至少一次 如第一问是三个旅行售货员问题，第二问是四如第一问是三个旅行售货员问题，第二问是四 本题是旅行售货员问题的延伸本题是旅行售货员问题的延伸多旅行售货员问题多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是本题所求的

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

6、的问题可使用近似算法来求得近似最优解的问题可使用近似算法来求得近似最优解. 2.图论的基本概念图论的基本概念 1) 图的概念图的概念 2) 赋权图与子图赋权图与子图 3) 图的矩阵表示图的矩阵表示 4) 图的顶点度图的顶点度 5) 路和连通路和连通 1) 图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中: 其中元素称为图其中元素称为图G的的顶点顶点. 组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边. ),( ji vv 定义定义 图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|, 用用来表示；来表示；v 图

7、的边的数目图的边的数目|E(G)|用用 来表示来表示. 也用也用来表示边来表示边 jiv v).,( ji vv ,)( 21 vvvGV是非空有限集，称为是非空有限集，称为顶顶点集点集，1) 2) E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对 ).,(EVG )(),(GEGVG 表示图，表示图，简记简记 用用 定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图. 只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图都称为所有图都称为非平凡图非平凡图. 定义若若图图G中的边均为有

8、序偶对中的边均为有序偶对,称称G为为有向有向),( ji vv 边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称 图图. 称边称边 为为有向边有向边或或弧弧,称称),( ji vve 是从是从),( ji vve i v 连接连接 j v，称，称 为为e的的尾尾，称，称 为为e的的头头. i v j v 若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称 jiv v 为为e的的端点端点. jiv ve i v j v i v j v 既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图. 常用术语常用术语 1) 边和它的两端

9、点称为互相边和它的两端点称为互相关联关联. 2)与同一条边关联的两个端点称与同一条边关联的两个端点称 为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合为一点的边称为端点重合为一点的边称为环环， 端点不相同的边称为端点不相同的边称为连杆连杆. 4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边 5) 既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 常用术语常用术语 6) 任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图.

10、 记为记为Kv. 7) 若若 ， ，且且X 中任意两顶点不中任意两顶点不YXGV)(YX ， 相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为 完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|) nm K , 8) 图图 叫做叫做星星. n K , 1 :X 1 x 2 x 3 x :Y1 y 2 y 3 y 4 y 二部图二部图 6 K :X 1 x 2 x 3 x :Y1 y 2 y 3 y 4 y4 , 1 K 4 , 3 K 2) 2

11、) 赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都赋以都赋以)(),(GEGVG 一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权 称为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图.),(EVG ),(EVG 1) 若若 ,称称 是是 的一个的一个子图子图,记记 EEVV, G G.GG 2) 若若 ， ，则称，则称 是是 的的生成子图生成子图.VV EE G G 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV V V 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的

12、子图，称 V G 为为 的的由由 导出的子图导出的子图，记为，记为 .G V VG 4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE E E E 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GG E 边导出的子图边导出的子图，记为，记为 . EG , 321 vvvG, 6543 eeeeG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV V V 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 V G 4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE E E

13、E 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GG E 边导出的子图边导出的子图，记为，记为 . EG G V VG 为为 的的由由 导出的子图导出的子图，记为，记为 . 3) 3) 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵: 1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： G )( ij aA ., 0 , 1 不相邻与若 相邻与若 ji ji ij vv vv a 5 4 3 2 1 54321 00100 00100 11011 00101 00110 v v v v v A vvvvv (以下均假设图为简单图以下均假设图为简单图

14、). 2) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： )( ij aA),(EVG .),(, 0 ,),(, 1 Evv Evv a ji ji ij 若 若 4 3 2 1 4321 0100 0010 0000 1110 u u u u A uuuu 其中：其中： 3) 对有向赋权图对有向赋权图 , 其邻接矩阵其邻接矩阵 , )( ij aA),(EVG .),(, ,0 ,),(, Evv ji wEvvw a ji ijjiij ij 若 ， 为其权，且若 4 3 2 1 4321 04 06 0 8730 u u u u A uuuu 对于无向赋权图的邻接矩阵可类似

15、定义对于无向赋权图的邻接矩阵可类似定义. 关联矩阵关联矩阵 1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,),(EVG )( ij mM 其中：其中： ., 0 , 1 不关联与若 相关联与若 ji ji ij ev ev m 5 4 3 2 1 54321 10000 01000 11110 00101 00011 v v v v v M eeeee 2) 对有向图对有向图 ，其关联矩阵，其关联矩阵 ,),(EVG )( ij mM ., 0 , 1 , 1 的头与尾不是若 的头是若 的尾是若 ji ji ji ij ev ev ev m 其中：其中： 4 3 2 1 54321 11

16、000 10110 00011 01101 u u u u M eeeee 4) 图的顶点度图的顶点度 定义定义 1) 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环 算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v). 称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点. 2) 在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点 v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v

17、). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度或或次数次数 定理定理 .2)( Vv vd 的个数为偶数的个数为偶数 推论推论 任何图中奇点任何图中奇点 4)( 1 vd 1)( 3 ud 2)( 3 ud 3)( 3 ud 5) 路和连通路和连通 定义定义1) 无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指 一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替 kkv eevevW 2110 地为顶点和边，使得对地为顶点和边，使得对 ， 的端点是的端点是 和和 ,ki 1 i e 1i v i v 称称W是从是从 到到 的一条的一条途径途

18、径，或一条，或一条 途径途径. 整整 0 v k v ),( 0k vv 数数k称为称为W的的长长. 顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点 ,0 v k v 而而 称为称为W的的内部顶点内部顶点. 121 , k vvv 2) 若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W 为为迹迹或或简单链简单链. 3) 若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路 或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路 0 v k v ),( 0k vv 记为记为).,( 0k vvP 定义定义 1)

19、途径途径 中由相继项构成子序列中由相继项构成子序列 kkv evevW. 110 称为途径称为途径W的的节节.jjiii vevev. 11 2) 起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径. 3) 起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长，长 为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck. 4) 若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G 中中连通连通. 5) 若在图若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之 之间的之间的距离距离d(u,v)是指图是指图G中最短中最短(u,

20、v)路的长；若没路的长；若没 没有路连接没有路连接u和和v，则定义为无穷大，则定义为无穷大. 6) 图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 7) 对于有向图对于有向图G，若，若 ，且，且 有有 kkv eevevW 2110 i e 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈. 头头 和尾和尾 ，则称，则称W为为有向途径有向途径. i v 1i v 例例 在右图中：在右图中： 途径或链：途径或链： 迹或简单链：迹或简单链： 路或路径：路或路径： 圈或回路：圈或回路： wugyexeyfxc yvbwcxdvaug uavdxcw uuav

21、bwcxfyg 3最短路问题及算法最短路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际 问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费 用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解. 最短路的定义最短路的定义 最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法 . 1) 求赋权图中从给定点到其余顶点的最短求赋权图中从给定点到其余顶点的最短 路路. . 2) 求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路. 2) 在赋权图在赋

22、权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的具有最小权 定义定义 1) 若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的各的各 边的权和边的权和 为为H的的权权. 类似地，若类似地，若 )( )()( HEe ewHw 称为路称为路P的的权权 若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称 )( )()( PEe ewPw 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3) 把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v) 路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v

23、). 1) 赋权图中从给定点到其余顶点的最短路赋权图中从给定点到其余顶点的最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非边上的权均非 负若负若 ，则规定，则规定 )(),(GEvu.),(vuw 最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路 求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点的最短路到其余顶点的最短路 Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，

24、用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 01 Su 10 ,min)( 1 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00

25、 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 01 Su 1)( 1 ul 02 Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(

26、 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 03 Su )( 3 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点

27、的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 04 Su )( 3 ul Dijkstra算法算法:

28、 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul

29、 7)( 4 ul 05 Su )( 3 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,

30、2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 7)( 4 ul )( 5 ul 06 Su )( 3 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停

31、止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul 7)( 4 ul )( 5 ul 4)( 6 ul 07 Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i S

32、v 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul )( 3 ul7)( 4 ul )( 5 ul4)( 6 ul 8)( 7 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulv

33、l ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 7,.,2 , 1,)(, 00 juluS j 1)( 1 ul2)( 2 ul )( 3 ul7)( 4 ul )( 5 ul4)( 6 ul )()(min 1 0 ulvl Sv 8)( 7 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对

34、，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). , 101 uuS 1)( 1 ul2)( 2 ul)( 3 ul 7)( 4 ul)( 5 ul 4)( 6 ul8)( 7 ul 12 Su 21 , 2min)

35、( 2 ul 2)( 2 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). , 101 uuS 1)

36、( 1 ul2)( 2 ul)( 3 ul 7)( 4 ul)( 5 ul 4)( 6 ul8)( 7 ul 12 Su 21 , 2min)( 2 ul 2)( 2 ul Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)( 0 ul 0 uv )(vl 00 uS 0i 2) 对每个对每个 ，用，用 i Sv),()(),(minvuwulvl ii 代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl )(minvl i Sv 一个顶点记为一个顶点记为 ，置，置 1i u. 11

37、 iii uSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i 替替i，并转，并转2). 定义 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v 0 u 的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱 点点，记为，记为z(v), 即即z(v)=w. 先驱点可用于追踪最短路径先驱点可用于追踪最短路径. 例例5的标号过程也的标号过程也 可按如下方式进行：可按如下方式进行： 首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵 02478 20634 46046 340357 63013 51022 73201

38、 847210 W 因因G是无向图，故是无向图，故W是对称阵是对称阵 1 u 0 u 6 u 7 u 2 u 4 u 3 u 5 u Dijkstra算法：算法：求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路 设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均均非负边上的权均均非负. 对每个顶点，定义两个标记（对每个顶点，定义两个标记（l(v)，z(v)），其中），其中: l(v) ：表从顶点表从顶点u0到到v的一条路的权的一条路的权 z(v) ：v的先驱点，用以确定最短路的路线的先驱点，用以确定最短路的路线. l(v)为从顶点为从顶点u0到到v的最短路的权的最短路

39、的权 算法的过程就是在每一步改进这两个标记，使最终算法的过程就是在每一步改进这两个标记，使最终 S：具有永久标号的顶点集：具有永久标号的顶点集. 输入输入: G的带权邻接矩阵的带权邻接矩阵 w(u,v) 备用备用-将求最短路与最短路径结合起来将求最短路与最短路径结合起来: 算法步骤：算法步骤： l(v) u0 v l(u) u w(u,v) 首先写出带权邻接矩阵首先写出带权邻接矩阵 02478 20634 46046 340357 63013 51022 73201 847210 W 例例 求下图从顶点求下图从顶点u0到到 其余顶点的最短路其余顶点的最短路 因因G是无向图，故是无向图，故W 是

40、对称阵是对称阵 1 u 0 u 6 u 7 u 2 u 4 u 3 u 5 u 见见Matlab程序程序-Dijkstra.doc 2) 求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路 算法的基本思想算法的基本思想 （I）求距离矩阵的方法）求距离矩阵的方法. （II）求路径矩阵的方法）求路径矩阵的方法. （III）查找最短路路径的方法）查找最短路路径的方法. Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路. 举例说明举例说明 算法的基本思想算法的基本思想 （I）求距离矩阵的方法）求距离矩阵的方法. （II）求路径矩阵的方法）求路径矩阵的方法. 在建立距离矩阵的

41、同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R i v j v （III）查找最短路路径的方法）查找最短路路径的方法. 然后用同样的方法再分头查找若：然后用同样的方法再分头查找若： 1 a v 2 a v 3 a v k a v 1 b v 2 b v m b v （IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路. 例例 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径. , 053142 503 3302 1204 4401 210 )0( D, 654321 654321 654321 654321 654321 654321

42、)0( R , 053142 503 3302 1204 4401 210 )0( D ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd插入点插入点 v1， ，得： 得： , 053132 503 3302 1204 3401 210 )1( D, 654311 654321 654321 654321 154321 654321 )1( R 矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素. ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd插入点插入点 v2， ，得： 得：

43、, 053132 503 3302 1204 3401 210 )1( D 矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素. , 053132 503 3302 12045 3401 2510 )2( D , 654311 654321 654321 654322 154321 654221 )2( R ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd , 053132 503 330267 12045 36401 27510 )3( D , 654311 654321 654333 654322 153321 6

44、53221 )3( R 插入点插入点 v3， ，得： 得： , 053132 503 3302 12045 3401 2510 )2( D ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd , 053132 503 330267 12045 36401 27510 )3( D 插入点插入点 v4， ，得： 得： , 053132 5035910 330267 152045 396401 2107510 )4( D , 654311 654444 654333 644322 143321 643221 )4( R , )4()5( DD 插入点插入点 v5

45、， ，得： 得： , )4()5( RR ,min ) 1() 1() 1()( k kj k ik k ij k ij dddd 插入点插入点 v6， ，得： 得： , 053132 5035910 330267 152045 396401 2107510 )5( D , 053132 503587 330265 152043 386401 275310 )6( D. 654311 654466 654336 644326 163321 666621 )6( R , 053132 503587 330265 152043 386401 275310 )6( D . 654311 654466

46、 654336 644326 163321 666621 )6( R 8 )6( 52 d 8 )6( 52 d故从故从v5到到v2的最短路为的最短路为8 6 )6( 52 R由由v6向向v5追溯追溯: . 6 )6( 56 R 由由v6向向v2追溯追溯: , 1 )6( 62 R. 2 )6( 12 R 所以从到的最短路径为：所以从到的最短路径为： . 2165 vvvv 见见Matlab程序程序-Floyd.doc 4最小生成树及算法最小生成树及算法 1 v 1) 树的定义与树的特征树的定义与树的特征 定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示. 树中

47、的边称为树中的边称为树枝树枝. 树中度为树中度为1的顶点称为的顶点称为树叶树叶. 孤立顶点称为孤立顶点称为平凡树平凡树. 2 v 3 v 4 v 5 v 平凡树平凡树 定理定理2 设设G是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价： 1) G是树（是树（ G无圈且连通）；无圈且连通）； 2) G无圈，且有无圈，且有n-1条边；条边； 3) G连通，且有连通，且有n-1条边；条边； 4) G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最 最小连通图最小连通图）；

48、）； 6) G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路. 2）图的生成树）图的生成树 定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树, 则称则称T是是G的的生成树生成树. 图图G中不在生成树的边叫做中不在生成树的边叫做弦弦. 定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的. 证明证明 必要性必要性是显然的是显然的. （II）找图中生成树的方法）找图中生成树的方法 可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法 : 深探法和广探法深探法和广探法 B 破圈法破圈法 A 避圈法避

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

50、标号为 步骤如下：步骤如下： i) 在点集在点集V中任取一点中任取一点u, ii) 若某点若某点v已得标号，检已得标号，检 端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给 w代代v，重复，重复ii). i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止. 给以标号给以标号0. 查一端点为查一端点为v的各边，另一的各边，另一 w以标号以标号i+1，记下边，记下边vw.令令 例例用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图10 0 12 3 4 5 6 78 9 1011 1213 13 a) 深探法深探法

51、 图10 0 12 3 4 5 6 78 9 1011 12 步骤如下：步骤如下： 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为 i) 在点集在点集V中任取一点中任取一点u, ii) 若某点若某点v已得标号，检已得标号，检 端是否均已标号端是否均已标号. 若有边若有边vw之之w未标号未标号,则给则给 w代代v，重复，重复ii). i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止. 给给u以标号以标号0. 查一端点为查一端点为v的各边，另一的各边，另一 w以标号以标号i+1，记下边，记下边vw.令令 例例用深探法

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

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

54、树的生成树 不唯一不唯一. B 破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做 “破圈法破圈法”. 这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈， 任意舍弃一条边，将这个圈破掉，重复这个步骤任意舍弃一条边，将这个圈破掉，重复这个步骤 直到图直到图G中没有圈为止中没有圈为止. 例例 用破圈法求出用破圈法求出 下图的一棵生成树下图的一棵生成树. B 破圈法 例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树. 不难发现，图不难发现，图 的生成树不是的生成树不是 唯一的唯一的 . 3) 最小生成树与算法最小生成树与算法 介绍最

55、小树的两种算法：介绍最小树的两种算法： Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法. A Kruskal算法（或避圈法）算法（或避圈法） 步骤如下：步骤如下： 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小； 2) 若已选定边若已选定边 ，则从，则从 i eee,., 21 ,., 21i eeeE 中选取中选取 ，使得，使得: 1i e i) 为无圈图，为无圈图，,., 121i eeeG ii) 是满足是满足i)的尽可能小的权，的尽可能小的权，)( 1i ew 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止. 定理定理4 由由Krus

56、kal算法构作的任何生成树算法构作的任何生成树 ,., 121 * eeeGT都是最小树都是最小树. , 876432 eeeeee 例例10用用Kruskal算法求下图的最小树算法求下图的最小树. 在左图中在左图中 权值权值 ,., 821 eee 最小的边有最小的边有 任取一条任取一条 , 51 ee, 1 e 在在 中选取权值中选取权值,., 832 eee , 5 e 最小的边最小的边 中权值最小边有中权值最小边有 , 从中选从中选 ： 73,e e ; 3 e 任取一条边任取一条边 , 87642 eeeee 会与已选边构成圈会与已选边构成圈,故停止故停止,得得 中选取在中选取中选取

57、在中选取, 7 e, 42 ee在 中选取中选取 . 但但 与与 都都 , 86 ee 84,e e 4 e 8 e B破圈法 算法算法2 步骤如下：步骤如下： 1) 从图从图G中任选一棵树中任选一棵树T1. 2) 加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈. 去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新 树树T2,以以T2代代T1,重复重复2)再再 检查剩余的弦，直到全检查剩余的弦，直到全 部弦检查完毕为止部弦检查完毕为止. 例例11用破圈法求下图的最小树用破圈法求下图的最小树. 先求出上图的一棵生成树先求出上图的一棵生成树. 加以弦加以弦 e2,得到的

58、圈得到的圈v1v3v2v1, 去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新 树仍是原来的树；树仍是原来的树； 2 e 再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4, 2 7 e 去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵 新树；如此重复进行，直到全新树；如此重复进行，直到全 全部的弦均已试过全部的弦均已试过,得得最小树最小树. 5. 旅行售货员问题旅行售货员问题 定义定义设设G=(V,E)是连通无向图，包含图是连通无向图，包含图G的每个的每个 顶点的路称为顶点的路称为G的的哈密尔顿路哈密尔顿路(Hamilton路路或或H路路). 包含图包含图G的每个顶点的圈，称为

59、的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈 (或或Hamilton圈圈或或H圈圈). 含含Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图(或或Hamilton 图图或或H图图). 旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题. 一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回 到出发地到出发地.给定各城镇之间的距离后，应怎样计划给定各城镇之间的距离后，应怎样计划 他的旅行路线，使他能对每个城镇恰好经过一次他的旅行路线，使他能对每个城镇恰好经过一次 而总距离最小？而总距离最小？ 它可归结为这样的它可归结为这样的图论问题：图论问题：在一个赋权完在一

60、个赋权完 全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为称这种圈为最优圈最优圈. 但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式 时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前还目前还 没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此 只能找一种求出相当好（不一定最优）的解只能找一种求出相当好（不一定最优）的解. 一个可行的办法一个可行的办法 : 是先求一个是先求一个H圈圈,然后适当然后适当 修改修改,以得到具有较小权的另以得到具有较小权的另 一个一个H圈圈. 定义 若对于