《运筹学图与网络分析》由会员分享，可在线阅读，更多相关《运筹学图与网络分析（107页珍藏版）》请在金锄头文库上搜索。
1、图与网络分析图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本知识图与网络的基本知识最短路问题最短路问题树及最小树问题树及最小树问题最大流问题最大流问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥哥尼尼斯斯堡堡（现现名名加加里里宁宁格格勒勒）是是欧欧洲洲一一个个城城市市，PregeiPregei河河把把该该城城分分成成两两部部分分，河河中中有有两两个个小小岛岛，十十八八世世纪纪时时，河河两两边边及及小小岛岛之之间间共共有有七七座座桥桥，当当时时人人们们提提出出这这样样的的问问题题：有有没没有有办办法法从从某某处处（如如A A）出出发发，经经过过各各桥桥一一次次且且仅
2、仅一一次次最最后后回回到到原地呢？原地呢？BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题哈哈密密尔尔顿顿（HamiltonHamilton）回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出，给给出出一一个个正正1212面面体体图图形形，共共有有2020个个顶顶点点表表示示2020个个城城市市，要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次，最最后后回回到到原原处处的的周周游游世世界界线线路路（并并不不要要求求经经过过每条边）。每条边）。有有7 7个个人人围围桌桌而而坐坐，如如果果要要
3、求求每每次次相相邻邻的的人人都都与与以以前前完完全全不不同同，试试问问不不同同的的就就座座方方案案共共有有多多少种？少种？用用顶顶点点表表示示人人，用用边边表表示示两两者者相相邻邻，因因为为最最初初任任何何两两个个人人都都允允许许相相邻邻，所所以以任任何何两两点点都都可可以以有边相连。有边相连。1 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12
4、23 37 76 64 45 5得到第一次就座方案是（1，2，3，4，5，6，7，1），继续寻求第二次就座方案时就不允许这些顶点之间继续相邻，因此需要从图中删去这些边。1 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5得出第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继
5、续相邻，只能从图中删去这些边。1 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 51 12 23 37 76 64 45 5得得到到第第三三次次就就座座方方案案是是（1 1，4 4，7 7，3 3，6 6，2 2，5 5，1 1），那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，只只能能从从图图中中删删去去这这
6、些些边边，只只留留下下7 7点点孤孤立立点点，所以该问题只有三个就座方案。所以该问题只有三个就座方案。1 12 23 37 76 64 45 5引论引论 图的用处图的用处 某公司的 组织机构设置图总公司总公司分公司分公司工厂或工厂或办事处办事处一、一、 图与网络的基本知识图与网络的基本知识（一）、（一）、图与网络的基本概念图与网络的基本概念 EADCB1、一个图是由点和连线组成。（连线可带箭头，也可、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）不带，前者叫弧，后者叫边）v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例图图1一一个个图图是是由由点点
7、集集 和和 中中元元素素的的无无序序对对的的一一个个集集合合 构构成成的的二二元元组组，记记为为G G =(=(V V，E E ) )，其其中中V V中中的的元元素素 叫叫做做顶顶点点，V表表示示图图G 的的点点集集合合；E中中的的元元素素 叫叫做做边，边，E表示图表示图G的边集合。的边集合。 jvV = = 2 2、不不带带箭箭头头的的连连线线叫叫做做边边。如如果果一一个个图图是是由由点点和和边边所所构构成成的的，则则称称其其为为无无向向图图，记记作作G G = = ( (V V，E E) )，连连接接点点的的边边记记作作 v vi i , , v vj j ，或或者者 v vj j , v
8、 , vi i 。 3 3、若点与点之间的连线有方向，称为弧。如果一个图是由点、若点与点之间的连线有方向，称为弧。如果一个图是由点和弧所构成的，那么称它为有向图，记作和弧所构成的，那么称它为有向图，记作D D=(=(V, AV, A) )，其中其中V V 表示有表示有向图向图D D 的点集合，的点集合，A A 表示有向图表示有向图D D 的弧集合。一条方向从的弧集合。一条方向从v vi i指向指向v vj j 的弧，记作的弧，记作( (v vi i , v , vj j) )。v4v6v1v2v3v5V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(
9、v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)图图2 4 4、一条边的两个端点是相同的、一条边的两个端点是相同的, ,那么称这条边是环。那么称这条边是环。 5 5、如果两个端点之间有两条以上的边，那么称它们为、如果两个端点之间有两条以上的边，那么称它们为多重边。多重边。 6 6、不含环和多重边的图称为简单图；有多重边的图称、不含环和多重边的图称为简单图；有多重边的图称为多重图。为多重图。7、每一对顶点间都有边相连的无向简单图称为完全图。、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有有向完全图则是指任意两个顶点之间有且
10、仅有一条有向边的简单图。向边的简单图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 次为零的点称为弧立点，次为次为零的点称为弧立点，次为1 1的点称为悬挂点。悬挂的点称为悬挂点。悬挂点的关联边称为悬挂边。次为奇数的点称为奇点，次为偶点的关联边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。数的点称为偶点。 8 8、以点、以点v v为端点的边的个数称为点为端点的边的个数称为点v v 的次，记作的次，记作 。图中图中 d(v1)=4，d(v6)=4（环计两次环计两次） 定理定理1 1 所有顶点次数之和等于所有边数的所有顶点次数之和等于所有边数的2 2倍。倍。 定理定理
11、定理定理2 2 2 2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。所有顶点的入次之和等于所有顶点的出次之和。 有有向向图图中中，以以 v vi i 为为始始点点的的边边数数称称为为点点v vi i的的出出次次，用用 表示表示 ；以；以 v vi i 为终点的边数称为点为终点的边数称为点v vi i 的入次，的入次，用用 表示；表示；v vi i 点的出次和入次之和就是该点的次。点的出次和入次之和就是该点的次。9 9 9 9、设设设设G=G=（V V，E E），GG = =（V V ,E,E ）如如果果V V, ,E E，称称G 是
12、是G的的子子图图；如如果果V =V, ,E E，称称G 是是G的的生生成成子子图图或或支支撑撑子图。子图。 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图在实际应用中，给定图中每条边在实际应用中，给定图中每条边 ，对应一，对应一个数个数 ，称之为，称之为 “ “权权”。通常把这种赋权的图称为。通常把这种赋权的图称为网络。网络。 10 10、由两两相邻的点及其相关联的边构成的点边序列、由两两相邻的点及其相关联的边构成的点边序列称为
13、链。称为链。 如如: :v v0 0 ，e e1 1，v v1 1，e e2 2，v v2 2，e e3 3 ，v v3 3 , ,v,vn-1n-1 , ,e en n ，v vn n， e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 11 11、图中任意两点之间均至少有一条链相连，则称此、图中任意两点之间均至少有一条链相连，则称此图为连通图。图为连通图。 其链长为其链长为 n，其中其中 v0，vn 分别称为链的起点和终点分别称为链的起点和终点 。所含的点、边均不相同的链称为初等链。起点和终点是。所含的点、边均不相同的链称为初等链。起点和终点是同一个点的链称为圈。同一个点
14、的链称为圈。（二）、（二）、 图的矩阵表示图的矩阵表示对于网络（赋权图）对于网络（赋权图）G=（V，E），其中边其中边有权有权 ，构造矩阵，构造矩阵 ，其中：，其中：称矩阵称矩阵A A为网络为网络G G的权矩阵。的权矩阵。 设图设图G=（V，E）中顶点的个数为中顶点的个数为n，构造一个构造一个矩阵矩阵 ，其中：，其中： 称矩阵称矩阵A A为网络为网络G G的邻接矩阵。的邻接矩阵。 例例权矩阵为：权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437 二、二、 树及最小树问题树及最小树问题 已已知知有有六六个个城城市市，它它们们之之间间 要要架架设设电电话话线线，要要求求
15、任任意意两个城市均可以互相通话，并且电话线的总长度最短。两个城市均可以互相通话，并且电话线的总长度最短。 v1v2v3v4v5v6 1 1、一个连通的无圈的无向图叫做树。、一个连通的无圈的无向图叫做树。 树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。 树树的性质：的性质： （1 1）数必连通，但无回路（圈）。数必连通，但无回路（圈）。 （2 2）n个顶点的树必有个顶点的树必有n-1条边条边。 （3 3）树树中任意两个顶点之间，恰有且仅有一条链（初中任意两个顶点之间，恰有且仅有一条链（初等链）。等链）。 （4 4）树）树连通，但去掉任一条边，
16、连通，但去掉任一条边， 必变为不连通。必变为不连通。 （5 5）树树无回路（圈），但不相邻的两个点之间加一条无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。边，恰得到一个回路（圈）。v1v2v3v4v5v6 2 2、 若图若图G=(V , E )的生成子图是一个树的生成子图是一个树, ,那么称那么称该树该树 是是G 的一个生成树（支撑树），或简称为图的一个生成树（支撑树），或简称为图G 的树。图的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。中属于生成树的边称为树枝，不在生成树中的边称为弦。一个图一个图G 有生成树的充要条件是有生成树的充要条件是G是连通图。是连通
17、图。 v1v2v3v4v5v1v2v3v4v5（一）（一）破圈法：在图中任选一个圈，从这个圈破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。直到得到一不含圈的图为止。用破圈法求出下图的一个生成树。用破圈法求出下图的一个生成树。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（二）（二）避圈法：开始选一条边，以后每一步中，避圈法：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成总从未被选取的边
18、中选出一条与已选边不构成圈的边，重复这个过程，直到不能进行为止。圈的边，重复这个过程，直到不能进行为止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5根据破圈法和避圈法两种方式得到了根据破圈法和避圈法两种方式得到了图的两个不同的生成树，由此可以看到连图的两个不同的生成树，由此可以看到连通图的生成树不是唯一的。通图的生成树不是唯一的。3 3、最小生成树问题、最小生成树问题 一一棵棵生生成成树树所所有有树树枝枝上上权权的的总总和和为为这这个个生生成成树树的权的权。具有最小权的生成树，称为最小生成树。具有最小权的生成树，称为最小生成树。求求赋
19、赋权权图图G G的的最最小小支支撑撑树树的的方方法法也也有有两两种种，“破破圈法圈法”和和“避圈法避圈法”。 破破圈圈法法：在在原原图图中中，任任选选一一个个圈圈，从从圈圈中中去去掉掉权权最最大大的的一一条条边边。在在余余下下的的图图中中重重复复这这个个步步骤骤，直直到到得得到到一一不不含含圈圈的的图图为止。为止。655172344v1v2v3v4v5v6v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253
20、3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v
21、3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323总造价总造价=1+4+9+3+17+23=57=1+4+9+3+17+23=57v1v2v3v4v
22、514231352避避圈圈法法：开开始始选选一一条条权权最最小小的的边边，以以后后每每一一步步中中，总总从从未未被被选选取取的的边边中中选选一一条条权权尽尽可可能能小小，且且与与已已选选边不构成圈的边。边不构成圈的边。 某某六六个个城城市市之之间间的的道道路路网网如如图图 所所示示，要要求求沿沿着着已已知知长长度度的的道道路路联联结结六六个个城城市市的的电电话话线线网网，使使电电话话线线的的总总长长度最短。度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v61234最最短短路路的的一一般般提提法法为为：设设 为为连连通通图图，图图中中各各边边 有有权权 （ 表表示示
23、之之间间没没有有边边）， 为为图图中中任任意意两两点点，求求一一条条路路 ，使使它它从从 到到 的的所所有有路路中中总总权权最最短短。即即： 最最小。小。( (一一) )、狄克斯彻、狄克斯彻(Dijkstra)(Dijkstra)算法算法适用于适用于w wijij00，给出了从，给出了从v vs s到任意一个点到任意一个点v vj j的最短路。的最短路。三三 、最短路问题、最短路问题算法步骤：算法步骤：1.1.给始点给始点v vs s以以P P标号标号 ，这表示从，这表示从v vs s到到v vs s的最的最短距离为短距离为0 0，其余节点均给，其余节点均给T T标号，标号， 。2.2.设节点
24、设节点v vi i为刚得到为刚得到P P标号的点，考虑点标号的点，考虑点v vj j，其中其中 ，且，且v vj j为为T T标号。对标号。对v vj j的的T T标号进行如下修标号进行如下修改：改：3.3.比较所有具有比较所有具有T T标号的节点，把最小者改为标号的节点，把最小者改为P P标标号，即：号，即：当当存存在在两两个个以以上上最最小小者者时时，可可同同时时改改为为P P标标号号。若若全全部部节节点点均均为为P P标标号号则则停停止止，否否则则用用 代代替替v vi i，返返回回步骤（步骤（2 2）。）。例一：用例一：用DijkstraDijkstra算法求下图从算法求下图从v v1
25、 1到到v v6 6的最短路。的最短路。 v1v2v3v4v6v5352242421解：（解：（1 1）首先给）首先给v v1 1以以P P标号，给其余所有点标号，给其余所有点T T标号。标号。（2 2）（3 3）（4 4）（5 5）（6 6）（7 7）（8 8）（9 9）（1010）反向追踪得反向追踪得v v1 1到到v v6 6的最短路为：的最短路为：v1v2v3v4v6v5352242421（二）、逐次逼近法（二）、逐次逼近法首先设任一点首先设任一点v vi i到任一点到任一点v vj j都有一条弧。都有一条弧。显显然然，从从v v1 1到到v vj j的的最最短短路路是是从从v v1
26、1出出发发，沿沿着着这这条条路路到到某某个个点点v vi i再再沿沿弧弧( (v vi i, ,v vj j) )到到v vj j。则则v v1 1到到v vi i的的这这条条路路必必然然也也是是v v1 1到到v vi i的的所所有有路路中中的的最最短短路路。设设P P1j1j表表示示从从v v1 1到到v vj j的的最最短短路路长长，P P1i1i表表示示从从v v1 1到到v vi i的的最最短短路路长长，则则有有下下列列方程：方程： 开始时，令开始时，令 即用即用v v1 1到到v vj j的直接距离做初始解。的直接距离做初始解。从第二步起，使用递推公式：从第二步起，使用递推公式：求
27、求 ，当进行到第，当进行到第t t步，若出现步，若出现则停止计算，则停止计算， 即为即为v v1 1到各点的最短路长。到各点的最短路长。例二、例二、18v1v2v3v4v52635135211211v6v7v837660-5-3v8-5-550-1v7-1-1-17101v6-3-310-1v5-7-7-73208v4-2-2-2-21-50-3v3-5-5-5-1206v200003-2-10v1P(4)P(3)P(2)P(1)v8v7v6v5v4v3v2v1求图中求图中v v1 1到到各点的最短路各点的最短路18v1v2v3v4v52635135211211v6v7v837（0，0）（v3
28、，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）例、求：例、求：5 5年内，哪些年初购置新设备，使年内，哪些年初购置新设备，使5 5年内的总费用最小。年内的总费用最小。 第第i i年度年度 12345购置费购置费1111121213设备役龄设备役龄0-11-22-33-44-5维修费用维修费用 5681118解：（解：（1）分析：可行的购置方案（更新计划）是很）分析：可行的购置方案（更新计划）是很多的，多的，如：如：1）每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=842)第一年购
29、置新的，一直用到第五年年底，第一年购置新的，一直用到第五年年底，则总费用为：则总费用为：11+5+6+8+11+18=59显然不同的方案对应不同的费用显然不同的方案对应不同的费用。 （2 2）方方法法：将将此此问问题题用用一一个个赋赋权权有有向向图图来来描描述述，然然后后求求这个赋权有向图的最短路。这个赋权有向图的最短路。 求解步骤：求解步骤： 1 1）画赋权有向图：）画赋权有向图： 设设 V Vi i 表表示示第第i i年年初初，( (V Vi i ,V,Vj j ) )表表示示第第i i 年年初初购购买买新新设设备备用用到到第第j j年年初初（j-1j-1年年底底），而而W Wi i j
30、j 表表示示相相应应费费用用，则则5 5年的一个更新计划相当于从年的一个更新计划相当于从V V1 1 到到V V6 6的一条路。的一条路。 2 2）求解）求解 （标号法）（标号法） W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31
31、v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6161622221818171717171616303041415959313123234141303022222323v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6161622221818171717171616303041415959313123234141303022222323四、四、最大流问题最大流问题（一）（一）基本概念基本概念1、设设一一个个赋赋权权有有向向图图G=（V, E）,在在V中中指指定定一一个个发发点点vs和和一一个个收收点点vt ,其其它它的的点点叫叫做做中中间间点点。对
32、对于于D中中的的每每一一个个弧弧（vi ,vj）E,都都有有一一个个非非负负数数cij,叫叫做做弧弧的的容容量量。我我们们把这样的图把这样的图G叫做容量网络，简称网络，记做叫做容量网络，简称网络，记做G=（V，E，C）。）。网络网络G上的流，是指定义在弧集合上的流，是指定义在弧集合E上的一个函数上的一个函数其中其中f(vi ,vj)=fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。2、称满足下列条件的流为可行流：、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（）容量条件：对于每一个弧（vi ,vj）E有有0fij cij 。（2）平衡条件：平衡条件：对于发点对于发点vs，有有
33、对于收点对于收点vt ，有有对于中间点，有对于中间点，有可行流中可行流中fijcij 的弧叫做饱和弧，的弧叫做饱和弧，fijcij的的弧叫做非饱和弧。弧叫做非饱和弧。vsv1v2v4v3vt374556378S 3、容容量量网网络络G=（V，E，C），vs为为始始点点，vt为终点。如果把为终点。如果把V分成两个非空集合分成两个非空集合使使，则则所所有有一一点点属属于于，而而另另一一点点属属于于的的弧弧的的集集合合，称称为为由由决决定定的的割割集集,记记作作。割割集集中中所所有有始始点点在在，终终点点在在的的弧弧的的容容量量之之和和，称称为为这这个个割割集集的的容量，记为容量，记为。关于最大流问
34、题的定理：关于最大流问题的定理：最大流最小割定理：任一网络中，最最大流最小割定理：任一网络中，最大流的流量等于最小割集的容量。大流的流量等于最小割集的容量。 4、容容量量网网络络G，若若为为网网络络中中从从vs到到vt的的一一条条链链，给给定定向向为为从从vs到到vt，上上的的弧弧凡凡与与方方向向相相同同的的称称为为前前向向弧弧，凡凡与与方方向向相相反反的的称为后向弧，其集合分别用称为后向弧，其集合分别用和和表示。表示。f是一个可行流，如果满足：是一个可行流，如果满足：则称则称为从为从vs到到vt 的关于的关于f 的一条增广链。的一条增广链。推论推论可行流可行流f 是最大流的充分必要条件是不存
35、是最大流的充分必要条件是不存在从在从vs到到vt 的关于的关于f 的一条可增广链。的一条可增广链。13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一个增广链是一个增广链显然图中增广链不止一条显然图中增广链不止一条（二）求最大流的标号法（二）求最大流的标号法 标号过程：标号过程：1给发点给发点vs标号（标号（0，+）。）。2取取一一个个已已标标号号的的点点vi，对对于于vi一一切切未未标标号号的的邻邻接点接点vj 按下列规则处理：按下列规则处理：（1）如果边）如果边，且，且，那么给，那么给vj 标标号号，其中：，其中：（2）如如果果边边，且且
36、，那那么么给给vj 标标号号，其中：，其中：3重重复复步步骤骤2，直直到到vt被被标标号号或或标标号号过过程程无无法法进进行行下下去去，则则标标号号结结束束。若若vt被被标标号号，则则存存在在一一条条增增广广链链，转转调调整整过过程程；若若vt未未被被标标号号，而而标标号号过过程程无无法法进进行下去，这时的可行流就是最大流。行下去，这时的可行流就是最大流。调整过程：调整过程：1令令2去去掉掉所所有有标标号号，回回到到第第一一步步，对对可可行行流流重新标号。重新标号。 求下图所示网络中的最大流，弧旁数为求下图所示网络中的最大流，弧旁数为(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(,+)(vs,4)(-v1,1)(-v2,1)(v2,1)(v3,1)得增广链，标号结得增广链，标号结束，进入调整过程束，进入调整过程(3,3)(5,2)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4vt(vs,3)(,+)无增广链，标号结束，得无增广链，标号结束，得最大流。同时得最小割。最大流。同时得最小割。
