图论软件包（图论里的程序）

% Test program for GrTheory functions % Author: Sergiy Iglin % e-mail: siglin@yandex.ru % personal page: http://iglin.exponenta.ru clear all % select test: % ntest=1 - grBase % ntest=2 - grCoBase % ntest=3 - grCoCycleBasis % ntest=4 - grColEdge % ntest=5 - grColVer % ntest=6 - grComp % ntest=7 - grCycleBasis % ntest=8 - grDecOrd % ntest=9 - grDistances % ntest=10 - grEccentricity % ntest=11 - grIsEulerian % ntest=12 - grMaxComSu % ntest=13 - grMaxFlows % ntest=14 - grMaxMatch % ntest=15 - grMaxStabSet % ntest=16 - grMinAbsEdgeSet % ntest=17 - grMinAbsVerSet % ntest=18 - grMinCutSet % ntest=19 - grMinEdgeCover % ntest=20 - grMinSpanTree % ntest=21 - grMinVerCover % ntest=22 - grPERT % ntest=23 - grPlot % ntest=24 - grShortPath % ntest=25 - grTravSale ntest=23; switch ntest % selected test case 1, % grBase test disp('The grBase test') V=[0 4;4 4;0 0;4 0;8 4;8 0;12 4;12 0;... -2 8;-4 4;0 -4;-4 -4;-4 0]; E=[1 2;3 4;2 4;2 5;4 6;5 6;5 7;6 8;8 7;... 1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11]; grPlot(V,E,'d','%d',''); title('\bfThe initial digraph') BG=grBase(E); disp('The bases of digraph:') disp(' N vertexes') for k1=1:size(BG,1), fprintf('%2.0f ',k1) fprintf('%d ',BG(k1,:)) fprintf('\n') end case 2, % grCoBase test disp('The grCoBase test') V=[0 4;4 4;0 0;4 0;8 4;8 0;12 4;12 0;... -2 8;-4 4;0 -4;-4 -4;-4 0]; E=[2 1;3 4;2 4;2 5;4 6;5 6;5 7;6 8;8 7;... 1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11]; grPlot(V,E,'d','%d',''); title('\bfThe initial digraph') CBG=grCoBase(E); disp('The contrabasis of digraph:') disp(' N vertexes') for k1=1:size(CBG,1), fprintf('%2.0f ',k1) fprintf('%d ',CBG(k1,:)) fprintf('\n') end case 3, % grCoCycleBasis test disp('The grCoCycleBasis 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;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 E=[E [1:size(E,1)]']; % edges with numbers grPlot(V,E,'g','','%d'); % the initial graph title('\bfThe initial graph') CoCycles=grCoCycleBasis(E); % all independences cut-sets for k1=1:size(CoCycles,2), grPlot(V,E(find(~CoCycles(:,k1)),:),'g','','%d'); % one cocycle title(['\bfCocycle N' num2str(k1)]); end case 4, % grColEdge test disp('The grColEdge 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;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,E,'g','','%d'); % the initial graph title('\bfThe initial graph') mCol=grColEdge(E); % the color problem for edges fprintf('The colors of edges\n N edge N col\n'); fprintf(' %2.0f %2.0f\n',[1:length(mCol);mCol']); grPlot(V,[E,mCol],'g','','%d'); % plot the colored graph title('\bfThe graph with colored edges') case 5, % grColVer test disp('The grColVer test') t=[0:4]'; V=[[5*sin(2*pi*t/5) 5*cos(2*pi*t/5)];... [4*sin(2*pi*(t-0.5)/5) 4*cos(2*pi*(t-0.5)/5)];... [2*sin(2*pi*(t-0.5)/5) 2*cos(2*pi*(t-0.5)/5)];[0 0]]; E=[1 7;7 2;2 8;8 3;3 9;9 4;4 10;10 5;5 6;6 1;... 1 10;2 6;3 7;4 8;5 9;1 12;2 13;3 14;4 15;5 11;... 6 14;7 15;8 11;9 12;10 13;... 11 12;12 13;13 14;14 15;15 11;1 16;2 16;3 16;4 16;5 16]; grPlot(V,E,'g','%d',''); % the initial graph title('\bfThe initial graph') nCol=grColVer(E); % the color problem for vertexes fprintf('The colors of vertexes\n N ver N col\n'); fprintf(' %2.0f %2.0f\n',[1:length(nCol);nCol']); grPlot([V,nCol],E,'g','%d',''); % plot the colored graph title('\bfThe graph with colored vertexes') case 6, % grComp test disp('The grComp test') V=[0 4;4 4;0 0;4 0;8 4;8 0;12 4;12 0;... -2 8;-4 4;0 -4;-4 -4;-4 0]; E=[1 2;3 4;2 4;2 5;4 6;5 6;5 7;6 8;8 7;... 1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11]; ncV=grComp(E); grPlot([V ncV],E,'g','%d',''); title(['\bfThis graph have ' num2str(max(ncV)) ' component(s)']) E=[2 4;2 5;4 6;5 6;5 7;6 8;8 7;... 1 9;9 10;10 1;3 11;11 12;12 13;13 3;3 12;13 11]; ncV=grComp(E); grPlot([V ncV],E,'g','%d',''); title(['\bfThis graph have ' num2str(max(ncV)) ' component(s)']) E=[2 4;2 5;4 6;5 6;5 7;6 8;8 7;... 1 9;9 10;10 1;3 11;11 12;3 12]; ncV=grComp(E,size(V,1)); grPlot([V ncV],E,'g','%d',''); title(['\bfThis graph have ' num2str(max(ncV)) ' component(s)']) case 7, % grCycleBasis test disp('The grCycleBasis 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;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,E,'g','%d',''); % the initial graph title('\bfThe initial graph') Cycles=grCycleBasis(E); % all independences cycles for k1=1:size(Cycles,2), grPlot(V,E(find(Cycles(:,k1)),:),'g','%d',''); % one cycle title(['\bfCycle N' num2str(k1)]); end case 8, % grDecOrd test disp('The grDecOrd 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;3 2;4 3;5 4;6 1;2 7;8 2;3 8;9 4;9 5;10 5;7 6;8 7;... 8 9;10 9;11 6;7 12;13 8;14 9;15 10;12 11;13 12;13 14;... 14 13;15 14;16 11;12 17;13 18;20 15;17 16;17 18;18 17;... 19 18;19 20;21 16;17 22;18 22;22 18;18 23;19 24;20 25;... 21 22;22 21;23 24;24 23;24 25]; grPlot(V,E,'d'); title('\bfThe initial digraph') [Dec,Ord]=grDecOrd(E); % solution disp('The classes of mutually connected vertexes:') disp(' N vertexes') for k1=1:size(Dec,2), fprintf('%2.0f ',k1) fprintf('%d ',find(Dec(:,k1))) fprintf('\n') end fprintf('The partial ordering of the classes:\n ') fprintf('%3.0f',1:size(Ord,2)) fprintf('\n') for k1=1:size(Ord,1), % the matrix of partial ordering fprintf('%2.0f ',k1) fprintf(' %1.0f ',Ord(k1,:)) fprintf('\n') end V1=V; for k1=1:size(Dec,2), V1(find(Dec(:,k1)),3)=k1; % weight = number of the class end grPlot(V1,E,'d','%d',''); title('\bfThe classes of mutually connected vertexes') case 9, % grDispances test disp('The grDispances 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 1;... 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]; s=1; % one vertex t=25; % other vertex grPlot(V,E); % the initial graph title('\bfThe initial graph with weighed edges') [dSP,sp]=grDistances(E(:,1:2),s,t); % the nonweighted task fprintf('The steps number between all vertexes:\n ') fprintf('%4.0f',1:size(dSP,2)) fprintf('\n') for k1=1:size(dSP,1), % the matrix of distances fprintf('%3.0f ',k1) fprintf(' %2.0f ',dSP(k1,:)) fprintf('\n') end grPlot(V(:,1:2),[sp(1:end-1);sp(2:end)]','d','%d','') title(['\bfThe shortest way between vertex ' ... num2str(s) ' and vertex ' num2str(t)]) [dSP,sp]=grDistances(E,1,25); % the weighted task fprintf('The distances between all vertexes: