初等数学方法建模
?a11a12?aa22A0??21?????an1an2来存放各边长度，其中：
?a1n??a2n??
?????ann?aii?0 i?1,2,?,n；
aij?? i,j之间没有边，在程序中以各边都不可能达到的充分大的数代替； aij?wij wij是i,j之间边的长度，i,j?1,2,?,n。
对于无向图，A0是对称矩阵，aij?aji。
Floyd算法的基本思想是：递推产生一个矩阵序列A0,A1,?,Ak,?,An，其中Ak(i,j)表示从顶点vi到顶点vj的路径上所经过的顶点序号不大于k的最短路径长度。
计算时用迭代公式：
Ak(i,j)?min(Ak?1(i,j),Ak?1(i,k)?Ak?1(k,j))
k是迭代次数，i,j,k?1,2,?,n。
最后，当k?n时，An即是各顶点之间的最短通路值。
例10 用Floyd算法求解例1。
矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的Matlab程序如下： clear; clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b)); for k=1:6 for i=1:6 for j=1:6
if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end
26
初等数学方法建模
end end
b, path §4 树
4.1 基本概念
连通的无圈图叫做树，记之为T。若图G满足V(G)?V(T)，E(T)?E(G)，则称T是G的生成树。图G连通的充分必要条件为G有生成树。一个连通图的生成树的个数很多，用?(G)表示G的生成树的个数，则有公式
公式 (Caylay)?(Kn)?nn?2。
公式 ?(G)??(G?e)??(G?e)。
其中G?e表示从G上删除边e，G?e表示把e的长度收缩为零得到的图。
树有下面常用的五个充要条件。
定理1 （i）G是树当且仅当G中任二顶点之间有且仅有一条轨道。 （ii）G是树当且仅当G无圈，且????1。 （iii）G是树当且仅当G连通，且????1。
（iv）G是树当且仅当G连通，且?e?E(G)，G?e不连通。 （v）G是树当且仅当G无圈，?e?E(G)，G?e恰有一个圈。 4.2 应用—连线问题
欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij，设计一个线路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。
下面介绍构造最小生成树的两种常用算法。 4.2.1 prim算法构造最小生成树
设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P?{v1}（假设构造最小生成树时，从顶点v1出发），集合Q的初值为Q??。prim算法的思想是，从所有p?P，v?V?P的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到P?V时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。
prim算法如下：
（i）P?{v1}，Q??； （ii）while P~?V
(pv,p?P,v?V?P} pv?minw
27
初等数学方法建模
P?P?{v} Q?Q?{pv}
end
例11 用prim算法求右图的最小生成树。
我们用result3?n的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下： clc;clear; M=1000;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;
a=[a;zeros(2,7)];
a=a+a';a(find(a==0))=M;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp);
[jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result
4.2.1 Kruskal算法构造最小生成树
科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法如下: (i)选e1?E(G)，使得w(e1)?min。
(ii)若e1,e2,?,ei已选好，则从E(G)?{e1,e2,?,ei}中选取ei?1，使得 ① G[{e1,e2,?,ei,ei?1}]中无圈，且 ② w(ei?1)?min。 (iii)直到选得e??1为止。
例12 用Kruskal算法构造例3的最小生成树。
我们用index2?n存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号u改记为此边的另一序号v，同时把后面边中所有序号为u的改记为v。此方法的几何意义是：将序号u的这个顶点收缩到v顶点，u顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。
Matlab程序如下：
28
初等数学方法建模
clc;clear; M=1000;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70;
[i,j]=find((a~=0)&(a~=M)); b=a(find((a~=0)&(a~=M)));
data=[i';j';b'];index=data(1:2,:); loop=max(size(a))-1; result=[];
while length(result) flag=find(data(3,:)==temp); flag=flag(1); v1=data(1,flag);v2=data(2,flag); if index(1,flag)~=index(2,flag) result=[result,data(:,flag)]; end if v1>v2 index(find(index==v1))=v2; else index(find(index==v2))=v1; end data(:,flag)=[]; index(:,flag)=[]; end result §5 匹配问题 定义 若M?E(G)，?ei,ej?M，ei与ej无公共端点（i?j），则称M为图G的一个对集；M中的一条边的两个端点叫做在对集M中相配；M中的端点称为被M许配；G中每个顶点皆被M许配时， M称为完美对集；G中已无使|M'|?|M|的对集M'，则M称为最大对集；若G中有一轨，其边交替地 在对集M内外出现，则称此轨为M的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。 若把可增广轨上在M外的边纳入对集，把M内的边从对集中删除，则被许配的顶点数增加2，对集中的“对儿”增加一个。 1957年，贝尔热(Berge)得到最大对集的充要条件： 定理2 M是图G中的最大对集当且仅当G中无M可增广轨。 1935年，霍尔(Hall)得到下面的许配定理： 定理3 G为二分图，X与Y是顶点集的划分，G中存在把X中顶点皆许配的对集的充要条件是， ?S?X，则|N(S)|?|S|，其中N(S)是S中顶点的邻集。 由上述定理可以得出： 29 初等数学方法建模 推论1：若G是k（k?0)正则2分图，则G有完美对集。 所谓k正则图，即每顶点皆k度的图。 由此推论得出下面的婚配定理： 定理4 每个姑娘都结识k(k?1)位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。 人员分派问题等实际问题可以化成对集来解决。 人员分派问题：工作人员x1,x2,?,xn去做n件工作y1,y2,?,yn，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？ 这个问题的数学模型是：G是二分图，顶点集划分为V(G)?X?Y，X1?{x1,?,xn}， Y1?{y1,?,yn}，当且仅当xi适合做工作yi时，xiyi?E(G)，求G中的最大对集。 解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。 匈牙利算法： （i）从G中任意取定一个初始对集M。 （ii）若M把X中的顶点皆许配，停止，M即完美对集；否则取X中未被M许配的一顶点u，记 S?{u}，T??。 （iii）若N(S)?T，停止，无完美对集；否则取y?N(S)?T。 （iv）若y是被M许配的，设yz?M，转（iii）；否则，取可增广轨P(u,y)，S?S?{z}，T?T?{y}，令M?(M?E(P))?(E(P)?M)，转（ii）。 把以上算法稍加修改就能够用来求二分图的最大对集。 最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图G的每边加了权w(xiyj)?0，表示xi干yj工作的效益，求加权图G上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入可行顶点标号与相等子图的概念。 定义 若映射l:V(G)?R，满足?x?X,y?Y， l(x)?l(y)?w(x,y)， 则称l是二分图G的可行顶点标号。令 El?{xy|xy?E(G),l(x)?l(y)?w(xy)}， 称以El为边集的G的生成子图为相等子图，记作Gl。 可行顶点标号是存在的。例如 30