华师大计量地理学课件第10章 地理网络分析

第10章地理网络分析

对于许多现实的地理问题，譬如，城镇体系问题、城市地域结构问题、交通问题、商业网点布局问题、物流问题、管道运输问题、供电与通讯线路问题等等，都可以运用网络分析方法进行研究。

网络分析，是运筹学的一个重要分支，它主要运用图论方法研究各类网络的结构及其优化问题。网络分析方法是计量地理学必不可少的重要方法之一。本章主要内容地理网络的图论描述

最短路径与选址问题

最大流与最小费用流第1节地理网络的图论描述地理网络的图论描述地理网络的测度

通俗意义上的“图”，主要是指各种各样的地图、遥感影像图，或者是由各种符号、文字代表的示意图，或者是由各种地理数据绘制而成的曲线图、直方图等等。

图论中的“图”，是一个数学概念，这种“图”能从数学本质上揭示地理实体与地理事物空间分布格局，地理要素之间的相互联系以及它们在地域空间上的运动形式、地理事件发生的先后顺序等。

（1）图：

设V是一个由n个点vi(i=1，2，…，n)所组成的集合，即V={v1，v2，…，vn}，E是一个由m条线ei（i=1，2，…，m）所组成的集合，即E={e1，e2，…，em}，而且E中任意一条线，都是以V中的点为端点；任意两条线除了端点外没有其他的公共点。

一、地理网络的图论描述（一）图的定义那么，把V与E结合在一起就构成了一个图G，记作G＝（V，E）。

（3）边：E中每一条线称为图G的边（或弧）；若一条边e连接u，v两个顶点，则记为e＝（u，v）。

（2）顶点：

V中的每一个点vi（i=1，2，…，n）称为图G的顶点。

（4）在图G＝（V，E）中，V不允许是空集，但E可以是空集。

（5）从以上定义可以看出，图包含两个方面的基本要素：点集（或称顶点集）；边集（或称弧集）。例：在如图10.1.1所示的图中，顶点集为

V＝｛v1，v2，v3，v4，v5，v6，v7，v8｝，边集为E＝{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11}。图10.1.1（6）在现实地理系统中，对于地理位置、地理实体、地理区域以及它们之间的相互联系，可以经过一定的简化与抽象，将它们描述为图论意义下的地理网络，即图。

地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、码头、村庄、城镇等——点。它们之间的相互联系，譬如，构造线、河流、交通线、供电与通讯线路、人口流、物质流、资金流、信息流、技术流等——点与点的连线。一个由基本流域单元组成的复杂的流域地貌系统，如果舍弃各种复杂的地貌形态，各条河流——线，河流分岔或汇聚处——点，流域地貌系统——水系的基本结局（树）。

列昂纳德·欧拉——7桥问题

东普鲁士的哥尼斯堡城（现在的加里宁格勒）是建在两条河流的汇合处以及河中的两个小岛上的，共有7座小桥将两个小岛及小岛与城市的其他部分连接起来，那么，哥尼斯堡人从其住所出发，能否恰好只经过每座小桥一次而返回原处？图论研究结果告诉我们，其答案是否定的。

（7）需要说明的是：图的定义只关注点之间是否连通，而不关注点之间的连结方式。对于任何一个图，他的画法并不唯一。

（二）图的一些相关概念

（1）无向图与有向图：

无向图——图的每条边都没有给定方向，

即（u，v）＝（v，u）；

有向图——图的每条边都给定了方向，

即（u，v）≠（v，u）。

一般将有向图的边集记为A，无向图的边集记为E。这样，G=（V，A）就表示有向图，而G=（V，E）则表示无向图。有向图

（2）赋权图：如果图G＝（V，E）中的每一条边（vi，vj）都相应地赋有一个数值wij，则称G为赋权图，其中wij称为边（vi，vj）的权值。除了可以给图的边赋权外，也可以给图的顶点赋权。这就是说，对于图G中的每一顶点vj，也可以赋予一个载荷a(vj)。

（3）关联边：若e＝（u，v），则称u和v是边e的端点，e是u和v的关联边。（4）环：若e的两个端点相同，即u＝v，则称为环。

（5）多重边：若连接两个端点的边多于一条以上，则称为多重边。

（6）多重图：含有多重边的图，称为多重图。

（7）简单图：无环、无多重边的图，称为简单图。

（8）点与次。以点v为端点的边的个数称为点v的次，记为d(v)。

