运筹学第八章课件

1、1,第八章 图与网络分析,学时安排：68学时。 教学目的：让学生了解图论的基本知识，掌握用网络表示所研究问题、对象的基本属性及其解决方法。 教学内容：基本概念、树、最短路、最大流、最小费用最大流等。 教学难点：建立网络图的技巧和各种方法产生的思路。,第八章 图与网络分析,2,运筹学中的图与几何学中图的区别：,运筹学中研究的图是日常生产和生活中经常碰到的各类图的抽象概括，它表明一些研究对象和这些对象之间的相互联系。如交通图是表明一些城镇及这些城镇之间的道路沟通情况。如果用点表示研究的对象，用边表示这些对象之间的联系，则图可以定义为点和边的集合。由此可知图是区别于几何学中的图。在几何图中，图中点的

2、位置、线的长度和斜率等十分重要。而这里只关心有多少个点以及那些点之间有线相连。（与线的长度、线是直线还是曲线无关）。,第八章 图与网络分析,3,历史上解决的比较有名的问题：,1、“哥尼斯堡七桥问题”：18世纪哥尼斯堡城中普雷格尔河中有两个小岛，它们之间与两岸有七座桥相连。问从岸上某点出发，是否存在经过每座桥一次且仅一次，最后又回到原出发点的走法。（1736年欧拉发表了有关图论方面的第一篇文章，在该文章中解决了该问题。）,第八章 图与网络分析,4,第八章 图与网络分析,2、1847年，物理学家基尔霍夫为解决有关线性方程组而发展了“树”的理论。他将网络中的电感、电容、电阻等抽象为点和线，得到一简单

3、的组合结构。这种结构便于运算，不必指明为何种元素。,3、1857年，凯莱研究饱和烃链CnH2n+2的同分异构体时，又一次引入树状结构，例如， C4H10 。,5,第一节 基本知识,第八章 图与网络分析,一、图与网络的基本概念 图、网络图 图用点代表事物，用边代表事物之间的联系，则运筹学中研究的图是点与边关系的图。即点集V=vi和V中元素（节点）之间的连线所组成。用m(G)=E（ A）表示图G中边（弧）的数量；用n(G)=V表示图G中点的数量。 网络图若给图中边赋以具体的含义和权数（如距离、费用、容量等），这样的图称网络图。,6,第八章 图与网络分析,1、有向图与无向图：如果节点之间的连线皆是无

4、方向的（称为边，边的集合记为E），此时图G称为无向图，记为G=（V，E）； 如果节点之间的连线有方向，即有向边（或称为弧，弧的集合记为A） ，此时图G称为有向图，记为 D =（V，A）。用m(D)=E（ A）表示图D 中边（弧）的数量；用n(D)=V表示图D中点的数量。,一个图是由点集V=vi和V中元素（节点）之间的连线所组成。,7,第八章 图与网络分析,G=（V，E） V=A，B，C，D，N，F，G，H，M E=A,A,A,B,A,C,H,M n(G)=9；m(G)=12,边,端点,端点,8,第八章 图与网络分析,D=（V，A） V=M，N，F，G A=M,G,G,F,M,N,N,F,弧,始

5、点,终点,9,第八章 图与网络分析,2、如果一条边的两端点相同，此边称为环，两点之间多于一条边的，称为多重边。,3、简单图：无多重边和环的图； 多重图：有多重边的图。,10,第八章 图与网络分析,4、链：点、边交替的序列（V1,e1, V2,e2, ,Vi,ei) ； 简单链： 边不重复， A, C, D, B, G,D,N; 初等链： 点、边不重复， A, B, G, F, N; 。,11,第八章 图与网络分析,5、 圈：链上首、尾节点是同一节点时，称为圈； 简单圈：圈中没有重复的边；(A,B,G,G,B,D,C,A) 初等圈：既无重复点，也无重复边;(A,B,D,C,A),12,第八章 图

6、与网络分析,路：链上边方向一致时，称为路； 回路：路上首、尾节点是同一节点时，称为回路。,13,第八章 图与网络分析,6、顶点的次：以点vi为端点的边数，记为d(vi )。,如图中d(A ) =2（用于无向图）。,14,第八章 图与网络分析,出次：以点vi为始点的边数，用d+(vi )表示 。 入次：以点vi为终点的边数，用d-(vi )表示。 d+(vi ) +d-(vi )= d(vi )（用于有向图）。,d+(A ) =1; d-(A )=1 d(A)=2,15,第八章 图与网络分析,偶点：d(v) = 偶数； 奇点：d(v)=奇数 悬挂点：d(v)=1； 悬挂边：与悬挂点连接的边； 孤

