图论教案final.doc

§1 图论的著名问题与历史
图论是数学中一个既古老又年轻的数学分支．欧拉1736年关于哥尼斯堡七桥问题论文的发表标志着图论的诞生．自二十世纪五十年代开始，由于运筹学、计算机科学的促进，以及应用领域的扩大，图论已成为一个独立的数学分支．特别在近三十年，图论正经历着一个蓬勃发展的时期，表现出年轻学科所具有的强大生命力．
一. 图论中的几个著名问题
例1.哥尼斯堡七桥问题
哥尼斯堡历史上曾是德国东普鲁士的省会，第二次世界大战后归苏联所有，也
就是现在的加里宁格勒市.普列格尔（Pregel）河穿城而过，河中有两个小岛，岛与河岸及岛与岛之间有七座桥.当时流行很广的一个难题是：能否从河岸或两个小岛中的任一处出发，经过每一座桥一次且仅一次再回到出发地呢？这个问题被瑞士数学家欧拉解决了.如下图所示，A、B、C、D表示陆地.
抽象成

1736年，欧拉（1707-1783）在俄国彼得堡科学院院报上发表了一篇论文.他在论文中引进了图的概念和方法，用抽象分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个「图」，将七桥问题转化为一笔画问题.欧拉证明了这个问题没有解——这是由于此「图」与每个顶点相关联的边数均为奇数，并且推广了这个问题.给出了对于一个给定的图可以某种方式一笔画的判定法则.这项工作使欧拉成为图论﹝及拓扑学﹞的创始人.
引深：图G是欧拉图的充要条件是什么？
例2．哈密尔顿多面体问题
1856年英国数学家哈密尔顿（1790-1868）提出了这样一个问题：用一个规则的实心十二面体，它的二十个顶点标出世界著名的二十个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即「绕行世界」.用图论的语言来说，游戏的目的是在十二面体的图中找出一个包含所有顶点的圈.这个问题后来就叫做哈密顿问题.由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究.
引深：什么图是哈密尔顿图呢？其判定条件如何？
例3.四色问题
在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色.每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点.四色猜想有一段有趣的历史.每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接.所以四色猜想是图论中的一个问题.它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用.
问题转化为：给平面图G的顶点着色，使任一对相邻顶点具有不同的颜色，那么至少要多少种颜色？
1852年，英国的弗兰西斯提出了四色问题；1878年凯莱在伦敦数学会宣布了此问题，引起了数学界的广泛重视.肯佩和泰特分别与1879年和1880年发表文章，声明证明了四色问题；11年后，希伍德于1890年指出了肯佩证明中的错误，却利用肯佩的方法证明了五色定理；1891年彼得森又指出了泰特证明中的错误，却利用泰特的方法证明了四色猜想的一个等价命题.世界上许多数学家为四色猜想倾注了大量心血.经过一百多年后，这个貌似简单的四色猜想被美国的阿佩尔和哈肯于1976年借助于电子计算机给出了证明.他们的证明用计算机大约需要1200小时，要作出100亿个独立的逻辑判断！他们的工作无疑具有开创性，是值得称赞的.给出四色定理一个无需借助于计算机的证明乃是一个未能解决的问题.
二、图论发展简史
1736年，欧拉关于哥尼斯堡七桥问题的论文的发表，人们普遍认为图论由此诞生.
1847年，德国数学家、物理家克希荷夫应用图论方法来分析电网络，奠定了现代网络理论的基础.
1852年，佛兰西斯提出了四色猜想，引起了数学界的广泛注意，使许多数学家对图论产生了浓厚的兴趣，极大地推动着图的着色理论的发展.
1856年，爱尔兰数学家哈密尔顿提出了正十二面体游戏问题，引出了哈密尔顿的理论.
1857年，英国数学家凯莱在研究饱和碳氢化合物的同分异性体时，发现了“树”的概念和理论，并由此预见了未知化合物的存在.
1936年，匈牙利数学家哥尼科，总结前人的成果，发表了第一部图论专著《有限图和无限图的理论》.
自二十世纪五十年代开始，由于运筹学、计算机的促进以及应用领域的扩大，图论已成为了一个独立的数学分支.特别在近二十年，图论正经历着一个蓬勃发展的时期，表现出年轻学科所具有的强大生命力.许多大学的系，如数学系、计算机科学系、运筹系、组合优化系、电机系等都开设了图论这门课.图论是一门应用广泛的数学分支，它不但在自然科学的许多领域有重要的应用，还应用于社会科学的诸多方面.许多实际问题（离散）所建立的数学模型就是一个图论模型.图论不但与大学生数学建摸竞赛联系甚紧，而且在中小学数学竞赛中经常出现来源于图论的题目.

