工程数学业.doc

工程数学考试最后一道题：论述网络优化中的主要问题及相应算法。答：1、最短路问题定义：设G是一个权图，路P的权w(P)称为P的长度，两点u，v之间最短路的长度称为u，v之间的距离，记为(u，v)，即定义：设G是一个权图，u0V(G)，SV(G)，u0到S内各点的所有路中长度最小者，称为u0到S的最短路，其长度称为u0到S的距离，记为(u0，S)讨论最短路问题：1) 假设G是简单图。2) 因为当w(uv)时，我们认为u，v重合，所以我们不妨假定所有边的权均为正数。根据假设，具体算法有：Dijkstra算法：假设S是V的真子集，u0S，令SVS，若Pu0是从u0到S的最短路，则显然，且P的(u0，)节必然是最短(u0，)路，所以利用该公式，便可按如下过程求最短路首先，确定距u0最近的一个顶点令S0u0，由于距u0最近的顶点必为u0的邻点，故只需求出u1使w(u0u1)minw(u0v)|v，即u0u1是与u0关联的最短边，显然，u0u1便是最短(u0，u1)-路又令S1u0，u1，且用P1表示路u0u1，一般地，若Sku0，u1，uk以及相应的最短路P1，P2，Pk已经确定，则可用(1)式来计算，并选取顶点uk+1使d(u0，uk+1)这时，d(u0，uk+1)d(u0，uj)w(ujuk+1)对某个k成立将边uj uk+1连接到路Pj上，即得最短(u0，uk+1)-路Pk+1，再令Sk+1u0，u1，uk，uk+1，这样一直下去，直到，即可求出u0到G中任意一点的最短路2、 最小生成树问题Kruskal算法：Kruskal算法的直观思想便是设有赋权图G，首先找到G的权最小的边，并取出来。然后，在剩下的边中再找出权最小且与已选出的边不构成回路的，再把它取出来，一直下去，直到选不出边在上述过程中，我们得到的图是无回路的。进一步地，我们可证明我们最终得到的是一棵最小生成树。设G是简单连通权图，w是其权函数。(1) 选取G的一边e1，使w(e1)minw(e)|eE，令E1e1，(2) 若已选出Eie1，ei，那么，从EEi中选取一边ei1，使() Eiei1的导出子图中不含回路；() w(ei1)minw(e)| eEEi , Eie的导出子图无回路(3) 若ei1存在，令Ei1Eiei1，i1i，转(2)；若ei1不存在，则输出Eie1，ei，算法停止。可以证明，如上算法所得到的边集的导出子图T*(就称其为算法得到的子图)，即为G的最小生成树。定理Kruskal算法得到的图T*是G的最小生成树证明由算法可知，T*必包含了G的所有顶点且是连通、无回路的，从而可知T*是生成树因而，若设G有n个顶点，则T*中也必有n个顶点，从而T*中必有n1条边，于是，T*是边集En1e1，e2，en1的导出子图，这里，e1，e2，en1依次是算法产生的边下面用反证法证明T*是最小生成树若不然，取所有最小生成树中与T*具有最多公共边者为T1，则边集E(T*) E(T1)，设ek是T*中第一条不在T1中的边，即e1，e2，ek1E(T1)，E(T1)由树的性质，T1ek必有回路C由于T*中无回路，C中的边必有不在T*中者，设回路中的边ek E(T*)，显然T2(T1ek)ek也是一棵生成树，且 w(T2)w(T1)w(ek)w(ek)因为e1，e2，ek1，ek E(T1)，故这k条边不构成回路，由Kruskal算法中ek的取法知w(ek)w(ek)所以，w(T2)w(T1)，因此T2也是一棵最小生成树，且与T*的公共边多于T1，与T1的定义矛盾这样就证明了T*必为最小生成树3、 最大流问题设NV，U为一个加权的有向图，权值为非负整数，若存在 X，YV，满足XY=，X中所有顶点的入度均为0，Y中所有顶点的出度均为0，则称有向图N为网络，并将X中的点称为源点，将Y中的点称为聚点（汇点），N中其他顶点称为中间点，N上的权函数c也称为容量函数一条弧ai，j的权值称为a的容量，记为c(a)或c()或c(i,j)我们主要讨论|X|=|Y|=1的情况，即假设网络中恰有一个源点x和一个聚点y，并总是将中间点集合记为I设NV,U为恰含有一个源点和一个聚点的网络，f为N的弧集U上的实数值函数，V1，V2V，用V1，V2表示起点在V1中，终点在V2中的弧的集合，记，当 V1=i时可以将f(V1,V2)简记为f(i,V2)定义1 设f为网络NV,U的弧集U上的实数值函数，如果函数f满足(1) 容量约束：0f(i,j)c(i,j)， i，jU，(2) 守恒条件：f(i,V)f(V, i)， i I，则称函数f为网络N的一个容许流，简称为流；当N的源点为x，聚点为y时，称f(x,V)为流的值，简记为f x, y由定义2可以证明定义2设函数f为网络NV,U的一个流，aU，如果f(a)=0，则称弧a是f -零的；如果f (a)0，则称弧a是f 正的；如果f (a) c (a)，则称弧a是f 不饱和的；如果f (a)= c (a)，则称弧a是f 饱和的4、 最大匹配定义1设图GV，E，M E，如果M中任意两条边在G中均不相邻，则称M是G的一个匹配M中一条边的两个端点称为在M下是配对的定义2若匹配M的一条边与顶点v关联，则称M饱和v，或称v是M-饱和的，否则称v是M-不饱和的定义3如果M是G的一个匹配，对G的任意匹配M ，有 | M | | M |，则称M是G的最大匹配定义4设M是G的一个匹配，边在E(G)- M和M中交错出现的路称为M-交错路，起点和终点都是M-不饱和点的M-交错路称为M-增广路定理1图G的一个匹配M是最大匹配的充要条件是G不包含M-增广路证明设M是G的一个最大匹配，若G包含一条M-增广路v0v1v2v2m+1，设M = (M v1v2，v3v4，v2m-1v2m) v0v1，v2v3，v2mv2m+1 ，显然，M E，且M 是G的一个匹配因 |M |M|1，与M是最大匹配矛盾因而，G不包含M-增广路反之，设G不包含M-增广路，若M不是最大匹配，令M 是G的一个最大匹配，设H是由M M导出的G的子图，则H的每个顶点在H中的度只能是1或2，因此H中的每一个分支或是一