grtheorytest.m

可求最短路径和最小边覆盖颠覆盖和旅行商问题的图论程序

    end
    grPlot(V,[E,[1:size(E,1)]'],'g','');
    title(['\bf This graph is ' st 'Eulerian'])
  case 12, % grMaxComSu test
    disp('The grMaxComSu test')
    V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
       3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
    E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;5 6;6 7;...
       5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
    grPlot(V(:,1:2),E,'g','%d',''); % the initial graph
    title('\bfThe initial graph')
    grPlot(V,E,'g','%d',''); % the initial graph
    title('\bfThe initial graph with weighed vertexes')
    nMS=grMaxComSu(E); % the maximal complete sugraph
    fprintf('Number of vertexes on the maximal complete sugraph = %d\n',...
      length(nMS));
    disp('In a maximal complete sugraph is the vertexes with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
    nMS=grMaxComSu(E,V(:,3)); % the weightd maximal complete sugraph
    fprintf(['Number of vertexes on the weighed maximal complete sugraph '...
      '= %d\n'],length(nMS));
    disp('In a weighed maximal complete sugraph is the vertexes with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
  case 13, % grMaxFlows test
    disp('The grMaxFlows test')
    V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       3 0;3 -1;4 0]; % vertexes coordinates
    E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
       2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
       5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
       9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
    s=1; % the network source
    t=11; % the network sink
    fprintf('The source of the net s=%d\nThe sink of the net t=%d\n',s,t)
    grPlot(V,E,'d','','%d'); % the initial digraph
    title('\bfThe digraph of the net')
    [v,mf]=grMaxFlows(E,s,t); % the maximal flow
    disp('The solution of the maximal flows problem')
    disp('  N arrow       flow')
    fprintf('   %2.0f      %12.8f\n',[[1:length(v)];v'])
    fprintf('The maximal flow =%12.8f\n',mf)
    grPlot(V,[E(:,1:2),v],'d','','%6.4f'); % plot the digraph
    title('\bfThe flows on the arrows')
  case 14, % grMaxMatch test
    disp('The grMaxMatch test')
    V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       3 0;3 -1;4 0]; % vertexes coordinates
    E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
       2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
       5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
       9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
    grPlot(V,E,'g','','%d'); % the initial graph
    title('\bfThe initial graph with weighed edges')
    nMM=grMaxMatch(E(:,1:2)); % the maximal matching
    fprintf('Number of edges on the maximal matching = %d\n',...
      length(nMM));
    disp('In a maximal matching is the edges with numbers:');
    fprintf('%d  ',nMM);
    fprintf('\nThe total weight = %d\n',sum(E(nMM,3)));
    grPlot(V,E(nMM,:),'g','','%d'); % the maximal matching
    title('\bfThe maximal matching')
    nMM=grMaxMatch(E); % the weighed maximal matching
    fprintf('Number of edges on the weighed maximal matching = %d\n',...
      length(nMM));
    disp('In a weighed maximal matching is the edges with numbers:');
    fprintf('%d  ',nMM);
    fprintf('\nThe total weight = %d\n',sum(E(nMM,3)));
    grPlot(V,E(nMM,:),'g','','%d'); % the weighed maximal matching
    title('\bfThe weighed maximal matching')
  case 15, % grMaxStabSet test
    disp('The grMaxStabSet test')
    V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
       3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
    E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;5 6;6 7;...
       5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
    grPlot(V(:,1:2),E,'g','%d',''); % the initial graph
    title('\bfThe initial graph')
    nMS=grMaxStabSet(E); % the maximal stable set
    fprintf('Number of vertexes on the maximal stable set = %d\n',...
      length(nMS));
    disp('In a maximal stable set is the vertexes with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
    grPlot(V,E,'g','%d',''); % the initial graph
    title('\bfThe initial graph with weighed vertexes')
    nMS=grMaxStabSet(E,V(:,3)); % the weightd maximal stable set
    fprintf(['Number of vertexes on the weighed maximal stable set '...
      '= %d\n'],length(nMS));
    disp('In a weighed maximal stable set is the vertexes with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
  case 16, % grMinAbsEdgeSet test
    disp('The grMinAbsEdgeSet test')
    V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       3 0;3 -1;4 0]; % vertexes coordinates
    E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
       2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
       5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 4;...
       9 10 5;8 11 5;9 11 4;10 11 4]; % arrows and weights
    grPlot(V,E,'g','','%d'); % the initial graph
    title('\bfThe initial graph with weighed edges')
    nMS=grMinAbsEdgeSet(E(:,1:2)); % the minimal absorbant set of edges
    fprintf('Number of edges on the minimal absorbant set = %d\n',...
      length(nMS));
    disp('In a minimal absorbant set is the edges with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(E(nMS,3)));
    grPlot(V,E(nMS,:),'g','','%d'); % the minimal absorbant set of edges
    title('\bfThe minimal absorbant set of edges')
    nMS=grMinAbsEdgeSet(E); % the minimal weighed absorbant set of edges
    fprintf('Number of edges on the minimal weighed absorbant set = %d\n',...
      length(nMS));
    disp('In a minimal weighed absorbant set is the edges with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(E(nMS,3)));
    grPlot(V,E(nMS,:),'g','','%d'); % the minimal weighed absorbant set of edges
    title('\bfThe minimal weighed absorbant set of edges')
  case 17, % grMinAbsVerSet test
    disp('The grMinAbsVerSet test')
    V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
       3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
    E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;5 6;6 7;...
       5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
    grPlot(V(:,1:2),E,'g','%d',''); % the initial graph
    title('\bfThe initial graph')
    grPlot(V,E,'g','%d',''); % the initial graph
    title('\bfThe initial graph with weighed vertexes')
    nMS=grMinAbsVerSet(E); % the minimal absorbant set of vertexes
    fprintf('Number of vertexes on the minimal absorbant set = %d\n',...
      length(nMS));
    disp('In a minimal absorbant set is the vertexes with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
    nMS=grMinAbsVerSet(E,V(:,3)); % the weightd minimal absorbant set of vertexes
    fprintf(['Number of vertexes on the weighed minimal absorbant set '...
      '= %d\n'],length(nMS));
    disp('In a weighed minimal absorbant set is the vertexes with numbers:');
    fprintf('%d  ',nMS);
    fprintf('\nThe total weight = %d\n',sum(V(nMS,3)));
  case 18, % grMinCutSet test
    disp('The grMinCutSet test')
    V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       3 0;3 -1;4 0]; % vertexes coordinates
    E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
       2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
       5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
       9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
    s=1; % the network source
    t=11; % the network sink
    fprintf('The source of the net s=%d\nThe sink of the net t=%d\n',s,t)
    grPlot(V,E,'d','','%d'); % the initial digraph
    title('\bfThe digraph of the net')
    [nMCS,mf]=grMinCutSet(E,s,t); % the minimal cut-set
    fprintf('The first minimal cut-set include arrows:');
    fprintf('  %d',nMCS);
    fprintf(['\nThe maximal flow through '...
      'each minimal cut-set = %12.6f\n'],mf)
    grPlot(V,E(setdiff(1:size(E,1),nMCS),:),'d','','%d');
    title('\bfThe digraph without first minimal cut-set')
  case 19, % grMinEdgeCover test
    disp('The grMinEdgeCover test')
    V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       3 0;3 -1;4 0]; % vertexes coordinates and weights
    E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;2 6 2;3 6 5;...
       3 7 2;4 7 3;5 6 1;6 7 1;5 8 5;6 8 2;6 9 3;7 9 2;...
       7 10 3;8 9 2;9 10 2;8 11 5;9 11 4;10 11 4]; % edges and weights
    grPlot(V,E,'g',''); % the initial graph
    title('\bfThe initial graph with weighed edges')
    nMC=grMinEdgeCover(E(:,1:2)); % the minimal edge covering
    fprintf('Number of edges on the minimal edge covering = %d\n',...
      length(nMC));
    disp('In a minimal edge cover is the edges with numbers:');
    fprintf('%d  ',nMC);
    fprintf('\nThe total weight = %d\n',sum(E(nMC,3)));
    grPlot(V,E(nMC,:),'g',''); % the minimal edge covering
    title('\bfThe minimal edge covering')
    nMC=grMinEdgeCover(E); % the weighed minimal edge covering
    fprintf('Number of edges on the weighed minimal edge covering = %d\n',...
      length(nMC));
    disp('In a weighed minimal edge cover is the edges with numbers:');
    fprintf('%d  ',nMC);
    fprintf('\nThe total weight = %d\n',sum(E(nMC,3)));
    grPlot(V,E(nMC,:),'g',''); % the weighed minimal edge covering
    title('\bfThe weighed minimal edge covering')
  case 20, % grMinSpanTree test
    disp('The grMinSpanTree test')
    V=[0 4;1 4;2 4;3 4;4 4;0 3;1 3;2 3;3 3;4 3;...
       0 2;1 2;2 2;3 2;4 2;0 1;1 1;2 1;3 1;4 1;...
       0 0;1 0;2 0;3 0;4 0];
    E=[1 2 1;3 2 2;4 3 3;5 4 4;6 1 5;2 7 6;8 2 7;3 8 8;...
       9 4 9;9 5 8;10 5 7;7 6 6;8 7 5;8 9 4;10 9 3;11 6 2;...
       7 12 1;13 8 2;14 9 3;15 10 4;12 11 5;13 12 6;13 14 7;...
       14 13 8;5 5 10;15 14 9;16 11 8;12 17 7;13 18 6;...
       20 15 5;17 16 4;17 18 3;18 17 2;19 18 1;19 20 2;...
       5 5 8; 21 16 3;17 22 4;18 22 5;22 18 6;18 23 7;...
       19 24 8;20 25 9;21 22 8;22 21 7;23 24 6;10 10 8;...
       24 23 5;24 25 4];
    grPlot(V,E); % the initial graph
    title('\bfThe initial graph with weighed edges')
    nMST=grMinSpanTree(E(:,1:2)); % the spanning tree
    fprintf('Number of edges on the spanning tree = %d\n',length(nMST));
    fprintf('The total weight = %d\n',sum(E(nMST,3)));
    grPlot(V,E(nMST,:)); % the spanning tree
    title('\bfThe spanning tree')
    nMST=grMinSpanTree(E); % the minimal spanning tree
    fprintf('Number of edges on the minimal spanning tree = %d\n',...
      length(nMST));
    fprintf('The total weight = %d\n',sum(E(nMST,3)));
    grPlot(V,E(nMST,:)); % the minimal spanning tree
    title('\bfThe minimal spanning tree')
  case 21, % grMinVerCover test
    disp('The grMinVerCover test')
    V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
       3 0 7;3 -1 1;4 0 5]; % vertexes coordinates and weights
    E=[1 2;1 3;1 4;2 3;3 4;2 5;2 6;3 6;3 7;4 7;6 5;6 7;...
       5 8;6 8;6 9;7 9;7 10;8 9;9 10;8 11;9 11;10 11]; % edges
    grPlot(V,E,'g','%d',''); % the initial graph
    title('\bfThe initial graph with weighed vertexes')
    nMC=grMinVerCover(E); % the minimal vertex cover
    fprintf('Number of vertexes on the minimal vertex cover = %d\n',...
      length(nMC));
    disp('In a minimal vertex cover is the vertexes with numbers:');
    fprintf('%d  ',nMC);
    fprintf('\nThe total weight = %d\n',sum(V(nMC,3)));
    grPlot(V(nMC,:)); % the solution of the MinVerCover problem
    title('\bfThe minimal vertex cover')
    nMC=grMinVerCover(E,V(:,3)); % the weightd minimal vertex cover
    fprintf(['Number of vertexes on the weighed minimal vertex cover '...
      '= %d\n'],length(nMC));
    disp('In a weighed minimal vertex cover is the vertexes with numbers:');
    fprintf('%d  ',nMC);
    fprintf('\nThe total weight = %d\n',sum(V(nMC,3)));
    grPlot(V(nMC,:)); % the solution of the weighed MinVerCover problem
    title('\bfThe weighed minimal vertex cover')
  case 22, % grPERT test
    disp('The grPERT test')
    V=[1 1;0 0;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       4 0;3 -1;3 0]; % events coordinates
    E=[2 1 5;2 3 5;2 4 5;1 3 2;3 4 2;1 5 3;...
       1 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
       5 8 5;6 8 2;6 11 3;7 11 2;7 10 3;8 11 2;...
       11 10 2;8 9 5;11 9 4;10 9 4]; % works and their times
    grPlot(V,E,'d','%d','%d');
    title('\bfThe schema of project')
    [CrP,Ts,Td]=grPERT(E);
    grPlot([V Ts'],[CrP(1:end-1);CrP(2:end)]','d','%d','');
    title('\bfThe critical path and start times for events')
    grPlot([V Ts'],[E(:,1:2) Td],'d','%d','%d')
    title('\bfThe start times for events and delay times for works')
  case 23, % grPlot test
    disp('The grPlot test')
    V=[0 0 2;1 1 3;1 0 3;1 -1 4;2 1 1;2 0 2;2 -1 3;3 1 4;...
       3 0 5;3 -1 1;4 0 5]; % vertexes coordinates and weights
    E=[1 2 5;1 1 2;1 1 5;2 2 3;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;2 6 2;3 6 5;3 7 2;...
       4 7 3;5 6 1;6 7 1;5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
       9 10 2;8 11 5;9 11 4;10 11 4;1 2 8;1 3 4;1 3 5;1 3 6]; % edges (arrows) and weights
    grPlot(V(:,1:2),E,'d');
    title('\bfThe digraph with weighed multiple arrows and loops')
    grPlot(V,E(:,1:2),[],'%d','');
    title('\bfThe graph with weighed vertexes without edges numeration')
    grPlot(V(:,1:2));
    title('\bfThe disconnected graph')
    grPlot([],fullfact([5 5]),'d')
    title('\bfThe directed clique\rm \itK\rm_5')
  case 24, % grShortPath test
    disp('The grShortPath test')
    V=[0 0;1 1;1 0;1 -1;2 1;2 0;2 -1;3 1;...
       3 0;3 -1;4 0]; % vertexes coordinates
    E=[1 2 5;1 3 5;1 4 5;2 3 2;3 4 2;2 5 3;...
       2 6 2;3 6 5;3 7 2;4 7 3;5 6 1;6 7 1;...
       5 8 5;6 8 2;6 9 3;7 9 2;7 10 3;8 9 2;...
       9 10 2;8 11 5;9 11 4;10 11 4]; % arrows and weights
    s=1; % the network source
    t=11; % the network sink
    fprintf('The source of the net s=%d\nThe sink of the net t=%d\n',s,t)
    grPlot(V(:,1:2),E,'d','','%d');
    title('\bfThe digraph with weighed edges')
    [dSP,sp]=grShortPath(E,s,t);
    disp('The shortest paths between all vertexes:');
    fprintf('    %2.0f',1:size(dSP,2));
    fprintf('\n');
    for k1=1:size(dSP,1),
      fprintf('%2.0f',k1)
      fprintf('%6.2f',dSP(k1,:))
      fprintf('\n')
    end
    grPlot(V(:,1:2),[sp(1:end-1);sp(2:end)]','d','%d','')
    title(['\bfThe shortest path from vertex ' ...
      num2str(s) ' to vertex ' num2str(t)])
  case 25, % grTravSale test
    disp('The grTravSale test')
%    C=[0 3 7 4 6 4;4 0 3 7 8 5;6 9 0 3 2 1;...
%       8 6 3 0 9 8;3 7 4 6 0 4;4 5 8 7 2 0];
    C=[0 16827.953945741592 16540.792060841584 ...
      16540.792060841584 16843.983614335415;...
      16827.953945741592 0 1558.8328967532088 ...
      1558.8328967532088 81.59656855530139;...
      16540.792060841584 1558.8328967532088 0 ...
      0 1484.9249139266267;...
      16540.792060841584 1558.8328967532088 0 ...
      0 1484.9249139266267;
      16827.953945741592 81.59656855530139 1484.9249139266267 ...
      1484.9249139266267 0];
    disp('The distances between cities:')
    fprintf('  %18.0f',1:size(C,2))
    fprintf('\n')
    for k1=1:size(C,1),
      fprintf('%2.0f',k1)
      fprintf('%20.12f',C(k1,:))
      fprintf('\n')
    end
    [pTS,fmin]=grTravSale(C);
    disp('The order of cities:')
    fprintf('%d   ',pTS)
    fprintf('\nThe minimal way =%3.0f\n',fmin)
  otherwise,
    error('Select the test')
end