7、立点：d(v)=0； 空图：E = ，无边图,16,第八章 图与网络分析,7、连通图：图G=（V,E）中任意两点间至少有一条链。 子图： G=（V,E），其中 VV ，E E。,17,第八章 图与网络分析,支撑（生成）子图：对于子图G=（V，E），当V=V时，且与图G=（V，E）的连通性相同的子图称为支撑子图，或生成子图。,18,第八章 图与网络分析,8、完全图：任意两点间皆有边相连的无向简单图。,19,第八章 图与网络分析,9、基础图：将有向图中弧去掉其方向所形成的无向图，称为原有向图的基础图。 网络：给图的边或点赋予某些数量指标（我们称之为“权”），这种赋权图又称为网络。,20,第八章 图

8、与网络分析,10、图的矩阵表示：邻接矩阵与权矩阵,（1）邻接矩阵：图G=(V，E)，V=n，构造一个矩阵邻接矩阵A=(aij)nn，其中,（2）权矩阵：图G=(V，E)，V=n，边（vi， vj)有权ij，构造矩阵权矩阵B=(bij)nn，其中,21,第八章 图与网络分析,22,第八章 图与网络分析,定理1 任何图中，顶点次的总和等于边数的2倍。,二、基本理论,d(G)=2; d(D)=2; d(N)=2;d(F)=2;,23,第八章 图与网络分析,次为奇数的点为奇点，次为偶数的点为偶点。奇点的集合可记为V1，偶点的集合记为V2。,定理2 任何图中，次为奇数的顶点必为偶数个。,24,第二节 树

9、的问题,树的概念与性质 生成树 最小生成树 根树,第八章 图与网络分析,25,第八章 图与网络分析,1.树连通且不含圈的无向图称为树。树中次为1的点为树叶，次大于1的点称为分枝点。,一、树的概念与性质,26,第八章 图与网络分析,2.生成树若图G的生成子图是一棵树，则称该树为G的生成树（或支撑树）。简称为图G的树。图中属于生成树的边叫树枝, 不在生成树的边叫弦。,树枝,树枝,树枝,树枝,树枝,弦,弦,弦,弦,27,第八章 图与网络分析,3.最小生成树连通图G=( V，E )，每条边上有非负权L( e )。一棵生成树所有树枝上权的总和称为这棵生成树的权。具有最小权的生成树称为最小生成树（最小支撑

10、树），简称最小树。,28,第八章 图与网络分析,定理3 设图G（V，E）是一棵树，n(G)2，则G 中至少有两个悬挂点,29,第八章 图与网络分析,（1）T无圈，且m=（n-1）。,定理4 图T=( V，E )，V=n，E=m，若T是一棵树，则下列关于树的说法是等价的。,30,第八章 图与网络分析,（2）T连通，且m=（n-1）。 （3）T无圈，但每加一新边即得唯一一个圈。,31,第八章 图与网络分析,（4）T连通，但任舍去一边就不连通。 (5 ) T中任意两点，有唯一链相连。,32,第八章 图与网络分析,定理5：图G有支撑树的充要条件为G是连通图。,该定理的证明给出了求生成树的方法（破圈法）

11、：每步选出一条边，使它与已经选出的边不形成圈，直至选出（n-1）条边为止。,33,第八章 图与网络分析,(1)支撑树的求法:破圈法,34,第八章 图与网络分析,35,第八章 图与网络分析,36,第八章 图与网络分析,37,第八章 图与网络分析,（1）避圈法每步从未选的边中选取e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够（n-1）条边为止。,（2）破圈法每步从未破掉的圈中任选一个圈，将该圈的边中权最大的一条边e去掉，直到图中无圈为止。,例82 一个乡有9个自然村，其间道路及各道路长度如下图所示，各边上的权表示距离，问如何拉电缆线才能使用线总长度最短。,解：这是一个最小生成树问题。

