文档视界 最新最全的文档下载
当前位置:文档视界 › (图论)matlab模板程序

(图论)matlab模板程序

(图论)matlab模板程序
(图论)matlab模板程序

第一讲:图论模型

程序一:可达矩阵算法

%根据邻接矩阵A(有向图)求可达矩阵P(有向图)

function P=dgraf(A)

n=size(A,1);

P=A;

for i=2:n

P=P+A^i;

end

P(P~=0)=1; %将不为0的元素变为1

P;

程序二:无向图关联矩阵和邻接矩阵互换算法

F表示所给出的图的相应矩阵

W表示程序运行结束后的结果

f=0表示把邻接矩阵转换为关联矩阵

f=1表示把关联矩阵转换为邻接矩阵

%无向图的关联矩阵和邻接矩阵的相互转换

function W=incandadf(F,f)

if f==0 %邻接矩阵转换为关联矩阵

m=sum(sum(F))/2; %计算图的边数

n=size(F,1);

W=zeros(n,m);

k=1;

for i=1:n

for j=i:n

if F(i,j)~=0

W(i,k)=1; %给边的始点赋值为1

W(j,k)=1; %给边的终点赋值为1

k=k+1;

end

end

end

elseif f==1 %关联矩阵转换为邻接矩阵

m=size(F,2);

n=size(F,1);

W=zeros(n,n);

for i=1:m

a=find(F(:,i)~=0);

W(a(1),a(2))=1; %存在边,则邻接矩阵的对应值为1 W(a(2),a(1))=1;

end

else

fprint('Please imput the right value of f'); end

W;

程序三:有向图关联矩阵和邻接矩阵互换算法

%有向图的关联矩阵和邻接矩阵的转换

function W=mattransf(F,f)

if f==0 %邻接矩阵转换为关联矩阵

m=sum(sum(F));

n=size(F,1);

W=zeros(n,m);

k=1;

for i=1:n

for j=i:n

if F(i,j)~=0 %由i发出的边,有向边的始点 W(i,k)=1; %关联矩阵始点值为1

W(j,k)=-1; %关联矩阵终点值为-1

k=k+1;

end

end

end

elseif f==1 %关联矩阵转换为邻接矩阵

m=size(F,2);

n=size(F,1);

W=zeros(n,n);

for i=1:m

a=find(F(:,i)~=0); %有向边的两个顶点

if F(a(1),i)==1

W(a(1),a(2))=1; %有向边由a(1)指向a(2) else

W(a(2),a(1))=1; %有向边由a(2)指向a(1) end

end

else

fprint('Please imput the right value of f'); end

W;

第二讲:最短路问题

程序0:最短距离矩阵

W表示图的权值矩阵

D表示图的最短距离矩阵

%连通图中各项顶点间最短距离的计算

function D=shortdf(W)

%对于W(i,j),若两顶点间存在弧,则为弧的权值,否则为inf;当i=j时W(i,j)=0 n=length(W);

D=W;

m=1;

while m<=n

for i=1:n

for j=1:n

if D(i,j)>D(i,m)+D(m,j)

D(i,j)+ D(i,m)+D(m,j); %距离进行更新

end

end

end

m=m+1;

end

D;

程序一:Dijkstra算法(计算两点间的最短路)

function [l,z]=Dijkstra(W)

n = size (W,1);

for i = 1 :n

l(i)=W(1,i);

z(i)=0;

end

i=1;

while i<=n

for j =1 :n

if l(i)>l(j)+W(j,i)

l(i)=l(j)+W(j,i);

z(i)=j-1;

if j

i=j-1;

end

end

end

i=i+1;

end

程序二:floyd算法(计算任意两点间的最短距离)function [d,r]=floyd(a)

n=size(a,1);

d=a;

for i=1:n

for j=1:n

r(i,j)=j;

end

end

r;

for k=1:n

for i=1:n

for j=1:n

if d(i,k)+d(k,j)

end

end

end

end

程序三:n2short.m 计算指定两点间的最短距离

function [P u]=n2short(W,k1,k2)

n=length(W);

U=W;

m=1;

while m<=n

for i=1:n

for j=1:n

if U(i,j)>U(i,m)+U(m,j)

U(i,j)=U(i,m)+U(m,j);

end

end

end

m=m+1;

end

u=U(k1,k2);

P1=zeros(1,n);

k=1;

P1(k)=k2;

V=ones(1,n)*inf;

kk=k2;

while kk~=k1

for i=1:n

V(1,i)=U(k1,kk)-W(i,kk);

if V(1,i)==U(k1,i)

P1(k+1)=i;

kk=i;

k=k+1;

end

end

end

k=1;

wrow=find(P1~=0);

for j=length(wrow):-1:1

P(k)=P1(wrow(j));

k=k+1;

end

P;

