摘 要 图的矩阵表示法，有着重要的意义。一般离散数学教材中对邻接矩阵的概念及其作用的介绍是零散的，学生感觉不到其重要性，也不知如何应用。为了让学生掌握如何利用矩阵来解决图论中的一些问题的知识，对邻接矩阵的作用进行有意义的总结和归类，并对教学内容进行设计，在教学实践中取得好的效果。
关键词 离散数学；图；邻接矩阵
中图分类号：G642.4 文献标识码：B 文章编号：1671-489X(2011)30-0034-02
Design of Teaching Content on Adjacency Matrix of Graph in Discrete Mathematics//Zhang Aihua
Abstract It is a very important and useful way to represent graph using adjacency matrix. In most of the textbook on discrete mathematics, the description of adjacency matrix is scattered, which is not good for students to study. The students do not know how to use it and how important it is. In order to teach students that how to use adjacency matrix to solve some problems on graphs, some very useful summary are made on adjacency matrix and its usage. Good effect has been gained while teaching in recent years.
Key words discrete mathematics; graph; adjacency matrix
Author’s address Computer School of Huazhong University of Science and Technology, Wuhan, China 430074
离散数学是信息学科尤其是计算机学科的一门重要的专业基础课程，而图论是建立和处理离散数学模型的一个重要工具，是一门实用性很强的学科。它在诸如社会科学、计算机科学、信息论和控制论等方面都有着广泛的应用。尤其是计算机科学，在后续的逻辑设计、数据结构、操作系统和程序设计等课程中都起着重要的作用[1]。
在图的几种常用的表示方法中，利用矩阵表示图，尤其重要。由于有了矩阵表示，可以将图表示成矩阵后，再以数组的形式保存到计算机中，将对图的一些操作搬到计算机中，把任务交给计算机程序，使得一些图论问题计算机程序化、自动化。
本文主要论述教给学生利用邻接矩阵的方法解决一些图论问题，并对一些方法进行设计。
1 邻接矩阵概念
【定义】设图G=
如果图G不是一个多重图，那么其邻接矩阵就是一个0-1矩阵，其中的项不是0就是1，有利于简化矩阵的运算。显然，任给一个图，都能确定一个邻接矩阵。反之，给定一个邻接矩阵，也可以确定一个图，并将其画出来。图与邻接矩阵之间建立起来联系。一个矩阵在计算机中可以用一个二维数组表示和保存起来，于是一个图也就可以在计算机中用一个二维数组表示和保存。
【定理】设G是具有顶点集V={v1,v2,...vn}和邻接矩阵A的图，则At(l=1,2,...)的第(i,j)项元素(aij)(t)n×n为连接顶点vi到vj的长度为t的路的数目[3]。
这是一个很重要的结论，它为邻接矩阵的应用打下好的基础。
2 邻接矩阵应用
当一个图表示成邻接矩阵后，就可以通过分析该邻接矩阵的特征，或者对该邻接矩阵进行一些操作和运算，得到图的一些性质，或者解决一些图论的问题。本节对邻接矩阵的作用进行有意义的归纳总结，便于学生学习和应用。
以下均假设A为具有顶点集V={v1,v2,...vn}的图G的邻接矩阵。
2.1 从邻接矩阵的一些基本的数量特征分析图的性质
1）如果G是一个无向图，则A的第i行的元素之和等于顶点vi的度，即与顶点vi关联的边的数目；同样第i列的和也如此。所以可利用这点计算图的每个顶点的度数。2）如果G是一个有向图，则A的第i行的元素之和等于顶点vi的出度，而第i列的和则等于点vi的入度。3）A的所有元素之和则等于G的总度数，它除以2则等于G的边的数目。4）如果G是无向图，而且A的某一行的元素之和为0，则对应的顶点vi为孤立点。5）如果A为非对称矩阵，则意味着G是一个有向图。6）如果A中有某些元素的值大于1，则G为多重图。7）如果A除主对交线外的所有元素皆为1，则G为完全简单图。
2.2 通过邻接矩阵的运算分析出图的性质
1）判断图同构。要判断两个图G和H是否同构不是件容易的事情。如果给出图G和H的邻接矩阵A和B，则可以通过变换A和B来进行判断。首先，可以编写计算机程序扫描A和B，利用上面2.1叙述的结论，分析G和H的一些基本特征是否一样，如果不一样，则说明G和H肯定不同构。其次，如果G、H两个图的基本特征都一样，则通过下面的方法确定是否同构。具体方法设计：矩阵只有行列交换的合同变换，对矩阵进行第一类初等变换，即只交换矩阵的某两行，或者某两列；而且当矩阵的第i行与第j行进行交换的同时，也必须交换矩阵的第i列和第j列，反之也一样。对邻接矩阵A进行一次只有行列交换的合同变换，得到另一矩阵后A1，那么A1对应的图跟A对应的图之间必然是同构的，因为它们之间相当于只是将顶点集的某两个顶点的顺序做了一次对换。于是，如果能通过有限次这样的合同变换将A变换成B，或者是将B变换成A，那么G与H同构；否则如果不可能将A变换成B，则说明G与H不同构。
2）判断图的两个顶点是否连接，并且计算其距离。在只有n个顶点的图G中，如果点vi与vj之间存在路的话，那么必然存在一条长度小于n的真路[3]。根据上面介绍的定理，在A1,A2,...,An-1这n-1个矩阵中，至少有一个At，它的第(i,j)项元素大于1，表示长度为t的路是存在的。为了简化计算，在计算矩阵的乘法时，采用布尔运算，那么得到的矩阵仍然是0-1矩阵。这样At的第(i,j)元素的值为1时表示有长度为t的路，为0则没有。于是可以设计算法：①检查A1的第(i,j)个元素，如果非零则说明vi与vj是连接的，结束；②循环计算At，检查其第(i,j)个元素，如果非零则结束循环，vi与vj是连接，距离等于t，否则t=t+1，当t≤n-1时循环继续上一步，否则结束，vi与vj是不连接。
3）判断图的连通性。根据2），如果计算出任两点之间是连接的，则图是连通的，否则不连通。
4）判断一个图是否为树。图论中，连通而且无环的图称作树。根据树的等价定义[3]，连通而且边数等于顶点数减1也就是树。于是利用邻接矩阵判断一个简单图是否是树的算法设计：①根据3.1的介绍，先计算图的边的数目，也即计算A的所有项之和再除以2，如果结果等于n-1则进入第二步，否则说明不是树，结束；②根据3）的算法，计算求证图G是否连通，如果连通，则G为树，否则不是树，结束。
5）寻找图的分图数。如果图G是连通的，则该图就一个分图；如果不连通，那么图的分图数就是一个待计算的问题。对图的邻接矩阵A进行一系列的只有行列交换的合同变换，如果能够将A变成一个分块对角矩阵，其中的每一个Ai为方阵，而且再也不能进一步分成更细的分块对角矩阵，那么这个分块对角矩阵的块数t就是图G的分图数，其中每一分块对应着G的一个分图。
3 总结
上面总结了如何利用邻接矩阵判断分析图的一些基本特性，也叙述和设计了一些算法，进一步计算图的性质。由于在计算机中可以用一个二维数组表示和保存一个矩阵，上面的算法都可以在计算机中程序实现。代码的设计不是本文的重点，这里不再叙述如何在计算机中代码实现这些算法，实际中鼓励学生自己去实现，锻炼学生动手解决问题和编程的能力。通过这些叙述和设计，学生对邻接矩阵的应用有了一个深入的了解，还可以学习思考用矩阵的方法解决更多的问题。
参考文献
[1]洪凡.离散数学基础[M].3版.武汉:华中科技大学出版社,2008:177.
[2]屈婉玲,耿素云,张立昂.离散数学[M].2版.北京:清华大学出版社,2009:172.
[3]Rosen K H. Discrete mathematics and Its Applications[M].4版.北京:机械工业出版社,2007:457.