12、具体解法如下：,二、最小生成树的算法,38,第八章 图与网络分析,最小树权值为W(T) =5+2+3+2+3+4+6+1=26。,1,2,3,3,4,5,6,2,39,第八章 图与网络分析,第三节 最短路问题,一、问题的提出,40,第八章 图与网络分析,二、最短路的定义,设D =（V，A）为一个赋权有向图，图中各弧（vi ，vj）有权ij0， vs、vt为图中任意两点，求一条路P0，它是从vs 到 vt的所有路P中总权最小的路。 w(p0) = min w(p),P=(v1 ,v2 , v4 , v5 ),(v1 , v3 , v5 ),P0= (v1 ,v2 , v4 , v5 ),w(p0

13、)=14,41,第八章 图与网络分析,三、Dijkstra算法(1959年),1、算法思路,(1) 当ij0时，若从vi 出发的弧中权值最小者是（vi ，vk）那么，从vi至 vk的最短路长必然是5。,42,第八章 图与网络分析,(2)若序列v1， v2， vk， ， vn 是从v1 至 vn 的一个最短路，则序列v1 ， v2 ， vk是从v1至 vk的一个最短路程。即，全局最优，一定是局部最优的。,序列v1， v4，v5 是从v1 至 vn 的一个最短路,则序列v1， v4是从v1 至 v4 的一个最短路,43,第八章 图与网络分析,从vs出发，给从vs 到 vk 最短路长的点 vk 赋予

14、固定标号P(permanent label)标号，并记下相应的最短路长（真实的长度）； 而未得到P标号的点赋予试探性（临时性标号）标号T(tentative label)标号，表示从vs 到vk 点的最短路长的上界。,（3）标记：,P (v1 ) =0,T(v2 )=3,T(v4 )=8,T(v6 )=14,44,第八章 图与网络分析,(1)给vs以P标号，P(vs)=0，其余各点均给T类标号， T(vi)=+ (2)若vi点为刚得到P标号的点,考虑这样的点vj： (vi，vj)E,且vj为T标号,对其T标号进行 如下更改： T(vj)=min T(vj ) , P (v i)+ij (3)比

15、较所有具有T标号的点,把最小者vk改为P标号： P(vk)=min T(vj) 若vt得到固定标号则停止,否则用vk 代替vi,转回(2)。,2、算法的步骤,45,第八章 图与网络分析,P(v1)=0,T(v3)=+,T(v2)=+,T(v4)=+,T(v2)=3,T(v3)=1,P(v3)=1,T(v4)=4,T(v2)=2,P(v2)=2,P(v4)=4,(vi)= vm :表示从v1到vi的最短路上, vi的前一个点是vm,(v2)=,v3,(v4)=,v3,S:已获得固定标号的点的集合,46,第八章 图与网络分析,例8-5 用Dijkstra算法求下图中vs 到 vt点的最短路。,3、

16、举例,P(vs)=0,T(v1)=+,T(v3)=+,T(v5)=+,T(v2)=+,T(v4)=+,T(v6)=+,T(vt)=+,47,第八章 图与网络分析,T(v1)=4,T(v2)=6,P(v1)=4,T(v3)=9,T(v4)=8,P(v2)=6,P(v4)=8,T(v5)=13,T(v6)=14,P(v3)=9,P(v5)=13,T(vt)=17,P(v6)=14,P(vt)=15,(vt)= v6,48,第八章 图与网络分析,4、带有负权网络的最短路解法逐次逼近法,（1）基本思想： 若v1 到 vj 的最短路总是沿着该路 从v1 到某一点vi ，然后再沿着边（ vi ，vj）到

17、vj 。则，从v1 到点vi的这条路，也是从v1 到点vi的最短路。 如果令P1i为从v1 到点vi的最短路长，则下列方程成立： P1j = minP1i +lij i=1, 2, , n 该方程表明： v1到 vj的最短路要依次考察网络中的所有点vi i=1, 2, , n。当改变 vj时，可以求出从v1到其它各个点的最短路。,49,第八章 图与网络分析,50,第八章 图与网络分析,（2）迭代公式：,51,第八章 图与网络分析,P1j(1) =0，3，1， ,P1j(2) =minP1i(1) +lij =P11(1) +l1j ， P12(1) +l2j ， P13(1) +l3j ， P

