《图论方法建模》PPT课件.ppt

2020 3 26 第十二讲图与网络建模方法 图与网络建模方法 漳州师范学院数学建模课件 2020 3 26 主要内容 匹配问题 旅行商问题 最小生成树问题 最大流问题 最小费用最大流问题 2020 3 26 三 最小生成树问题 Kruskal算法构造最小生成树 2020 3 26 三 最小生成树问题 调用leasttree 2 m的m函数文件 命令形式 leasttree 2 a 功能 a是权矩阵 该矩阵中的主对角全部是0 并且不包含重复的权 返回树的节点和权值 2020 3 26 三 最小生成树问题 例12用Kruskal算法求右图的最小生成树 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 leasttree 2 a 2020 3 26 三 最小生成树问题 调用mintreek m的m函数文件 命令形式 a b mintreek n w 功能 w是权矩阵 该矩阵中的主对角全部是inf n是顶点数 a返回最小生成树的权的总长度 b是返回其具体的节点 并最终返回最小生成树的图形 2020 3 26 三 最小生成树问题 例13用Kruskal算法求右图的最小生成树 M Inf a1 M 50 60 M M M M a2 50 M M 65 40 M M a3 60 M M 52 M M 45 a4 M 65 52 M 50 30 42 a5 M 40 M 50 M 70 M a6 M M M 30 70 M M a7 M M 45 42 M M M w a1 a2 a3 a4 a5 a6 a7 n 7 a b mintreek n w 2020 3 26 三 最小生成树问题 调用kruskal m的m函数文件 命令形式 out len kruskal map 功能 map是输入矩阵 map 起点1终点1边长1 起点2终点2边长2 起点n终点n边长n out 输出边阵 起点终点 len 输出最小生成树的总长度 并最终返回最小生成树的图形 2020 3 26 三 最小生成树问题 例14用Kruskal算法求右图的最小生成树 a1 1250 1360 a2 2465 2540 a3 3452 3745 a4 4550 4630 4742 a5 5670 map a1 a2 a3 a4 a5 out len kruskal map 2020 3 26 三 最小生成树问题 例15用Kruskal算法求右图的最小生成树 a1 1250 1360 a2 2465 2540 a3 3452 3745 a4 4550 4630 4742 a5 5670 map a1 a2 a3 a4 a5 out len kruskal map 2020 3 26 四 匹配问题 例指派问题 图的匹配 2020 3 26 这个问题可以用图的语言描述 其中表示工人 表示工作 边表示第i个人能胜任第j项工作 这样就得到了一个二部图G 用点集X表示 点集Y表示 二部图G X Y E 上述的工作分配问题就是要在图G中找一个边集E的子集 使得集中任何两条边没有公共端点 最好的方案就是要使此边集的边数尽可能多 这就是匹配问题 四 匹配问题 2020 3 26 二分图的概念 二分图又称作二部图 是图论中的一种特殊模型 设G V R 是一个无向图 如顶点集V可分割为两个互不相交的子集 并且图中每条边依附的两个顶点都分属两个不同的子集 则称图G为二分图 四 匹配问题 2020 3 26 最大匹配 给定一个二分图G 在G的一个子图M中 M的边集 E 中的任意两条边都不依附于同一个顶点 则称M是一个匹配 选择这样的边数最大的子集称为图的最大匹配问题 如果一个匹配中 图中的每个顶点都和图中某条边相关联 则称此匹配为完全匹配 也称作完备匹配 四 匹配问题 2020 3 26 匈牙利算法 求最大匹配的一种显而易见的算法是 先找出全部匹配 然后保留匹配数最多的 但是这个算法的复杂度为边数的指数级函数 M中任意一条边的端点v称为 关于M的 饱和点 G中其他定点称为非饱和点 若P是图G中一条连通两个未匹配顶点的路径 并且属M的边和不属M的边 即已匹配和待匹配的边 在P上交替出现 则称P为相对于M的一条增广路径 四 匹配问题 2020 3 26 结论 P的路径长度必定为奇数 第一条边和最后一条边都不属于M M为G的最大匹配当且仅当不存在相对于M的增广路径 四 匹配问题 2020 3 26 四 匹配问题 2020 3 26 例1求二部图G中的最大匹配 X1 Y1 Y2 Y3 Y4 X2 X3 X4 四 匹配问题 2020 3 26 四 匹配问题 2020 3 26 最大匹配就是 X1 Y1 Y2 Y3 Y4 X2 X3 X4 四 匹配问题 2020 3 26 四 匹配问题 调用pipei m的m函数文件 格式 e total pipei d 功能 d是二部图矩阵 0 1矩阵 e 输出匹配的路径 total 最大匹配的边数 d 0100 1101 0110 0110 e total pipei d 2020 3 26 最佳匹配 如果边上带权 找出权和最大的匹配叫做求最佳匹配 实际模型 某公司有职员x1 x2 xn 他们去做工作y1 y2 yn 每个职员做各项工作的效益未必一致 需要制定一个分工方案 使得人尽其才 让公司获得的总效益最大 数学模型 G是加权完全二分图 求总权值最大的完备匹配 四 匹配问题 2020 3 26 KM算法 穷举的效率 n 我们需要更加优秀的算法 定理 设M是一个带权完全二分图G的一个完备匹配 给每个顶点一个可行顶标 第i个x顶点的可行标用lx i 表示 第j个y顶点的可行标用ly j 表示 如果对所有的边 i j inG 都有lx i ly j w i j 成立 w i j 表示边的权 且对所有的边 i j inM 都有lx i ly j w i j 成立 则M是图G的一个最佳匹配 四 匹配问题 2020 3 26 KM算法 对于任意的G和M 可行顶标都是存在的 l x maxw x y l y 0欲求完全二分图的最佳匹配 只要用匈牙利算法求其相等子图的完备匹配 问题是当标号之后的Gl无完备匹配时怎么办 1957年 Kuhn和Munkras给出了一个解决该问题的有效算法 用逐次修改可行顶标l v 的办法使对应的相等子图之最大匹配逐次增广 最后出现完备匹配 四 匹配问题 2020 3 26 四 匹配问题 例2考虑完全的2部图 其中 边上的权如下矩阵 2020 3 26 修改方法如下 先将一个未被匹配的顶点u uin x 做一次增广路 记下哪些结点被访问那些结点没有被访问 求出d min lx i ly j w i j 其中i结点被访问 j结点没有被访问 然后调整lx和ly 对于访问过的x顶点 将它的可行标减去d 对于所有访问过的y顶点 将它的可行标增加d 修改后的顶标仍是可行顶标 原来的匹配M仍然存在 相等子图中至少出现了一条不属于M的边 所以造成M的逐渐增广 四 匹配问题 2020 3 26 KM算法步骤 Kuhn Munkras算法流程 1 初始化可行顶标的值 2 用匈牙利算法寻找完备匹配 3 若未找到完备匹配则修改可行顶标的值 4 重复 2 3 直到找到相等子图的完备匹配为止 四 匹配问题 2020 3 26 四 匹配问题 调用km m的m函数文件 命令形式 M MaxZjpp km A n 功能 A是输入二部图的权矩阵 n是匹配点 M 输出匹配矩阵 MaxZjpp 输出最优匹配的总长度 A 35541 22022 24410 01100 12133 M MaxZjpp km A 5 2020 3 26 五 旅行商问题 Euler图和Hamilton图 2020 3 26 五 旅行商问题 Euler图和Hamilton图 2020 3 26 五 旅行商问题 例5旅行商问题 网络流 2020 3 26 五 旅行商问题 2020 3 26 五 旅行商问题 调用tsp m的m函数文件 命令形式 circle sum tsp a c1 c2 功能 a是输入的权矩阵 c1是开始的圈 c2是改变的圈 circle 输出经过的点 sum 输出最优的总长度 2020 3 26 五 旅行商问题 2020 3 26 五 旅行商问题 a 1 2 56 a 1 3 35 a 1 4 21 a 1 5 51 a 1 6 60 a 2 3 21 a 2 4 57 a 2 5 78 a 2 6 70 a 3 4 36 a 3 5 68 a 3 6 68 a 4 5 51 a 4 6 61 a 5 6 13 a 6 0 a a a c1 51 46 c2 561 4 circle sum tsp a c1 c2 2020 3 26 六 最大流问题 网络中的流 2020 3 26 六 最大流问题 例如 2020 3 26 六 最大流问题 网络中的流 2020 3 26 六 最大流问题 网络中的流 2020 3 26 六 最大流问题 最大流 2020 3 26 六 最大流问题 最大流的标号算法 调用ford m的m函数文件 命令形式 f wf ford C n 功能 C是输入的容量矩阵 n是总的顶点数 f 输出最大流矩阵 wf 输出最大流量 2020 3 26 六 最大流问题 例4求下图中的最大流 2020 3 26 六 最大流问题 n 8 c1 05430000 00005300 c2 00000320 00000020 c3 00000004 00000003 c4 00000005 00000000 C c1 c2 c3 c4 f wf ford C n 2020 3 26 六 最大流问题 最小费用最大流 2020 3 26 六 最大流问题 例如 2020 3 26 六 最大流问题 最小费用最大流 调用mford m的m函数文件 命令形式 f wf zwf mford C