图的矩阵表示
——无向图及有向图的关联矩阵
作者 现代的导师
摘要：图论的内容丰富多彩，应用广泛，在许多学科中都有涉及图论的内容，篇是关于图论的一些小诠释，图的矩阵表示，无向图及有向图定义的声明和部分例题的证明以及解释。
关键字：图论，图的矩阵表示，关联矩阵
离散数学是现代数学的一个重要分支, 是以一切离散量为研究对象的一门学科, 包括数理逻辑、关系代数、图论、组合数学、集合论等多方面内容。离散数学课程在讲授离散问题建模、数学理论等技术和知识的同时培养了学生数学抽象能力和严密的逻辑推理能力。特别是在计算机学科诞生后, 这一特点更为显著, 其中图论的相关教学内容表现得更为突出。而在实际教学中, 由于教学内容概念多, 定理抽象, 许多学生对相关内容的掌握程度并不理想。因此, 在计算机等相关专业的离散数学教学中如何提高图论部分的教学质量从而促进整个离散数学教学的效果成为教学研究中的热点问题[1][2], 这也是为相关后继课程建立坚实基础的有效途径。
图论是研究由线连接的点集的理论, 在数学中图论是拓扑学的一个分支。图论问世一般以1736 年Euler 提出的七桥问题为标志, 这样明确的时间记载在数学史中是罕见的。图论的发展与其他数学分支相比较也是存在一定的差异, 因为单纯从数学的观点看图论的价值并不大, 所以图论出现后相当长一个时期只被作为讨论一些娱乐性命题的内容。但是随着近代数学的发展, 特别是计算机技术的出现, 使得图和网络作为一种计算工具被广泛应用到工程的各个领域。应当指出的是如果没有计算机的帮助图论的应用范围不可能达到今天这样的程度,因此图论的最终教学目的是培养学生将问题抽象建立数学模型并使用计算机编写相关的程序求解的能力。
图的矩阵表示
给定一个图G=，使用图形表示法很容易把图的结构展现出来，而且这种表示直观明了。但这只在结点和边(或弧)的数目相当小的情况下才是可行的。显然这限制了图的利用。
现在提供另一种图的表示法——图的矩阵表示法。它不仅克服了图形表示法的不足，而且这种表示可以充分利用现代工具电子计算机，以达到研究图的目的。
性质：
若第j列与第k列相同，则ej与ek为平行边
一个简单图G=由V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。
有向图的邻接矩阵
性质 ：
一个简单图G=由V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点
对于给定图D，显然不会因结点编序不同而使其结构发生任何变化，即图的结点所有不同的编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的邻接矩阵都是相似的。
今后将略去这种由于V中结点编序而引起邻接矩阵的任意性，而取该图的任一个邻接矩阵作为该图的矩阵表示。
性质 ：
A(D)中所有元素之和为D中长度为1的通路总数，其中
主对角线元素之和为D中长度为1的回路(环)的总数。
邻接矩阵可展示相应图的一些性质：
若邻接矩阵的元素全为零，则其对应的图是零图；
若邻接矩阵的元素除主对角线元素外全为1，则其对应的图是连通的且为简单完全图。
此外，当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵A，显然可以唯一地作出以A为其邻接矩阵的简单图G。于是，所有n个结点的不同编序的简单图的集合与所有n阶对称矩阵的集合可建立一一对应。
当所给图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有n个结点的不同编序的简单图的集合，与所有n阶邻接矩阵的集合亦可建立一一对应。
不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。
由给定有向图D的邻接矩阵A可计算出矩阵A的l次幂，即Al。
在一些实际问题中，有时要判定图中结点vi到结点vj是否可达，或者说vi到vj是否存在一要链(或通路)。如果要利用图D的邻接矩阵A，则应计算A2，A3，···，An，···。当发现其中某个Ar中 ≥1，就表明vi可达vj或vi到vj存在一条链(或通路)。但这种计算繁琐量大，又不知计算Ar到何时为止。
根据定理10.2.2可知，对于有n个结点的图，任何基本链(或通路)的长度不大于n-1和任何基本圈(或回路)的长度不大于n。因此，只需考虑 就可以了，其中1≤r≤n。即只要计算Bn=A+A2+A3+···+An。
求下列有向图的通路总数,回路总数,可达矩阵,及强连通分支的顶点集.
长度小于等于5的通路总数70
长度小于等于5的回路总数12
该图的强连通分支的顶点集为{v1},{v2},{v3,v4,v5}.