发布时间 : 星期四 文章图论基础知识汇总(适合建模)更新完毕开始阅读
?l?min{l(x)?l(y)?w(xy)}，
x?S,y?T?l(v)??l,v?S? l(v)??l(v)??l,v?T，
?l(v),其它? l?l ，Gl?Gl。 （iv）选NGl(S)?T中一顶点y，若y已被M许配，且yx?M，则S?S?{z}，
；否则，取Gl中一个M可增广轨P(u,y)，令 T?T?{y}，转（iii）
M?(M?E(P))?(E(P)?M)， 转（ii）。
其中NGl(S)是Gl中S的相邻顶点集。
§6 Euler图和Hamilton图
6.1 基本概念
定义 经过G的每条边的迹叫做G的Euler迹；闭的Euler迹叫做Euler回路或E回路；含Euler回路的图叫做Euler图。
直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。
定理7 （i）G是Euler图的充分必要条件是G连通且每顶点皆偶次。
（ii）G是Euler图的充分必要条件是G连通且G??Ci?1di，Ci是圈，
E(Ci)?E(Cj)??(i?j)。
（iii）G中有Euler迹的充要条件是G连通且至多有两个奇次点。
定义 包含G的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或H圈；含Hamilton圈的图叫做Hamilton图。
直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。
6.2 Euler回路的Fleury算法
1921年，Fleury给出下面的求Euler回路的算法。 Fleury算法：
1o. ?v0?V(G)，令W0?v0。
2o. 假设迹Wi?v0e1v1?eivi已经选定，那么按下述方法从E?{e1,?,ei}中选取边ei?1：
（i）ei?1和vi相关联；
（ii）除非没有别的边可选择，否则ei?1不是Gi?G?{e1,?,ei}的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。
3o. 当第2步不能再执行时，算法停止。 6.3 应用
6.3.1 邮递员问题 中国邮递员问题
-17-
一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。
上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。
显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。
对于非Euler图，1973年，Edmonds和Johnson给出下面的解法： 设G是连通赋权图。
（i）求V0?{v|v?V(G),d(v)?1(mod2)}。
（ii）对每对顶点u,v?V0，求d(u,v)（d(u,v)是u与v的距离，可用Floyd算法求得）。
（iii）构造完全赋权图K|V0|，以V0为顶点集，以d(u,v)为边uv的权。
（iv）求K|V0|中权之和最小的完美对集M。
（v）求M中边的端点之间的在G中的最短轨。
（vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。
（vii）在（vi）中得的图G'上求Euler回路即为中国邮递员问题的解。 多邮递员问题：
邮局有k(k?2)位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。
kPP的数学模型如下：
G(V,E)是连通图，v0?V(G)，求G的回路C1,?,Ck，使得
（i）v0?V(Ci)，i?1,2,?,k， （ii）max1?i?kke?E(Ci)?w(e)?min，
i（iii）
?E(C)?E(G)
i?16.3.2 旅行商（TSP）问题
一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。
一个可行的办法是首先求一个Hamilton圈C，然后适当修改C以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈C?v1v2?vnv1。
（i）对于1?i?1?j?n，构造新的Hamilton圈: Cij?v1v2?vivjvj?1vj?2?vi?1vj?1vj?2?vnv1,
它是由C中删去边vivi?1和vjvj?1，添加边vivj和vi?1vj?1而得到的。若则以Cij代替C，Cij叫做C的改良圈。 w(vivj)?w(vi?1vj?1)?w(vivi?1)?w(vjvj?1)，
（ii）转（i），直至无法改进，停止。
-18-
用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。
这个算法的优劣程度有时能用Kruskal算法加以说明。假设C是G中的最优圈。则对于任何顶点v，C?v是在G?v中的Hamilton轨，因而也是G?v的生成树。由此推知：若T是G?v中的最优树，同时e和f是和v关联的两条边，并使得
w(e)?w(f)尽可能小，则w(T)?w(e)?w(f)将是w(C)的一个下界。
这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。
例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表： L M N Pa Pe T L 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 61 13 解：编写程序如下： clc,clear
a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60; a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70; a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61; a(5,6)=13; a(6,:)=0; a=a+a';
c1=[5 1:4 6]; L=length(c1); flag=1;
while flag>0 flag=0; for m=1:L-3
for n=m+2:L-1 if
a(c1(m),c1(n))+a(c1(m+1),c1(n+1)) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end end end sum1=0; for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1)); end circle=c1; -19- sum=sum1; c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动 flag=1; while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end end end sum1=0; for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1)); end if sum1 circle,sum §7 最大流问题 7.1 最大流问题的数学描述 7.1.1 网络中的流 定义 在以V为节点集，A为弧集的有向图G?(V,A)上定义如下的权函数： （i）L:A?R为孤上的权函数，弧(i,j)?A对应的权L(i,j)记为lij，称为孤 (i,j)的容量下界（lower bound）； （ii）U:A?R为弧上的权函数，弧(i,j)?A对应的权U(i,j)记为uij，称为孤(i,j)的容量上界，或直接称为容量（capacity）； （iii）D:V?R为顶点上的权函数，节点i?V对应的权D(i)记为di，称为顶点i的供需量（supply／demand）； 此时所构成的网络称为流网络，可以记为 N?(V,A,L,U,D)。 由于我们只讨论V,A为有限集合的情况，所以对于弧上的权函数L,U和顶点上的权函数D，可以直接用所有孤上对应的权组成的有限维向量表示，因此L,U,D有时直接称为权向量，或简称权。由于给定有向图G?(V,A)后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。 在流网络中，弧(i,j)的容量下界lij和容量上界uij表示的物理意义分别是：通过该弧发送某种“物质”时，必须发送的最小数量为lij，而发送的最大数量为uij。顶点i?V对应的供需量di则表示该顶点从网络外部获得的“物质”数量（di?0时），或从该顶 -20-