§2 图 的 基 本 概 念

一. 无向图、有向图、子图
1. （无向）图 无向图是指三元组，其中是一个非空集合，称为顶点集；是任意集合，称为边集；是到的映射，记作或．
在E中重复次的边称为重边；两端点重合的边称为环．
2. 有向图 有向图是指三元组，其中是非空顶点集，是边的集合，是到的映射,记作或．
有向图与无向图的差别仅在于中元素是中元素的有序对还是无序对．然而，无序对可以视为两个有序对和．也就是说，对于无向图，将中每条边用两条与有相同端点的对称边和来替代后得到一个有向图，这样得到的有向图称为的对称有向图．于是无向图可以视为特殊的有向图.例如，城市交通中，双行道可以视为对开的两个单行道．以下我们只对无向图来叙述．
图可以画出它的直观图形，称为此图的图形表示．

3.简单图 无重边也无环的无向图称为简单图．
4.子图
如果，那么图称为图的子图，记作．
如果是的子图，且，则称是的生成子图或支撑子图．
若，则子图称为由导出子图，记为．
设，记的导出子图为．
设，是中的边的所有端点所成的集，则的子图称为由导出的子图，记为，又记．
两个图可以引入交、并、联的运算．
二. 顶点的度
1.设是图，，中与关联的边数（重边按重数计）称为顶点的度，记作．
为奇（偶）顶点为奇（偶）数．
2.对于有向图，可定义出度与入度．
3.结论
① 握手引理：设是任意图，则．
② 任意一个图的奇顶点的个数是偶数．
三. 正则图、完全图、二部图．
1. 若，有（常数），则称为正则图．
2. 设，则的任意两顶点均邻接的简单图称为阶完全图，记为．
3. 是单点图；是空图
4. 若图的顶点集有一个划分，且是空图，则称是（具有二划分的）二部图，记作，二部图亦称为偶图．
对于简单二部图，若的任一顶点与的任意顶点都相邻，则称为完全二部图，记为，其中．

§3 路 与 连 通 性

一. 链、迹、路、圈
链 图的链是中顶点与边交替出现的有序序列.称为起点，称为终点，中边的条数称为的长度．
迹 图中任意两边均不相同的链称为迹．
路 图中任意两顶点均不相同的链称为路，显然，路必是迹，但反之不然．
在上面的链、迹、路中，当起点与终点重合时，分别称为闭链、闭迹、闭路．闭路亦称为圈，圈的长度定义为其中边的条数，长度为奇数的圈称为奇圈；长度为偶数的圈称为偶圈．
二部图的刻划：图为二部图中不含奇圈．
二. 连通与连通分解
考虑图，设，若存在与间的路，则称与是连通的．若图的任意两顶点都连通，则称为连通图．
任意图均可表成若干个两两顶点不重复，边也不重复的连通子图的并，这些连通子图称为的连通分支，的连通分支数记为．
考虑有向图，可定义的有向路．
若有向路中，，存在到的有向路或存在到的有向路，则称是单向连通的．
若有向图中，，既存在到的有向路又存在到的有向路，则称是强连通的．
有向图的顶点集中元素之间的强连通关系是上元间的等价关系．由这种关系得到的等价类在中导出子图称为的强连通分支．的强连通分支数记为．若，则称为强连通图，反之，称为非强连通图．
三.可靠通信网问题
在战争状态，我方要构作一个有线通讯网，使得敌方炸毁我方几个通讯站后，其余的通讯仍然可以彼此通话，自然希望不怕被敌方炸毁的通讯站要尽可能多.但限于施工的条件、时间、造价等.要每两个通讯站间均架设直通线路是有困难的，那么满足一定可靠程度的通讯网该如何构作呢？这就涉及到一个连通度、边连通度问题.若图G中存在不相邻的顶点，则使G—不连通. 称为图G的顶点割.
图G的连通度定义为：

