文档介绍：“矩阵论”课程研究报告科目:矩阵理论及其应用专业: 机械工程教师:刘德强学号: 类别: 上课时间:2014年9月至2014年12月考生成绩: 阅卷评语: “矩阵论”课程研究报告科目:矩阵理论及其应用专业: 机械工程教师:刘德强学号: 类别: 上课时间:2014年9月至2014年12月考生成绩: 阅卷评语: 阅卷教师(签名) 航班问题摘要:针对航空公司经营4、B、C、D和H五个城市的航线业务,其中H为中心城市的A到B航班路线条数计算问题,使用离散数学中的邻接矩阵方法,建立关联各个城市的有向图邻接矩阵,并通过计算可得到从A到B,刚好是三个相连的航班的路线有3条;从A到B,要求不多于四个相连的航班的路线有条,从而推知可计算任意多个城市多个相连航班的路线条数。关键词:离散数学;邻接矩阵;路线条数正文一、问题描述一家航空公司经营A、B、C、D和H五个城市的航线业务,其中H为中心城市。各个城市间的路线见图1。\/叭©e图1假设你想从A城市飞往B城市,因此要完成这次路线,至少需要两个相连的航班,即A->H和HtB。如果没有中转站的话,就不得不要至少三个相连的航班。那么问题如下:从A到B,有多少条路线刚好是三个相连的航班;从A到B,有多少条路线要求不多于四个相连的航班。二、方法简述因为上述问题所给的各个城市的路线图是各个顶点之间的关系,此外,各个顶点之间有方向关系,所以采用一个二维数组的有向图邻接矩阵来存放A、B、C、D、H顶点关系的数据。建立邻接矩阵后,通过计算得出结果。根据题目所给的有向图取D=VV,E>,假设V={Vi,l/2,V3,・「Vn},其中,(%代表A"?代表及%代表C,%代表代表H),|E|=m。令含j⑴为%•邻接到巧•的边的条数,则(街⑴人也为D的邻接矩阵记为A(D)根据图一所给的有向图的关系,得出邻接矩阵A(D)为:0010110001A(D)=0001101001-11110从上述邻接矩阵可以看出⑴(1)第i行元素之和为M的岀度,数学表达式为:n)=1nn n1=1;=1 1=1(2)第j列元素之和为Vj的入度,数学表达式为:ni=l且:nnttA^;=1i=ln》犷(%)=m1=1有前面的分析可知,式子71 71工m⑴1=1;=1代表有向图屮所有的单向关系的个数(双方都有关系的记为2)总和,也可看作有向图D的关系总和。并给出了以下定义⑵向图D=<V,E>,V={Vi“2,V3,…,VJ,D屮为1个相连的航班次数可以用(4(D))'来表示,即:(AW)'=(Aj(0)nxn其中Aj(0=^AkU_1)-Ak(1)k(4(D))'(街⑴)®即,(/1(D))1="(D))—(71(D))1贝IJ,鈿(')为顶点《到Vj的相连航班的个数为1, (71(D))Z中所有元素之和为有向图D屮个数为1的相连航班数。推论:]2 T __设爲=(4(D)) +(力(D)) +•••+(4(D)),则倂屮的元素为有向图D屮%到舟相连航班数小于等于啲个数。根据以上定义和推论,就可以得出我们所要得到的问题结果三、实验数据和结果根据题意可得,rO0101-10001"(D))=鈿⑴=0001**********-因为(S(D))'=(S(D))I,(71(D))001ol001Ol11121-21io001io00111211故,(4(D)) =(4(