次等于1的点称为悬挂点；与悬挂点关联的边称为悬挂边。次为零的点称为孤立点。次为奇数的点称为奇点；次为偶数的点称为偶点。（9）连通图。在图G中，若任何两点之间至少存在一条路（对于有向图，则不考虑边的方向），则称G为连通图，否则称为不连通图。

（10）路（链）：若图G＝（V，E）中，若顶点与边交替出现的序列（对于有向图来说，要求排在每一条边之前和之后的顶点分别是这条边的起点和终点）P＝{vi1，ei1，vi2，ei2，…，eik-1，vik}

满足

eit

=(vit，vi，t+1)(t=1,2,…,k-1)

则称P为一条从vi1到vik的路（或链），简记为

P＝{vi1，vi2，…，vik}。

（11）回路：若一条路的起点与终点相同，即vi1=vik，则称它为回路。（12）树：不含回路的连通的无向图称为树。

（13）基础图：从一个有向图D＝（V，A）中去掉所有边上的箭头所得到的无向图，就称为D的基础图，记之为G（D）。（14）截：如果从图中移去边的一个集合将增加亚图的数目时，被移去的边的集合就称为截。（15）子图：设G＝（V，E）是一个无向图，V1与E1分别是V与E的子集，即V1V，E1E。如果对于任意ei∈E1，其两个端点都属于V1，则称G1＝（V1，E1）是图G的一个子图。

（16）支撑子图：设G1＝（V1，E1）是图G＝（V，E）的一个子图，如果V1＝V，则称G1是G的支撑子图。（17）支撑树：设G＝（V，E）是一个无向图，如果T＝（V1，E1）是G的支撑子图，并且T是树，则称T是G

的一个支撑树。（18）树的重量：一个树的所有边的权值之和称为该树的重量。（19）最小支撑树：在一个图的所有支撑树中，重量最小的那个叫做该图的最小支撑树。二、地理网络的测度

许多现实的地理问题，只要经过一定的简化和抽象，就可以将它们描述为图论意义下的地理网络，点和线的排布格局，并可以进一步定量化地测度它们的拓扑结构，以及连通性和复杂性。

树状型地理网络平面网络（二维的）非平面网络（非二维的）道路型环状型细胞型图10.1.5地理网络的拓扑分类

目前关于地理网络的拓扑研究，最多、最常见的是基于平面图描述的二维平面网络。

所谓平面图，被规定为：各连线之间不能交叉，而且每一条连线除顶点以外，不能再有其他的公共点（牛文元，1987）。

以下的讨论，除非特别申明外，都限于二维平面网络。

（一）关联矩阵与邻接矩阵

关联矩阵

测度网络图中顶点与边的关联关系。

假设网络图G＝（V，E）的顶点集为V={v1，v2，…，vn}，边集为E={e1，e2，…，em}，则该网络图的关联矩阵就是一个n×m矩阵，可表示为

式中：gij为顶点vi与边ej相关联的次数。v3v1v2v4v5e1e2e3e4e5e6e7该图的关联矩阵为

例：

邻接矩阵测度网络图中各顶点之间的连通性程度。

假设图G＝（V，E）的顶点集为V={v1，v2，…，vn}，则邻接矩阵是一个n阶方阵，可表示为式中：aij表示连接顶点vi与vj的边的数目。

该图的邻接矩阵为

v3v1v2v4v5e1e2e3e4e5e6e7例：

（二）有关测度指标对于任何一个网络图，都存在着3种共同的基础指标：

①连线（边或弧）数目m；

②结点（顶点）数目n；

③

网络中亚图的数目p。由它们可以产生如下几个更为一般性的测度指标：β指数、回路数k、α指数、γ指数。

也称为线点率，是网络内每一个结点的平均连线数目

β=0，表示无网络存在；网络的复杂性增加，则β值也增大。

没有孤立点存在的网络，连线数目为n-p,则β指数为β指数如果地理网络不包含次级亚图，即P＝1，则其最低限度连接的指数值为。回路数k

回路是一种闭合路径,它的始点同时也是终点。

若网络内存在回路，则连线的数目就必须超过n-p（最低限度连接网络的连接数目）。

回路数k为实际连线数目减去最低限度连接的连线数目，即

指数

指数指实际回路数与网络内可能存在的最大回路数之间的比率。

网络内可能存在的最大回路数目为连线的最大可能数目减去最低限度连接的连线数目，即所以，

指数为

指数也可以用百分率表示对于非平面网络，其指数为指数的变化范围，一般介于[0，1]区间，＝0意味着网络中不存在回路；＝1，说明网络中已达到最大限度的回路数目。