设S与是V的非空子集，用表示图G中一端属于S，一端属于的一切边所构成的边集.特别地当，S,而.则称是G的边割.
对于一个非平凡连通图G，去掉其中任何一个边割后得到的图必不连通.于是可定义图G的边连通度如下：

四.通知球员问题
某足球俱乐部职业队新聘A为主教练，A确定了全队队员名单，需通知所有队员到俱乐部报到，A通知每一名队员所需费用不同，A知道有的队员可以转告其他队员．
A通知每个队员的费用（元）及可以转告队员名单

费 用
5
6
4
12
10
7
8
5
0.5
10
4
3
可 转 告 队 员

—

—

问：A应通知哪些队员，使费用最少？

我们用图的顶点来表示全队n名队员．若可以直接转告，则连以有向边，A通知所需的费用为，记作顶点所带的权，这就得到一个顶点赋权有向图，于是，问题转化为求的顶点集的一个子集，满足：（1），有或者有，使中存在到的有向路；（2）所含的顶点数最少；（3）中顶点的权和最少．这就是通知球员问题的图论模型．
设D=是有向图，,若,都有或者存在,使中存在到的有向路，则称是的一个点基．中含顶点数最小的点基称为最小点基．又设是顶点赋权有向图，是顶点的权，是的点基，则称为的权，于是通知球员问题的解就是相应有向图的具有最小权的最小点基．
设是的一个强连通分支，若中不存在终点在中而始点不在中的有向边，则称是的一个最高强连通分支．
由最高强连通的定义，可以证明：从中的每一个最高强连通分支中各任取一个顶点，所组成的集合就是的一个最小点基，并取一个最小权的顶点．
（求出强连通分支，后代集，前代集，）
五.最短路问题
考虑n个城市的公路网络，试求一个城市到其余各城市的最短路．
以城市为顶点，公路为边，得到一个图，每条公路都有长度（公里数），这样，给赋以一个实数称为的权，于是得到一个赋权图，设，路的权（或子图的权）为其各边的权和，试求到的权和最小的路，亦称为最短路．
求最短路的算法——Dijkstra算法：
(i) 令，又令
(ii) 对每个，用代替，计算，把达到这个最小值的顶点记为，令
(iii) 若，则停止；若，则用代替，转向（ii）．
2
1
2
例1：求下图中到各顶点的最短路．

1
4
5
1
2

7
8
3
3
6

2
4
4

2
4
6

9
4
7
6
6

例2: 求天然气管道最优路径
筹建中的天然气管道网设计如图所示：

1
3
3
3
1
2
5

3
2
4
4
4
6

4

3
3
4

5

5

2

表示压缩机站，流动主向用箭头表示，每个管道旁的数字表示管段长度，现需要求该网络从起点A到终点L的最短通道，并确定沿最优路径相应的压缩机站所处的节点．
解为：

§4 树

一. 树的概念及性质
连通的无圈图称为树，常用表示．
无圈图称为林．
若,,则称顶点为树的树叶．

例如

乙烷
甲烷

家族树

4顶点的树

3顶点的树
2顶点的树

