第5章01图与网络

1、.定理定理1：在一个图中，所有顶：在一个图中，所有顶点次的和等于边的两倍。点次的和等于边的两倍。定理定理2：在任意一个图中，奇：在任意一个图中，奇顶点的个数必为偶数。顶点的个数必为偶数。定义（连通图）定义（连通图）如果图中的任如果图中的任意两点之间至少存在一条通路，意两点之间至少存在一条通路，则称图为则称图为连通图连通图，否则为不连，否则为不连通图。通图。1 在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只有一条通路。1 在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只有一条通路。2 在图中划去一条边，则图不连通。在图中划去一条边，则图不

2、连通。1 在图中任意两点之间必有一条而在图中任意两点之间必有一条而且只有一条通路。且只有一条通路。2 在图中划去一条边，则图不连通。在图中划去一条边，则图不连通。3 在图中不相邻的两个顶点之间加在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。一条边，可得一个且仅得一个圈。网络中不属于生成树的边称为生成树的弦 重排九宫问题重排九宫问题游戏游戏 在一个在一个3乘乘3的九宫中的九宫中有有1-8的的8个数个数及一个空格随及一个空格随机摆放在其中机摆放在其中的格子里。如的格子里。如图所示。现在图所示。现在要求实现这样要求实现这样的问题：将该的问题：将该九宫调整为如九宫调整为如右图所示的形右图所

3、示的形式。调整规则式。调整规则是：每次只能是：每次只能将与空格（上，将与空格（上，下或左，右）下或左，右）相临的一个数相临的一个数字平移到空格字平移到空格中。中。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G基本算法：基本算法：1）从某个顶点出发开始访问，被访问的顶点作相应的标记，）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；并输出访问顶点号； 2）从被访问的顶点出发，依次搜索与该顶点有边关联的所有）从被访问的顶点出发，依次搜索与该顶点有边关联的所有未被访问的邻接点，并作相应的标记。未被访问的邻接点，并作相应的标记。 3）再依次

4、根据）再依次根据2）中所有被访问的邻接点，访问与这些邻接点）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。相关的所有未被访问的邻接点，直到所有顶点被访问为止。如下图，找出如下图，找出C1到到C6的一条最短路径并求出其路程总长度的一条最短路径并求出其路程总长度(采采用广度优先搜索的顶点访问序列为用广度优先搜索的顶点访问序列为C1,C2,C3,C4,C5,C6)。 网络优化网络最小费用流问题网络最大流问题最短路径问题网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生

5、成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进生成树的变换对应于线性规划单纯形法的进 基和离基变换基和离基变换b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561需求节点供应节点cij 单位流量的费用ij 初始基本可行解生成树b6=-5b2=-2b4=3b3=5b5=-6b1=5x13=3x46=3x35=8x56=2x12=2234561确定非基变量x24和x34b2=-2b6=-5b3=5b5=-6b1=5c24=5

6、c46=1c13=3c35=2c56=4c34=4c12=6234561b4=3ij 检验数计算闭回路法求x24的检验数24 ：闭回路法b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c12=6234561C24- z24 =-(-c46+c56+c35+c13-c12)+c24=(-1+4+2+3-6)+5=3求x34的检验数34 闭回路法b2=-2b4=3b3=5b5=-6b6=-5b1=5c46=1c13=3c35=2c56=4c34=4c12=6234561-z34 +c34 =-(-c46+c56+c35)+c34=-(-1+4

7、+2)+4=-1，x34进基基变换变量x34进基，确定离基变量minx56,x35=min2,8=2, x56离基，调整流量，进行基变换b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=3x13=3x35=8x56=2x34=0 x12=2234561确定非基变量x24和x56b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561计算x24和x56的检验数-z24 +c24 =-(c34+c13-c12)+c24=-(4+3-6)+5= 4-z56 +c56 =-(c46+c34-c35)+c56=-(1+4-2)+4=

8、 1b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561ij ij 最优性判断最优解最优解的目标函数值为：min z=62+33+42+26+15=46b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561网络最大流问题网络最大流问题2354671ffc25=6c42=2c45=4c23=3c13=7c34=4c46=3c36=1c65=7c57=9c67=8c12=8边的容量和流量容量cij，流量fij可行流满足以下条件的流称为可行流：1、中间每一

9、个节点流量平衡2、0fij cij边的容量和流量、可行流21cij=5fij=521fij=3cij=5饱和边、不饱和边、流量的间隙（1，2）是饱和的2、如果fij0（和链的方向相反称为反向边 ），边从j到i的方向是不饱和的（2，1）是不饱和的间隙为12=f21=5设C是网络中从节点1到节点m的一条链（注意：链中的边方向可以不同），如果链C满足以下条件：不饱和链1、链的起点为1，终点为m，链的方向是从节点1到节点m；不饱和链2、链中各边（i，j）的流量xij满足以下条件：如果（i，j）与链的方向相同（称为正向边），且fij0，并且记ij=fij，称ij为边（i，j）上流量的间隙；则称链C为网络

