运筹学05_图与网络分析1.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * v9 v1 v8 v7 v6 v5 v4 v3 v2 4 3 4 3 4 4 4 9 6 5 5 2 圈上重复边长=13大于24/2 检查图中圈：总权=24 v9 v1 v8 v7 v6 v5 v4 v3 v2 4 3 4 3 4 4 4 9 6 5 5 2 去了原重复边，添上原没有的重复边 v9 v1 v8 v7 v6 v5 v4 v3 v2 4 3 4 3 4 4 4 9 6 5 5 2 重复边总长=15，得最优方案 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 总造价=1+4+9+3+17+23=57 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 避圈法 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 总造价=1+4+9+3+17+23=57 中国邮递员问题 一名邮递员负责投递某个邮区的邮件。从邮局出发，经过投递邮区内每条街道至少一次，最后返回邮局。问：如何安排一条最短的投递线路。 邮递员问题，用图的语言来描述，就是给定一个连通图G，在每条边上有一个非负的权，要寻求一个圈，经过G的每条边至少一次，并且圈的权数最小。这个问题是我国管梅谷教授（1990年到复旦管院任教）于1962年首先提出来的，国际上称该问题为中国邮递员问题（Chinese Postman Problem）。 一笔画问题 设有一个连通图G，如果在G中存在一条链，经过G的每条边一次且仅一次，那么这条链叫做欧拉链。如在G中存在一个简单圈，经过G的每条边一次，那么这个圈叫做欧拉圈。一个图如果有欧拉圈，那么这个图叫做欧拉图。很明显，一个连通图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链。 一笔画问题 定理3 一个连通图G是欧拉图的充分必 要条件是G中无奇点。 推论1 一个连通图G是欧拉图的充分必 要条件是G边集可剖分成若干个 初等圈。 推论2 一个连通图G有欧拉链的充分必 要条件是G有且仅有两个奇点。 一笔画问题 一个连通图能一笔画的条件是： （1）它没有奇点；或者 （2）它恰好有两个奇点。 情况（1）出现，该图是个欧拉圈； 情况（2）出现，该图是个欧拉链。 一笔画问题 前面提到的哥尼斯堡七桥问题，欧拉把它抽象成具有四个顶点，并且都是奇点的图（左下）。一个漫步者无论如何也不可能重复的走完七座桥，并最终回到原出发地。 右下图仅有两个奇点，可以一笔画出。 D C B A v5 v6 v4 v2 v1 v3 中国邮递员问题 从一笔画问题的讨论可知，一个邮递员在他所负责投递的街道范围内，如果街道构成的图中没有奇点，那么他就可以从邮局出发，经过每条街道一次，且仅一次，并最终回到原出发地。但是，如果街道构成的图中有奇点，他就必然要在某些街道重复走几次。 中国邮递员问题 v5 v6 v4 v2 v1 v3 a v5 v6 v4 v2 v1 v3 b 在下图中，每条边长为1。按照一条路线走： v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1, 总长是12。 也可以按照另一条路线走： v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1, 总长是11。 中国邮递员问题 在连通图G中，如果在边[vi,vj]上重复走几次，那么就在点vi,vj之间增加了几条相应的边，每条边的权和原来的权相等，并把新增加的边叫做重复边。显然，这条路线构成新图中的欧拉圈。 中国邮递员问题 中国邮递员问题也