浅谈图论中邻接矩阵的应用

浅谈图论中邻接矩阵的应用

[摘 要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。

[关键字] 邻接矩阵、算法、连通性、最小生成树

1、引言

首先介绍图论中邻接矩阵的一个重要定理:

G是一个图,V (G)为 G的顶点集, E(G)为 G的边集。设G中有 n个顶点，v1,v2, ,vn;A=(aij)n×n为 G的邻接距阵, 其中

定理 1:设 A (G)为图 G的邻接距阵,则 G中从顶点 vi 到顶点 vj,长度为 k的道路的Ak条数为中的 i行 j列元素。

证:对 k用数学归纳法

k =1时,显然结论成立;假设 k时,定理Al.A= Al+1成立,考虑 k +1的情形。

记 Al的 i行 j列元素为l≥2,因为所以

(1)

而从vi,vj到长 k +1的道路无非是从vi 经 k步到某顶点vl(1≤l≤n),再从vl走一步到vj; 由归纳假设从vl到vj长为 k的道路共计 而从vl到vj 长为 1的道路为aij条,所以长为k+1的vl经过k部到vi再一步到vj的道路共有 条故从vi经 k +1步到vj的路径共有

1、 邻接矩阵现实问题中的运用

锁具装箱问题

某厂生产一种弹子锁具,每个锁具的钥匙有 5个槽,每个槽的高度从 {1, 2, 3, 4, 5, 6}6个数 (单位略 )中任取一数由于工艺及其他原因,制造锁具时对 5个槽的高度还有两个限制:至少有 3个不同的数,相邻两槽的高度之差不能为 5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每 60个装一箱出售。问每一批具有多少个,装多少箱。

分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有 5个槽,每个槽有 6个高度,至少有三个不同高度的槽。且相邻槽高差不为 。我们先求出无相邻高5差为 5的锁具数量,再减去仅有一个、两个槽高的锁具数目。

先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。为此,构造一个 6节点的图:将 1, 2, 3, 4, 5, 6这 6个数作为 6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具各槽之间的关系示意图 (见图 1)。

由图我们可以试着画出这个图的邻接矩阵来：

邻接矩阵 A的所有元素之和表示两个槽高无 1, 6相邻的锁具的个数,每个无 1, 6相邻的 5位数与图 1中长度为 4的一条链 1 - 1对应,如 12345, 11111, 22335等。A的 k次方中各元素之和就是长度为 k的链的个数。事实上,从这2个具体问题可以看出, A 中第 i行第 j列

第1页下一页