《《运筹学图论与网络》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学图论与网络》PPT课件.ppt（52页珍藏版）》请在金锄头文库上搜索。
1、运筹学刘新旺刘新旺刘新旺刘新旺 博士博士博士博士 副教授副教授副教授副教授研究领域研究领域研究领域研究领域：物流与供应链管理、不确定决策与优化物流与供应链管理、不确定决策与优化讲授课程讲授课程讲授课程讲授课程：运筹学、现代企业管理系统、供应链管理运筹学、现代企业管理系统、供应链管理单单单单 位位位位：东南大学经济管理学院（管理科学与工程系）东南大学经济管理学院（管理科学与工程系） E-mailE-mail： 电电电电 话话话话：83794008(H) 83794849 (O)第十章第十章 图与网络分析图与网络分析网络的基本概念网络的基本概念 最小生成树最小生成树最短路径问题最短路径问题 网络最
2、大流问题网络最大流问题2一、起源一、起源 1736年年瑞瑞士士数数学学家家欧欧拉拉（E.Euler）在在求求解解七七桥桥一一笔笔画画难难题题时时，就用了点线图来分析论证：就用了点线图来分析论证：每个点均有奇数条边时，一笔画问题无解。每个点均有奇数条边时，一笔画问题无解。ACBDCDAB(前苏)哥尼斯堡城中的普雷格尔河1、图的基本概念、图的基本概念图有一些点和点之间的联线（带箭头或不带箭头）所组图有一些点和点之间的联线（带箭头或不带箭头）所组成。成。不带箭头的联线称为边，不带箭头的称为弧。不带箭头的联线称为边，不带箭头的称为弧。点和边组成无向图：点和边组成无向图：G=（V,E)。点和弧组成有向图
3、：点和弧组成有向图：D=（V,A)。端点、关联边、多重边、环端点、关联边、多重边、环简单图、多重图。简单图、多重图。点的次：悬挂点、悬挂边、孤立点、奇点、偶点。点的次：悬挂点、悬挂边、孤立点、奇点、偶点。4一、图：无向图一、图：无向图5有向图有向图6 1、点：以无向图为例 相邻点：关联同一条边的两顶点称为相邻点。如：v1与v2,v2与v4等称为相邻点。 点的次数（度数）：与点vi关联的边数称为的次数（度数），记为d(vi)。如：d(v1) =5，称顶点v1的 次数为5，或称v1为5度关联。 奇点：次数（度数）为奇数的点叫奇点。如：v1,v2等均是奇点。 偶点：次数（度数）为偶数的点叫偶点。如v
4、7,v8等均是偶点。 悬挂点：次数（度数）为1的点叫悬挂点。如：v4,v5均是悬挂点。 孤立点：次数（度数）为0的点叫孤立点。即与任何边都没有关联的顶点。如v9为孤立点。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e127 所有点的次数之和等于边数的两倍。这是因为在计算各点的次数时，每条边均用了两次。 奇点的个数必为偶数。因为所有点的次数之和是偶数，则所有奇点的次数也是偶数，故奇点成对出现。 8 2、边：以无向图为例 相邻边：关联同一顶点的两条边称为相邻边。如：e1与e3称为相邻边。边也可用vivj表示。 多重边：并联于两个相邻顶点的边称为多重边。
5、如：e11与e13称为多重边。 环： 两端点接于同一顶点的边称为环。如：e12称为环。 悬挂边：与悬挂点关联的边叫悬挂边。如e3,e7均是悬挂边。 三、简单图 无环无多重边的图叫简单图。 V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e129四、链和路1、链：从某点开始的点边交替序列称为链。 如上图中的v4,e3,v2,e1,v1,e4,v3,e2,v2,e1,v1,e6,v6,e8,v7称为一条链。 圈(闭链)：首尾相连的链叫圈（或闭链）。 简单链：无重复边的链叫简单链。 如上图中的v4,e3,v2,e1,v1,e4,v3,e5,v6,e6,v1,
6、e11,v8称为一条简单链。2、路：无重复点的简单链叫做路。 如上图中的v4,e3,v2,e1,v1,e4,v3,e5,v6,e9,v8称为一条路。 回路：首尾相连的路叫回路。 如上图中的v1,e4,v3,e5,v6,e6,v1称为一回路。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e12 以上点边序列中的边表示为e=vi,vj,所以点边序列可由点列确定。 如上面的回路可写为 v1,v3,v6,v1。 在有向图中，弧区分为正向弧和反向弧，其链和路的概念与无向图相似，点弧序列中弧也有正向弧和反向弧之分。10五、连通图： 任意两点之间可由一条链连接起来
7、相通的图叫连通图。否则，称为非连通图。如上图就不是连通图，因为点V9与任何点之间均没有链连接起来相通。V1V2V4V3V5V6V7V8V9e1e2e3e4e5e6e7e8e9e10e11e13e12六、子图和部分图：设G1=（V1，E1）， G2=（V2，E2）， 1、子图： 若V2V1，E2 E1，则称G2是G1的一个子图 。 真子图：若V2V1，E2 E1，则称G2是G1的一个真子图 。2、支撑子图：若V2=V1，E2 E1，则称G2是G1的一个支撑子图，即包含原图全部顶点的子图。11第二节第二节 树树什么是树？什么是树？树的性质和判定树的性质和判定求支撑树的方法求支撑树的方法最小支撑树问
8、题最小支撑树问题求最小支撑树的方法求最小支撑树的方法12定义定义定义定义 一个无圈的连通图称为树。一个无圈的连通图称为树。一个无圈的连通图称为树。一个无圈的连通图称为树。 有线通讯网和交通网中，在保证节点连通的条件下，边数最有线通讯网和交通网中，在保证节点连通的条件下，边数最有线通讯网和交通网中，在保证节点连通的条件下，边数最有线通讯网和交通网中，在保证节点连通的条件下，边数最少（可以节省材料和投资）的线路图必然是树。图书分类、会计少（可以节省材料和投资）的线路图必然是树。图书分类、会计少（可以节省材料和投资）的线路图必然是树。图书分类、会计少（可以节省材料和投资）的线路图必然是树。图书分类、
9、会计科目、决策过程等等也都可以画成树图科目、决策过程等等也都可以画成树图科目、决策过程等等也都可以画成树图科目、决策过程等等也都可以画成树图树的性质：树的性质：树的性质：树的性质：1 1 1 1 树至少有两个悬挂点。树至少有两个悬挂点。树至少有两个悬挂点。树至少有两个悬挂点。2 2 2 2 一个图为树的充要条件是：不含圈，边数比点数少一个图为树的充要条件是：不含圈，边数比点数少一个图为树的充要条件是：不含圈，边数比点数少一个图为树的充要条件是：不含圈，边数比点数少1.1.1.1.3 3 3 3 一个图为树的充要条件是：连通，边数比点数少一个图为树的充要条件是：连通，边数比点数少一个图为树的充要
10、条件是：连通，边数比点数少一个图为树的充要条件是：连通，边数比点数少1.1.1.1.4 4 4 4 一个图为树的充要条件是：任两点之间恰有一条链。一个图为树的充要条件是：任两点之间恰有一条链。一个图为树的充要条件是：任两点之间恰有一条链。一个图为树的充要条件是：任两点之间恰有一条链。树的判定方法有几种？树的判定方法有几种？树的判定方法有几种？树的判定方法有几种？树树13树的性质（性质树的性质（性质树的性质（性质树的性质（性质4 4 4 4）：）：）：）：1 1 1 1 在图中任意两点之间必有一条而且只有一条通路。在图中任意两点之间必有一条而且只有一条通路。在图中任意两点之间必有一条而且只有一条
11、通路。在图中任意两点之间必有一条而且只有一条通路。2 2 2 2 在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。3 3 3 3 在图中不相邻的两个顶点之间加一条边，可得一在图中不相邻的两个顶点之间加一条边，可得一在图中不相邻的两个顶点之间加一条边，可得一在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。个且仅得一个圈。个且仅得一个圈。个且仅得一个圈。14定义定义定义定义 如果一个图的支撑子图是树，如果一个图的支撑子图是树，如果一个图的支撑子图是树，如果一个图的支撑子图是树， 则称为该图则称为该图则称为该图则称为该
12、图的支撑树。的支撑树。的支撑树。的支撑树。定理定理定理定理 图图图图G G G G有支撑树的充分必要条件为图是连通图。有支撑树的充分必要条件为图是连通图。有支撑树的充分必要条件为图是连通图。有支撑树的充分必要条件为图是连通图。求支撑树的方法有求支撑树的方法有求支撑树的方法有求支撑树的方法有破圈法破圈法破圈法破圈法和和和和避圈法避圈法避圈法避圈法。支撑树支撑树15例例v1v2v3v5e2e3e5e1e6e7e8破圈法破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法避圈法v2e2e3e5e4v4v1v3v5e1e6e7e816定义定义定义定义 图的各边赋予一定的物理量，则叫做赋权图，图的各
13、边赋予一定的物理量，则叫做赋权图，图的各边赋予一定的物理量，则叫做赋权图，图的各边赋予一定的物理量，则叫做赋权图，所赋予的物理量叫做权。所赋予的物理量叫做权。所赋予的物理量叫做权。所赋予的物理量叫做权。权可以是：距离、时间、成本、容量等权可以是：距离、时间、成本、容量等权可以是：距离、时间、成本、容量等权可以是：距离、时间、成本、容量等定义定义定义定义 对赋权图，一个图的支撑树是所有支撑树中对赋权图，一个图的支撑树是所有支撑树中对赋权图，一个图的支撑树是所有支撑树中对赋权图，一个图的支撑树是所有支撑树中总权值最小者，则称为该图的最小支撑树。总权值最小者，则称为该图的最小支撑树。总权值最小者，则
14、称为该图的最小支撑树。总权值最小者，则称为该图的最小支撑树。求最小支撑树的方法也有求最小支撑树的方法也有求最小支撑树的方法也有求最小支撑树的方法也有破圈法破圈法破圈法破圈法和和和和避圈法避圈法避圈法避圈法。破圈法：破圈法：破圈法：破圈法：任取一圈，去掉权重最大的边，重复进任取一圈，去掉权重最大的边，重复进任取一圈，去掉权重最大的边，重复进任取一圈，去掉权重最大的边，重复进行直到无圈可破。行直到无圈可破。行直到无圈可破。行直到无圈可破。避圈法：避圈法：避圈法：避圈法：选取权重最小的边，重复进行直到形成选取权重最小的边，重复进行直到形成选取权重最小的边，重复进行直到形成选取权重最小的边，重复进行直
15、到形成部分树，并保证不构成圈。部分树，并保证不构成圈。部分树，并保证不构成圈。部分树，并保证不构成圈。最小支撑树最小支撑树17655172344v1v2v3v4v5 避圈法避圈法 破圈法破圈法655172344v1v2v4v6v3v21v42v53v64v1518v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636最小支撑树：线路费用最小支撑树：线路费用19v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 1232320v1v1v7v7
16、v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总造价总造价=1+4+9+3+17+23=5721v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636避圈法避圈法22v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636总造价总造价=1+4+9+3+17+23=5723第三节第三节 最短路问题最短路问题什么是最短路问题？什么是最短路问题？求解最短路问题的基本思路求解最短路问题的基本思
17、路Dijstra （荷兰人）算法：标号法荷兰人）算法：标号法Ford（美国人）算法：修正标号法美国人）算法：修正标号法寻找最短路径的方法：双标号寻找最短路径的方法：双标号24一、什么是最短路问题？一、什么是最短路问题？在在连通图中，寻找一条从始点到终点的路，该路的权之和连通图中，寻找一条从始点到终点的路，该路的权之和最小。最小。25 标号法思想是：标号法思想是：先先找一个可行流。找一个可行流。对于一个可行流，经过标号过程得到对于一个可行流，经过标号过程得到从发点从发点v vs s到收点到收点v vt t的增广链；经过调的增广链；经过调整过程沿增广链增加可行流的流量，整过程沿增广链增加可行流的流
18、量，得新的可行流。重复这一过程，直到得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。可行流无增广链，得到最大流。26二、求解最短路问题的基本思路二、求解最短路问题的基本思路使用线性规划的解法，但不能利用最短路问题的特点，使用线性规划的解法，但不能利用最短路问题的特点，使解法更有效。使解法更有效。利用动态规划的思路，即对于在始点到终点的总体最短利用动态规划的思路，即对于在始点到终点的总体最短路径上的任意一点，从始点到该点的最短路在总体最短路径上的任意一点，从始点到该点的最短路在总体最短路径上。路径上。根据上述第二点，可以用标号法求解。根据上述第二点，可以用标号法求解。27三、三、Di
19、jkstra算法算法对每个节点，用两种标号：对每个节点，用两种标号：T和和P，表示从始点到该节点表示从始点到该节点的距离，的距离，P是最短距离，是最短距离，T是目前路径的距离。是目前路径的距离。通过不断改进通过不断改进T值，当其最小时，将其改为值，当其最小时，将其改为P标号。标号。开始时，令始点有开始时，令始点有P=0，的，的P标号，其它节点有标号，其它节点有T=M。S: 已确定最短路的（即具有已确定最短路的（即具有P标号）的节点集合。标号）的节点集合。P：最短路径长度信息；：最短路径长度信息；T: 目前路径长度信息。目前路径长度信息。 : 相关长度的路径信息相关长度的路径信息28V1V2V3
20、 V4V5V6V7V8V90631S Svv1 1 V1V2V3 V4V5V6V7V8V90V1V2V3 V4V5V6V7V8V90111T:T:P:P: :29V1V2V3 V4V5V6V7V8V90631711S Svv1 1,v ,v4 4 V1V2V3 V4V5V6V7V8V901V1V2V3 V4V5V6V7V8V9011144T:T:P:P: :30V1V2V3 V4V5V6V7V8V90531711S Svv1 1,v ,v4 4 ,v3 ,v3 V1V2V3 V4V5V6V7V8V9031V1V2V3 V4V5V6V7V8V9031144T:T:P:P: :31V1V2V3 V
21、4V5V6V7V8V90531711S Svv1 1,v ,v4 4 ,v3 ,v3 V1V2V3 V4V5V6V7V8V9031V1V2V3 V4V5V6V7V8V9031144T:T:P:P: :32V1V2V3 V4V5V6V7V8V90531611S Svv1 1,v ,v4 4 ,v3, V2 ,v3, V2 V1V2V3 V4V5V6V7V8V90531V1V2V3 V4V5V6V7V8V9031124T:T:P:P: :33V1V2V3 V4V5V6V7V8V905316109128S Svv1 1,v ,v4 4 ,v3, V2, V5 ,v3, V2, V5 V1V2V3 V
22、4V5V6V7V8V905316V1V2V3 V4V5V6V7V8V9031124T:T:P:P: :34V1V2V3 V4V5V6V7V8V905316109128S Svv1 1,v ,v4 4 ,v3, V2, V5, V9 ,v3, V2, V5, V9 V1V2V3 V4V5V6V7V8V90531695V1V2V3 V4V5V6V7V8V9031125555T:T:P:P: :35V1V2V3 V4V5V6V7V8V905316109118S Svv1 1,v ,v4 4 ,v3, V2, V5, V9, ,v3, V2, V5, V9, V7 V7 V1V2V3 V4V5V6V7
23、V8V90531695V1V2V3 V4V5V6V7V8V9031125595T:T:P:P: :36最短路径问题最短路径问题237184566134105275934682求从1到8的最短路径37四、四、Ford算法算法Dijkstra算法计算停止判别标准：算法计算停止判别标准：（1 ）对于求）对于求VSVt的最短路，的最短路，Vt标上标上P标号时计算停止；标号时计算停止；（2）对于求）对于求VS所有点的最短路，所有点标上所有点的最短路，所有点标上P标号时计算停止。标号时计算停止。Dijkstra算法的说明算法的说明 （1） 路权为负值时失效（交通网络中一般不存在）路权为负值时失效（交通网络
24、中一般不存在） （2） 对于无向图对于无向图（将原图中的每条边视为由方向相反的两条弧组成，（将原图中的每条边视为由方向相反的两条弧组成，其权相等。其权相等。 具有负权的网络，应当用具有负权的网络，应当用Ford算法又叫修正标号法。修正标号法的算法又叫修正标号法。修正标号法的特点是：不但最小特点是：不但最小T标号应当改为标号应当改为P标号，标号，P标号也可以修改，修改后的标号也可以修改，修改后的P标号再次改为标号再次改为T标号。标号。38第四节第四节 最大流问题最大流问题网络流的基本概念网络流的基本概念求解网络最大流的基本原理求解网络最大流的基本原理寻找网络最大流的标号法寻找网络最大流的标号法确
25、定网络中最大流的方法确定网络中最大流的方法39一、网络流的基本概念一、网络流的基本概念流量与容量流量与容量可行流：节点和边的限制条件可行流：节点和边的限制条件饱和弧和非饱和弧饱和弧和非饱和弧正向弧和反向弧正向弧和反向弧增广链：对于一可行流增广链：对于一可行流 ，网络的一条链满足，网络的一条链满足40二、求解网络最大流的基本原理二、求解网络最大流的基本原理数学模型数学模型41二、求解网络最大流的基本原理二、求解网络最大流的基本原理给出一初始可行流，例如给出一初始可行流，例如 。寻找增广链，若存在，则通过该增广链调整、增加网络寻找增广链，若存在，则通过该增广链调整、增加网络流。流。若不存在增广链，
26、则网络流不可再增加。求得最大流。若不存在增广链，则网络流不可再增加。求得最大流。定理：可行流定理：可行流f为最大流的充分必要条件是当且仅当网络为最大流的充分必要条件是当且仅当网络不存在增广链。不存在增广链。42三、寻找网络最大流的标号法三、寻找网络最大流的标号法Ford-Fulkson标号算法，给每个节点以一对标号，第一标号算法，给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链。否则不存在增广链。点有了标号，则找到一条增广链。否则不存在增广链。调整过程：在增广链上，正向弧加上调整量，反向弧减调
27、整过程：在增广链上，正向弧加上调整量，反向弧减去调整量。经过调整网络流去调整量。经过调整网络流v(f)增加一个调整量：增加一个调整量：43 给一个有向图给一个有向图D(V,A)，指定两个点，一个点指定两个点，一个点称为称为发点发点，记为，记为vs，另一个点称为另一个点称为收点收点，记为，记为vt，其其余点称为中间点。余点称为中间点。3511 42352vsv2v1v3v4vt 对于对于D中的每一个弧中的每一个弧(vi,vj)，相应相应地给地给一个数一个数cij（cij0），称为弧称为弧(vi,vj)的容量的容量。我们把这我们把这样的样的D称为网络（或容量网络称为网络（或容量网络），记为D(V,
28、A,C)。三、寻找网络最大流的标号法三、寻找网络最大流的标号法44 所谓网络上的流，是指定义在弧集所谓网络上的流，是指定义在弧集A上的函数上的函数ff(vi,vj)，并称并称f(vi,vj)为弧(vi,vj)上的流量，简记为简记为fij。可行流、可行流的流量、最大流可行流、可行流的流量、最大流。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt45 给定容量网络给定容量网络D(V,A,C)，若点集若点集V被剖分为两个非空集被剖分为两个非空集合合V1和和V2，使使 vsV1 ，vtV2，则把弧集把弧集(V1,V2)称为（分离分离vs和vt的）截集截集。 显然，若把某
29、一截集的弧从网络中去掉，则从显然，若把某一截集的弧从网络中去掉，则从vs到到vt便不存在路。所以，直观上说，截集是从便不存在路。所以，直观上说，截集是从vs到到vt的必经之的必经之路路。截集的容量截集的容量(简称截量简称截量) 最小截集最小截集。3511 42352vsv2v1v3v4vt46 对于可行流对于可行流ffij，我们把网络中使我们把网络中使fijcij的弧称为的弧称为饱和弧，使饱和弧，使fij0的弧称为非零流弧的弧称为非零流弧。 设设f是一个可行流，是一个可行流，是从是从vs到到vt的一条链，若的一条链，若满足满足前前向弧向弧都是非饱和弧都是非饱和弧,后向弧都是后向弧都是都是非零流
30、弧都是非零流弧,则称则称是（可是（可行流行流f的）一条的）一条增广链增广链。 若若是联结发点是联结发点vs和和收点收点vt的一条链，我们规的一条链，我们规定链的方向是从定链的方向是从vs到到vt，则链上的弧被分成两类：则链上的弧被分成两类：前前向弧、向弧、后后向弧向弧。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt47 对最大流问题有下列定理：对最大流问题有下列定理： 定理定理1 可行流可行流f*fij*是最大流，当且仅当是最大流，当且仅当D中不存在关于中不存在关于f*的增广链。的增广链。 定理定理2（最大流最小截定理）任一网络中，最大（最大流最小截定理）任一
31、网络中，最大流的流量等于最小截集的截量。流的流量等于最小截集的截量。48 标号法思想是：标号法思想是：先先找一个可行流。找一个可行流。对于对于一个可行流，经过标号过程得到从发点一个可行流，经过标号过程得到从发点v vs s到收点到收点v vt t的增广链；经过调整过程沿增广的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到复这一过程，直到可行流无增广链，得到最大流最大流。49 标号过程标号过程: : (1) (1)给给vsvs标号标号(-,+)，vsvs成为已标号未检查的成为已标号未检查的点，其余都是未标号点
32、。点，其余都是未标号点。 (2)取一个已标号未检查的点取一个已标号未检查的点vivi，对一切未标号对一切未标号点点vjvj：若有非饱和弧若有非饱和弧( (vi,vj)vi,vj)，则则vjvj标号标号( (vi,l(vj)vi,l(vj)，其中其中l(vj)l(vj)minl(vi),minl(vi),cij-fij，vj成为已标号未检成为已标号未检查的点；若有非零弧查的点；若有非零弧(vj,vi)，则vj标号标号(-vi,l(vj)，其中其中l(vj)minl(vi),fji，vj成为已标号未检查的点。成为已标号未检查的点。vivi成为已标号已检查的点。成为已标号已检查的点。 (3)(3)重
33、复步骤重复步骤(2)(2)，直到，直到vtvt成为标号点或所有标成为标号点或所有标号点都检查过。若号点都检查过。若vtvt成为标号点，表明得到一条成为标号点，表明得到一条vsvs到到vtvt的增广链，转入调整过程；若所有标号点都检的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。查过，表明这时的可行流就是最大流，算法结束。 调整过程：在增广链上，前向弧流量增加调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少后向弧流量减少l(vt)。 50下面用实例说明具体的操作方法：例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3
34、)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt在图中给出的可在图中给出的可行流的基础上，行流的基础上，求求vs到到vt的最大流。的最大流。(-,+)(vs,4)(-v1,1)(-v2,1)(v2,1)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4vt(vs,3)(-,+) 得增广链，标号结束，得增广链，标号结束，进入调整过程进入调整过程 无增广链，标号结束，得无增广链，标号结束，得最大流。同时得最小截。最大流。同时得最小截。51二、中国邮递员问题二、中国邮递员问题1962年，管梅谷先生提出年，管梅谷先生提出中国邮递员问题中国邮递员问题若图中无奇点，欧拉圈即为所求若图中无奇点，欧拉圈即为所求若图中有奇点，则奇点必为偶数，在奇点间加边（重复若图中有奇点，则奇点必为偶数，在奇点间加边（重复走），使其变为偶数而成欧拉图。走），使其变为偶数而成欧拉图。中国邮递员问题是要求所加边的权之和最小。中国邮递员问题是要求所加边的权之和最小。52