γ指数γ指数指网络内连线的实际数目与连线可能存在的最大数目之间的比率，对于平面网络，其计算公式为γ指数也可以用百分比表示

γ指数是测度网络连通性的一种指标，其数值变化范围为[0，1]。

γ＝0，表示网络内无连线，只有孤立点存在；γ＝1，则表示网络内每一个结点都存在与其他它所有结点相连的连线。

对于非平面网络，指数的计算公式为

表10.1.1几种简单网络图的有关测度指标

第2节最短路径与选址问题

最短路径问题选址问题

对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。

“纯距离”意义上的最短路径例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？“经济距离”意义上的最短路径

例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？一、最短路径问题（一）最短路径的含义

“时间”意义上的最短路径

例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？

以上3类问题，都可以抽象为同一类问题，即赋权图上的最短路径问题。

不同意义下的距离都可以被抽象为网络图中边的权值。

权——这种权值既可以代表“纯距离

”，又可以代表“经济距离

”，也可以代表“时间距离

”。

（二）最短路径的算法标号法1959年E.W.Dijkstar

提出的标号法是最短路径问题最好的求解方法。

标号法优点

不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其他任何一个顶点的最短路径及其长度；同时适用于求解有向图或无向图上的最短路径问题。.标号法的基本思想

设G是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。

首先从v1开始，给每一个顶点标一个数，称为标号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标号。那么，最多经过k-1步，就可以求得到从起点v1到每一个顶点的最短路径及其长度。标号法具体计算步骤

①如果刚刚得到P标号的点是vi，那么，对于所有这样的点将其T标号修改为：min[T(vj)，P(vi)+wij]。②若G中没有T标号，则停止。否则，把点的T标号修改为P标号，然后再转入①。

其中，满足

开始，先给v1标上P标号P(v1)＝0，其余各点标上T标号T(vj)＝+∞（j≠1）。例1：在图10.2.1所示的赋权有向图中，每一个顶点vi（i=1，2，…，n）代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。

图10.2.1赋权有向交通网络图解：首先给v1标上P标号P(v1)=0，表示从v1到v1的最短路径为零。其他点(v2，v3，…，v7)标上T标号T(vj)＝+∞（j＝2，3，…，7）。第1步：①

v1是刚得到P标号的点。因为(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T标号，所以修改这3个点的T标号为

T(v2)＝min[T(v2)，P(v1)+w12]＝min[+∞，0+2]＝2

T(v3)＝min[T(v3)，P(v1)+w13]＝min[+∞，0+5]＝5

T(v4)＝min[T(v4)，P(v1)+w14]＝min[+∞，0+3]＝3②

在所有T标号中，T(V2)＝2最小，于是令P(V2)＝2。第2步：①v2是刚得到P标号的点。因为(v2，v3)，(v2，v6)∈E，而且v3,v6是T标号，故修改v3和v6的T标号为T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4

T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9

②在所有的T标号中，T(v4)＝3最小，于是令P(v4)＝3。第3步：①v4是刚得到P标号的点。因为(v4，v5)∈E，而且v5是T标号，故修改v5的T标号为

T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8

②在所有的T标号中，T(v3)＝4最小，故令P(v3)＝4。第4步：①v3是刚得到P标号的点。因为(v3，v5)，(v3，v6)∈E，而且v5和v6为T标号，故修改v5和v6的T标号为

T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7

T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9

②

在所有的T标号中，T(v5)＝7最小，故令P(v5)＝7。

第5步：①

v5是刚得到P标号的点。因为(v5，v6)，(v5，v7)∈E，而且v6和v7都是T标号，故修改它们的T标号为T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]=8

T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14

②

在所有T标号中，T(v6)＝8最小，于是令：P(v6)＝8。第6步：①

v6是刚得到P标号的点。因为(v6，v7)∈E，而且v7为T标号，故修改它的T标号为T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13

②目前只有v7是T标号，故令：P(v7)＝13。

从城镇v1到v7之间的最短路径为(v1，v2，v3，v5，v6，v7)，最短路径长度为13。二、选址问题

选址问题，是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。选址问题的数学模型取决于两个方面的条件：可供选址的范围、条件；怎样判定选址的质量。本节的讨论仅限于选址的范围是一个地理网络，而且选址位置位于网络图的某一个或几个顶点上。

对这样的选址问题，根据其选址的质量判据，可以将其归纳为求网络图的中心点与中位点两类问题。

（一）中心点选址问题

例：某县要在其所辖的6个乡镇之一修建一个消防站，为6个乡镇服务，要求消防站至最远乡镇的距离达到最小。

中心点选址问题的质量判据

