图的邻接矩阵的教学设计

2021-02-04廖云华刘建刚谢小良

现代商贸工业 2021年6期

廖云华刘建刚谢小良

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

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

中图分类号：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中的三角形的数目的六倍。

2 邻接矩阵的应用

一个农夫带着一只狼，一只羊和一筐白菜，欲从河和北岸坐船到南岸。由于船太小，农夫每次最多只能带一样东西过河。如果没有农夫看管的话，狼会吃羊，羊会吃白菜，但狼不会吃白菜。设计一个方案，使农夫能将所有东西运过河。

农夫过河问题是一个经典的算法设计问题，但在这里我们使用图论中的邻接矩阵来解决这个问题。首先，对河流两岸进行描述，设N表示北岸，S表示南岸。然后，对两岸的状态进行描述，可用4位二进制数顺序分别表示农夫、狼、羊和白菜的位置状态，用0表示不在，1表示在。例如，（N1010）表示农夫和羊在北岸，同时也表明狼和白菜在南岸。共有32个状态，但根据题意，满足狼、羊、菜三者之间都和平相處的安全状态只有20个。由于只有农夫能撑船，我们只需要考虑有农夫的安全状态，这样的安全状态只有如下10个：

v1N111，v2N1110，v3N1101，v4N1011，v5N1010，v6S1111，v7S1110，v8S1101，v9S1011，v10S1010

以V=v1，v2，…，vn为顶点集，一次渡河前后南北两岸的两个状态之间连边，我们得到了各状态间的关系示意图（见图1）。

该图的邻接矩阵为：

A=0A1A10

其中，

A1=0000100110001110011100100

由性质1，我们应考虑最小的k，使得Ak中第6行1列的元素不为0，此时k为最少的渡河次数，Ak中第6行1列的元素为最佳路径的数目。

经过计算，k=7，此时A7中第6行1列的元素为2，所以需要7次渡河，有2条最佳路径。然后，利用逆向搜索法，确定两条最佳路径为v1v10v3v7v4v8v5v6和v1v10v3v9v2v8v5v6。对应的方案分别为：

方案1：

v1N111带羊去南岸v10S1010独回北岸v3N1101带狼去南岸v7S1110带羊回北岸

v4N1011带菜去南岸v8S1101独回北岸v5N1010带羊去南岸v6S1111

方案2：