生成树（支撑树） 若树是图的生成子图，则称是的生成树（或支撑树）．
树的若干充要条件：
设是图，记，则以下诸命题等价：
(i) 是树；
(ii) 中任意两顶点间恰有一条路；
(iii) 中无圈，且
(iv) 连通, 且
(v) 连通,但，不连通（极小连通图）；
(vi) 无圈但，必有圈（极大无圈图）．

二、有向树、二元树
设有向图，，若均存在有向路，则称是的一个根．
有向图的基础图是指去掉各边的方向后所得到的无向图．
有向树：若有向树的基础图是树，且有根，则称是以为根的有向树．
易知：有向树恰有一个根．
在有向树中，出度为0的顶点称为树叶．
若有向树的每一顶点间都排有顺序，则称为有序树．在有序树中，若，均有，则称为元树，当时，称为二元树．
若在中除叶外均有，则称为完全元树．

有向树

完全元树

三、 连线问题、最优树
1. 连线问题
考虑连接若干个城镇的铁路网络，如何设计才能使总造价最少？
以这些城市为顶点，可修铁路为边，每边都赋以权，为两城镇与间的铁路造价，得到一个赋权连通图．
试在中，求具有最小权的连通的生成子图，由于要求权最小，这样的子图必不含圈，故此生成子图必是的生成树，赋权图的具有最小权的生成树称为最优树．
2. 求赋权图的最优树的算法：
（i） 选择，使最小．
（ii） 若已选出边，则从中选择满足：
① 无圈．
② 是满足①的尽可能小的权．

（iii） 当第（ii）步不能继续执行时停止．
3
15
例如

9
8
16
5

7
4
2
1
10

6

§5 E图、H图及其推广

这是由哥尼斯堡七桥问题和周游世界问题引出的图论问题．
一、图（E图）
若图中有包含一切边的闭迹，则称为图，而这样的闭迹称为的闭迹．若中有包含一切边的迹，则称为半图，而这样的迹称为迹．显然，每一个图都是半图．
图简称为图，形象地说，图就是从任一顶点出发通过每一条边恰好一次又能回到出发点的图，下面的结果给出图的特征．
１.设是连通图，则下列三命题相互等价：
（i）是图；
（ii）的每个顶点都是偶顶点；
（iii）可表成若干个边不交的圈之并，即，是圈，且当时，．
２.设是连通图，则中存在迹的充要条件是中的奇顶点个数为0或2．
二、中国邮递员问题
一个邮递员每天投递邮件都要走遍他所负责投递区域内的每条街道，完成投
递任务后回到邮局．他应怎样选择路线，才能使他所走的总路线最短？国际上称这个问题为中国邮递员问题，它是由我国数学家管梅谷教授于1960年首先提出并进行研究的．
我们把邮递员所负责投递区域看作一个连通的加权有向图，其中街道
的交叉口视为的顶点，街道（单向）视为边，街道的长度视为边的权．经过中每条边至少一次的有向闭链称为邮路，具有最小权的邮路称为最优邮路．解中国邮递员问题就是在连通的加正权有向图中找出一条最优邮路．
在现实生活中，有许多问题，比如城市里的洒水车、扫雪车、垃圾清洁车和参观展览馆等最佳行走路线问题都可以归结为中国邮递员问题．中国邮递员问题的广泛应用，引起了人们极大研究兴趣，提出了许多有效算法.
三、图（H图）
包含图的所有顶点的路称为路或路；包含图的所有顶点的圈称为圈或圈．若一个图存在圈，则称为图或图．
图的研究起源于1856年提出的“周游世界问题”，与图的情况相反，图的能方便应用的充要条件目前尚未找到，这是图论中尚未解决的主要问题之一．由于它的重要性，吸引了不少图论学者对它进行研究．关于图的性质有以下结果：
1．（图的必要条件）若图是图，则，且，有．
2．（图的充要条件，定理）若是个顶点的简单图，且，不相邻,有 ，则是图．
3．设是有个顶点的简单图，若有，则是图．
4．设是简单图，是中不相邻的顶点，且适合，则是图是图．
5．设为简单图的闭包，则是图的充要条件为是图．
6．设是个顶点的简单图，若是完全图，则是图．
四、货郎担问题（旅行推销员问题）
货郎担问题是与图有关的著名问题. 它的提法是：一个货郎挑着担子从家里出发到各村去卖货，然后回到家里，各村有远有近，应怎样选择他的路线，使他到每个村至少一次而总路程最短，这个问题称为货郎担问题．
我们以货郎家及各村为图的顶点，各村间的道路为边，道路的长度定义为边的权，得到一个赋权连通图，于是货郎担问题就转化为在给定的赋权连通图中找一条最小权的圈或找一条经过中每个顶点至少一次的最小权闭链，分别称为最优圈和最优链，一般的连通赋权图未必存在最优圈，然而最优链总是存在的.
我们用图的顶点来表示货郎家及各村，各村间的道路用边来表示，道路的长度定义为边的权，边e的权记作.于是得到一个赋权图G.于是货郎担问题就是要在给定的赋权连通图G中找一条最小权的H圈或找出一条经过G中每个顶点并且有最小权的闭链，分别称为最优圈和最优链，一般的连通赋权图未必存在最优圈.然而最优链总是存在的.关于一个连通赋权图的最优链算法参见：
1、 徐俊明《图论及其应用》，中国科大出版社，1998，第五章，§5
2、 杜端甫《运筹图论》，北京航空航天大学出版社，1990，第十二章
美国大学生数学建模竞赛90年B题“扫雪问题”就要用到“中国投递员问题”的理论.
中国大学生数学建模竞赛98年B题“灾情巡视路线”，用到“货郎担问题”的理论.

