图论与网络模型第五章及方法

第五章图与网络模型及§1图论于18世纪。第一篇图论是数学家欧拉于1736年的“哥尼年，凯莱在计数烷CnH2n21859年提图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的1最短路问题（SPP－shortestpath例 例 例 postman梅谷教授1960年首先，所以国际上称之为中国邮递员问题。例 例 的运费已知，那么如何安排方案可以使总成本最低？种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（on）问network（netwokoptimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多络流（networkflows）或网络流规划等。§2一个无向图(undirectedgraph)G是由一个非空有限集合V(G和V(G中某些元素的E(G)GV(GE(G))V(G{v1,v2,vn}称为图G的顶点集（vertexset）或节点集（nodeset，V(G)中的每一个元素vi(i1,2,n)称为该图的一个顶点（vertex）或节点（nodeE(G){e1,e2,,em称为图G的边集（edgesetE(G中的每一个元素ek(即V中某两个元素vivj的无序对)记为ekvi,vjekvivjv被称为该图的一条从vi到vj的边（edge

(k1,2,,m)当边ekvivj时，称vivj为边ek的端点，并称vj与vi相邻（adjacent；边ek为与顶点vi,vj关联（ 图G中相邻。network一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号|V|(G)表示，边数用|E|或(G表示当讨论的图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母G，例如，分别用V,E,和代替V(G),E(G),(G)和(G)。端点重合为一点的边称为环(loop)定义一个有向图（directedgraph或digraph）G是由一个非空有限集合V和V中某些元素的有序对集合A构成的二元组，记为G(V,A)。其中V{v1v2,vn}称为图G的顶点集或节点集，V中的每一个元素vi(i1,2,n称为该图的一个顶点或节点A{a1a2,am}称为图G的弧集（arcset），中的每一个元素ak(即V中某两个元素vivj的有序对)记为akvi,vj或akvivj(k1,2,n)，被称为该图的一条从vi到vj的弧（arc当弧akvivj时，称vi为ak的尾（tailv为ak的头（head，并称弧ak为vi的出弧（outgoingarc，为vj的入弧（ingarc。样的有向图称为G的一个定向图。的完全图记为Kn。若V(GXYXY，|X||Y|0（这里|X|X中的元素个数XY中亦然，则称G为二分图(bipartitegraph)；特别地，若H叫做图G的子图（subgraph）HGV(HV(G)E(HE(GH是G的子图，则GH的母图G的支撑子图（spanningsubgraph，又成生成子图）是指满足V(HV(G的子图H。设vV(G，G中与v关联的边数（每个环算作两条边）称为v的度(degree)，记d(v)。若d(v)是奇数，称v是奇顶点(oddpoint)d(v)是偶数，称v是偶顶点(evend(v)GVA是一个简单有向图，|V|n,|A|m，并假设V中的顶点用自然数1,2,nGVAC是一个nn的01C(cij)nn{0,1}nncij

(i,j)(i,j)例 00 00 1 1 0 同样，对于网络中的权，也可以用类似邻接矩阵的nn矩阵表示。只是此时一条

jV,k(i,j)jV,k(j,i)终点，则关联矩阵中对应的元素为1；如果一个节点与一条弧不关联，则关联矩阵中有2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的空间。但由于87所示的图，如果关联矩阵中每列对应弧的顺序为(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵100010000000101000000000011000001100 所对应的权在增加的行中。弧表表示法将图以弧表（arclist）的形式在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2m个存应地用额外的单元表示。例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)8，9，6，4，0，3，67，则弧表表示如下：1123445523423534权89640367邻接表表示法将图以邻接表（adjacencylists）的形式在计算机中。所谓图的示。例如，例7所示的图，邻接表表示为(1,3)9对于有向图G(V,A)，一般用A(i)表示节点i的邻接表，即节点i的所有出弧构))示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n出发的所有孤。对每条弧，要依次存放其（forwardstar）（1,2（l,3（2,4（3,2（4,3（4,5节点号1234566781123445523423534权89640367point(n1)m1。对于节点i如果point(i)point(i1)，则节点i没有出弧。这种表示法与弧表表示法也非常相号后有序存放，并增加一个数组（point）记录每个节点出发的弧的起始编号。有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reversestar）表后存放进入节点n的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关个节点的入孤的起始地址（即弧的编号7所示的图，可以用反向星形表示节点对应的入弧的起始地址编号数组（记为rpoint节点号123456起始地址1782233344531权763前向星形表示法的基础上，加上上面介绍的rpoint数组和如下的trace数组即可。这相两种表示法中的弧的对应关系（记为trace12345678正向法中弧编号trace(41257836①星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的空间较少，并且对那些不提供指针类型的语言（如FORTRAN语言量较大（需要花费O(m的计算时间。有关“计算时间”的观念是网络优化中需要考息（如上三角部分0和1，而不含有1，因为此时不区分边的起点和终点。又如，在邻接表和星形表示Wv0e1v1e2ekvk，其中eiE(G，1ik，vjV(G，0jk，ei与vi1vi关联，称W是图G的一条道路(walk)，k为路长，顶点v0和vk分别称为W的起点和终点，而v1v2,vk1称为它的内部顶点。若道路W的边互不相同，则W称为迹(trail)。若道路W的顶点互不相同，则W称若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。u,v间的的长叫做uv间的距离。记作d(uv。若图G的任二顶点均连通，则称G是连通图。P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的图C是一个圈的充要条件是C是各顶点的度均为2对G的每一边e，赋以一个实数w(e—直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点u0,v0间的具最小权的轨。这条轨叫做u0v0间的最短路，它的权叫做u0v0间的距离，亦记d(u0v0)。求最短路已有成算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0 近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至v0（或直至G的所有顶点，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是令l(u00，对vu0，令l(vS0u0i0对每个vSi（SiVSimin{l(v),l(u)代替l(v)。计算min{l(v)}，把达到这个最小值的一个顶点记为ui1，令Si1Si{ui1}(iii若i|V|1，停止；若i|V|1，用i1代替i，转(ii)算法结束时，从u0到各顶点v的距离由v的最后一次的标号l(v)给出。在v进入Si之前的标号l(vTv进入Si时的标号l(vP标号。算法就是不断修改各项TPP标号所由来的边在图上标明，则算法结束时，u0至各项点的最短路也在图上标示出来了。例9某公司在六个城市c1,c2,,c6中有，从ci到cj的直接航程票价记在

0用矩阵ann（n为顶点个数存放各边权的邻接矩阵，行向量pbindex1index2dP标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分0pb(i)0

；index2(i)存放始点到第i点最短通路中第i顶点前一顶点的序号d(i)存放由始点到第i求第一个城市到其它城市的最短路径的程序如下whilesum(pb)<length(a)iflength(index)>=2d,index1,计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra间复杂度为O(n3)。第二种解决这一问题的方法是由FloydRW算法，称之假设图G权的邻接矩A0 a1n aA

2n an

annaii0aijaij

,wij是ijij1,2,nFloyd算法的基本思想是：递推产生一个矩阵序列A0A1Ak,An，其中Ak(i,j)vivjk的最短路径长 Ak(ijmin(Ak1(ijAk1(i,kAk1(kj))k是迭代i,jk1,2,n。例10用Floyd算法求解例1fork=1:6fori=1:6ifb, 连通的无圈图叫做树，记之为T。若图G满足V(G)V(TE(T)E(G则称T是G的生成树。图G连通的充分必要条件为G有生成树。通图的生成树的个数很多，用(G)表示G的生成树的个数，则有(Caylay)(Knnn2(G(Ge(Ge)其中Ge表示从G上删除边eGe表示把e的长度收缩为零得到的图。1（i）G是树当且仅当GG是树当且仅当G无圈，且1G是树当且仅当G连通，且1G是树当且仅当G连通，且eE(GGen个城市的铁路，已知ij城之间的铁路造价为Cij，设计一个线prim设置两个集合P和Q,P用于存放G的最小生成树中的顶点，集合Q存放G，集合pv，将顶点vPpv加入集合Q中，如PV时，最小生成树构造完毕，这时集合Q中包含了最小生成树prim算法如下（i）P{v1}，QwhileP~pvminw(pv,pP,vVPPQQ11prima(1,2)=50;a(2,4)=65; Kruskal算法构造最小生成若e1e2ei已选好，则从E(G){e1,e2,ei}中选取ei1①②w(ei1min直到选得e1为止我们用inden号中较大序号u改记为此边的另一序号v，同时把后面边中所有序号为u的改记为v。此方法的几何意义是：将序号u的这个顶点收缩到vu顶点不复存在。后面继续a(1,2)=50;a(2,4)=65;whilelength(result)<loopifindex(1,flag)~=index(2,flag)if 定义ME(GeiejMei与ej无公共端点（ij）MG的一个对集；MM中相配；M中的端点称为被M许配；G中每个顶点皆被M许配时，M称为完美对集；G中已无使|M'||M|的MM称为最大对集；若G中有一轨，其边交替地在M内外出现，则称此轨为M的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。顶点数增加2，对集中的“对儿”增加一个。定理 M是图G中的最大对集当且仅当G中无M可增广轨3GX与YGX中顶点皆许配的SX，则|N(S)||S|N(S)S中顶点的邻集。1：若G是k（k02分图，则G有完美对集。所谓k正则图，即每顶点皆k度的图。定理4 每个姑娘都结识k(k1)位小伙子，每个小伙子都结识k位姑娘，则每位人员分派问题：工作人员x1x2,xn去做n件工作y1y2,yn，每人适合做其这个问题的数学模型是：G是二分图，顶点集划分为V(GXY，G中的最大对集。从GM许配的一顶点u，记S{u}TN(STyN(STyMyzMSS{z}TT{y}，转（iii否则，取可增广轨P(u,y)M(ME(P))(E(P)M，转（ii。这个问题的数学模型是：在人员分派问题的模型中，图G的每边加了权 定义若映射l:V(GR，满足xXyYl(x)ly)w(x,y)，则称l是二分图GEl{xy|xyE(G),l(xlyw(xy)}，El为边集的G的生成子图为相等子图，记作Gl。l(x)maxl(y)

xXyY定理 Gl的完美对集即为G的权最大的完美对集选定初始可行顶点标号l，确定Gl，在GlMM许配的顶点uSu}，T。若 (S)T，转（iv；若N(S)T， lmin{l(x)l(y)w(xyl(v)

l(v),vT llGlGl（iv）NGl(STyMyxM，则SSiii；否则，取（ii

M(ME(P))(E(P)M)NGl(S是GlS EulerHamilton定义经过G的每条边的迹叫做GEulerEulerEuler直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即定理 （i）G是Euler图的充分必要条件是G连通且每顶点皆偶次d（ii）G是Euler图的充分必要条件是G连通且G i

Ci是圈，E(CiE(Cj(ij定义包含GHamilton(哈密顿)轨；闭的Hamilton直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种1o.vV(G，令Wv 2o.假设迹WvevevE{e,,e 01 i ei1ei1和vi相关联除非没有别的边可选择，否则ei1不是GiG{e1,,ei}的割边(cutedge)。(所谓割边是一条删除后使连通图不再连通的边)。 设G是连通赋权图。（i）求V0v|vV(Gd(v1(mod2)}对每对顶点uvV0，求d(uv)（d(uv是u与vFloyd算构造完全赋权图K|V0|，以V0为顶点集，以d(uv)为边uv的权00M中边的端点之间的在G（在（vi）中得的图GEuler回路即为中国邮递员问题的解。邮局有k(k2)位投递员，同时投递信件，全城街道都要投递，完成任务返回邮kPP的数学模型如下G(VE)是连通图，v0V(G)，求G的回路C1,Ck，使（i）v0V(Ci)，i1,2,,kmaxw(e)mini1ikeE(CikE(Ci)i旅行商（TSP）问一个可行的办法是首先求一个Hamilton圈C，然后适当修改C以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈Cv1v2vnv1。对于1i1jn，构造新的Hamilton圈Cijv1v2vivjvj1vj2vi1vj1vj2vnv1它是由C中删去边vivi1vjvj1，添加边vivjvi1vj1w(vivjw(vi1vj1w(vivi1w(vjvj1，则以Cij代替C，Cij叫做C的改良（i这个算法的优劣程度有时能用Kruskal算法加以说明。假设C是G中的最优圈。则对于任何顶点vCv是在GvHamilton轨，因而也是Gv的生成树。由此推知：若TGv中的最优树，同时e和f是和v关联的两条边，并使得w(ew(fw(Tw(ew(fw(C的一个下界。更为有效；然而，有点奇怪的是，进一步推广这法，就不利了。例13从（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)LMNTLMNTc1=[51:4whilefori=1:L-1c1=[561:4];%改变初始圈，该算法的最后一个顶点不动whileforn=m+2:L-iffori=1:L-1ifsum1<sum 定义在以VA为弧集的有向图GVALAR为孤上的权函数，弧(i,jAL(i,jlij(ij的容量下界（lowerboundU:AR为弧上的权函数，弧(i,jA对应的权U(i,j记为uij(i,j)的容量上界，或直接称为容量（capacityD:VR为顶点上的权函数，节点iVD(i记为di，称为顶点i的供需量（supply／demand权函数D，可以直接用所有孤上对应的权组成的有限维向量表示，因此L,U,D有时直接称为权向量，或简称权。由于给定有向图G(V,A)后，我们总是可以在它的弧集在流网络中，弧(ij)的容量下界lij和容量上界uij表示的物理意义分别是：通过该发送到网络外部的“物质”数量（di0时。下面我们给出严格定义。定义NVAL,UD，其上的一个流（flow）fNAR的一个函数，即对每条弧(ij赋予一个实数fij（称为弧(i,j的流量果流ffijj:(i,j

fjidij:(j,i

iV lijfijuij (i,j) flownetwork可见，当di0时，表示有di个单位的流量从该项点流出，因此顶点i（supplynode）或源（sourcedi0时，表示有|di|个单位的流量流入该点（或说被该顶点吸收，因此顶点i称为需求点（demandnode）或汇（sink，有时也形象地称为终止点或收点等；当di0时，顶点idi

L0（即所有孤(i,j的容量下界lij0），并将L0时的流网络简记为N(V,A,UD)。此时，相应的容量约束（2）为0xijuij (ijA定义NVA,UD中，对于ffij (i,j)称该弧为饱和弧（saturatedarc）；如果某条弧(ij上的流量小于其容量（fijuijarc。考虑如网络N(V,A,U,D)：节点s为网络中唯一的源点，t为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f，此时称流f的流量（或流值，flowvalue）ds（根据（3），它自然也等于dt，通常记为v或v(f