程序四、n1short.m(计算某点到其它所有点的最短距离) function[Pm D]=n1short(W,k)

n=size(W,1);

D=zeros(1,n);

for i=1:n

[P d]=n2short(W,k,i);

Pm{i}=P;

D(i)=d;

end

程序五:pass2short.m(计算经过某两点的最短距离) function [P d]=pass2short(W,k1,k2,t1,t2) [p1 d1]=n2short(W,k1,t1);

[p2 d2]=n2short(W,t1,t2);

[p3 d3]=n2short(W,t2,k2);

dt1=d1+d2+d3;

[p4 d4]=n2short(W,k1,t2);

[p5 d5]=n2short(W,t2,t1);

[p6 d6]=n2short(W,t1,k2);

dt2=d4+d5+d6;

if dt1

d=dt1;

P=[p1 p2(2:length(p2)) p3(2:length(p3))]; else

d=dt1;

p=[p4 p5(2:length(p5)) p6(2:length(p6))]; end

P;

d;

第三讲:最小生成树

程序一:最小生成树的Kruskal算法

function [T c]=krusf(d,flag)

if nargin==1

n=size(d,2);

m=sum(sum(d~=0))/2;

b=zeros(3,m);

k=1;

for i=1:n

for j=(i+1):n

if d(i,j)~=0

b(1,k)=i;b(2,k)=j;

b(3,k)=d(i,j);

k=k+1;

end

end

end

else

b=d;

end

n=max(max(b(1:2,:)));

m=size(b,2);