§6 匹配与独立集

一、匹配
１.匹配问题的研究是由工作分配问题、配偶问题等实际问题引深的.
[工作分配问题] 某单位要从m位职工中挑选n位职工来分别承担n项不同的新工作.用L={}表示n项新工作的集，用G={ }表示这m位职工之集.设G中能承担这一工作的职工的集合为 (i=1,2…,n).试问在什么条件下，能从G中找出n位职工来分别承担这n项不同的新工作. (即要这n位职工分别属于)(i=1,2…,n).如果找不到n位职工来分别承担这n项不同的新工作，那么最多能使n项工作的几项分别有人承担？
2.匹配的有关概念
（1） 设G是一个图，ＭＥ（Ｇ），Ｍ.若M中的边都是连杆（即不是环），且任意两边都不相邻.则称M为G的一个匹配.
（2） 设M是图G的匹配，v V(G).若v是M中某条边的端点，则称v是M的饱和点.
（3） 设是图G的一个匹配，若G的匹配M，均有

则称是G的一个最大匹配．

（最大）匹配：

（4） 若图G的匹配M满足：= ，则称M是G的一个完美匹配.（并不是每个图都有完美匹配）
（5）设M是图G的一个匹配，P是G一条路，若从P的起点到终点所经过的边依次交错地属于E(G)\M与M，则称P是一条M交错路.
3.若干结论和定理
（1） 完美匹配必是最大匹配，而最大匹配未必是完美匹配.
（2） M是G的完美匹配 M是G的匹配且G的每个顶点都是M的饱和点.
（3） 任何图都有最大匹配，但却未必有完美匹配.一个图G有完美匹配的必要条件是为偶数.
（4） 设M是图G的一个匹配.则M是G的最大匹配的充要条件为：G中不存在连接两个不同的M非饱和点的M交错路.
（5） 设G(X,Y)是二部图（偶图），则G存在饱和X中每个顶点的匹配的充要条件为： , 有 .这里N(S)表示G中与S中的顶点相邻的顶点集合.
（6） 若G是k(k>0) 正则二部图，则G有完美匹配.
二、独立集、覆盖
１.独立集
设G一简单图，S V(G)，若S中任意两个顶点在G中都不相邻.即G[S]是空图，则称S是G的一个点独立集或独立集.
图G的满足顶点数最多的独立集称为G的最大独立集.图G的最大独立集的基数称为G的独立数.记为G）.
图G的匹配亦称为边独立集，图G的最大匹配称为G的最大边独立集.图G的最大边独立集的基数（即G的最大匹配数）称为G的独立数.记为(G).
2.覆盖
设G是图，KV(G)，若G的每一条边中至少有一个端点属于K，则称K为G的一个覆盖.图G的顶点数最少的覆盖称为最小覆盖.图G的最小覆盖基数称为G的覆盖数.记为 (G).
设G是图.LE(G).若G的每个顶点都是L中某条边的端点，则称L是G的一个边覆盖.边数最少的边覆盖称为G的最小边覆盖.G的最小边覆盖的条数称为G的边覆盖数.记为 (G).
3.结论或定理
①设是图，，则是的独立集的充要条件为是的覆盖.
②任意一个图的独立数与覆盖数之和等于图的阶，即.
③若图没有孤立点，则.
④设是二部图，则.
匹配、独立集、覆盖理论有许多实际应用,工作分配问题、配偶问题、防止罪犯串供捉拿方案问题、公路配备消防车问题、收款台的设置问题等都是其理论应用的例子.全国大学生数学建模竞赛试题94年B题、99年B题都涉及到匹配、独立集理论.

