打字猴:1.70100992e+09
1701009920 (3)在图中不相邻的两个顶点之间加一条边,可得一个且仅得一个圈。
1701009921
1701009922 (4)图中边数有ne=p-1(p为顶点数)。
1701009923
1701009924 生成树:如果图T是G的一个生成子图,而且T又是一棵树,则称图T为一棵生成树。
1701009925
1701009926 【问题】
1701009927
1701009928 如图8-20所示为一图模型,试求其最小生成树。
1701009929
1701009930
1701009931
1701009932
1701009933 图8-20 图模型
1701009934
1701009935 【分析】
1701009936
1701009937 Kruskal算法又称避圈法,对于求解最小树模型很有效,其具体求解流程如下:
1701009938
1701009939 (1)选择边e1,使得w(e1)尽可能小;
1701009940
1701009941
1701009942
1701009943
1701009944 (2)若已选定边,则从中选取,使得:
1701009945
1701009946
1701009947 ①为无圈图;
1701009948
1701009949
1701009950 ②是满足(i)的尽可能小的权。
1701009951
1701009952 ③当第(2)步不能继续执行时,则停止。
1701009953
1701009954 采用计算机,MATLAB编程如下:
1701009955
1701009956     %避圈法    clc %清屏    clear all; %删除workplace变量    close all; %关掉显示图形窗口    b=[1 2 1;        1 3 4;        2 3 2;        2 4 3;        2 5 5;        3 4 1;        3 5 3;        4 5 2]    [T,v,c]=kruskal(b)
1701009957
1701009958 其中Kruskal算法脚本文件如下:
1701009959
1701009960     %Kruskal算法    %b-图的边权矩阵    %T-最小生成树的边集合    %v-最小生成树的邻接矩阵    %c-最小生成树的权    %j-迭代的次数    %k-已经被选入生成树的边数    function [T,v,c]=kruskal(b)    %根据边权矩阵求出图的边数    m=size(b,1);     %根据边权矩阵求出图的顶点数,注意此处顶点的标号需要以自然数序    n=max(b(1:2*m));     %整理边权矩阵让其按照权值由小到大的次序重新排列    [B,index]=sortrows(b,3);    B=B’;    %数据的初始化    t=1:n;    k=0;    T=[];    c=0;    %更新T,c,t(i)    for i=1:m        if t(B(1,i))~=t(B(2,i))  %判断第i条边是否与树中的边形成圈            k=k+1;            T(1:2,k)=B(1:2,i);            c=c+B(3,i);            tmin=min(B(1,i),B(2,i));            tmax=max(B(1,i),B(2,i));            for j=1:n                if t(j)==tmax                    t(j)=min(tmin,t(tmin));                end            end        end        if k==n-1            break;        end    end    %根据最小生成树的边集合构造邻接矩阵    v=zeros(n);    k=size(T,2);    for i=1:k        v(T(2*i-1),T(2*i))=1;        v(T(2*i),T(2*i-1))=1;    end
1701009961
1701009962 运行程序输出结果如下:
1701009963
1701009964     b =         1     2     1         1     3     4         2     3     2         2     4     3         2     5     5         3     4     1         3     5     3         4     5     2    T =         1     3     2     4         2     4     3     5    v =         0     1     0     0     0         1     0     1     0     0         0     1     0     1     0         0     0     1     0     1         0     0     0     1     0    c =         6
1701009965
1701009966 由结果可知,最小树模型为:
1701009967
1701009968
1701009969
[ 上一页 ]  [ :1.70100992e+09 ]  [ 下一页 ]