使最佳选址位置所在的顶点的最大服务距离为最小。中心点选址问题适宜于医院、消防站点等一类服务设施的布局问题。

设G＝（V，E）是一个无向简单连通赋权图，连接两个顶点的边的权值代表它们之间的距离，对于每一个顶点vi，它与各个顶点之间的最短路径长度为di1，di2，…，din。这些距离中的最大数称为顶点vi的最大服务距离，记为e(vi)。

那么，中心点选址问题，就是求网络图G的中心点，使得中心点选址问题的数学描述

例2：假设某县下属的6个乡镇及其之间公路联系如图所示。每一顶点代表一个乡镇；每一条边代表连接两个乡镇之间的公路，每一条边旁的数字代表该条公路的长度。现在要设立一个消防站，为全县的6个乡镇服务。试问该消防站应该设在哪一个乡镇（顶点）？

图10.2.2解：第1步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij（i，j＝1，2，…，6），并将它们写成如下的距离矩阵

第2步：求每一个顶点的最大服务距离。显然，它们分别是矩阵D中各行的最大值，即：e(v1)＝6，e(v2)＝7，e(v3)＝6，e(v4)＝7，e(v5)＝6，e(v6)＝7。

第3步：判定。因为e(v1)＝e(v3)＝e(v5)＝min{e(vi)}＝6，所以v1，v3，v5都是中心点。也就是说，消防站设在v1，v3，v5中任何一个顶点上都是可行的。中位点选址问题的质量判据

使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。（二）中位点选址问题中位点选址问题的数学描述

设G＝（V，E）是一个简单连通赋权无向图，连接两个顶点的边的权值为该两顶点之间的距离；对于每一个顶点vi（i＝1，2，…，n），有一个正的负荷a(vi)，而且它与其他各顶点之间的最短路径长度为di1，di2，…，din。那么，中位点选址问题，就是求图G的中位点，使得例3：某县下属7个乡镇，各乡镇所拥有的人口数a(vi)（i=1，2，…，7），以及各乡镇之间的距离wij（i，j=1，2，…，7）如图所示。现在需要设立一个中心邮局，为全县所辖的7个乡镇共同服务。问该中心邮局应该设在哪一个乡镇（顶点）？

图10.2.3解：第1步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij（i，j＝1，2，…，7），并将其写成如下距离矩阵

第2步：以各顶点的载荷（人口数）加权，求每一个顶点至其他各个顶点的最短路径长度的加权和

第3步：判断。因为

所以，v3和v4都是图10.2.3的中位点。即：中心邮局设在点v3或点v4都是可行的。

第3节最大流与最小费用流

最大流问题及其求解方法最小费用流及其求解方法一、最大流问题及其求解方法

（一）最大流问题最大流问题设有向网络N（V，A），在发点Vs

有一批货，要通过网络上的弧运输到收点Vt

去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij

辆，分析：如何组织运输才能使从Vs到Vt

在单位时间内通过的车辆达到最多？上面描述的这类问题，称为最大流问题。

最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。例：如图10.3.1中，有一批物资需要用汽车尽快从发点①运到收点⑦，弧（i，j）上所标的数字表示该条道路在单位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从①调到⑦。图10.3.1┍┑线

性

规

划

方

法┕┙

点①出发的车辆数应该与点⑦到达的车辆数相同，除①和⑦以外的各中间点，进的车辆数应该与离去的车辆数应该相同。xij

是通过弧(i，j)的车辆数。（10.3.1）（10.3.4）（10.3.5）（10.3.6）（10.3.2）（10.3.3）

对所有弧（i，j），应满足约束

满足（10.3.1）～（10.3.7）的解称为从①到⑦的一个可行流。我们的目的：在所有可行流中求出一个方案，使得这个可行流得到的f最大。

若从收点到发点连接一条假想弧(7，1)，设它的容量c71=∞，那么

对点①：

对点⑦：

最大流问题的目标为┍┑线

性

规

划

方

法┕┙

（10.3.7）（10.3.8）（10.3.9）（10.3.10）所以，对于发点为Vs，收点为Vt的网络N（V，U），当增加一条约束为cts=∞的假想弧（t，s）后，最大流问题就成为：

容量约束

平衡条件

目标函数┍┑线

性

规

划

方

法┕┙

（10.3.11）（10.3.12）（10.3.13）（二）求最大流的方法：弧标号法

尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法——弧标号法，求解上述最大流问题。

