11 | 如何运用线性代数方法解决图论问题?

你好,我是朱维刚。欢迎你继续跟我学习线性代数,今天我要讲的内容是“如何运用线性代数方法解决图论问题”。

“图”这个字在计算机科学领域很常见,特别是在数据结构中。一说到图,是必定要联系到图论(Graph Theory)的,因为它是以图为研究对象的数学的一个分支。图论中的图,是由若干给定的及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。

说到这,你也许会问,这个和线性代数、矩阵有什么关系?

图的数学定义

既然是数学课,我们还是要先讲一下图的数学定义:一个图 是指一个有序三元组 是非空的顶点集; 是不与 相交的边集; 是关联函数,它使 的每条边对应于 的无序顶点对。如果 是一条边, 是顶点,使得

好了,现在是时候通过两个应用场景来看下,如何把矩阵和图论关联起来,并运用在解决实际问题中了。

邻接矩阵应用

首先,是邻接矩阵(Adjacency Matrix),邻接矩阵是表示顶点之间相邻关系的矩阵。假设 是一个图, 的顶点集, 的边集,设 中有 个顶点,

已知情况是这样的,那我们现在来看一下邻接矩阵在现实问题中的应用。这个例子来源于 1994 年全国大学生数学建模竞赛试题 B 题。

某厂生产一种弹子锁具,每个锁具的钥匙有 5 个槽,每个槽的高度从

  1. 至少有 3 个不同的数;
  2. 相邻两槽的高度之差不能为 5。

满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每 60 个装成一箱出售。问:每一批锁具有多少个,装多少箱?

我们先来看下弹子锁具的样子,否则自己想象会要一些时间。

这是一个 7 个槽的弹子锁具,只是比我们例子的 5 个槽多了两个槽。有了弹子锁具形象化输出后,我们开始解题。锁具装箱是一个排列组合的数学问题,但如果我们用图论的邻接矩阵方法来解这个问题,就能够起到化繁为简的作用。

首先,我们构造一个 6 节点的图:把 1、2、3、4、5、6 这 6 个数作为 6 个节点,如果两个数字可以相邻,那这两个节点之间就加一条边,每个节点有自己到自己的一条边。于是,我们得到了锁具各槽之间的关系图:

接着,构建邻接矩阵 ,根据前面说的,如果两点之间有一条边,那在矩阵中,相应位置的值就是 1,比如:节点 1 和 2 之间有一条边,那矩阵第一行第二列和第二行第一列的值就是 1,节点 1 和 6 之间没有边,那矩阵第一行第六列和第六行第一列的值就是 0,因为每个节点有自己到自己的一条边,所以第一行第一列的值就是 1,其它 5 个节点也是一样的。

因为我们从没有 1、6 相邻的关系图得到了邻接矩阵 ,所以 中所有元素之和表示两个槽高无 1、6 相邻的锁具个数。而每个无 1、6 相邻的 5 位数与关系图中长度是 1 的一条链一一对应。于是, 中各元素之和就是长度为 的链接个数。比如, 中第 行第 列的元素就是 开始经过两条边到达 的链接个数。我们这里因为是 5 个元素,也就是要经过 4 条边,所以需要计算

中的元素求和,就能得到相邻高差为 5 的锁具数是 6306。

最后,因为题目的限制提到了槽的高度至少有 3 个不同的数,我们还要把 6306 这个数字减去仅有一个、两个槽高的锁具:

所以,我们得到一批锁具的个数是 5880,总共装 5880/60=98 箱。

这样,我们通过邻接矩阵的图论知识,解决了一批锁具的数量问题,比其它方法看起来更简单。

特别提示:文中用到的 在图论中的实际意义,是来自刘亚国的一篇文献《图论中邻接矩阵的应用》。

关联矩阵应用

接下来,我们在邻接矩阵上再升级一下,把边变成有向边。这样就形成了另一类矩阵:关联矩阵。关联矩阵经常被用在图论中,现在我们就来看一下关联矩阵和图之间的关系。如下图所示,我们定义了一个拥有 4 个节点和 6 条边的图。

接下来,定义一个 6×4 的矩阵来描述这个图,其中列表示点 (1) 到点 (4),行表示边 1 到边 6:

矩阵 只包含了三类元素:-1、1、0。-1 表示点的箭头的出方向,1 表示点的箭头的入方向,0 则表示点和点之间没有关联。举例来说,矩阵 的第一行元素是 -1、1、0、0,那对于边 1 和点 (1)、点 (2) 说,我们从图中可以看到边 1 是从点 (1) 到点 (2), 中 -1 对于点 (1) 来说是箭头的出方向,1 对于点 (2) 来说是箭头的入方向,而边 1 和点 (3)、点 (4) 没有任何关系,所以第一行第三列和第四列都是 0。

这里,我们把关联矩阵用到现实场景中,比如:让它为电子电路服务,用它来分析整个电路的情况,也就是电路的拓扑结构,这里的电路指的是基尔霍夫定律,是分析和计算较为复杂电路的基础。假设

由此可见,结果是差值,也就是沿着边 1 到 6 的电势差,有了电势差,就说明有电流,但如果 Ax=0 会怎样呢?也就是方程满足这样的等式:

很明显,这些差值,也就是电势差都等于 0,意味着没有电流。同理,如果把电压值换成温度呢?那应用场景就切换成热传导了。

刚才我们看到了

而在电路例子中,它表示的是所有六个电势差都是 0,也就意味着:所有四个电压值是相等的,在零空间中的每个 都是一个常向量:

刚才我们说的是电压,现在我们来具体看看关联矩阵在基尔霍夫电流定律上的运用。我们来定义一个拥有 4 个节点和 5 条边的图:

基尔霍夫电流定律定义:

这里 -1,0,1 的含义上面有所描述,第一行和 向量相乘后得到:

好了,到这里简单电路的数学知识,也就是关联矩阵讲完了,如果碰到更复杂的电路,比如:在节点之间,也就是边上有电流源,那么,等式就要从

本节小结

本节是第一篇应用篇,所以我从更贴近生活的例子来讲解线性代数的应用,通过弹子锁具,让你能够了解,邻接矩阵与图论之间是怎么关联的;通过基尔霍夫定律,让你能够了解关联矩阵与图论之间是怎么关联的。

所以,邻接矩阵、关联矩阵的最大意义就是用数学的方式描述图,进而来描述某些事物之间的某种特定关系,是不是发现问题后通过数学工具来解决问题很美妙呢?

线性代数练习场

这次的练习题稍微有些难度,是一道传统练习题。

三名商人各带一个随从乘船渡河,现有一只小船只能容纳两个人,由他们自己划行,若在河的任一岸的随从人数多于商人,他们就可能抢劫财物。但如何乘船渡河由商人决定,试给出一个商人安全渡河的方案,使得渡河的次数最少。

注意:这里的问题包含两层含义——安全渡河和渡河次数最少。
提示:使用本节的第一个例子的邻接矩阵和 来解这道题。

欢迎在留言区晒出你的运算过程和结果,我会及时回复。同时,也欢迎你把这篇文章分享给你的朋友,一起讨论、学习。