§7 图的着色
一 引入
如果某两种化学药品接触后会产生有害反应，为了避免意外，它们就不宜存放在一起.假定有n种化学药品，问至少把它们分多少处存放，才能保证安全？现将此问题转化为图论问题.
用顶点表示n种药品，若药品与不宜放在一起，就把顶点与连一条边，于是得到一个图，给此图的顶点进行染色，使得相邻的顶点染上不同的颜色.于是：至少要把这些化学药品分多少处存放至少要用多少种颜色去染图的顶点，使任意两个相邻的顶点的颜色不同.
二 顶点着色的有关概念
给图的顶点染上颜色，使得任一对相邻的顶点具有不同颜色称为图的顶点着色.
若图的某一个顶点着色中所用的颜色数目，则称此着色为着色.若图存在着色，则称是可着色的.
使得是可着色的的最小值称为的点色数，简称为色数，记作.若图满足，则称是色图.
求图的色数是图的着色理论中一个重要问题，也是最难的问题.
三 几个结论
①空图的色数是1；非空二部图的色数为2.
②图的色数为部图但不是部图.
③若表示图的最大度，则

④当为奇圈时，，，有；当为完全图，，，有.
⑤（布鲁克斯定理）若是简单连通图，并且不是奇圈，也不是完全图，则.
四 四色问题
在§1提到了四色问题，现把四色问题作如下转化：若把至少属于三个国家的边界上的点看成图的顶点，连接两个顶点的两个国家的公共边界看成边，又当一个国家被另一个国家全部包围时，就在其公共边界的闭曲线上任取一点作为顶点，则地图就成为了一个平图，国家对应于此平图的面.
注：所谓平图是指画在平面上且交点均为顶点的图.
此平图是一个无割边的图.这是因为一条边界的两侧总是不同的国家.作此平图的对偶图（对偶图的概念参见有关图论教材），则是一个无环的平图.的面与的顶点相对应，的两面相邻的相应顶点相邻，给的面（国家）染色给的顶点染色.
四色猜想即为：对于任意简单平面图，有.
五色定理：若是任意简单平面图，则.

§8 网 络 流
1、网络
所谓网络是指具有两个不同的特定顶点和的赋权连通有向图，记为，其中和分别称为发点和收点.若为非负的函数，则称网络为容量网络，其中在边上的值称为边的容量.若对任何，都是非负整数，则称为整容量网络.
2、流
约定：设为一有向图，，令到实数集中的所有映射的集合对于函数（映射）的加法、数量乘法所成的线性空间为.
又令表示中所有以为起点的边集，表示中所有以为终点的边集.设，这样就是一个赋权图，而为权函数，令.
设为容量网络，若使得
（ⅰ）；
（ⅱ）
则称是中从到的流，简记为流.
易知，对于中任何一个流均有：

