摘要图论作为近年来较为活跃的数学分支，它在数学的其他领域的应用也是越来越广泛。矩阵作为一种纵横排列的二维数据表格，我们可以很直观、方便地利用矩阵来表示图中点与边之间的关系。图中顶点与顶点之间的关系、顶点与边之间的关系、边与回路的关系，都可以用矩阵表示。因此矩阵恰好可以成为研究图中的一些性质的一种重要工具。本文将总结前人对一些矩阵（邻接矩阵，关联矩阵，圈矩阵，长度矩阵）的定义以及这些矩阵在图论中一些应用，例如判断图的同构，Euler回路，Hamilton回路；计算有关于图的一些数据。并且在前人的基础上，对一些定理和问题做了一定的推广，例如利用邻接矩阵来计算图的直径。65259

毕业论文关键词 邻接矩阵，关联矩阵，圈矩阵，长度矩阵，无向连通图，图的同构，Euler回路，Hamilton回路

毕业设计说明书（论文）外文摘要

Title   Matrix in the application of graph theory                     

Abstract

Graph theory as a branch of mathematics not only becomes more active in recent years but also in other fields of mathematics is more and more widely used. As a two-dimensional data tables, matrix can help us understand the relationship between vertexes and edges of graph easily. We can use matrices to show the relationships between vertexes and other vertexes, between vertexes and edges, and between edges and circuits. Therefore, matrices can be a very important tool to research some properties of graphs. In this article, definitions of some matrices, which were presented by the predecessors, are summarized and applications of these matrices are provided. Furthermore, on the basis of the predecessors, I find something new. For example, the adjacent matrix can be used to calculate the diameter of a graph.

Keywords: adjacent matrix, incidence matrix, circ matrix, weight matrix, undirected connected graph, graph isomorphism, Euler circuit, Hamilton circuit

目   次  

1 引言 1

2  图与矩阵的基本知识 2

2.1  图的基本概念 2

2.2  矩阵的基本概念 3

2.3  矩阵的基本运算 3

3  邻接矩阵 6

3.1  理论 6

3.2  图中的应用 7

4  关联矩阵 16

4.1  理论 16

4.2  图中的应用 20

4.3  生活中的应用 22

5  圈矩阵 23

5.1  理论 23

5.2  图中的应用26

6  长度矩阵28

6.1  理论28

6.2  图中的应用29

结论  33

致谢  34

参考文献35

1  引言

图论是数学的一个分支，以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过，作为一门古老而经典的课程来说，学习者需要有不同的眼光去看待这门课程。从古至今，图论一直都是一个热门学科,图论知识的应用是相当广泛的，是近年来较为活跃的数学分支。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。论文网