数学建模 图论模型 图论
图论算法§1 最小生成树 11 生成树的概念 设图G(V，E)是一个连通图，当从图中任一顶点出发遍历图G时，将边集E(G)分成两个集合A(G)和B(G)。其中A(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V，A)是图G的子图，则称子图G1是连通图G的生成树。图的生成树不是惟一的。如对图1(a)，当按深度和广度优先搜索法进行遍历就可以得到图1中(b)和(c)的两棵不同的生成树，并分别称之为深度优先生成树和广度优先生成树。 对于有n个顶点的连通图，至少有n-1条边，而生成树中恰好有n-1条边，所以连通图的生成树是该图的极小连通子图。若图G的生成树中任意加一条边属于边集B(G)中的边，则必然形成回路。 求解生成树在许多领域有实际意义。例如，对于供电线路或煤气管道的铺设问题，即假设要把n个城市联成一个供电或煤气管道网络，则需要铺设n1条线路。任意两城市间可铺设一条线路，n个城市间最多可能铺设n(n1)/2条线路，各条线路的造价一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择n-1条使该网络的建造费用最少，这就是下面要讨论的最小生成树问题。 1.2 网的最小生成树 在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。 假设，要在n个居民点之间敷设煤气管道。由于，在每一个居民点与其余n1个居民点之间都可能敷设煤气管道。因此，在n个居民点之间，最多可能敷设n(n-1)/2条煤气管道。然而，连通n个居民点之间的管道网络，最少需要n-1条管道。也就是说，只需要n-1条管道线路就可以把n个居民点间的煤气管道连通。另外，还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在n(n-1)/2条可能的线路中优选n-1条线路，构成一个煤气管道网络，从而既能连通n个居民点，又能使总的花费代价最小。 解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点，把居民点之间的煤气管道看作边，而把敷设各条线路的代价当作权赋给相应的边。这样，便构成一个带权的图，即网。对于一个有n个顶点的网可以生成许多互不相同的生成树，每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。 如何构造这种网的最小生成树呢?下面给出这样一种解法： (1)已知一个网，将网中的边按其权值由小到大的次序顺序选取。 (2)若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。 (3)如此依次进行，直到选够(n-1)条边即得到最小生成树。 现以图2为例说明此算法。设此图是用边集数组EV表示的，且数组中各边是按权值由小到大的次序排列，如下表所示。 k12345678910EVk.p12242651115EVk.p23436475626COSTEVk.p1,EVk.p2561011141819212733 按权值由小到大选取各边就是在数组中按下标k由1到en(图中边数)的次序选取。选前2条边(2，3)，(2，4)时均无问题，保留作为树的边；到第3条边(4，3)时将与已保留的边形成回路，将其舍去；同样继续做：保留(2， 6)；舍去(6，4)；保留(5，7)，(1，5)，(1，6)，此时，保留的边数已够(n-1)=6条边，此时必定将7个顶点全部互相连通了，后面剩下的边(1，2)，(5，6)就不必再考虑了。最后得到的最小生成树如图2a中深色边所示，其各边权值总和等于80。由离散数学中的图论可以证明，这就是最小生成树了，其权值最小。当图中有权值相等的边时，其最小生成树可能有不同的选取方案。 实现此算法的关键是，在选取某条边时应判断是否与已保留的边形成回路。 这可用将各顶点划分为集合的办法解决：假设数组tag(1.en)作为顶点集合划分的标志初值为0。在算法的执行过程中，当所选顶点u，v是连通的，则将相应位置的tagu，tagv置以相同的数字，而不连通的点在初期分属不同的集合，置不同的数字；一旦两个不同的连通分支连通了，则修改tag的值，将新的连通分支改为相同的数字。我们以图2为例。首先选(2，3)(2，4)边，由于是连通的，并且不出现回路。tag2:1，tag3:=tag4:=1是同一个集合 A；选(6，2)边与A集合连通；tag6:=1；再选(5，7)与集合A不连通，tag5: tag7:2构成另一集合B；选(1，5)边与集合B连通，tag 1:=2；此时，集合A 2，3，4，6；集合B5，7，1；当选(1，6)边时，(1，6)与集合A、集合B都连通，并且两个顶点分别属于两个不同的集合A、B，这使得集合A与集合B通过边(1，6)连通。修改集合B中tag的值，置为1，即将集合B并入集合A。边为n-1条，这就是一棵最小生成树。 根据集合标志数组tag的变化过程，很容易判断，选择一条新的边是否构成回路。当新选边的两个顶点u、v，若tagu和tagv相同并且均不等于0时，即u，v已在生成树集合中被保留过，加入u，v后即形成回路，不能选。而当tag u<>tagv或者tagutagv0时，可以选并且不形成回路，说明u，v中至少有一个顶点未被选过或者被选过的u、v分别属于两个不同的集合，此时选择u，v可以将含u的集合与含v的集合连通，修改tag数组。如此下去，到所有顶点均已属于一个集合时，此最小生成树就完全构成了。 网的最小生成树算法描述如下： 假设算法中用到的数据结构是经过处理的。 COST(1.n，1.n)是带权数组存放网中顶点之间的权。EV(1.n*(n-1/2)按权从小到大存放排序后的顶点对，即EVK.P1存放一个顶点，边的另一顶点存放在EVK.P2之中。 tag(1.n)：顶点集合划分标志的数组。 Enumb：当前生成树的边数。 SM：当前权累计和。 PROC minspanningtree(VAR cost；VAR ev)； Var tag； BEGIN CALL INITIAL(tag); Enumb：0；SM:=0; 诸参量初始化 k:=1; 边数累计 WHILE (Enumb<=n-1) AND (k<n) DO Begin U:=EVk.P1；V:=EVk.P2； 选一对顶点(U，V) CALL FIND(U，T)； 找到含顶点U的集合T CALL FIND(V，W)； 找到含顶点V的集合W IF (T<>W) THEN Begin write(u，v)；Enumb:=Enumb+1； 最小生成树增加一条边 SM:=SM+COSTu，v； MERGE(T，W)；选u，v不会形成环，合并T，W集合，并修改tag end K:=K+1; 找下一条边 end IF Enumb<n-1 THEN write('There is not a minspanning tree') ELSE write(SM) END；由算法可知图2的最小生成树的结果是(2，3)，(2，4)，(2，6)，(5，7)，(1，5)，(1，6)。 §2 最短路径在一个赋权有向图上寻找最短路径问题也是图应用的一个重要课题。 假定图3中的有向图G=(V，E)是一个航空图，V的每一顶点表示个城市，正中的每条弧v>w表示从城市v到城市W的航线，弧V>w上的标号代表从V城飞到w城所需要的时间。要寻找由该航空图上一给定城市到另一城市所需要的最短飞行时间。可以用求解这个有向图的单源最短路径算法来完成。 下面，我们讨论求解单源最短路径问题的贪心算法，也称Dijkstra算法。 设有向图G=(V，E)，其中，V=1，2，n)cost是表示G的邻接矩阵，costi，j表示有向边(i，j)的权。若不存在有向边(i，j)，则costi，j的权为无限大(oo)。令S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。 (1)令顶点V0为源点，集合S的初态只包含顶点V0，即S=V0。数组dist记录从源点到其他各顶点当前的最短距离，其初值为disti:=costv0，i，(i=2，n)。 (2)从S之外的顶点集合V-S中选出一个顶点W，使distW的值最小。于是，从源点到达W只通过S中的顶点，我们把W加入集合S。 (3)调整dist中记录的从源点到V-S中每个顶点V的距离：从原来的distv和distw+costw，v中选择较小的值作为新的distv。 (4)重复上述过程(2)和（3），直到S中包含V的全部顶点。 最终数组dist记录了从源点到V中其余各顶点的最短路径。 对图3所示的加权有向图应用Dijkstra算法，从源点V2出发到达各顶点的最短路径如下表所示。 最短路径 - 源点 中间顶点 终止顶点 长度 2 5 10 3 15 3 4 30 3 1 35 6 oo - 对图3的执行过程：初始时，S2，dist1oo，dist315，dist4oo，dist510，dist6oo，第一遍处理时，W2使dist5最小、于是把5加入S。然后，调整dist中从源点到其余各顶点的距离：dist315，为次小，将3加入S。dist4cost2，3+cost3，4=15+1530，经中间点3。S2，5，3，4，同理，dist1cost2，3+cost3，135，S2，5，3，4，1，由于2没有一条到6的路径，所以dist6=oo。 由此我们给出最短路径算法如下PROC shortpath(VAR cost；VAR dist；VAR path；VAR S，V0)；BEGIN FOR W:=1 TO n DO Begin distW:=costV0，W;