上式中等号两边的值称为流的流量，记为.中具有最大流量的流称为中最大流.
3、最大流与最小截
设为容量网络.，，表示中起点在而终点在的边集，则称为截边集，而称为的容量，记为.具有最小容量的截边集称为中的最小截.
最大流最小截定理：在任何容量网络中，最大流量等于最小截容量.
整数最大流最小截定理：任何整容量网络中都存在整数最大流，而且其流量等于最小截容量.
最大流最小截定理是网络分析方法的基础.由此定理不仅可以求出网络中的最大流和最小截，而且可以导出图论中许多著名的定理.

§9 网络流的应用

一、运输方案的设计
商品从产地运到销地必经之途构成一个交通系统.假定此交通系统多段运输容量给定.试设计一个运输方案，由此方案将产地运到销地有最大的输送量.如果再想提高输送量，需要增加那些路段的运输容量.
试将此交通系统看作是一个容量网络，其中D是由这个交通系统构成的简单连通图，发点和收点分别看作商品的产地和销地，容量函数看成是运输容量.于是上述问题归结为在N中求一个最大（）流和最小容量的（）截边集.
设是N=中的流，是D中顶点，，并设P是D中一条连接和的路（未必是有向路）.给定P从x到u的方向为正向，用和分别表示E（P）中与P的正向和反向一致的边集.令

并令
若.则称P是的饱和路；若，则称P是非饱和路.非饱和的路P称为增广路.之所以称为增广路,是由于流f的流量沿此路是可以增加的.事实上，由

所定义的是中的流并且此处称为基于的增广路的修正流.
定理 中的流是最大流N中不含增广路.
此定理提供了一个求整容量网络中最大流（最小截）的有效算法.算法的基本思想是从N中任何一个已知（x, y）流（例如零流）开始，递归地构造出一个其流量不断增加的序列，并且终止于最大流.在每个新的流作出之后.如果存在增广路P，则作出基于P的修正流，然后将作为初始流重新执行算法.如果不存在增广路，则算法停止，由定理知是最大流.
二、最优运输方案的设计
在前面设计运输方案时，我们考虑的仅仅是流量，而没有考虑到费用（或者说仅考虑在各路段中单位输送量的费用都相等）.在实际问题中，费用的因素很重要.由于在各路段中运输设备的不同，因此单位输送量的费用不尽相等.这就要求我们设计一个输送量最大且总的运输费用最小的运输方案，这样的运输方案称为最优运输方案.
用一个被称为费用容量网络表示该交通系统，其中表示单位流量费用函数，是容量函数.

边上的有序对分别表示该边上的费用（单位流）和容量.

费用容量网络
设f是N中（x ,y）流，则定义为f的费用.
用网络的语言来说，最优运输方案的设计就是在费用容量网络中求最大（x,y）流且使费用最小，这样的流就称为最小费用最大流.
设为费用容量网络，是N中（x,y）的流，C是D中有指定正向的圈.令

若D中的圈C存在一个定向使>0，则称C为f增广圈，对于增广圈C，定义如下：

易证是N中（x,y）流而且.称为基于增广圈C的修正值.
设C是f增广圈，则定义f增广圈C的费用为
若对N中其流量等于的任何一个流均有，则称为最小费用流.
定理 N中流是最小费用流N中每条增广圈C都有.
此定理提供了解最小费用最大流问题的一个算法，其基本思想是：从N中任何一个最大流出发，检查每个增广圈.若所有增广圈的费用都是非负的，则就是所求的最小费用最大流.若存在增广圈C使得，则用修正流替代再重复上述过程.
关于寻找费用为负的增广圈，可以通过作辅助图及其负圈来解决，具体作法从略.

图论与网络专题第 22 页 共 22 页