六中国邮递员问题.pptx

Euler circuit and Chinese Postman Problem歌尼斯堡七桥难题普莱格尔河结论：不存在这样一种走法。用A、B表示两座小岛，C、D表示两岸，连线AB表示A、B之间有一座桥。问题简化为：ABCD在该图中，从任一点出发，能否通过每条线段一次且仅仅一次后又回到原来的出发点七桥问题的数学模型：类似的问题：一笔画问题字的一笔画：如“中、日、口、串”等可一笔画而：“田、目”等不能一笔画图的一笔画：可一笔画不可一笔画6.6.1 欧拉图与中国邮递员问题开链一笔画问题圈存在欧拉回路：该图特点：该图不存在欧拉回路 欧拉图定理 无向连通图G为欧拉图的 充要条件是G中无奇点已知G=（V,E)为欧拉图，即存在一条欧拉回路C，C经过G的每一条边，由于G为连通图，所以G中的每个点至少在C中出现一次证明：必要性充分性：若无向连通图G=(V,E)中无奇点，则G为欧拉图例：例：判断下图是否为欧拉图，若是，求出欧拉回路推论 无向连通图G有欧拉道路的充要条件 是G中恰有两个奇点一笔画问题：1、一个连通图的顶点都是偶点，没有奇点，则该图 可以一笔画出2、一个连通图的顶点恰有两个奇点，其余均为偶点，则从任一奇点出发，可以一笔画出该图，而终点 则是另一个奇点。（从任一点出发均可）3、一个连通图的顶点有两个以上的奇点，则该图 不能一笔画出田日中白回不连通可一笔画可一笔画不可一笔画可一笔画可一笔画不可一笔画不可一笔画6.6.2 中国邮路问题提出问题的人：管梅谷教授时间：1962年提出的问题：一个邮递员从邮局出发分送邮件，要走完他负责投递的所有街道，最后再返回邮局，应如何选择投递路线，才能使所走的路线最短？邮路问题的图论描述：取一无向赋权连通图G=（V，E）E中的每一条边对应一条街道每条边的非负权l(e)=街道的长度V中某一个顶点为邮局，其余为街道的交叉点在G上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小1、若G中的顶点均为偶点，即G中存在欧拉回路，则该回路过每条边一次且仅一次，此回路即为所求的投递路线邮路问题的图论描述：在无向连通赋权G=（V，E）上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小2、G中有奇点：不存在欧拉回路投递路线：至少有一街道要重复走一次或多次即不存在每条街道走一次且只走一次的投递路线分析：重复边结论：选择最佳投递路线=选择重复边的权和最小的路线111111111111111111111111111反之，对邮路图G，对该链上的每一条边增加一条重复边111111111111111111投递路线欧拉图结论：对任意一个含奇点的邮路图G，由于奇点的个数为偶数个，把每两个配成一对，由于G为连通图，每对奇点之间至少存在一条链，对该条链上的每一条边增加一条重复边，可得一欧拉图，该欧拉图对应一条投递路线寻找最佳投递路线方法：在原邮路图上增加一些重复边得一个欧拉图，在所得欧拉图上找出一条欧拉回路。计算重复边的权和，重复边权和最小欧拉回路既为所求的最佳投递路线管梅谷奇偶点图上作业法奇偶点图上作业法：例：求解右图所示的邮路问题第一步：确定一个初始可行方案方法：检查图G中是否有奇点无奇点：，找出一条以v1为起点的欧拉回路，该回路就是最佳投递路线有奇点：图G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边，得一个欧拉图G1，由G1所确定的欧拉回路即为一个可行方案v2，v8，v4，v6G中有奇点：取v2到v4的一条链：v2v1v6v7v8v9v4取v6到v8的一条链：v6v1v2v3v4v9v8G243469544354G1显然G1不是最佳方案G1是欧拉图，第二步：调整可行方案，使重复边权和下降重复边权和=若图中某条边有两条或多于两条的重复边同时去掉偶数条，G2使图中每一条边最多有一条重复边G2的重复边权和=24346954435步骤1、可得到重复边权和较小的欧拉图4G2243469544354512124346954435G2是欧拉图，重复边权和=21G242、使图中每个初等圈重复边的 权和不大于该圈权和的一半9个初等圈24346954435G24G3G3是欧拉图，重复边权和=17G32434695443546（1）v1v2v5v6v1167（2）v6v5v8v7v61410（3）v2v3v4v5v2244（4）v5v4v9v8v516G3的初等圈权和重复边权和13（5）v1v2v5v8v7v6v124G4243469544354G42434695443547（1）v1v2v5v6v1164（2）v6v5v8v7v6144（3）v2v3v4v5v2248（4）v5v4v9v8v516G4的初等圈权和重复边权和11（5）v1v2v5v8v7v6v124（6）v2v3v4v9v8v5v2324（8）v6v5v4v9v8v7v6（7）v1v2v3v4v5v6v12811224（9）v1v2v3v4v9v8v7v6v1367G4是最佳方案奇偶点图上作业法：第一步：确定一个初始可行方案方法：检查图G中是否有奇点。无奇点：，找出一条以v0为起点的欧拉回路，该回路就是最佳投递路线有奇点：图G已是欧拉图把所有奇点两两配成一对，每对奇点找一条链，在该条链上的每一条边增加一条重复边第二步：调整可行方案，使重复边权和下降1、使图中每一条边最多有一条重复边若图中某条边有两条或多于两条的重复边，同时去掉偶数条2、使图中每个初等圈重复边的权和该圈权和的一半若图中某初等圈重复边的权和大于该圈权和的一半去掉圈中的重复边同时将圈中没有重复边的边加上重复边2326154231223261542312最佳投递路线：v0v3v0V4v3v4v5v3v2v523261542312v1v2v1v4v1v0说明:关于中国邮递员问题的有效算法由关于中国邮递员问题的有效算法由Edmonds和和Johnson19731973年给出。年给出。J.Edmonds，E.L.Johnson.Matching Euler tours and the Chinese postman.Mathematical Programming,1973,5:88-124小结:会用闭圈法和破圈法求最小支撑树会用闭圈法和破圈法求最小支撑树 会用会用Dijkstra算法求两点间的最短路径算法求两点间的最短路径 会求最大流和最小截集会求最大流和最小截集 会解最小费用最大流问题会解最小费用最大流问题