第18讲 最短路与最优问题.ppt

算法原理—— 求距离矩阵的方法 返回 算法原理—— 求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R． 即当　k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径． 返回 ) ( n R i j 算法原理—— 查找最短路路径的方法 pk p2 p1 p3 q1 q2 qm 则由点i到j的最短路的路径为： 返回 算法步骤 TO　MATLAB　(road2(floyd)) 返回　 一、 可化为最短路问题的多阶段决策问题 二、 选 址 问 题 1． 中心问题 2． 重心问题 返回 可化为最短路问题的多阶段决策问题 返回 选址问题--中心问题 TO MATLAB　(road3(floyd)) S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=10, S(v5)=7, S(v6)=7, S(v7)=8.5 S(v3)=6,故应将消防站设在v3处. 返回 选址问题--重心问题 返回 匹配 匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想. 定义1.设G=V,E是无环图,M?E(G),M??,若M中任意两条边都不相邻,则称M是图G的一个匹配.若对图G的任何匹配M’ ,均有?M’? ?M?,则称M是图G的最大匹配,记作?’(G). 定义2.设M是图G的匹配,G中与M中的边关联的顶点称为M饱和点.若图G的顶点都是M饱和,则称为G的完美匹配. 说明:(1)完美匹配是最大匹配,反之未然; (2)匹配的定义与边的方向无关,故匹配是针对无向图而言. (3)图G的边不交匹配的最小数目即为G的边色数. 定义3.(可增广路):设M是图G的匹配,P是G的一条路,且在P中,M的边和E(G)-M的边交替出现,则称P是G的一条交错路.若M交错路P的两个端点为M非饱和点,则称P为M可增广路. 例1.求下图G的一条交错路和一条可增广路. 6 2 3 4 1 5 8 7 匹配的几个性质定理 定理1.设M1和M2是图G的两个不同匹配,由M1?M2导出的G 的边导出子图记作H,则H的任意连通分支是下列情况之 一:(1)边在M1和M2中交错出现的偶圈. (2)边在M1和M2中交错出现的路. 证明:记H= M1?M2,因为H是边导出子图,所以?(H)≥1.由 于M1和M2是图G的两个不同匹配,所以H的任意顶点x至多 与一条M1的边关联,同时也至多与一条M2的边关联,所以 Deg(x)≤2,所以? ≤2,故H的每个连通分支或者是一条路 或者是一个圈.据匹配的定义,H的任意两条邻接边一定分 别属于不同的匹配M1和M2,从而每条路或者圈的边交错 地属于M1和M2且每个圈是偶圈. 定理2.M是图G的最大匹配,当且仅当G中不存在M可增广路. 证明:(?)假设存在M可增广路P,则M’=M?P是G的一个新的匹配,且|M’|＝|M|＋1|M|,矛盾. (?)若M不是G的最大匹配,则存在匹配M’,使得|M’||M|,作H=M’?M,由定理1,H的任意边导出子图Q是下列两种情况之一:(1)交错偶圈:Q中每个结点度数为2.(2)交错路.Q中除端点外,其余结点度数均为2. 因为|M’||M|,故|E(H)?M’||E(H)?M|,因而H中必有一条起始于M’且终止于M’的连通分支P,故P是M可增广路,矛盾,所以命题正确. 定义:NG(S):设S是图G的任意顶点子集,G中与S的顶点邻接的所有顶点的集合,称为S的邻集,记做NG(S). 定理3(Hall定理,1935)设G是有二部划分(V1,V2)的二分图, 则G含有饱和V1的每个顶点的匹配M的充要条件是,对?S?V1,有?N(S)???S?. 证明:(?)对?S?V1,匹配M将S中的每个顶点与N(S)中的顶 点配对,所以?N(S)???S?. (?)当对?S?V1,有?N(S)???S?时.可按下述方法作出饱和V1的匹配M. 先作一初始匹配M1,若已经饱和V1,定理得证.否则,V1中至少有一非饱和点x1,检查以x1为起点,终点在V2中的交错路.考虑下面两种情形: (1)不存在任何一条交错路可以到达V2的非饱和点.此时从X1开始的一切交错路的终点还是在V1中.故存在A?V1,使得?N(A)??A?,矛盾. (2)存在一条以x1为起点,终点为V2的非饱和点的交错路P,显然P是可增广路,作新匹配M2=M1?P,则M2饱和x1,且?M2??M1?,因此,重复该过程就可以找到饱和V1的全部顶点的匹配M. 1.图论问题的起源 18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相