[B,i]=sortrows(b',3);

B=B';

c=0;T=[];

k=1;t=1:n;

for i=1:m

if t(B(1,i))~=t(B(2,i))

T(1:2,k)=B(1:2,i);

c=c+B(3,i);

k=k+1;

tmin=min(t(B(1,i)),t(B(2,i))); tmax=max(t(B(1,i)),t(B(2,i)));

for j=1:n

if t(j)==tmax

t(j)=tmin;

end

end

end

if k==n

break;

end

end

T;

c;

程序二:最小生成树的Prim算法

function [T c]=Primf(a)

l=length(a);

a(a==0)=inf;

k=1:l;

listV(k)=0;

listV(1)=1;

e=1;

while (e

min=inf;

for i=1:l

if listV(i)==1

for j=1:l

if listV(j)==0 & min>a(i,j)

min=a(i,j);b=a(i,j);

s=i;d=j;

end

end

end

end

listV(d)=1;

distance(e)=b;

source(e)=s;

destination(e)=d;

e=e+1;

end

T=[source;destination];

for g=1:e-1

c(g)=a(T(1,g),T(2,g));

end

c;

第四讲:Euler图和Hamilton图程序一:Fleury算法(在一个Euler图中找出Euler环游)

注:包括三个文件;fleuf1.m, edf.m, flecvexf.m

function [T c]=fleuf1(d)

%注:必须保证是Euler环游,否则输出T=0,c=0

n=length(d);

b=d;

b(b==inf)=0;

b(b~=0)=1;

m=0;

a=sum(b);

eds=sum(a)/2;

ed=zeros(2,eds);

vexs=zeros(1,eds+1);

matr=b;

for i=1:n

if mod(a(i),2)==1

m=m+1;

end

end

if m~=0

fprintf('there is not exit Euler path.\n') T=0;c=0;

end

if m==0

vet=1;

flag=0;

t1=find(matr(vet,:)==1);

for ii=1:length(t1)

ed(:,1)=[vet,t1(ii)];

vexs(1,1)=vet;vexs(1,2)=t1(ii);

matr(vexs(1,2),vexs(1,1))=0;

flagg=1;tem=1;

while flagg

[flagg ed]=edf(matr,eds,vexs,ed,tem); tem=tem+1;

if ed(1,eds)~=0 & ed(2,eds)~=0

T=ed;

T(2,eds)=1;

c=0;

for g=1:eds

c=c+d(T(1,g),T(2,g));

end

flagg=0;

break;

end

end

end

end

function[flag ed]=edf(matr,eds,vexs,ed,tem)

flag=1;

for i=2:eds

[dvex f]=flecvexf(matr,i,vexs,eds,ed,tem);

if f==1

flag=0;

break;

end

if dvex~=0

ed(:,i)=[vexs(1,i) dvex];

vexs(1,i+1)=dvex;

matr(vexs(1,i+1),vexs(1,i))=0;

else

break;

end

end

function [dvex f]=flecvexf(matr,i,vexs,eds,ed,temp) f=0;

edd=find(matr(vexs(1,i),:)==1);

dvex=0;

dvex1=[];

ded=[];

if length(edd)==1

dvex=edd;

else

dd=1;dd1=0;kkk=0;

for kk=1:length(edd)

m1=find(vexs==edd(kk));

if sum(m1)==0

dvex1(dd)=edd(kk);

dd=dd+1;

dd1=1;

else

kkk=kkk+1;

end

end

if kkk==length(edd)

tem=vexs(1,i)*ones(1,kkk);

edd1=[tem;edd];

for l1=1:kkk

lt=0;ddd=1;

for l2=1:eds

if edd1(1:2,l1)==ed(1:2,l2)

lt=lt+1;

end

end

if lt==0

ded(ddd)=edd(l1);

ddd=ddd+1;

end

end

end

if temp<=length(dvex1)

dvex=dvex1(temp);

elseif temp>length(dvex1) & temp<=length(ded)

dvex=ded(temp);

else

f=1;

end

end

程序二:Hamilton改良圈算法(找出比较好的Hamilton路)

function [C d1]= hamiltonglf(v)

%d表示权值矩阵

%C表示算法最终找到的Hamilton圈。

%v =[ 51 67;37 84;41 94;2 99;18 54;4 50;24 42;25 38;13 40;7 64;22 60;25 62;18 40;41 26];

n=size(v,1);

subplot(1,2,1)

hold on;

plot (v(:,1),v(:,2),'*'); %描点

for i=1:n

str1='V';str2=num2str(i);

dot=[str1,str2];

text(v(i,1)-1,v(i,2)-2,dot); %给点命名

end

plot (v(:,1),v(:,2));%连线

plot([v(n,1),v(1,1)],[v(n,2),v(1,2)]);

for i =1:n

for j=1:n

d(i,j)=sqrt((v(i,1)-v(j,1))^2+(v(i,2)-v(j,2))^2);

end

end

d2=0;

for i=1:n

if i

d2=d2+d(i,i+1);

else

d2=d2+d(n,1);

end

end

text(10,30,num2str(d2));

n=size(d,2);

C=[linspace(1,n,n) 1];

for nnn=1:20

C1=C;

if n>3

for m=4:n+1

for i=1:(m-3)

for j=(i+2):(m-1)

if

(d(C(i),C(j))+d(C(i+1),C(j+1))

for k=(i+1):j

C1(k)=C(j+i+1-k);

end

C1((j+1):m)=C((j+1):m);

end

end

end

end

elseif n<=3

if n<=2

fprint('It does not exist Hamilton circle.');

else

fprint('Any cirlce is the right answer.');

end

end

C=C1;

d1=0;

for i=1:n

d1=d1+d(C(i),C(i+1));

end

d1;

end

subplot(1,2,2);

hold on;

plot (v(:,1),v(:,2),'*'); %描点

for i=1:n

str1='V';str2=num2str(i);

dot=[str1,str2];

text(v(i,1)-1,v(i,2)-2,dot); %给点命名

end

v2=[v;v(1,1),v(1,2)];

plot(v(C(:),1),v(C(:),2),'r');

text(10,30,num2str(d1));

第五讲:匹配问题及算法

程序一:较大基础匹配算法

function J=matgraf(W)

n=size(W,1);

J=zeros(n,n);

while sum(sum(W))~=0

a=find(W~=0);

t1=mod(a(1),n);

if t1==0

t1=n;

end

if a(1)/n>floor(a(1)/n)

t2=floor(a(1)/n)+1;

else

t2=floor(a(1)/n);

end

J(t1,t2)=1,J(t2,t1)=1;

W(t1,:)=0;W(t2,:)=0;

W(:,t1)=0;W(:,t2)=0;

end

J;

程序二:匈牙利算法(完美匹配算法,包括三个文件fc01,fc02,fc03)function [e,s]=fc01(a,flag)

if nargin==1

flag=0;

end

b=a;

if flag==0

cmax=max(max(b)');

b=cmax-b;

end

m=size(b);

for i =1:m(1)

b(i,:)=b(i,:)-min(b(i,:));

end

for j=1:m(2)

b(:,j)=b(:,j)-min(b(:,j));

end

d=(b==0);

[e,total]=fc02(d);

while total~=m(1)

b=fc03(b,e);

d=(b==0);

[e,total]=fc02(d);

end

inx=sub2ind(size(a),e(:,1),e(:,2)); e=[e,a(inx)];

s=sum(a(inx));

function [e,total]=fc02(d)

total=0;m=size(d);

e=zeros(m(1),2);

t=sum(sum(d)');

nump=sum(d');

while t~=0

[s,inp]=sort(nump);

inq=find(s);

ep=inp(inq(1));

inp=find(d(ep,:));

numq=sum(d(:,inp));

[s,inq]=sort(numq);

eq=inp(inq(1));

total=total+1;

e(total,:)=[ep,eq];

inp=find(d(:,eq));

nump(inp)=nump(inp)-1;

nump(ep)=0;

t=t-sum(d(ep,:))-sum(d(:,eq))+1; d(ep,:)=0*d(ep,:);

d(:,eq)=0*d(:,eq);

end

function b=fc03(b,e)

m=size(b);t=1;

p=ones(m(1),1);

q=zeros(m(1),1);

inp=find(e(:,1)~=0);

p(e(inp,1))=0;

while t~=0

tp=sum(p+q);

inp=find(p==1);

n=size(inp);

for i=1:n(1)

inq=find(b(inp(i),:)==0);

q(inq)=1;

end

inp=find(q==1);

n=size(inp);

for i=1:n(1)

if all(e(:,2)-inp(i))==0

inq=find((e(:,2)-inp(i))==0); p(e(inq))=1;

end

end

tq=sum(p+q);

t=tq-tp;

end

inp=find(p==1);

inq=find(q==0);

cmin=min(min(b(inp,inq))');

inq=find(q==1);

b(inp,:)=b(inp,:)-cmin;

b(:,inq)=b(:,inq)+cmin;

第六讲:最大流最小费用问题

程序一:2F算法(Ford-Fulkerson算法),求最大流

%C=[0 5 4 3 0 0 0 0;0 0 0 0 5 3 0 0;0 0 0 0 0 3 2 0;0 0 0 0 0 0 2 0; %0 0 0 0 0 0 0 4;0 0 0 0 0 0 0 3;0 0 0 0 0 0 0 5;0 0 0 0 0 0 0 0 ] function [f wf]=fulkersonf(C,f1)

%C表示容量

%f1表示当前流量,默认为0

%f表示最大流±íê?×?′óá÷

%wf表示最大流的流量

n=length(C);

if nargin==1;

f=zeros(n,n);

else

f=f1;

end

No=zeros(1,n);

d=zeros(1,n);

while (1)

No(1)=n+1;

d(1)=Inf;

while (1)

pd=1;

for (i=1:n)

if (No(i))

for (j=1:n)

if (No(j)==0 & f(i,j)

No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;

if (d(j)>d(i))

d(j)=d(i);

end

elseif (No(j)==0 & f(j,i)>0)

No(j)=-i;d(j)=f(j,i);pd=0;

if (d(j)>d(i))

d(j)=d(i);

end

end

end

end

end

if (No(n)|pd)

break;

end

end

if (pd)

break;

end

dvt=d(n);t=n;

while (1)

if(No(t)>0)

f(No(t),t)=f(No(t),t)+dvt;

elseif (No(t)<0)

f(No(t),t)=f(No(t),t)-dvt;

end

if (No(t)==1)

for (i=1:n)

No(i)=0;d(i)=0;

end

break

end

t=No(t);

end

end

wf=0;

for (j=1:n)

wf=wf+f(1,j);

end

f;

wf;

程序二:Busacker-Gowan算法(求最大流最小费用)

%C=[0 15 16 0 0;0 0 0 13 14;0 11 0 17 0;0 0 0 0 8;0 0 0 0 0] %b=[0 4 1 0 0;0 0 0 6 1;0 2 0 3 0;0 0 0 0 2;0 0 0 0 0]

%function [f wf zwf]=BGf(C,b)

%C表示弧容量矩阵

%b表示弧上单位流量的费用

%f表示最大流最小费用矩阵

%wf最大流量

%zwf表示最小费用

n=size(C,2);

wf=0;wf0=inf;

f=zeros(n,n);

while (1)

a=ones(n,n)*inf;

for (i=1:n)

a(i,i)=0;

end

for (i=1:n)

for (j=1:n)

if(C(i,j)>0 & f(i,j)==0)

a(i,j)=b(i,j);

elseif (C(i,j)>0 & f(i,j)==C(i,j)) a(j,i)=-b(i,j);

elseif (C(i,j)>0)

a(i,j)=b(i,j);

a(j,i)=-b(i,j);

end

end

end

for (i=2:n)

p(i)=inf;s(i)=i;

end

for (k=1:n)

pd=1;

for (i=2:n)

for (j=1:n)

if (p(i)>p(j)+a(j,i))

p(i)=p(j)+a(j,i);s(i)=j;pd=0;

end

end

end

if (pd)

break;

end

end

if (p(n)==inf)

break;

end

dvt=inf;t=n;

while (1)

if (a(s(t),t)>0)

dvtt=C(s(t),t)-f(s(t),t);

elseif (a(s(t),t)<0)

dvtt=f(t,s(t));

end

if (dvt>dvtt)

dvt=dvtt;

end

if (s(t)==1)

break;

end

t=s(t);

end

pd=0;

if (wf+dvt>=wf0)

dvt=wf0-wf;pd=1;

end

t=n;

while (1)

if (a(s(t),t)>0)

f(s(t),t)=f(s(t),t)+dvt;

elseif (a(s(t),t)<0)

f((t),s(t))=f(t,s(t))-dvt;

end

if (s(t)==1)

break;

end

t=s(t);

end

if (pd)

break;

end

wf=0;

for (j=1:n)

wf=wf+f(1,j);

end

end

zwf=0;

for (i=1:n)

for (j=1:n)

zwf=zwf+b(i,j)*f(i,j);

end

end f;

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法: 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j <d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii <0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解:用Warshall-Floyd 算法,MATLAB 程序代码如下: n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)

(图论)matlab模板程序

(图论)matlab模板程序

第一讲:图论模型 程序一:可达矩阵算法 %根据邻接矩阵A(有向图)求可达矩阵P(有向图) function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; %将不为0的元素变为1 P; 程序二:无向图关联矩阵和邻接矩阵互换算法F表示所给出的图的相应矩阵 W表示程序运行结束后的结果 f=0表示把邻接矩阵转换为关联矩阵 f=1表示把关联矩阵转换为邻接矩阵 %无向图的关联矩阵和邻接矩阵的相互转换 function W=incandadf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F))/2; %计算图的边数 n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; %给边的始点赋值为1 W(j,k)=1; %给边的终点赋值为1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; %存在边,则邻接矩阵的对应值为1 W(a(2),a(1))=1;

end else fprint('Please imput the right value of f'); end W; 程序三:有向图关联矩阵和邻接矩阵互换算法 %有向图的关联矩阵和邻接矩阵的转换 function W=mattransf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 %由i发出的边,有向边的始点 W(i,k)=1; %关联矩阵始点值为1 W(j,k)=-1; %关联矩阵终点值为-1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); %有向边的两个顶点 if F(a(1),i)==1 W(a(1),a(2))=1; %有向边由a(1)指向a(2) else W(a(2),a(1))=1; %有向边由a(2)指向a(1) end end else fprint('Please imput the right value of f'); end W;

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是,设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点,记()l v 为顶点 v 到源点v 1的最短距离, ,i j v v V ?∈,若 (,)i j v v E ?,记i v 到j v 的权ij w =∞。 Dijkstra 算法: ① 1{}S v =,1()0l v =;1{}v V v ??-,()l v =∞,1i =,1{}S V v =-; ② S φ=,停止,否则转③; ③ ()min{(),(,)} j l v l v d v v =, j v S ∈,v S ?∈; ④ 存在 1 i v +,使 1()min{()} i l v l v +=,v S ∈; ⑤ 1{} i S S v +=, 1{} i S S v +=-,1i i =+,转②; 实际上,Dijkstra 算法也是最优化原理的应用:如果12 1n n v v v v -是从1v 到 n v 的最短路径,则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中,我们用到了距离矩阵,矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ,若i v 到j v 无边,则realmax ij w =,其中realmax 是 MATLAB 常量,表示最大的实数+308)。 function re=Dijkstra(ma)

图论与网络优化课程设计_Matlab实现

图论与网络优化课程设计 四种基本网络(NCN、ER、WS、BA) 的构造及其性质比较 摘要:网络科学中被广泛研究的基本网络主要有四种,即:规则网络之最近邻耦合网络(Nearest-neighbor coupled network),本文中简称NCN;ER随机网络G(N,p);WS小世界网络;BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件,计算各种规模下(例如不同节点数、不同重连概率或者连边概率)各自的网络属性(包括边数、度分布、平均路径长度、聚类系数),给出图、表和图示,并进行比较和分析。 关键字:最近邻耦合网络;ER随机网络;WS小世界网络;BA无标度网络;Matlab;NodeXL。

四种基本网络(NCN、ER、WS、BA) 的构造及其性质比较 1.概述 1.网络科学的概述 网络科学(Network Science)是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学,研究涉及到复杂网络的各种拓扑结构及其性质,与动力学特性(或功能)之间相互关系,包括时空斑图的涌现、动力学同步及其产生机制,网络上各种动力学行为和信息的传播、预测(搜索)与控制,以及工程实际所需的网络设计原理及其应用研究,其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种,即:规则网络之最近邻耦合网络(Nearest-neighbor coupled network),本文中简称NCN;ER随机网络G(N,p);WS小世界网络;BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下(例如不同节点数、不同重连概率或者连边概率)各自的网络属性(包括边数、度分布、平均路径长度、聚类系数),给出图、表和图示,并进行比较和分析。 2.最近邻耦合网络的概述 如果在一个网络中,每一个节点只和它周围的邻居节点相连,那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。 常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点,其中每K个邻居节点相连,这里K是一个偶数。这类网络的一个重要特征个节点都与它左右各/2 就是网络的拓扑结构是由节点之间的相对位置决定的,随着节点位置的变化网络拓扑结构也可能发生切换。 NCN的Matlab实现: %function b = ncn(N,K) %此函数生成一个有N个节点,每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵 function b = ncn(N,K) b=zeros(N); for i = 1:N for j = (i+1):(i+K/2) if j<=N b(i,j)=1; b(j,i)=1; else b(i,j-N)=1;

(完整版)数字图像处理MATLAB程序【完整版】

第一部分数字图像处理

实验一图像的点运算 实验1.1 直方图 一.实验目的 1.熟悉matlab图像处理工具箱及直方图函数的使用; 2.理解和掌握直方图原理和方法; 二.实验设备 1.PC机一台; 2.软件matlab。 三.程序设计 在matlab环境中,程序首先读取图像,然后调用直方图函数,设置相关参数,再输出处理后的图像。 I=imread('cameraman.tif');%读取图像 subplot(1,2,1),imshow(I) %输出图像 title('原始图像') %在原始图像中加标题 subplot(1,2,2),imhist(I) %输出原图直方图 title('原始图像直方图') %在原图直方图上加标题 四.实验步骤 1. 启动matlab 双击桌面matlab图标启动matlab环境; 2. 在matlab命令窗口中输入相应程序。书写程序时,首先读取图像,一般调用matlab自带的图像, 如:cameraman图像;再调用相应的直方图函数,设置参数;最后输出处理后的图像; 3.浏览源程序并理解含义; 4.运行,观察显示结果; 5.结束运行,退出; 五.实验结果 观察图像matlab环境下的直方图分布。 (a)原始图像 (b)原始图像直方图 六.实验报告要求 1、给出实验原理过程及实现代码; 2、输入一幅灰度图像,给出其灰度直方图结果,并进行灰度直方图分布原理分析。

实验1.2 灰度均衡 一.实验目的 1.熟悉matlab图像处理工具箱中灰度均衡函数的使用; 2.理解和掌握灰度均衡原理和实现方法; 二.实验设备 1.PC机一台; 2.软件matlab; 三.程序设计 在matlab环境中,程序首先读取图像,然后调用灰度均衡函数,设置相关参数,再输出处理后的图像。 I=imread('cameraman.tif');%读取图像 subplot(2,2,1),imshow(I) %输出图像 title('原始图像') %在原始图像中加标题 subplot(2,2,3),imhist(I) %输出原图直方图 title('原始图像直方图') %在原图直方图上加标题 a=histeq(I,256); %直方图均衡化,灰度级为256 subplot(2,2,2),imshow(a) %输出均衡化后图像 title('均衡化后图像') %在均衡化后图像中加标题 subplot(2,2,4),imhist(a) %输出均衡化后直方图 title('均衡化后图像直方图') %在均衡化后直方图上加标题 四.实验步骤 1. 启动matlab 双击桌面matlab图标启动matlab环境; 2. 在matlab命令窗口中输入相应程序。书写程序时,首先读取图像,一般调用matlab自带的图像, 如:cameraman图像;再调用相应的灰度均衡函数,设置参数;最后输出处理后的图像; 3.浏览源程序并理解含义; 4.运行,观察显示结果; 5.结束运行,退出; 五.实验结果 观察matlab环境下图像灰度均衡结果及直方图分布。 (a)原始图像 (b)均衡化后图像

多目标优化实例和matlab程序

NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ,该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1. 适应值函数m 文件: function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2. 调用gamultiobj 函数,及参数设置: clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations',200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3;种群大小populationsize 为100,最大进化代数generations 为200, % 停止代数stallGenLimit 为200, 适应度函数偏差TolFun 设为1e-100,函数gaplotpareto :绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)

matlab图论程序算法大全

精心整理 图论算法matlab实现 求最小费用最大流算法的 MATLAB 程序代码如下: n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路

for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是,设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点,记()l v 为顶点 v 到源点v 1的最短距离, ,i j v v V ?∈,若 (,)i j v v E ?,记i v 到 j v 的权 ij w =∞ 。 Dijkstra 算法: ① 1{}S v =,1()0l v =;1{}v V v ??-,()l v =∞,1i =,1{}S V v =-; ② S φ=,停止,否则转③; ③ ()min{(),(,)} j l v l v d v v =, j v S ∈,v S ?∈; ④ 存在1i v +,使1()min{()}i l v l v +=,v S ∈; ⑤ 1{}i S S v += ,1{}i S S v +=-,1i i =+,转②; 实际上,Dijkstra 算法也是最优化原理的应用:如果121n n v v v v - 是从1v 到n v 的最短路径,则121n v v v - 也必然是从1v 到1n v -的最优路径。 在下面的MATLAB 实现代码中,我们用到了距离矩阵,矩阵第i 行第j 行元素表示顶点i v 到 j v 的权 ij w ,若i v 到 j v 无边,则 realmax ij w =,其中realmax 是 MATLAB 常量,表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma)

图论算法及其MATLAB程序代码

图论算法及其MATLAB程序代码 求赋权图G = (V, E , F )中任意两点间的最短路的Warshall-Floyd算法: 设A = (a ij )n×n为赋权图G = (V, E , F )的矩阵, 当v i v j∈E时a ij= F (v i v j), 否则取a ii=0, a ij = +∞(i≠j ), d ij表示从v i到v j点的距离, r ij表示从v i到v j点的最短路中一个点的编号. ①赋初值. 对所有i, j, d ij = a ij, r ij = j. k = 1. 转向② ②更新d ij, r ij . 对所有i, j, 若d ik + d k j<d ij, 则令d ij = d ik + d k j, r ij = k, 转向③. ③终止判断. 若d ii<0, 则存在一条含有顶点v i的负回路, 终止; 或者k = n终止; 否则令k = k + 1, 转向②. 最短路线可由r ij得到. 例1求图6-4中任意两点间的最短路. 图6-4 解:用Warshall-Floyd算法, MA TLAB程序代码如下: n=8;A=[0 2 8 1 Inf Inf Inf Inf 2 0 6 Inf 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0]; % MATLAB中, Inf表示∞ D=A; %赋初值 for(i=1:n)for(j=1:n)R(i,j)=j;end;end%赋路径初值 for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)

图论举例MATLAB

例1 某公司在六个城市621,,,c c c 中有分公司,从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。(∞表示无直接航路),请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ? ? ??? ? ? ? ? ?????????∞∞∞∞∞∞ 055252510550102025251001020402010015252015050102540500 用矩阵n n a ?(n 为顶点个数)存放各边权的邻接矩阵,行向量pb 、1index 、2index 、 d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ?? ?=顶点未标号 当第顶点已标号 当第i i i pb 01)(; )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号; )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的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); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)=2

