图论例题.doc

例1 设有5个居民点（如图1），每条边代表两居民点的道路，数字代表路长。现要在这5个居民点之间设置通信线路网，以保证5个居民点的联络。如果已知设置通信线路代价与道路长成正比，问如何建立该通信联络网，使联网代价最小？v5v3v4v1v2解：对本例而言是寻找最小生成树。运用kruskal算法求出图1的最小生成树，即可得到最佳建立网络的方案。求解如下：clear;n=5;w=inf*ones(5);w(1,2,3,4=1,7,3;w(2,3,5=6,4;w(3,4,5)=8,5;w(4,5)=2;a,b=mintreek(n,w)% 输出顶点与边的标记，最小树的构成一目了然e1(v1v2)e8(v4v5)e4(v1v4)e7(v3v1)% 最小生成树的权值a= 11 % 其含义见程序mintreek.m的说明b=1 2 1 14 5 2 81 4 3 43 5 5 7图1是a、b图的重叠，图b用红颜色标出。最小生成树图b是一种建立通信联络网的方案。例2 某公司使用一种设备，这种设备在一定年限内随着时间推移逐渐损坏。所以，保留这种设备的时间越长，每年的维修费用就越大。假设该公司在第1年开始时必须购置一台这种设备，并假设计划使用这种设备的时间为5年，估计这台设备的购买费和维修费（单位：万元）如图表1和表2所列。表1 第1年 第5年的购买价格年号12345价格2020222223表2 不同使用年限的设备的维修费使用年限0112233445维修费57121825这家公司希望确定应在哪一年购买一台新设备，使得维修费和新设备的购置费的总和最小。解： 考虑6个点，其中表示在第年初要购买新设备。是虚设点，表示在第5年底才购买新设备。再从点引出指向点的弧，弧表示第年年初购进的新设备要使用到第年的年初。弧上所赋的权为第年的购置费加上从第年初到第年初这段时间的维修总费用。例如，（万元），如此计算可得到所有权值，见下面的赋权有向图。本问题为在上面的赋权图中求一条从到总权最小的路径。求解如下：clear;n=6;w=inf*ones(6);w(1,2,3,4,5,6)=25,32,44,62,87;w(2,3,4,5,6)=25,32,44,62;w(3,4,5,6)=27,34,46;w(4,5,6)=27,34;w(5,6)=28;s,d=minroute(1,n,w)% 输出，每列表示最短路径的顶点序号s=1 1 1 1 1 10 2 3 4 5 30 0 0 0 0 6% 最短路径的权值d=0 25 32 44 62 78可见，从到总权最小的路径为，权值为78。由图3可以看出也是一条总权最小的路径，权值为78，可知最小路径不唯一。2525272728626234344432324687例3 8个城市之间有公路网，每条公路为下图中的边，边上的权数表示通过该公路所需的时间。设现处在城市，那么从该城市到其他各城市，应选择什么路径使所需的时间最少？解： 这是一个无向网，根据题意是要求一条从到其他各城市的最短路径。求解如下：clear;w=inf*ones(8);w=(1,2,3,5,6,7)=1,2,7,4,8;w(2,1,3,4,7)=1,2,3,7;w(3,1,2,4,5)=2,2,1,5;w(4,2,3,5,8)=3,1,3,6;w(5,1,3,4,6,8)=7,5,3,3,4;w(6,1,5,7,8)=4,3,2,6;w(7,1,2,6,8)=8,7,2,4;w(8,4,5,6,7)=6,4,6,4;s,d=minroute(1,8,w,1)%输出s=1 1 1 1 1 1 1 10 3 3 3 3 6 6 30 0 0 4 4 0