[精品]数学建模论文1

《[精品]数学建模论文1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图的矩阵表示摘要文章主要阐述图的矩阵表示以及分步决策的运用，对于图论问题的解决有重要的作用。通过对一些实际图论问题采用图的矩阵來解决，表明图的矩阵是使图论问题描述更加简单，直观，更加接近计算机语言，是图论的重耍内容。关键词图的连接矩阵算法分步决策在《图论及其应用》［1］一书中提到了一些图的若干问题，最短路径，最优二元树，最优Hamilton图，课木中已经给出了一些经典的解法，通过查阅资料发现，如果采用图的矩阵表示这类方法，可以为这些问题提供新的解答思路或者可以优化原来的解答过程；此外，如果采用图的矩阵表示，将使其描述更

2、加接近计算机逻辑和语言，方便将图论问题转换成计算机语言，进而借助计算机的运算性能解决图论的一些复杂计算问题。因而，在图论中图的矩阵表示有着重要的地位。基木定义：(1)一个图G=(V,E)由它的顶点与边Z间的关联关系唯一确定；也由它的顶点对之间的连接关系唯一确定。图的这种关系可以用矩阵来描述，分别称为G的关联矩阵与邻接矩阵。/0,若vev.veE(G)令：M(G)二{aij}nXn,其中二弧11,-其他称M(G)为G的邻接矩阵.(2)令G二(V,E)为一个加权无向图，其中V={v.,v2,-,vn}为顶点集合，E为边集合

3、。图G中每一条边e都对应一个实数W(c),则称w(c)为该边的权。/W..,若(Uv)eE(G)且粘为两点之间的令：M(G)二{dij}nXn,a；j二to若i=j权以下尝试使用图的炖阵來描述或解决图论中的一些定义和问题［2］(-)连通图的判别设图G的邻接矩阵为M(G),作一个p阶方阵：R(G)=M(G)+M2(G)+・・・+MP-l(G),R(G)称为G的可达矩阵。则有如下判断：定理1阶至少为3的图G是连通的充分必要条件为R(G)屮的每个元素都不等于零。(二)最短路径问题Dijkstra算法是

4、=

5、前为止求解最短路问

6、题的最好算法。传统的Dijkstra算法计算量较大，运算速度较慢，但是如果将Dijkstra算法和矩阵算法结合运用，可使计算时间明显减少，并能获得精度较高的结果。［3］算法的简单描述：计算点Vi(Xi,Yi)到点Vj(Xj,Yj)的最短路径(递归运算)(1)判断是否为同一点，是，退出；否则继续；(2)找出(Xi,Yi)周围的八个点分别计算出到(Xj,Yj)路径的长;(3)找出在第二步屮计算出的最短路径。将第(2)步细化(下面所说的点指的是周囤的八个点)在《图论及其应用》［1］一书中提到了一些图的若干问题，最短路径，最优

7、二元树，最优Hamilton图，课木中已经给出了一些经典的解法，通过查阅资料发现，如果采用图的矩阵表示这类方法，可以为这些问题提供新的解答思路或者可以优化原来的解答过程；此外，如果采用图的矩阵表示，将使其描述更加接近计算机逻辑和语言，方便将图论问题转换成计算机语言，进而借助计算机的运算性能解决图论的一些复杂计算问题。因而，在图论中图的矩阵表示有着重要的地位。基木定义：(1)一个图G=(V,E)由它的顶点与边Z间的关联关系唯一确定；也由它的顶点对之间的连接关系唯一确定。图的这种关系可以用矩阵来描述，分别称为G的关联矩阵与

8、邻接矩阵。/0,若vev.veE(G)令：M(G)二{aij}nXn,其中二弧11,-其他称M(G)为G的邻接矩阵.(2)令G二(V,E)为一个加权无向图，其中V={v.,v2,-,vn}为顶点集合，E为边集合。图G中每一条边e都对应一个实数W(c),则称w(c)为该边的权。/W..,若(Uv)eE(G)且粘为两点之间的令：M(G)二{dij}nXn,a；j二to若i=j权以下尝试使用图的炖阵來描述或解决图论中的一些定义和问题［2］(-)连通图的判别设图G的邻接矩阵为M(G),作一个p阶方阵：R(G)=M(G)+M2(

9、G)+・・・+MP-l(G),R(G)称为G的可达矩阵。则有如下判断：定理1阶至少为3的图G是连通的充分必要条件为R(G)屮的每个元素都不等于零。(二)最短路径问题Dijkstra算法是

10、=

11、前为止求解最短路问题的最好算法。传统的Dijkstra算法计算量较大，运算速度较慢，但是如果将Dijkstra算法和矩阵算法结合运用，可使计算时间明显减少，并能获得精度较高的结果。［3］算法的简单描述：计算点Vi(Xi,Yi)到点Vj(Xj,Yj)的最短路径(递归运算)(1)判断是否为同一点，是，退出；否则继续；(2)找出(Xi,

12、Yi)周围的八个点分别计算出到(Xj,Yj)路径的长;(3)找出在第二步屮计算出的最短路径。将第(2)步细化(下面所说的点指的是周囤的八个点)1)将访问标记置位；2)首先判断此点的路径长是否已知(即TArrEle.Dis