矩阵在图论中的应用

矩阵在图论中的应用

摘要

图可以用矩阵表示，图中顶点与顶点之间关系、顶点与边之间关系、边与回路的关系，都可以用矩阵来表示。本文章所涉及的只是图论中的1些基本概念和理论，将图用矩阵(关联矩阵、邻接矩阵)表示，在方法上应用矩阵来研究图的1些性质。用矩阵表示1个图的各种关系，不仅是给出图的1种表示方法，而且可以充分利用矩阵代数中的各种运算，来研究图的结构特征及性质，这样便于用计算机处理图。

关键词：矩阵；图；关联矩阵；邻接矩阵；回路；2部图

The Implication of Matrix for Graph

Abstract

Graph can be denoted by matrix. In the graph , all the correlations such as two vertexes, the vertex with the sideline, and the sideline with the cycle can be illustrated through the matrix . This paper involves only some basic concepts and theory in the graph. It’s committed to exercise the matrix theory to do some hart operation based on the affiliated matrix and the adjacency matrix , and make efforts to do some research on the characteristics of graph. Matrix can represent each kind of relations of graph ,not only give one expression method of graph, moreover can fully use operation in the matrix algebra, studing the structure characteristic and the nature of graph ,bringing much convenience to the graph  processing in computer.

Key words: matrix;graph; affiliated matrix; adjacency matrix; cycle; bipartite graph

1 引言

图论是近210年来发展10分迅速、应用比较广泛的1个新兴的数学分支，在许多领域，诸如物理学、化学、运筹学、信息论、控制论、计算机等方面甚至在生产生活中都有广泛的应用。因此受到全世界越来越广泛的重视。图论的内容10分丰富，涉及面也比较广。本文章所涉及的只是图论中的1些基本概念和理论，在方法上应用矩阵来研究图的1些性质。用矩阵表示1个图的各种关系，不仅是给出图的1种表示方法，而且可以充分利用矩阵代数中的各种运算，来研究图的结构特征及性质，且便于计算机处理。用矩阵表示图，必须首先将图的顶点、边等分别按照某种顺序排列，然后并按照这种顺序依次给定惟1标号，使其成为标号图，最后给出其矩阵表示。 （转载自http://zw.NSEAC.com科教作文网）
本文通过运用邻接矩阵和关联矩阵的特征，把图的运算转化成矩阵的运算，这就包括图的点边运算、求补图运算、图的交和并运算、图的边的收缩。运用图的1些性质，转化为矩阵，进而判断图是否具有其他性质，这就包括用邻接矩阵判断图的回路，判断图是否为2部图。