图论matlab程序

第一讲:图论模型 程序一:可达矩阵算法 function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P; 程序二:关联矩阵和邻接矩阵互换算法 function W=incandadf(F,f) if f==0 m=sum(sum(F))/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W;

程序三:有向图关联矩阵和邻接矩阵互换算法 function W=mattransf(F,f) if f==0 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=-1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); if F(a(1),i)==1 W(a(1),a(2))=1; else W(a(2),a(1))=1; end end else fprint('Please imput the right value of f'); end W;

超全图论matlab程序

超全的图论程序 关注微信公众号“超级数学建模”,教你做有料、有趣的数模人 程序一:可达矩阵算法 function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P; 程序二:关联矩阵和邻接矩阵互换算法 function W=incandadf(F,f) if f==0 m=sum(sum(F))/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W;

程序三:有向图关联矩阵和邻接矩阵互换算法 function W=mattransf(F,f) if f==0 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=-1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); if F(a(1),i)==1 W(a(1),a(2))=1; else W(a(2),a(1))=1; end end else fprint('Please imput the right value of f'); end W;

图论最短路MATLAB程序

最短路法MATLAB 程序 例1: 某公司在六个城市621,,,c c c 中有分公司,从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。(∞表示无直接航路),请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ??????????????????∞∞∞∞∞∞ 05525251055010202525100102040 2010015252015050102540500 用矩阵n n a ?(n 为顶点个数)存放各边权的邻接矩阵,行向量pb 、1index 、 2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ??=顶点未标号当第顶点已标号当第i i i pb 01)(; )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号; )(i d 存放由始点到第i 点最短通路的值。 求第一个城市到其它城市的最短路径的Matlab 程序如下: 程序一: clc,clear

a=zeros(6); %邻接矩阵初始化 a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; %将矩阵数据对称赋予矩阵 a(find(a==0))=inf; %找到0值并赋值为inf pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0; temp=1; %最新的P标号的顶点 while sum(pb)

图论matlab程序大全

图论程序大全 程序一:可达矩阵算法 function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P; 程序二:关联矩阵和邻接矩阵互换算法function W=incandadf(F,f) if f==0 m=sum(sum(F))/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=1;

k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W; 程序三:有向图关联矩阵和邻接矩阵互换算法 function W=mattransf(F,f) if f==0

m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=-1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); if F(a(1),i)==1 W(a(1),a(2))=1; else

