1图论的一个基本应用

下图描述了4个城市之间的航空航线图,

为了描述着4个城市之间航线的邻接关系，定义邻接矩阵

第i行描述从城市i出发,可以达到各个城市的情况,

可以证明,矩阵A^N表示一个人连续坐N次航班可以达到的城市,元素大小对应方法种数

例:下图描述了6个城市之间的航空航线图，带箭头线段表示两个城市之间的航线.

1若某人连续乘坐5次航班,那么他从哪一个城市出发到达哪一个城市方法最多

2若某人可以乘坐一次、二次、三次、或四次航班,那么他从哪一个城市出发总是不能达到哪一个城市

运行Test.m

%邻接矩阵
A=[0 1 0 0 0 1;0 0 1 1 0 0;0 0 0 1 1 0;0 1 0 0 0 0;1 0 1 0 0 0;0 1 0 0 1 0];
%连续乘坐5次航班
m =max(max(A^5));
[i,j] = find(A^5 == m);
fprintf('从一个城市出发到另一个城市方法最多有%d条,有：\n',m);
disp([i,j])
%可以乘坐1、2、3或4次
A = A+A^2+A^3+A^4;
[i,j] = find(A == 0);
fprintf('不能从一个城市达到另一个城市的有：\n');
disp([i,j])

2情报检索问题

假如数据库中包括了n个文件,而搜索所用的关键词有m个，关键词按字母顺序排列,我们就可以把数据库用一个mxn的矩阵A来表示,矩阵A的第j列表示第j个文件

矩阵A的第i行表示第i个关键词,矩阵A中的元素aij表示第i个关键词在第j个文件中出现的相对频率。用于检索的关键词清单用m维列向量x表示,假如检索策略中含有

i、j、k三个关键词,则让搜索向量x的第i、j、k个元素为1,其它为0。当确定了数据库矩阵和搜索向量x后,进行线性变换运算,y=A'x，y即为检索结果,数字大小对应着匹配度高低

3.MATLAB命令x=A\b

1)当方程组为适定方程组，x为方程组的唯一解

2)当方程组为欠定方程组时，x为方程组的一个特解

3)当方程组为超定方程组时,x为按照最小二乘原理得到的一组近似解

4已知向量组

请用向量u和v来线性表示向量w,并绘制向量图

易得方程组的解2u+3v=w

程序drawvec.m是一个绘制二维向量的函数

function drawvec(u)
plot([0;u(1)],[0;u(2)]);%画向量线段
hold on
theta = acos(u(1)/norm(u));%计算向量u与x轴的夹角,0<theta<pi
if(u(2) < 0)
theta = 2*pi - theta;%当u向量在第三和第四象限时,theta>pi
end
fill([u(1)-0.5*cos(theta+pi/12),u(1),u(1)-0.5*cos(theta-pi/12)],[u(2)-0.5*sin(theta+pi/12),u(2),u(2)-0.5*sin(theta-pi/12)],'black');%给向量箭头填充
hold off

程序la.m绘制了向量u和向量v线性表示向量w的几何图形,其中调用了drawvec.m

clear

close all
u=[1;2];v=[2;-1];w=[8;1];
u1 = u*2; v1= v*3;
%调用函数drawvec(),画向量
drawvec(u);hold on
drawvec(v);hold on
drawvec(u1);hold on
drawvec(v1);hold on
drawvec(w);hold on
%补虚线,将线条属性设置为虚线--
A = [u1,w];
B = [v1,w];
plot(A(1,:),A(2,:),'--k',B(1,:),B(2,:),'--r');
%显示坐标
text(A(1,1),A(2,1),['(',num2str(A(1,1)),',',num2str(A(2,1)),')'],'EdgeColor','red');
text(A(1,2),A(2,2),['(',num2str(A(1,2)),',',num2str(A(2,2)),')'],'EdgeColor','green');
text(B(1,1),B(2,1),['(',num2str(A(1,1)),',',num2str(A(2,1)),')'],'EdgeColor','blue');
axis([-2 10 -5 6]),grid on%设置坐标范围和网格线

运行la.m