廖云华 刘建刚 谢小良

摘 要：邻接矩阵不仅是代数图论的基石，也是图论与计算机程序间的桥梁，因此邻接矩阵具有重要的意义。但一般运筹学教材中对邻接矩阵只是简单介绍其概念，学生感觉不到邻接矩阵的重要性，更不知道如何应用邻接矩阵去解决运筹学和图论中的问题。为了让学生更好地理解和掌握邻接矩阵，我们对邻接矩阵教学内容进行了设计，在教学实践中取得好的效果。

关键词：邻接矩阵;图的矩阵表示;运筹学

中图分类号：G4 文献标识码：Adoi：10.19311/j.cnki.16723198.2021.06.071

任给一个图，都存在唯一的邻接矩阵与之对应;反之，任给一个邻接矩阵，也存在唯一的图与之对应。所以，图与邻接矩阵之间具有一一对应关系。由于矩阵在计算机中可以用一个二维数组表示，于是一个图也就可以在计算机中用一个二维数组表示，使得能够利用计算机编程解决一些困难的图论问题，例如著名的四色定理。邻接矩阵在图论与计算机程序之间架设了桥梁，具有重要的理论意义和应用价值。本文拟对邻接矩阵的性质与应用进行教学设计，提升邻接矩阵的教学效果。

1 邻接矩阵的概念与性质

邻接矩阵是表示顶点之间相邻关系的矩阵。G是一个图，V（G）为G的顶点集，E（G）为G的边集。设G中有n个顶点v1，v2，…，vn;A=aijn×n为图G的邻接矩阵，其中，

aij=1，vivj∈E（G）;0，vivjE（G）.

邻接矩阵具有下面几个重要性质。

性质1 设A为图G的邻接矩阵，则图G中顶点vi，vj之间长为k的途径的条数等于Ak中的i行j列元素akij。

性质2A2中的（i，i）元是顶点vi的度;A3中的（i，i）元是包含顶点vi的三角形的数目的二倍;A3的迹图G中的三角形的数目的六倍。……