18、14(1) +l4j ,P14(2) =minP1i(1) +lij =P11(1) +l14 ， P12(1) +l24 ， P13(1) +l34 ， P14(1) +l44 =0+ ，3+5，1+3， +0=4,P14(2) =4 , (v4)= v3,52,第八章 图与网络分析,P1j(3) =minP1i(2) +lij =P11(2) +l1j ， P12(2) +l2j ， P13(2) +l3j ， P14(2) +l4j ,P14(3) =minP1i(2) +li4 =P11(2) +l14 ， P12(2) +l24 ， P13(2) +l34 ， P14(2) +l44

19、 =0+ ，2+5，3+3， 4+0=4,53,第八章 图与网络分析,例8-6:求v1到各点的最短路。,第一步：初始条件为： P1j(1) =0，2，5，-3，,54,第八章 图与网络分析,第二步：第一次迭代（k=2） P11(2) = minP11(1) ， P12(1) ， P13(1) ，P14(1) ， P15(1) ， P16(1) ， P17(1) ，P18(1) ,+ l11 + l21 + l31 + l41 + l5 1 + l61 + l71 + l81,= min(0+0, 2+, 5+, -3+, , , , ) = 0,55,第八章 图与网络分析,P12(2) = m

20、inP11(1) ，P12(1) ， P13(1） ，P14(1) ， P15(1) ，P16(1) ， P17(1) ， P18(1) ,+ l12 + l22 + l32 + l42 + l52 + l62 + l72 + l82,= min (0+2, 2+0, 5+, -3+, , , , ) = 2,56,第八章 图与网络分析,V1 V2 V3 V4 V5 V6 V7 V8,i,j,lij,v1 v2 v3 v4 v5 v6 v7 v8,0 ,2 0 ,5 -2 0 4,-3 0 7,4 0 -3 3,6 0 2,0 -1,4 0,P1j(1),P1j(2),P1j(3),P1j(4

21、),P1j(5),0 2 5 -3,0 2 0 -3 6 11,0 2 0 -3 6 6 15,0 2 0 -3 3 6 14 10,0 2 0 -3 3 6 9 10,57,第八章 图与网络分析,P1j(k) =minP1i(k-1) +lij ,58,第八章 图与网络分析,三、求任意两点间最短距离(Floyd algorithm),1、权矩阵：图G=(V，E)，V=n，边（vi， vj)有权ij，则权矩阵 D =(dij)nn被定义为：,2、步骤： （1）输入权矩阵 D（0）=D； （2） D(k) = ( dij (k)nn dij (k) = min(dij (k-1) , dik (

22、k-1) + dik (k-1) ) (3) D(t+1) =D (t)时，迭代结束。,59,第八章 图与网络分析,注意：（1）dij (1)表示从vi到vj，借助于v1或不借助于v1到达vj时的最短路。同理，dij (k)表示从vi 到 vj，借助于k个中间点v1 、 v2 、 、 vk 到达vj的最短路。 由于在第一次迭代时v1已经使用过，第二次迭代只需增加一个新点v2 。依次类推，增加 v3、 v4等等。 （2）当图中不存在负回路(即回路上边的权之和为负数)时，两点间的最短路径最多不超过n-1步。 （3）如果有无向边，要理解为存在方向相反的两条边。 （4）如果要知道最短路径的信息，则要保

23、留有关下标的信息。,60,问题的提出 有关概念 有关理论 最大流判别 标号算法,第四节 最大流问题,第八章 图与网络分析,61,第八章 图与网络分析,一、问题的提出,3,3,2,1,4,62,第八章 图与网络分析,1.网络与流 （1）网络:设有向连通图D=(V，A)，G的每条弧(vi，vj)上有非负数 cij 称为弧的容量，仅有一个入次为0的点vs称为发点(源)，一个出次为0 的点 vt 称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记为D=(V，A，C)。,二、有关概念,63,第八章 图与网络分析,发点,收点,中间点,中间点,(容量),(容量),(容量),(容量),(容量),（

24、1）网络,容量网络,64,第八章 图与网络分析,w为网络流的总流量。,对中间点vi ，有,对收、发点vt 、vs ，有,平衡条件,65,第八章 图与网络分析,一个流 f = fij ，当 fij= cij，则称流 f 对弧(vi，vj)是饱和的，简称(vi，vj)是饱和弧；当 fij 0，则称弧(vi，vj) 是非零流弧。,饱和弧、零流弧,66,第八章 图与网络分析,2最大流问题,最大流问题就是求一个流fij使其流量w最大，并且满足容量限制条件和平衡条件。,67,第八章 图与网络分析,2.增广链,若是网络中联结发点和收点的一条链,定义链的方向为从发点到收点,则链上的弧分为两类：一类是弧的方向与

25、链的方向一致,称为前向弧(+ ) ；另一类是弧的方向与链的方向相反(- ) ，称为后向弧。,链=（ v1 , v2 , v3 , v4 ）,+=( v1 , v2 ),( v3 , v4 ),-=( v2 , v3 ),68,第八章 图与网络分析,增广链,设f是一个可行流, 是从vs到vt的一条链,若满足下列条件,称为（关于可行流）的增广链 在弧（ vi , vj ） +上，0f ijc ij ，即+中每一条弧是非饱和弧； 在弧（ vi , vj ） -上，0 f ij c ij ，即-中每一条弧是非零流弧,链=（ v1 , v2 , v3 , v4 ）,69,第八章 图与网络分析,容量网络D

26、=(V，A，C)，若有弧集A为A的子集，将D分为两个彼此独立的子图D1、 D2，其顶点集合分别为V1、V2， V1 V2=V，V1 V2=，满足： （1）vsV1 ，vtV2 ； （2） D*=(V，A- A)不连通；而A中任一真子集A， D*=(V，A- A)仍连通。则称弧集A为D的截集。,3、截集、截量,A=(v1 ,v2 ), (v3 ,v2 ), (v3 ,v4 ),70,第八章 图与网络分析,71,第八章 图与网络分析,72,第八章 图与网络分析,73,第八章 图与网络分析,74,第八章 图与网络分析,75,第八章 图与网络分析,76,一、问题的提出,输油管道网各管道上的最大输油能力

27、（称容 量）已知，问如何确定各管道的输油量才能使起点到终点的总输油量最大？,（最大输油量取决于最薄弱的环节）,第八章 图与网络分析,77,1.容量网络 设有向连通图G=(V，E，C)，G的每条弧(vi，vj)上有非负数cij称为边的容量，仅有一个入次为0的点vs称为发点(源)，一个出次为0的点vt称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记为G=(V，E，C)。 （说明）：若有多个起点或多个终点，可将其化为只有一个起点或一个终点的网络。,二、有关概念,第八章 图与网络分析,78,第八章 图与网络分析,79,2.流、可行流 对任一G中的弧(vi，vj)有流量fij，称集合f=

28、fij 为网络G上的一个流。称满足下列两个条件的流 f 为可行流： （1）容量限制条件： 对G中每条弧(vi，vj)，有0 fij cij （2）平衡条件： 对中间点vi ，有 对收、发点vt 、vs ，有 w为网络流的总流量。,第八章 图与网络分析,80,注：可行流总是存在的。,第八章 图与网络分析,81,3.饱和弧、非饱和弧、零流弧、非零流弧 饱和弧： 一个流f = fij ，当 fij= cij，则称流 f 对弧(vi，vj)是饱和的，简称(vi，vj)是饱和弧； 非饱和弧： 当 fij0，则称弧(vi，vj) 是非零流弧。,第八章 图与网络分析,82,4.割集、割集容量、最小割集 割集

29、：（将其去掉，该图便不连通） 容量网络G=(V，A，C)，将G的顶点集合分为V1（vsV1)，V2 （vsV1) ，有 V1 V2=V，V1 V2=，且 vtV1 ，vsV2 ；我们把所有从V1指向V2的弧（称正向弧）及V2指向V1的弧（称反向弧）所组成的集合A*称为G的割集。 注： 1、 （G*=(V，A- A*)不连通；而A*中任一 真子集A*， G*=(V，A- A*)仍连通）。 2 、去掉任何割集，该图便不连通。,第八章 图与网络分析,83,第八章 图与网络分析,84,割集容量: 把割集上所有从V1指向V2弧（即正向弧）的容量之和称为割集容量，记为C(V1，V2)。,最小割集: 容量最