(完整word版)图论算法及matlab程序的三个案例.docx

图论实验三个案例 单源最短路径问题 1.1 Dijkstra算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是,设置一个顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且 仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点,记l (v) 为顶点 v 到源点 v1的最短距离,v i ,v j V ,若 (v i , v j ) E ,记 v i到 v j的权 w ij。 Dijkstra算法: ①S{ v 1 } , l (v 1 ) 0 ; v V { v 1 } , l (v) , i 1,S V { v1}; ②S ,停止,否则转③; ③l (v) min{ l (v), d (v j , v)} , v j S ,v S ; ④存在v i 1,使l (v i 1) min{ l (v)},v S; ⑤S S U { v i 1 } , S S { v i 1 } ,i i 1,转②; 实际上,Dijkstra算法也是最优化原理的应用:如果v 1 v 2 L v n 1 v n是从 v 1 到 v n的最 短路径,则v 1 v 2 L v n 1也必然是从 v 1 到 v n 1的最优路径。 实现代码中,我们用到了距离矩阵,矩阵第i 行第 j 行元 在下面的 MATLAB 素表示顶点v i 到 v j的权 w ij,若 v i 到 v j无边,则 w ij realmax ,其中 realmax 是 MATLAB常量,表示最大的实数 (1.7977e+308) 。 function re=Dijkstra(ma)

