资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图与网络分析,(Graph Theory and Network Analysis),图与网络的基本知识,最短路问题,树及最小树问题,最大流问题,最小费用最大流问题,B,D,A,C,A,B,C,D,哥尼斯堡“七桥”难题,一笔画问题,问题：一个游者怎样才能一次连续走过这七座桥且每座桥只走一次，回到原出发点。,欧拉,用,A,B,C,D,四点表示河的两岸和小岛，用两点间的联线表示桥。七桥问题变为：,从,A,B,C,D,任一点出发，能否通过每条边一次且仅一次，再回到该点,?,一、,图与网络的基本知识,（一）、,图与网络的基本概念,E,A,D,C,B,v,1,v,2,v,3,v,4,v,5,v,6,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,10,图,1,v,4,v,6,v,1,v,2,v,3,v,5,图,2,4.,一条边的两个端点如果相同,称此边为环。,6.,不含环和多重边的图称为简单图，含有多重边的图称为多重图。,8.,有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,5.,两个点之间多于一条边的，称为多重边,.,7.,每一对顶点间都有边相连的无向简单图称为完全图。,有,n,个顶点的无向完全图记作,K,n,次为零的点称为弧立点，次为,1,的点称为悬挂点。连结悬挂点的边称为悬挂边。次为奇数的点称为奇点，次为偶数的点称为偶点。,定理,2,任何图中，次为奇数的顶点必为偶数个。,有向图中,所有顶点的入次之和等于所有顶点的出次之和,定理,1,任何图中，顶点次数的总和等于边数的,2,倍。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,10,e,11,(,a,),e,5,e,7,v,1,v,2,v,5,v,6,v,7,e,1,e,6,e,8,(,b,),子图,v,1,v,2,v,3,v,4,v,5,v,6,v,7,e,1,e,6,e,7,e,9,e,10,e,11,(,c,),支撑子图,e,3,v,1,v,2,v,3,v,4,v,5,v,6,e,7,e,8,e,1,e,2,e,4,e,5,e,6,e,9,e,10,图,3,一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。,v,4,v,6,v,1,v,2,v,3,v,5,e,2,e,1,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,10,图,4,例,权矩阵为：,邻接矩阵为：,v,5,v,1,v,2,v,3,v,4,v,6,4,3,3,2,2,5,6,4,3,7,二、 树及最小树问题,已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,v,1,v,2,v,3,v,4,v,5,v,6,1,、连通且不含圈的无向图称为树。,树中次为,1,的点称为树叶，次大于,1,的点称为分支点。,一个图,G,有生成树的充要条件是,G,是连通图。,v,1,v,2,v,3,v,4,v,5,v,1,v,2,v,3,v,4,v,5,用破圈法求出下图的一个生成树。,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v,1,v,2,v,3,v,4,v,5,e,2,e,4,e,6,e,8,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,（一）,破圈法,（二）,避圈法,v,1,v,2,v,3,v,4,v,5,v,6,v,1,v,3,v,1,v,3,v,2,v,1,v,3,v,2,v,5,v,6,v,1,v,3,v,2,v,5,v,6,v,4,v,1,v,3,v,2,v,5,某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。,v,1,v,2,v,3,v,4,v,5,v,6,6,5,1,5,7,2,3,4,4,5,v,1,v,2,v,3,v,4,v,5,v,6,1,2,3,4,4,求最小树的方法：,一、破圈法：在给定连通图,G,中，任取一圈，去掉一条最大权边（若有两条或两条以上的权均是最大权边，则任意去掉其中一条），在余图中任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即得到图,G,的最小树。,二、避圈法：在给定连通图,G,中，任取权值最小的一条边，在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止，已选边与顶点构成的图,T,即为所求的最小树。,v,1,v,2,v,3,v,4,v,5,1,4,2,3,1,3,5,2,破圈法求最小树：,v,1,v,2,v,3,v,4,v,5,1,4,2,3,1,3,5,2,v,1,v,2,v,3,v,4,v,5,1,4,2,3,1,3,5,2,避圈法求最小树：,v,1,v,2,v,3,v,4,v,5,1,4,2,3,1,3,5,2,三、最短路问题,最短路问题是重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且经常被作为一个基本工具，用于解决其他的优化问题。,Dijkstra,标号法,例：如图所示是某地区交通运输示意图，问从,v,1,出发，经那条路线到达,v,8,才能使总行程最短,?,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,3,5,6,7,4,2,3,5,6,9,5,2,1,1,1,3,5,6,7,4,1,2,1,3,5,2,1,9,5,例,2,、,用,Dijkstra,算法求下图从,v,1,到,v,6,的最短路。,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,解,（,1,）首先给,v,1,以,P,标号，给其余所有点,T,标号。,（,2,）,（,3,）,（,4,）,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,（,5,）,（,6,）,（,7,）,（,8,）,（,9,）,（,10,）,反向追踪得,v,1,到,v,6,的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从,1,到,8,的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1, w,1,=0,min c,12,c,14,c,16,=min 0+2,0+1,0+3=min 2,1,3=1,X=1,4, p,4,=1,p,4,=1,p,1,=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,4,min c,12,c,16,c,42,c,47,=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2,X=1,2,4, p,2,=2,p,1,=0,p,4,=1,p,2,=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,min c,13,c,23,c,25,c,47,=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3,X=1,2,4,6, p,6,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,min c,23,c,25,c,47,c,67,=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,X=1,2,4,6,7, p,7,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,25,c,75,c,78,=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6,X=1,2,4,5,6,7, p,5,=6,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,53,c,58,c,78,=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8,X=1,2,3,4,5,6,7, p,3,=8,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,min c,38,c,58,c,78,=min 8+6,6+4,3+7=min 14,10,11=10,X=1,2,3,4,5,6,7,8, p,8,=10,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,8,1,到,8,的最短路径为,1,，,4,，,7,，,5,，,8,，长度为,10,。,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,求从,V,1,到,V,8,的最短路线。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,3,5,6,7,4,2,3,5,6,9,5,2,1,1,1,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,P,=0,T=+,T=+,T=+,T=+,T=+,T=+,T=+,P,=T=3,T=+,T=7,T=+,T=+,T=+,T=+,T=6,T=7,P,=T=5,T=+,T=+,T=+,P,=T=6,T=6,T=8,T=+,T=+,P,=T=6,T=8,T=9,T=12,P,=T=8,T=10,T=10,P,=T=9,T=11,再无其它,T,标号，所以,T(V,8,)=P(V,8,)=10; min L()=10,P,=T=10,由此看到，此方法不仅求出了从,V,1,到,V,8,的最短路长，同时也求出了从,V,1,到 任意一点 的最短路长。将从,V,1,到 任一点的最短路权标在图上，即可求出从,V,1,到 任一点的最短路线。本例中,V,1,到,V,8,的最短路线是：,v,1, v,2, v,5, v,6, v,8,6,2,3,1,2,1,6,4,10,3,6,2,3,4,2,10,（二）、 逐次逼近法,算法的基本思路与步骤：,首先设任一点,v,i,到任一点,v,j,都有一条弧。,显然，从,v,1,到,v,j,的最短路是从,v,1,出发，沿着这条路到某个点,v,i,再沿弧,(,v,i,v,j,),到,v,j,。则,v,1,到,v,i,的这条路必然也是,v,1,到,v,i,的所有路中的最短路。设,P,1j,表示从,v,1,到,v,j,的最短路长，,P,1i,表示从,v,1,到,v,i,的最短路长，则有下列方程：,开始时，令,即用,v,1,到,v,j,的直接距离做初始解。,从第二步起，使用递推公式：,求 ，当进行到第,t,步，若出现,则停止计算， 即为,v,1,到各点的最短路长。,例,2,、,1,8,v,1,v,2,v,3,v,4,v,5,2,6,3,5,1,3,5,2,1,1,2,1,1,v,6,v,7,v,8,3,7,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,P,(1),P,(2),P,(3),P,(4),v,1,0,-1,-2,3,0,0,0,0,v,2,6,0,2,-1,-5,-5,-5,v,3,-3,0,-5,1,-2,-2,-2,-2,v,4,8,0,2,3,-7,-7,-7,v,5,-1,0,1,-3,-3,v,6,1,0,1,7,-1,-1,-1,v,7,-1,0,5,-5,-5,v,8,-3,-5,0,6,6,求图中,v,1,到,各点的最短路,1,8,v,1,v,2,v,3,v,4,v,5,2,6,3,5,1,3,5,2,1,1,2,1,1,v,6,v,7,v,8,3,7,（0，0）,（,v,3,，-5）,（,v,1,，-2）,（,v,3,，-7）,（,v,2,，-3）,（,v,4,，-5）,（,v,3,，-1）,（,v,6,，6）,例,3,、求：,5,年内，哪些年初购置新设备，使,5,年内的总费用最小。,解：（,1,）分析：可行的购置方案（更新计划）是很多的，,如：,1,） 每年购置一台新的，则对应的费用为：,11+11+12+12+13 +5+5+5+5+5 = 84,2 ),第一年购置新的，一直用到第五年年底，则总费用为：,11+5+6+8+11+18 = 59,显然不同的方案对应不同的费用。,第,i,年度,1 2 3 4 5,购置费,11,11,12,12,13,设备役龄,0-1 1-2 2-3 3-4 4-5,维修费用,5 6 8 11 18,（,2,）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。,求解步骤：,1,）画赋权有向图：,设,V,i,表示第,i,年初，,(V,i,V,j,),表示第,i,年初购买新设备用到第,j,年初（,j-1,年底），而,W,i,j,表示相应费用，则,5,年的一个更新计划相当于从,V,1,到,V,6,的一条路。,2,）求解 （标号法）,W,12,=11+5=16,W,13,=11+5+6=22,W,14,=11+5+6+8=30,W,15,=11+5+6+8+11=41,W,16,=11+5+6+8+11+18=59,W,23,=11+5=16 W,24,=11+5+6=22,W,25,=11+5+6+8=30 W,26,=11+5+6+8+11=41,W,45,=12+5=17,W,46,=12+5+6=23,W,56,=13+5=18,W,34,=12+5=17,W,35,=12+5+6=23,W,36,=12+5+6+8=31,例,4,、 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,年份,1,2,3,4,5,购置费,18,20,21,23,24,使用年数,0,1,1,2,2,3,3,4,4,5,维修费,5,7,12,18,25,年份,1,2,3,4,5,购置费,18,20,21,23,24,使用年数,0,1,1,2,2,3,3,4,4,5,维修费,5,7,12,18,25,28,v,1,v,2,v,3,v,4,v,5,v,6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,四、最大流问题,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),是一个增广链,显然图中增广链不止一条,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),设 ，,则截集为,容量为,24,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),设 ，,则截集为,容量为,20,在此过程中，网络中的点或为标号点或为未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链，第二个标号是为确定增广链的调整量,用的。,例：用标号法求下图所示的网络最大流,13 (7),9 (9),4 (4),5 (5),6(6),5 (0),5 (2),5 (5),4 (4),4 (0),9 (7),10 (5),13 (7),9 (9),4 (4),5 (5),6(6),5 (0),5 (2),5 (5),4 (4),4 (0),9 (7),10 (5),13 (11),9 (9),4 (0),5 (5),6(6),5 (4),5 (2),5 (5),4 (4),4 (4),9 (9),10 (9),求下图所示网络中的最大流，弧旁数为,(1 ,1),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 1),(1 , 1),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,1),(1 ,1),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 1),(1 , 1),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,1),（,0,，,+,）,（,-,v,1, 1,）,（,+,v,s, 4,）,（,-,v,2,，,1,）,（,+,v,2,，,1,）,(+,v,3,，1),(1 ,0),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 2),(1 , 0),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,2),(1 ,0),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 2),(1 , 0),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,2),（,0,，,+,）,（,+,v,s, 3,）,最小截集,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),13 (11),9 (9),4 (0),5 (5),6(6),5 (5),5 (4),5 (4),4 (4),4 (3),9 (9),10 (7),截集,1,截集,2,最小截量为：,9+6+5=20,70,（,70,）,70,（,50,）,130,（,100,）,150,（,130,）,150,（,150,）,50,（,20,）,50,（,50,）,120,（,30,）,100,（,100,）, （,120,）, （,230,）, （,150,）, （,200,）,第五节 最小费用最大流问题,定义,8.17,已知网络,G =,（,V,，,E,，,C,，,d,），,f,是,G,上的一个可行流， 为一条从,v,s,到,v,t,的增广链， 称为链的费用。,若,*,是从,v,s,到,v,t,的增广链中费用最小的增广链，则称,*,是最小费用增广链。,结论：,如果可行流,f,在流量为,W(,f,),的所有可行流中的费用最小，并且,*,是关于,f,的所有增广链中的费用最小的增广链，那么沿增广链,*,调整可行流,f,，,得到的新可行流,f,*,也是流量为,W(,f,*,),的所有可行流中的最小费用流。当,f,*,是最大流时，就是最小费用最大流。,寻找关于,f,的最小费用增广链：,构造一个关于,f,的赋权有向图,L(,f,),，其顶点是原网络,G,的顶点，而将,G,中的每一条弧,(,v,i,v,j,),变成两个相反方向的弧（,v,i,，,v,j,）,和,(,v,j,v,i,),，,并且定义图中弧的权,l,ij,为：,1.,当 ，令,2.,当（,v,j,，,v,i,）,为原来网络,G,中（,v,i,，,v,j,）,的反向弧，令,在网络,G,中寻找关于,f,的最小费用增广链等价于在,L(,f,),中寻求从,v,s,到,v,t,的最短路。,步骤：,（,1,）取零流为初始可行流 ，,f,(0) =0,。,（,2,）,一般地，如果在第,k-1,步得到最小费用流,f,(,k,-1),，则构造图,L(,f,(,k,-1),),。,（,3,）在,L(,f,(,k,-1),),中，寻求从,v,s,到,v,t,的最短路。若不存在最短路，则,f,(,k,-1),就是最小费用最大流；否则转,(4),。,（,4,）如果存在最短路，则在可行流,f,(,k,1),的图中得到与此最短路相对应的增广链，在增广链上，对,f,(,k,1),进行调整，调整量为：,令,得到新可行流,f,(,k,),。对,f,(,k,),重复上面步骤，返回（,2,）。,例,8.11,求网络的最小费用最大流，弧旁权是（,b,ij,c,ij,）,(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),3,v,s,v,2,v,1,v,t,v,3,1,6,4,1,2,2,(1) L(,f,(0),),(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),0,v,s,v,2,v,1,v,t,v,3,3,0,0,3,3,3,(2),f,( 1),1,=3,W(,f,(1),)=3,1,(3) L(,f,(1),),2,3,v,s,v,2,v,1,v,t,v,3,1,6,4,1,2,1,2,1,v,s,v,2,v,1,v,t,v,3,4,0,0,3,4,3,(4,),f,( 2),2,=1,W(,f,(2),)=4,(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),(5) L(,f,(2),),3,v,s,v,2,v,1,v,t,v,3,1,4,1,2,2,2,3,1,6,6,1,v,s,v,2,v,1,v,t,v,3,4,0,1,4,5,3,(6,),f,( 3),3,=1,W(,f,(3),)=5,(7) L(,f,(3),),v,s,v,2,v,1,v,t,v,3,3,1,4,1,-2,2,3,1,6,1,v,s,v,2,v,1,v,t,v,3,4,3,4,4,5,0,(8,),f,( 4),4,=3,W(,f,(4),)=8,0,v,s,v,2,v,1,v,t,v,3,4,4,5,5,5,0,5,=1,W(,f,(5),)=9,(10,),f,( 5),1,-2,3,1,v,s,v,2,v,1,v,t,v,3,3,4,1,2,6,(9),L,(,f,( 4),),-4,-6,3,1,2,1,4,(11) L(,f,( 5),),1,2,6,4,v,s,v,2,v,1,v,t,v,3,6,第六节 中国邮递员问题,一、 欧拉回路与道路,定义,8.18,连通图,G,中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。,具有欧拉回路的图称为欧拉图。,定理,8.7,一个多重连通图,G,是欧拉图的充分必要条件是,G,中无奇点。,推论 一个多重连通图,G,有欧拉道路的充分必要条件是,G,有且仅有两个奇点。,A,B,C,D,二、,奇偶点图上作业法,（,1,）找出图,G,中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。,（,2,）如果边,e,=,（,u,v,）,上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。,（,3,）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（,2,）。,判定标准,1:,在最优邮递路线上，图中的每一条边至多有一条重复边。,判定标准,2 :,在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。,例,8.12,求解下图所示网络的中国邮路问题，图中数字为该边的长。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,6,4,3,4,5,5,l,12,+2,l,23,+2,l,36,+2,l,89,+2,l,78,+,l,69,+,l,14,+2,l,47,=51,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,
展开阅读全文