图论和网络流优化概念.ppt

图论和网络流优化概念 华南理工大学数学学院 刘深泉教授 Konigsberg 七桥问题 1736年Euler访问Konigsberg时，发现当地市民正从事一项非常有趣的消遣活动。城中有一条名叫Pregel的河流横经其中，在河上建有七座桥, 问题是能否作一次散步,走过所有七座桥的，每座桥只能经过一次,且起点与终点是同一地点。 七桥问题的数学模型 Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，得到如下的图形-图: Euler推出此种走法是不可能的。 Euler论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地时，他同时也由另一座桥离开此点。所以每行经一点时，计算两座桥，从起点离开的线与最後回到始点的线亦计算两座桥，每一个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，任务不可能实现。 欧拉数学判断原理 对给定的任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次（不一定回到原出发点），并用数学方法给出了3条判定的规则： （1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。 （2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。 （3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。 上述判定规则包含了任一连通无向图是否存在“欧拉路径”和“欧拉回路”的判定条件。根据判定规则（3）可以得出，任一连通无向图存在欧拉回路的充分必要条件是图的所有顶点均有偶数度。 赛纳河问题 赛纳河流经巴黎的河中有两个岛，河岸与岛间架设了15座桥,问： (1)能否从某地出发，经过这15座桥各一次后再回到出发点？- 就是否存在欧拉回路的问题 (2)若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？- 就是否存在欧拉路径的问题 ?A和B是通偶数座桥的地方，C和D是通奇数座桥的地方，满足欧拉给出的判定规则（2），即如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到欧拉路径；但不满足规则（3），即不存在欧拉回路。 图的定义 有序二元数组 G = （V，E）称为一个图. 其中V称为顶点集，E称为边。若每个边对应一个数F，称（V，E，F）为一个赋权图. 如果两点是有序的，则称有向图，否则称无向图. 经过G的每条边的迹叫做G的Euler迹. 闭的Euler迹叫做Euler回路. 含Euler回路的图叫做Euler图. Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点. Euler图 G是Euler图的充分必要条件是G连通且每顶点皆偶次。 弗罗莱（Fleury）算法 任取v0∈V(G)，令P0=v0； 设Pi=v0e1v1e2…ei vi已经行遍，按下面方法从中选取ei+1： （1）ei+1与vi相关联； （2）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,?…, ei}中的桥（所谓桥是一条删除后使连通图不再连通的边）； （3）当（2）不能再进行时，算法停止。 可以证明,当算法停止时所得的简单回路v0,e1,v1,e2,….em,vm=v0为G中一条欧拉回路。 Hamilton图 包含G每个顶点的轨叫做Hamilton轨； 闭的Hamilton轨叫Hamilton圈； 含Hamilton圈的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。 汉密尔顿问题 1859年威廉·汉密尔顿爵士在给朋友的信中谈到关于十二面体的一个数学游戏，即能否在如图中找到一条回路，使其含有此图中所有结点？- 周游世界问题 欧拉回路和汉密尔顿回路 欧拉图是每边经过一次. 汉密尔顿图是每顶经过一次. /ntsbarsh/opre640a/partIII.htm 最短路问题shortest path problem In the following network various costs are assigned for the path from one node to another. For example, the cost from node 2 to node 4 is 6. The objective function considers the cost to move from each node to another from source to destination. The constraints are broken into three groups. The constraint for the origin node says that you mus