基于离散数学邻接矩阵航班问题的研究

第1页航班问题机械工程学院摘要本次论文采用离散数学邻接矩阵的方法解决航班问题，通过邻接矩阵求解A→B的通路数。不仅解决了A→B的航班问题，同时可以得到任意两地之间的航班安排问题，极大地的简化了计算过程。关键词：邻接矩阵通路数一、问题描述现有一家航空公司经营A、B、C、D和H五个城市的航线业务，其中H为中心城市。各个城市间的路线见下图。图1-1假设你想从A城市飞往B城市，因此要完成这次路线，至少需要两个相连的航班，即A→H和H→B。如果没有中转站的话，就不得不要至少三个相连的航班。那么问题如下：（1）从A到B，有多少条路线刚好是三个相连的航班；（2）从A到B，有多少条路线要求不多于四个相连的航班。二、名称解释及理论依据名词解释邻接矩阵：是表示点与点之间逻辑关系的矩阵。图1-1作为有向图，可以依此列出其五点之间逻辑关系的矩阵，其中1表示两点之间的通路是可行的，0表示两点之间的通路是不可行的，如表1-1所示。邻接矩阵展示了两点之间长度为1的通路数。理论依据以长度为2来说，邻接矩阵为G=(aij)55,若结点A到B存在长度为2的路，则中间必定存在一个结点X（任意C，D或H），即AXB，且aik=akj=1，即aik.akj=1；若结点A到B不存在长度为2的路，则aik=akj=0,即aik.akj=0。故，从结点A到B长度为2的路的数目为：第2页ai1.a1j+ai2.a2j+…+ain.anj=而这恰好等于矩阵G2中第i行第j列的元素。三、模型假设1、计算时为了满足航班次数的要求，航班有时在两地之间往复。2、为了满足航班次数的要求和方便计算，在求解过程中将与目的地之间的往复也计算在内。3、本次论文提出的解决方案主要用于理论计算，不做实际指导。四、模型分析为了方便用矩阵理论求解，本次论文建立航班飞行邻接矩阵G，通过计算G2，G3，G4可以分别得出A→B长度为2，3，4的通路数。五、模型的建立与求解建立航班飞行邻接矩阵：表1-1至从ABCDHA00101B10001C00011D01001H11110表1-1表示航班在各地之间的逻辑关系，例如A→A值为0表示A不能直接到达A，A→B，值为0表示A不能直接到达B，A→C值为1表示A可以直接到达C，A→H表示A可以直接到达H，其他以此类推。所得邻接矩阵G如下：G=[0010110001000110100111110]矩阵G表示航班可直接到达的关系，从矩阵中可以看出A→B的值为0。则两次航班的矩阵表示为G×G=G2nkkjikaa1.第3页G2=[0010110001000110100111110]×[0010110001000110100111110]=[1112111211121112111111114]从矩阵中可以看出A→B两个相连航班的值为1，表示从A经过两个相连航班到B的路线只有1个，即：A→H→B三次航班的矩阵表示为G×G×G=G3G3=[1112111211121112111111114]×[0010110001000110100111110]=[2322522235322252232555554]从矩阵中可以看出A→B三个相连航班的值为3表示从A经过两个相连航班到B的路线只有3个，即：A→C→H→BA→C→D→BA→H→D→B同理四次航班的矩阵表示为G×G×G×G=G4G4=[2322522235322252232555554]×[0010110001000110100111110]=[87779787797787977789999920]从矩阵中可以看出A→B四个相连航班的值为7，表示从A经过两个相连航班到B的路线有7个，即：A→C→D→H→BA→C→H→D→BA→H→C→D→BA→H→C→H→BA→H→D→H→BA→H→A→H→BA→H→B→H→B需要说明的是A→H→B→H→B这种情况在矩阵运算时也被计算在内，如果需要可将这种情况排除在外。因此从A到B共有1+3+7=11条路线且满足要求，不多于四个相连的航班。参考资料[1]周生明，廖元秀.离散数学[M]，北京：科学出版社，2010