10、的不饱和链。 =minij|（i，j）C为不饱和链C的间隙。沿着不饱和链调整流量，即对于正向边，新的流量fij=fij+,对于反向边，新的流量fij=fij-,网络的流量从原来的f增加到f+。算法：1）给出一个初始的可行流fij=02354671f=0f=06243743179880000000000002）找到一条从1到7的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已求得最大流。2354671f=0f=06243743179880000000000002354671f=0f=064374317988000000000003）找出这条路上各条弧的最小的顺流容量pf。

11、最小的顺流容量： pf = min8,3,1,8=120235467164274307977000000011114）在这条路上各条弧的顺流容量减去最小的顺流容量pf，同时增加逆流容量pf，返回2）最小的顺流容量： pf = min8,3,1,8=1调整链的流量：fij=fij+ pf cij=cij- pf 20235467164274307977000000011112）找到一条从1到7的路(1,2,5,7)，在这条路上的每一条弧顺流方向的容量都大于零, 如果不存在这样的路，则已求得最大流。3)找出这条路上各条弧的最小的顺流容量pf。最小的顺流容量： pf = min7,6,9=6调整链的

12、流量：fij=fij+ pf cij=cij- pf 20235467104274307371600000611174）在这条路上各条弧的顺流容量减去最小的顺流容量pf，同时增加逆流容量pf，返回2）最小的顺流容量： pf = min7,6,9=6调整链的流量：fij=fij+ pf cij=cij- pf 20235467104274307371600000611172）找到一条从1到7的路(1,3,4,6,7)，在这条路上的每一条弧顺流方向的容量都大于零, 如果不存在这样的路，则已求得最大流。3)找出这条路上各条弧的最小的顺流容量pf。最小的顺流容量： pf = min7,4,3,7=3调

13、整链的流量：fij=fij+ pf cij=cij- pf 2023546710424100734163303064117最小的顺流容量： pf = min7,4,3,7=3调整链的流量：fij=fij+ pf cij=cij- pf 4）在这条路上各条弧的顺流容量减去最小的顺流容量pf，同时增加逆流容量pf，返回2）2023546710424100734163303064117最小的顺流容量： pf = min7,4,3,7=3调整链的流量：fij=fij+ pf cij=cij- pf 4）在这条路上各条弧的顺流容量减去最小的顺流容量pf，同时增加逆流容量pf，返回2）2023546710

14、424100734163301064117最小的顺流容量： pf = min4,1,4,3=1调整链的流量：fij=fij+ pf cij=cij- pf 202）找到一条从1到7的路(1,3,4,5,7)，在这条路上的每一条弧顺流方向的容量都大于零, 如果不存在这样的路，则已求得最大流。3)找出这条路上各条弧的最小的顺流容量pf。23546710323000724164413074117最小的顺流容量： pf = min4,1,4,3=1调整链的流量：fij=fij+ pf cij=cij- pf 204）在这条路上各条弧的顺流容量减去最小的顺流容量pf，同时增加逆流容量pf，返回2）235

15、46710323000724164411074117最大的顺流容量： F=11=7+4202）已找不到一条从1到7的路，在这条路上的每一条弧顺流方向的容量都大于零, 所以已求得最大流。 对比其它解法得到的结果（最大流最小割定理）参考：运筹学教程机械工业出版社 邱菀华等 2004.5 p177 p2002354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0已求得最大流2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0

16、x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0f=11最大流f=11，最小割集为（2,5）（3,4）（3,6）u25+u34+u36=6+4+1=11最短路径问题-Dijkstra算法教材p231237184566134105275934682求从1到8的最短路径237184566134105275934682I=1, (0,s), J=2,4,6, (1,1)(0,s)237184566134105275934682I=1,4 J=2,7,6(0,s)(1,1)(2,1)237184566134105275934682I=1,2,4, J=3,5,6,7(2,1)(1,1)(

17、0,s)(3,1)(3,4)237184566134105275934682I=1,2,4,6,7, J=3,5,8(2,1)(1,1)(0,s)(3,1)(3,4)237184566134105275934682I=1,2,4,6,7, J=3,5,8(2,1)(1,1)(0,s)(3,1)(3,4)(6,7)237184566134105275934682I=1,2,4,5,6,7, J=3,8(2,1)(1,1)(0,s)(3,1)(3,4)(6,7)(8,2)237184566134105275934682I=1,2,3,4,5,6,7, J=8(2,1)(1,1)(0,s)(3,1)(3,4)(6,7)(8,2)(10,5)237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。(2,1)(1,1)(0,s)(3,1)(3,4)(6,7)(8,2)(10,5)艾兹格W迪科斯彻 艾兹格W迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日-2002年8月6日）荷兰计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年AFIP