《数学建模提高班第六讲-网络优化模型及案例分析.ppt》由会员分享，可在线阅读，更多相关《数学建模提高班第六讲-网络优化模型及案例分析.ppt（94页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、网络优化模型及案例分析网络优化模型及案例分析赵承业赵承业 2011/4/2 2011/4/24 4本专题学习目的本专题学习目的掌握把实际问题转化为图或网络问题的方法了解图的基本概念和矩阵表示方法掌握最短路问题、最小生成树问题的算法了解旅行商问题主要内容主要内容主要内容主要内容图论的起源：七桥问题图论的起源：七桥问题 c a b d c a b d 图论的起源：七桥问题图论的起源：七桥问题图1图2欧拉图论之父 定理1：一个图存在通过每边正好一次回到出发点的路线的充要条件是：1）图要是连通连通的2）与图中每一顶点相连的边必须是偶数偶数条。于是得出结论：七桥问题无解。图论的起源：七桥问题图论的起源：
2、七桥问题返返返返 回回回回无向图，一般用大写字母G,H表示。一种表示工具一种表示工具图图顶点顶点边边 d c a b 图3 无向图：G=(V,E)，顶点集：V；边集：E。e与顶点u,v相关联。u与v相邻。两边相邻。重边 c a b d 一种表示工具一种表示工具图图图4两种特殊图：简单图 完全图，记为Knb d c a b d c a 一种表示工具一种表示工具图图图6图5有向图：V1V2V3V5V4你能给出一个可用有向图描述的实际例子吗？一种表示工具一种表示工具图图图7网络网络这些数字可以代表距离距离，费用费用，可可靠性靠性或其他的相关参数。12345869157103一种表示工具一种表示工具图
3、图图8(G)和(G)分别表示图G的顶点数和边数在无向图中，v的度数，记为d(v)；在有向图中，v的出度，记为d+(v);v的入度，记为d-(v)。一种表示工具一种表示工具图图返返返返 回回回回一个时间安排问题一个时间安排问题 学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。一个时间安排问题一个时间安排问题表1SNGRPM完成上述表示课程冲突关系的图直观、清晰地表达已知信息的方式一个时间安
4、排问题一个时间安排问题返返返返 回回回回图9人狼羊菜渡河问题人狼羊菜渡河问题摆渡人F狼W羊G菜C图10 南岸状态：16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：人狼羊菜渡河问题人狼羊菜渡河问题FWGCFWG FWC FGCFGOCGWWC寻求图中从顶点“FWGC”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。语言描述时未显示的关系跃然纸上人狼羊菜渡河问题人狼羊菜渡河问题图11FWGCFWG FWC FGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC人狼羊菜渡河问题人狼羊菜渡河问题返返返返
5、回回回回图12图的矩阵表示方法图的矩阵表示方法邻接矩阵关联矩阵边矩阵邻接顺序表返返返返 回回回回v1v2v5v6v7v4v3abjkcghidfe邻接矩阵图13 无向图的邻接矩阵：A=(aij)nn，其中无向图的邻接矩阵有何特点？由邻接矩阵是否能作出原图？邻接矩阵返返返返 回回回回关联矩阵v1v2v5v6v7v4v3abjkcghidfe图13 无向图的关联矩阵：M=(mij)nm,其中 无向图的关联矩阵有哪些特征？由关联矩阵能否作出原图？关联矩阵返返返返 回回回回边矩阵v1v2v5v6v7v4v3abjkcghidfe返返返返 回回回回图13最短路问题及算法最短路问题及算法 最短路问题是图论
6、应用的基本问题，很多实际最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法.1)1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路.2)求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.2)在赋权图在赋权图G中，从顶点中，
7、从顶点u到顶点到顶点v的具有最小权的具有最小权定义定义1 1)若若H是赋权图是赋权图G的一个子图，则称的一个子图，则称H的各的各边的权和边的权和 为为H的的权权.类似地，若类似地，若称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3)把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v).1)赋权图中从给定点到其余顶点的最短路赋权图中从给定点到其余顶点的最短路 假设假设G为赋权有向图或
8、无向图，为赋权有向图或无向图，G边上的权均非边上的权均非负若负若 ，则规定，则规定 最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路例例 求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点的最短路到其余顶点的最短路图14Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijk
9、stra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若
10、，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达
11、到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每
12、个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其
13、余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，
14、并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).Dijkstra算法算法:求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路.1)置置 ，对，对 ，且且 .2)对每个对每个 ，用，用代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的一个顶点记为一个顶点记为 ，置，置
15、 3)若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代替替i，并转，并转2).定义2 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱点点，记为，记为z(v),即即z(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径.例例5的标号过程也的标号过程也可按如下方式进行：可按如下方式进行：首先写出左图带权邻接矩阵首先写出左图带权邻接矩阵因因G是无向图，故是无向图，故W是对称阵是对称阵表2续表2图82)求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路算法的基本
16、思想（I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.（III）查找最短路路径的方法）查找最短路路径的方法.Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.举例说明举例说明算法的基本思想算法的基本思想（I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：图16（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的
17、最短路.例例 2求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径.图17插入点插入点 v1，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.插入点插入点 v2，得：得：矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.插入点插入点 v3，得：得：插入点插入点 v4，得：得：插入点插入点 v5，得：得：插入点插入点 v6，得：得：故从故从v5到到v2的最短路为的最短路为8 由由v6向向v5追溯追溯:由由v6向向v2追溯追溯:所以从到的最短路径为：所以从到的最短路径为：返返返返 回回回
18、回最小生成树及算法最小生成树及算法许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。1)树的定义与树的特征定义定义3 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示.树中的边称为树中的边称为树枝树枝.树中度为树中度为1的顶点称为的顶点称为树叶树叶.孤立顶点称为孤立顶点称为平凡树平凡树.平凡树平凡树图18定理定理2 设设G是具有是具有n个顶点的图，则下述命题等个顶点
19、的图，则下述命题等价：价：1)G是树（是树（G无圈且连通）；无圈且连通）；2)G无圈，且有无圈，且有n-1条边；条边；3)G连通，且有连通，且有n-1条边；条边；4)G无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即连通，且删去一条边就不连通了（即G为为最最最小连通图最小连通图）；）；6)G中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.2）图的生成树）图的生成树定义定义4 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的的生成树生成树.图图G中不在生成树的边叫做中不在生成树的边
20、叫做弦弦.定理定理3 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.证明证明 必要性必要性是显然的是显然的.（II）找图中生成树的方法）找图中生成树的方法可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法破圈法 A 避圈法避圈法 定理定理3的充分性的证明提供了一种构造图的生的充分性的证明提供了一种构造图的生成树的方法成树的方法.这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一中，每步选出一条边使它与已选边不构成圈，直到选够条边使它与已选边不构成圈，直到选够n-1条边为条边为止止.这种
21、方法可称为这种方法可称为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边的选法不同，找图中生在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：成树的方法可分为两种：深探法深探法和和广探法广探法.a)深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边vw之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点
22、得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边vw.令令例例3用深探法求出下图用深探法求出下图10的一棵生成树的一棵生成树 图19012345678910111213图203b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.对所有未对所有未标标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号0.Vi,检查检查Vi,VV
23、i中的边端点中的边端点边边.例例4用广探法求出下图用广探法求出下图10的一棵生成树的一棵生成树 图191012213212234标号为止标号为止.图21B 破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈法破圈法”.这种方法就是在图这种方法就是在图G中任取一个圈，中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤任意舍弃一条边，将这个圈破掉，重复这个步骤直到图直到图G中没有圈为止中没有圈为止.例例5 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.图22B B 破圈法破圈法例例6 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一
24、棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的.图233)最小生成树与算法最小生成树与算法 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法.5A Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下：1)选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2)若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)的尽可能小的权，的尽可能小的权，3)当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止.定理定理4 由由Kruskal算
25、法构作的任何生成树算法构作的任何生成树都是最小树都是最小树.例例7用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值最小的边有最小的边有 任取一条任取一条 在在 中选取权值中选取权值最小的边最小的边 中权值最小边有中权值最小边有 ,从中选从中选任取一条边任取一条边会与已选边构成圈会与已选边构成圈,故停止故停止,得得中选取在中选取中选取在中选取 中选取中选取 .但但 与与 都都图24B破圈法算法算法2 步骤如下：步骤如下：1)从图从图G中任选一棵树中任选一棵树T1.2)加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈.去掉此去掉此 圈中最大权
26、边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止.例例8 用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树.加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全全部的弦均已试过全部的弦均已试过,得最小树得最小树.
27、返返返返 回回回回图25旅行售货员问题旅行售货员问题 定义定义6设设G=(V,E)是连通无向图，包含图是连通无向图，包含图G的每个的每个顶点的路称为顶点的路称为G的的哈密尔顿路哈密尔顿路(Hamilton路路或或H路路).包含图包含图G的每个顶点的圈，称为的每个顶点的圈，称为G的的哈密尔顿圈哈密尔顿圈(或或Hamilton圈圈或或H圈圈).含含Hamilton圈的图称为圈的图称为哈密尔顿图哈密尔顿图(或或Hamilton图图或或H图图).旅行售货员问题或货郎担问题旅行售货员问题或货郎担问题 一个旅行售货员想去访问若干城镇，然后回一个旅行售货员想去访问若干城镇，然后回到出发地到出发地.给定各城镇
28、之间的距离后，应怎样计划给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？而总距离最小？它可归结为这样的它可归结为这样的图论问题：图论问题：在一个赋权完在一个赋权完全图中全图中,找出一个最小权的找出一个最小权的H圈圈,称这种圈为称这种圈为最优圈最优圈.但这个问题是但这个问题是NP-hard问题，即不存在多项式问题，即不存在多项式时间算法时间算法.也就是说也就是说,对于大型网络对于大型网络(赋权图赋权图),目前还目前还没有一个求解旅行售货员问题的有效算法，因此没有一个求解旅行售货员问题的有效算法，因此只能找一种求出
29、相当好（不一定最优）的解只能找一种求出相当好（不一定最优）的解.一个可行的办法一个可行的办法:是先求一个是先求一个H圈圈,然后适当然后适当修改修改,以得到具有较小权的另以得到具有较小权的另一个一个H圈圈.图26定义7 若对于某一对若对于某一对i和和j，有，有则圈则圈Cij将是圈将是圈C的一个的一个改进改进.定义定义8 二边逐次修正法二边逐次修正法:在接连进行一系列修改之后在接连进行一系列修改之后,最后得一个圈最后得一个圈,不能不能再用此方法改进了，这个最后的圈可能不是最优的再用此方法改进了，这个最后的圈可能不是最优的,但是它是比较好的，为了得到更高的精度，这个但是它是比较好的，为了得到更高的精
30、度，这个程序可以重复几次，每次都以不同的圈开始程序可以重复几次，每次都以不同的圈开始.这种这种方法叫做方法叫做二边逐次修正法二边逐次修正法.例例9 对下图对下图,用二边逐次修正法求较优用二边逐次修正法求较优H圈圈.较优较优H圈圈:其权为其权为W(C3)=192图27 分析分析:找出的这个解的好坏可用最优找出的这个解的好坏可用最优H圈的权圈的权的下界与其比较而得出的下界与其比较而得出.即利用最小生成树可得最即利用最小生成树可得最优优H圈的一个下界，圈的一个下界，方法如下方法如下：设设C是是G的一个最优的一个最优H圈，则对圈，则对G的任一顶点的任一顶点v,C-v是是G-v的路，也的路，也G-v是的
31、生成树是的生成树.如果如果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(v1v3)+w(v2v3)=178.故最优故最优H圈的权圈的权v1v3和和v2v3,故故w(C)应满足应满足178 w(C)192.返返返返 回回回回1.1.设设某某校校的的田田径径选选拔拔赛赛共共设设六六个个项项目目的的比比赛赛
32、，即即跳跳高高，跳跳远远，标标枪枪，铅铅球球，100100米米和和200200米米短短跑跑，规规定定每每个个选选手手至至多多参参加加三三个个项项目目的的比比赛赛。现现有有七七名名选选手手报报名名，选选手手所所选选项项目目如如表表1 1所所示示。现现在在要要求求设设计计一一个个比比赛赛日日程程安安排排表表，使得在尽可能短的时间内完成比赛使得在尽可能短的时间内完成比赛。田径赛的时间安排练习题练习题表1 参赛选手比赛项目表 附录：图论算法的附录：图论算法的matlab实现实现最短路问题最短路问题例 某公司在六个城市中有分公司，从ci到cj的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助
33、该公司设计一张城市c1到其它城市间的票价最便宜的路线图。用矩阵 （为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、index2、d分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 index2(i)存放始点到第点最短通路中第顶点前一顶点的序号；d(i)存放由始点到第点最短通路的值。Dijkstra 的Matlab程序如下：M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zer
34、os(1,5),55;a(6,:)=zeros(1,6);a=a+a;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);end index2(temp)=index;endd,index1,index2 Floyd算法的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,
35、3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);b=a+a;path=zeros(length(b);for k=1:6 for i=1:6 for j=1:6 if b(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;end end endendb,path最小生成树问题最小生成树问题prim算法如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,
36、7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresultKruskal算法如下：clc;clear;M=1000
37、;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=find(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号改记为此边的另一序号，同时把后面边中所有序号为的改记为。此方法的几何意义是：将序号的这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。while length(result)v2 index(find(index=v1)=v2;else index(find(index=v2)=v1;end data(:,flag)=;index(:,flag)=;endresult