资源描述：
《离散数学第3章讲义-3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九讲:哈密顿图、图的矩阵表示4.6运输网络问题v1v3v2v4xy9.38.47.45.12.29.56.05.410.4网络4.6运输网络问题4.6.1网络的流定义1:(网络)设N=(V,U)是一个有向图,满足:(1)V中有两个结点的子集X和Y,X中任一结点的引入次数为零,Y中任一结点的引出次数为零;(2)边集U上定义一个非负整数值函数C;则称N为一个网络.X中的结点称为源,Y中的结点称为汇,既非源又非汇的结点称为中间结点,函数C称为网络N的容量函数,容量函数C在边a上的值c(a)称为边a的容量.边a的容量记为c(a)或c(i，j).流:网络N中通
2、过每条边（i,j）的某事物的多少称为通过该边的流，记为f(i,j).设从源x流出的流为fxy,从汇y流出的流为－fxy,则v1v3v2v4xy9.38.47.45.12.29.56.05.410.4网络N的流：F={f(i,j)
3、(i,j)U}可行流：若F满足式(1)、（2），则称F是N的可行流fxy称为流F的值。饱和边：当f(i,j)=c(i,j)时，称边（i,j)为饱和边，否则称为非饱和边。零流：流值为0的流称为零流。每个网络N至少有一个可行流。问题：求网络N的流值最大的可行流.标记法求最大流的算法：v1v3v2v4xy9.38.47.45.12
4、.29.56.05.410.4v1v3v2v4xy9.38.47.45.12.09.56.15.410.4第一步：给出一个可行流v1v3v2v4xy9.38.47.45.12.09.56.15.410.4第二步：标记过程(1)v1v3v2v4xy9.38.47.45.12.09.56.15.410.4第二步：标记过程(1)（x,+,+)（x,+,4)（x,+,3)v1v3v2v4xy9.38.47.45.12.09.56.15.410.4第二步：标记过程(1)（x,,+)（x,+,4)（x,+,3)（1,+,4)v1v3v2v4xy9.38.47
5、.45.12.09.56.15.410.4第二步：标记过程(1)（x,,+)（x,,4)（x,+,3)（1,+,4)（2,+,3)v1v3v2v4xy9.38.47.45.12.09.56.15.410.4第二步：标记过程(1)（x,,+)（x,,4)（x,,3)（1,+,4)（2,+,3)（4,+,3)v1v3v2v4xy9.38.47.45.12.09.56.15.410.4第三步：增广过程(1)（x,,+)（x,,4)（x,,3)（1,,4)（2,,3)（4,,3)v1v3v2v4xy9.38.47.75.12.09.
6、86.15.410.7（x,,+)（x,,4)（x,,3)（1,,4)（2,,3)（4,,3)第三步：增广过程(1)v1v3v2v4xy9.38.47.75.12.09.86.15.410.7（x,+,+)（x,+,4)第二步：标记过程(2)（1,+,4)v1v3v2v4xy9.38.47.75.12.09.86.15.410.7（x,,+)（x,+,4)（1,+,4)（1,+,6)第二步：标记过程(2)v1v3v2v4xy9.38.47.75.12.09.86.15.410.7（x,,+)（x,,4)（1,+,4)（1,+,
7、6)（2,+,1)第二步：标记过程(2)v1v3v2v4xy9.38.47.75.12.09.86.15.410.7（x,,+)（x,,4)（1,,4)（1,+,4)（2,+,1)（3,+,1)第二步：标记过程(2)v1v3v2v4xy9.38.47.75.12.09.86.15.410.7（x,,+)（x,,4)（1,,4)（1,,4)（2,,1)（3,,1)第三步：增广过程(2)v1v3v2v4xy9.48.57.75.12.09.86.15.510.7（x,,+)（x,,4)（1,,4)（1,,4)（2,,1)（
8、3,,1)第三步：增广过程(2)v1v3v2v4xy9.48.57.75.12.09.86.15.510.7（x,+,+)（x,+,3)第二步：标记过程(3)v1v3v2v4xy9.48.57.75.12.09.86.15.510.7（x,+,+)（x,+,3)（1,+,1)第二步：标记过程(3)v1v3v2v4xy9.48.57.75.12.09.86.15.510.7（x,,+)（x,+,3)（1,+,1)（1,+,3)第二步：标记过程(3)v1v3v2v4xy9.48.57.75.12.09.86.15.510.7（x,,+)（x,
9、,3)（1,+,1)（1,+,3)（2,+,1)第二步：标记过程(3)v1v3v2v4xy9