30、小的割集称最小割集。,第八章 图与网络分析,85,5.可增广链、剩余容量,第八章 图与网络分析,86,可增广链：容量网络G，若为网络中从vs到vt的一条链，给定向为从vs到vt ， 上的边凡与同向称为前向弧，凡与反向称为后向弧，其集合分别用+和-表示，f 是一个可行流，如果满足 ： （1）上的所有前向弧（与同向）皆非饱和弧 （2） 上的所有后向弧（与反向）皆非零流弧 则称为从vs到vt 的（关于f 的）可增广链。 剩余容量：沿可增广链的最大可增流量叫剩余容量，记作。,第八章 图与网络分析,87,定理10 ： 设 f 为网络G=(V，A，C)的任一可行流，流量为w，（V1， V2）是G的任一割集

31、，则有 w C(V1，V2),定理11 (最大流-最小割集定理): 任一个网络G 中，从vs到vt的最大流的流量等于分离vs 、 vt的最小割的容量。,三、有关理论,第八章 图与网络分析,88,证明 设 f *是一个最大流，流量为w，用下面的方法定义点集V1： 令vsV1； 若点vi V1，且 fij0，则令vjV1。 反复上面步骤，直到V1无法再扩充为止。 若vtV1，根据V1的定义，可得到从vs到vt的一条链，规定上凡与同向的边称为前向弧，凡与反向称为后向弧。显然，所有前向弧有fij0。我们令,第八章 图与网络分析,89,我们把 f *修改为 f1 *：,不难验证 f1 *仍为可行流，但

