图论和网络流优化概念.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）算法,任取v0V(G)，令P0=v0； 设Pi=v0e1v1e2ei 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 must leave node 1 and go to node 2 or 3. The intermediate node constraints say that if you ever come into a node you must leave that node. The destination node is similar to origin node in that you must reach to this node from one of the neighboring node.,指派问题 Assignment problem,Typically, we have a group of n “applicants“ applying for n “jobs,“ and the non-negative cost Cij of assigning the ith applicant to jth job is known. The objective is to assign one job to each applicant in such a way as to achieve the minimum possible total cost. Define binary variables Xij with value of either 0 or 1. When Xij = 1, it indicates that we should assign applicant i to job j. Otherwise (Xij = 0), we should not assign applicant i to job j.,中国邮递员问题 Chinese postman problem,管梅谷负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过每条街道至少一次，最后返回邮局）？ 若图中有欧拉回路，任何一个欧拉回路即为此问题的解。 若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于等于2个。有些边需要再重复一次，使奇数边的端点变为偶数边的端点。,用图来模拟一个镇的街道，标示红色的路口有奇数条路通过。,旅行商问题 Traveling salesman problem,A salesperson has to visit cities 1, 2,n, and his/her trip begins at, and must end in, Home City. Let Cij be the cost of traveling from city i to city j, which is given. The problem is to determine an optimal order for traveling the cities so that the total cost is minimized.,运输问题 Transportation Problem,Transportation models play an important role in logistics and supply chain management for reducing cost and improving service. Therefore, the goal is to find the most cost effective way to transport the goods.A shipper having m warehouses with supply ai of goods at his ith warehouse must ship goods to n geographically dispersed retail centers, each with a given customer demand ej, which must be met. The objective is to determine the minimum possible transportation costs given the unit cost of transportation between the ith warehouse and the jth retail center is Cij.,Maximum Flow Problem,In a network with flow capacities on the arcs, the problem is to determine the maximum possible flow from the source to the sink while honoring the arc flow capacities. Consider a network with m nodes and n arcs with a single commodity flow. Denote the flow along arc (i to j) by Xij. We associate with each arc a flow capacity, kij. In such a network, we wish to find the maximum total flow in the network, F, from node l to node m.,Maximum Flow Problem,In the LP formulation, the objective is to maximize F. The amount that leaves the origin by various routes. For every intermediate node, what comes in must be equal to what goes out. In some routes the flow can go both ways. The capacity amount that can be sent in a particular direction is also shown on the each route.,Minimum Cost Flow Problem,All the above network problems are special cases of the minimum cost flow problem. Like the maximum flow problem, it considers flows in networks with capacities. Like the shortest path problem, it considers a cost for flow through an arc. Like the transportation problem, it allows multiple sources and destinations. Therefore, all of these problems can be seen as special cases of the minimum cost flow problem. The problem is to minimize the total cost subject to availability and demand at some nodes, and upper bound on flow through each arc,Critical Path in Project Plan Network,The successful management of large projects, be they construction, transportation, or financial, relies on careful scheduling and coordinating of various tasks. Critical Path Method (CPM) attempts to analyze project scheduling. This allows for better control and evaluation of the project. For example, we want to know how long will the project take? When will we be able to start a particular task? If this task is not completed on time, will the entire project be delayed? Which tasks should we speed up (crash) in order to finish the project earlier?,Given a network of activities, the first problem of interest is to determine the length of time required to complete the project and the set of critical activities that control the project completion time. Suppose that in a given project activity network there are m nodes, n arcs (i.e. activities) and an estimated duration time, Cij, associated with each arc (i to j) in the network. The beginning node of an arc corresponds to the start of the associated activity and the end node to the completion of an activity. To find the Critical Path (CP), define the binary variables Xij, where Xij = 1 if the activity i j is on the CP and Xij = 0 otherwise. The length of the path is the sum of the duration of the activities on the path. The length of the longest path is the shortest time needed to complete the project. Formally, the CP problem is to find the longest path from node 1 to node m.,公路连接问题,某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，如何决定在哪些城市间修建高速公路，使得总成本最小？,共同的两个特点,寻求某种意义下的最优方案，数学上称为图论最优化或优化问题（optimization）. 易于用图形直