(1)为了便于弧标号法的计算，首先需要将最大流问题（譬如图10.3.1）重新改画成为图10.3.2的形式。图10.3.2在图10.3.2中，每条弧上标有两个数字，其中，靠近点i的是，靠近点j的是。如①②表示从①到②的最大通过量是5（百辆），从②到①的最大通过量是0；②③表示从②到③和从③到②都可以通过2（百辆）；等等。

图10.3.2

(2)求最大流的基本步骤：标号法求最大流的过程，就是对图10.3.2反复地进行修改的过程，其计算步骤如下：

步骤1.从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。

步骤2.在选定的路上，找到最小的容许量cij定为P。

步骤3.对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为cij-P，对于与路反向的弧，将cij修改为cij+P。修改完毕后再转入步骤1。步骤4.用原图中各条弧上起点与终点数值减去修改后的图中对应点的数值，得到正负号相反的两个数，并将从正到负的方向用箭头表示。这样，就得到一个最大流量图。

第1次修改：

①从发点s到收点t找一条路，使得这条路上的所有弧前面的约束量。从图10.3.2中可以看出，显然，①—③—⑥—⑦就是满足这样的条件的一条路。

下面，我们用弧标号法求解图10.3.2中的最大流。

②在路①—③—⑥—⑦中,,,，所以取。

③在路①—③—⑥—⑦中，修改每一条弧的容量通过第1次修改，得到图10.3.3。图10.3.3返回步骤①，进行第2次修改。

第2次修改：选定①—②—⑤—⑦，在这条路中，由于，所以，将改为2，改为0，改为5，、、改为3。修改后的图变为图10.3.4。

图10.3.4返回步骤①继续做第3次修改。第3次修改：取①—②—③—⑤—⑦，在这条路中，由于所以将改为0，改为5，改为0，改为4，改为1，改为2，改为3,c75改为5。修改后的图变为图10.3.5。

图10.3.5返回步骤①，继续做第4次修改。，

第4次修改：选定①—④—⑥—⑦，在这条路中，由于P=c67=1，所以将c14改为4,c41改为1,c46改为4,c64改为1,c67改为0，c76改为7。修改后的图为变为图10.3.6。

图10.3.6返回步骤①，继续做第5次修改。

第5次修改：选定①—④—⑥—⑤—⑦,在这条路中，由于P=c65

=1，所以将c14和c46均改为3，c65改为0，c57改为2，c41、c64、c56均改为2，c75改为6。修改后的图变为图10.3.7。

图10.3.7需要注意的是，由图10.3.7中可以看出，弧本来在图10.3.2中是无容量可通过的，但经过几次修改，由③⑥变成③⑥，即此时从③到⑥还可通过1（百辆），而从⑥到③，可以通过6（百辆）的容量，这说明，修改过程实际上是把计划中从③到⑥的通过车辆数减少了。第6次修改：取①—④—⑥—③—⑤—⑦，在这条路中，由于P=c35=1，所以将c14和c46均改为2，c63改为5,c35改为0，c57改为1，c41、c64、c53均改为3，c36改为2，c75改为7。修改后的图变为图10.3.8。

图10.3.8在图10.3.8中，从发点①到收点⑦，再也不存在连通的起点容量都大于零的弧了，所以图10.3.8为最大流图。

转入步骤④，用原图中各条弧上发点与收点数值减去修改后的图上各点的数值，将得到正负号相反的两个数，将这个数标在弧上，并将从正到负的方向用箭头表示,这样就得到最大流量图。例如原来弧是③⑥，现在是③⑥，相减为±5，③那边为正，我们就记作③⑥。这样，就得到图10.3.9，即最大流量图。依这样的调度方式，可以从发点s调运14（百辆）汽车到收点t。

图10.3.9最大流量图

(3)最大流算法的讨论：

①从上面的标号计算过程可以看出，一个图成为最大流图的条件是从发点到收点的每一条路上总存在某个起点容量为零的弧，我们称这样的路为饱和路；如果从s到t有一条路，它上面每条路的起点容量都大于零，则称为非饱和路。由此可以得到一个结论：一个图是最大流图的充分必要条件是不存在从s到t的非饱和路。

②将网络中的点分成两组，一组包括发点，称为发集，一组包括收点t，称为收集，连接到的所有弧称为截集，截集中各弧在旁的容量和称为截集的容量。

例如，在图10.3.2中，

图10.3.2我们取，，则截集为{(2,5),(3,5),(1,4),(3,6),(3,4)}，它的容量为3+3+5+7+3=21；若在图10.3.6中，取，，则截集为{(2,5),(3,5),(6,5),(6,7)}，其容量为0+1+1+