32、f1 *的总流量却比f1 多了，这与 f *是最大流矛盾。故vt不属于V1。,令V2=V- V1，我们有vtV2。于是我们得到一个割集（V1， V2），并且有,第八章 图与网络分析,90,但流量又满足,所以最大流的流量等于最小割的容量。,第八章 图与网络分析,91,可行流f是最大流的充要条件是不存在从vs到vt 的（关于f 的）可增广链。,基本思想： 对于一个可行流，在网络中找一个增广链，经调整，求得一个新的流值已增大的新的可行流，反复进行下去，直到找不到增广链为止。 步骤,五、标号算法,四、最大流判别,第八章 图与网络分析,92,步骤 1、给定一可行流。 2、判断目前可行流是否为最大流 ，即

33、标号过程。 注：标号分两部分，第一部分表示使这个点vj得到标号的前一个点vi的代号（当（vi,vj）为前向弧时，标号为+ vi,否则为-vi）。第二部分表示从上个标号的点vi到该标号点vj的流量的最大允许调整值（可推断出也是从发点到该点的最大允许调整值），该值为 或 当vt得到标号时，可以反向找出可增广链。 若vt得不到标号，也就是无可增广链。结束，否则，转向调整过程，即进行增流运算。,第八章 图与网络分析,93,标号的具体过程： 1.发点为（0，+） 2.对刚标号的点vi（若有多个，则选择其中一个）,考察与其相邻的且为未标号的点vj,第八章 图与网络分析,94,当vt得到标号时，可以反向找出

34、可增广链。 若vt得不到标号，也就是无可增广链。结束，否则，转向调整过程，即进行增流运算。,第八章 图与网络分析,95,3.调整过程（实际上是在增广链上调整）,我们把 f 0修改为 f1 ：,不难验证 f1 为流量已增的可行流,4.对新的可行流，重新进行标号运算直到vt得不到标号。,第八章 图与网络分析,96,vs,v5,v2,v6,v3,vt,v4,v1,(5,5),(5,2),(4,2),(3,2),(3,3),(3,0),(4,2),(3,3),(2,2),(5,2),(5,4),(,+),(v1,2),(vs,1),(v2,2),(-v5,2),(vs,2),(v4,2),(4,4),

35、(3,2),(3,1),(5,4),(4,4),(,+),(vs,1),(v3,1),(v6,1),(-v6,1),(3,3),(5,3),(5,5),(,+),最大流的流量为12。,第八章 图与网络分析,97,vs,v1,v2,v4,vt,v5,v3,v6,(5,4),(4,4),3,(6,4),(4,3),(4,3),(3,3),(3,2),(2,2),2,(2,2),(,+),(vs,1),(vs,1),(vs,1),(v2,1),(v2,1),5,4,6,4,4,3,3,2,2,vt,第八章 图与网络分析,98,(3,3),(4,4),(4,2),(2,2),(9,6),(5,3),(4,3),(8,5),(3,1),(3,3),(4,3),(,+),vs,v1,v2,v3,v4,v5,vt,(vs,3),(v3,2),(-v2,2),(v1,2),(v4,2),(v3,1),(9,8),(5,5),(4,0),