图论程序算法大全

图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下: n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1) for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;en d if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量 if(dvt>dvtt)dvt=dvtt;end if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量 t=s(t);end %继续调整前一段弧上的流f pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值 t=n;while(1) %调整过程 if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整 elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整 if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程

图论算法及其Matlab程序

求单源最短路径的Dijkstra算法的Matlab程序 function [d index1 index2]=Dijkf(a) M=max(max(a)); pb(1:length(a))=0; pb(1)=1; index1=1; index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)=2 index=index(1); end index2(temp)=index; end d; index1; index2; 求任意两点间最短路的Floyd算法的Matlab程序 function [D,R]=floyd(a) n=size(a,1); D=a; for i=1:n for j=1:n R(i,j)=j; end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)

end end end D;R ; 求Euler回路的Fleury算法的Matlab程序function [eu,cEu]=arEuler(E) eu=0; cEu=[]; ncV=arComp(E); if max(ncV)>1 return end n=max(max(E(:,1:2))); m=size(E,1); for i=1:n b(i)=0; for j=1:m if E(j,1)==i|E(j,2)==i b(i)=b(i)+1; end end end rp=rem(b,2); srp=sum(rp); switch srp case 0, eu=1; case 2, eu=0.5; otherwise, return end if srp==0 v1=1; else v1=find(rp); v1=v1(1); end vc=v1; m=size(E,1); E1=[E(:,1:2),[1:m]'];

常用离散信号MATLAB程序及波形

常用离散信号MATLAB 表示 单位抽样序列 n=-10:10; x=[n==0]; stem(n,x); title('单位抽样信号'); xlabel('n');ylabel('x');grid on ; -10 -8 -6 -4 -2 02 4 6 8 10 00.10.20.30.40.50.60.70.80.91单位抽样信号 n x 延迟k=4个单位后的图像为: -10 -8 -6 -4 -2 02 4 6 8 10 00.10.20.30.40.50.60.70.80.91单位抽样信号 n x

单位阶跃信号 n=-5:10; x=[zeros(1,5),ones(1,11)]; stem(n,x,'m','p'); axis([-5,10,-0.5,1.5]); title('单位阶跃信号'); xlabel('n');ylabel('幅度') grid on ; -5 510 -0.50 0.5 1 1.5 单位阶跃信号 n 幅度 矩形序列 n=-5:15; x=[zeros(1,5),ones(1,11),zeros(1,5)]; stem(n,x,'r','h') axis([-5,15,-0.5,1.5]); title('矩形序列'); xlabel('时间');ylabel('幅度') grid on ;

-5 51015 -0.50 0.5 1 1.5 矩形序列 时间 幅度 正弦序列 n=-5:0.1:5; xn=2*sin(0.5*pi*n+pi/3); stem(n,xn) axis([-5,5,-3,3]); title('正弦序列'); xlabel('时间');ylabel('幅度'); grid on ; -5 -4-3-2-1 012345 -3-2 -1 1 2 3 正弦序列 时间 幅度

用matlab实现寻找最短路

用matlab寻找赋权图中的最短路中的应用 1引言 图论是应用数学的一个分支,它的概念和结果来源都非常广泛,最早起源于一些数学游戏的难题研究,如欧拉所解决的格尼斯堡七桥问题,以及在民间广泛流传的一些游戏的难题,如迷宫问题,博弈问题等。这些古老的难题,吸引了很多学者的注意。 1847年,图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的问题时,发挥出很大的作用。在实践中,图论已成为解决自然科学,工程技术,社会科学,军事等领域中许多问题的有力工具之一。 最短路问题是图论理论中的经典问题,寻找最短路径就是在指定网络中两节点间找一条距离最小的路。 2 最短路 2.1 最短路的定义(short-path problem) 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能ij 够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生 w≥的情况下选择Dijkstra算法。活中,我们所遇到的问题大都不含负权,所以我们在()0 ij 若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一,它不仅可以直接应用于解决生产实际的许多问题,如管路铺设、线路安装、厂区布局和设备更新等,而且经常被作为一个基本的工具,用于解决其他的做优化问题。 定义1:若图G=G(V,E)中个边[v i,v j]都赋有一个实数w ij ,则称这样的图G为

相关文档