第七节*　矩阵概念应用举例

从行列式到矩阵概念的出现，历史上经过了100多年的时间。矩阵的本质就是一个矩形的数表，但是随着科学技术的进步，特别是计算机科学的发展，矩阵概念的应用日趋广泛。本节我们介绍矩阵概念应用的两个经典的例子，一是图像增强问题，另一个是空中交通线路问题，后者也涉及矩阵在图论应用中的一个著名的案例，即哥尼斯堡七桥问题。

一、图像增强问题

设有一张人物照片（如图2.1所示），因为某种原因，照片显得模糊，视觉效果不太好。在医学图像与航天航空等学科中常常需要分析图片不够清晰的原因，并且采用适当的方法加以增强处理。

现在我们用MATLAB读取这一张图片，假设图像文件的名称为“儿童.tif”，那么MATLAB中的函数命令X=imread（儿童.tif）就把该图片读取为一个矩形数表：

该数表是291×240大小的图片像素灰度矩阵（省略了矩阵两边的大括号）。为什么照片显得模糊？对此我们需要分析其像素灰度值的分布情况。使用MATLAB中的像素直方图统计函数imhist（X）对其灰度值进行统计，如图2.2所示。

图片像素灰度的最大范围是［0，255］。而该照片的像素灰度值仅分布在［74，224］之间，分布范围相对比较狭小，于是照片上不同区块灰度差异小，所以给人的感觉照片显得模糊不清。

图像处理的方法有很多。其中最简单的是对像素值做线性化的“拉伸”处理。即按照以下公式重新计算图像上每一点的像素灰度值

式中，Xij是原始照片上每一点的像素灰度值。并由此得到一个新的像素灰度值矩阵

对这个新的像素矩阵利用imhist（Y）函数重新做像素灰度值统计，如图2.3所示。

这时，做“拉伸”处理后的像素矩阵Y值的变化范围是［0，255］，灰度值分布在一个较大的范围。接着再利用MATLAB中的图像显示命令imshow（Y）把灰度矩阵数表Y显示为图像，如图2.4所示。

这样的图像处理方法通常叫做“图像增强”。因为照片像素灰度值分布范围增大，使得照片看起来要清晰一些。

在这个过程中我们能看到或者说感觉到的是图像的变化，其实它是对照片灰度值矩阵的一种统计增强处理。当然，如果希望获得更好的处理效果，还可以采用像素灰度的非线性变换，空间滤波甚至多光谱变换等更多的技术手段。不论采用什么样的处理方法，我们都已经了解到在计算机科学中，图像的表达与处理总离不开矩阵概念，离不开数学方法，这一点是毋庸置疑的。

二、空中交通线路问题

考虑5个城市之间的飞行交通问题，见图2.5。城市用数字1～5来代表，也叫交通网络的节点。当两个城市之间有一条飞行航线时，那么就在图的两个顶点之间画一条有向弧线。

这种以顶点代表城市，以弧线边代表两个城市之间的飞行线路的表达方法称之为一个图，记为G（V，A），其中V是图的顶点集，A是图的边集，边也叫弧。有一个数学学科叫图论学就是专门研究图论问题的。

一个图的信息怎么样完整、简便地记录呢？

1.邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。具体定义是：有n个顶点的图G（V，A）的邻接矩阵C是一个n×n的0-1矩阵，规定为

也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。

由此上述交通图就有相应的邻接矩阵

可以看出，这种矩阵表示法非常简单、直接。如果一个图是无向图，即任何两个顶点之间的弧线没有方向性限制，则该图的邻接矩阵就是一个n阶的实对称矩阵。

邻接矩阵表示法方便于对网络图做进一步的分析研究。例如，对任意i（i=1，2，…，n），把矩阵C的第i行元素相加，就得到从图的第i个顶点出发的所有弧的个数，也叫第i个顶点vi的出度；同样对任意j（j=1，2，…，n），把矩阵C的第j列元素相加，就得到到达或者指向图的第j个顶点vj的弧的个数，也叫第j个顶点vj的入度。对于一个无向图来说，与每个顶点连接的弧线数，又简称为该顶点的度数。

在邻接矩阵的所有n2个元素中，设只有m个为非零元。如果网络比较稀疏，即m≪n，这种表示法也会浪费大量的存储空间，增加在网络中查找弧的时间。

现在的问题是：如果这n个城市的飞行售票系统由一家网络公司代理，试问该网络公司最多需要为所有航线设计多少种不同样式的飞机票面？

2.线路计算问题求解

任意两个城市之间的飞行线路除了两地直达外，也有可能经由第三地中转。在任意两个城市之间，假设除了两地直达航线外，我们约定仅考虑经由某地一转或者经由其它两个城市二转的情况。每一种不同的飞行线路，当然就对应一种不同样式的飞机票面。

那么上述空中交通问题，总共有多少种不同的飞行线路呢？

我们这样来做：首先求邻接矩阵C的平方矩阵

矩阵C与C2，它们元素的实际意义分别是什么？首先，C矩阵的元素cij等于1或0，就表示从城市i到城市j，有没有一条直达线路，这是很明显的。矩阵C2=C·C的元素记为dij（i=1，2，…，n；j=1，2，…，n），由矩阵乘法定义，有

例如，元素d52=1，这是因为C矩阵的第五行元素中c53=1，同时C矩阵的第二列元素中对应序号的元素c32=1，于是d52=c53·c32=1。这说明从城市5到城市2之间，经由第三地城市k=3是可以一转到达的。

但是需要指出，矩阵C2的主对角线上的元素，例如d44=1，显然表示城市4与某个其他城市之间存在往返直达折返回到该城市本身的线路，而这种直达线路已经体现在C矩阵的非零元素中了。换句话说，因为根本不需考虑任何城市到自己本身的飞行航线，所以计算不同两地之间飞行线路时，矩阵C2的主对角线上的非零元素无需考虑。于是记

再计算矩阵C的3次方矩阵（的一种变化形式）

矩阵的非零元素，例如e42=1，因为

它表示在城市4与城市2之间，从城市4到城市k=5有一条直达线路，而从城市k=5到城市2之间有一条一转线路。合起来，从城市4与城市2也就有一条二转线路。

同样，矩阵的主对角线上的非零元素也是不必去考虑的，又记

如此，在一个复杂的网络图中，如果从节点vi到vj之间没有直达线路，那么至少经过多少次中转才可以到达呢？回答是就看图的连接矩阵C的方次，其对应的（i，j）位置上的元素什么时候不等于零，则两个节点间就有最少经过几次（方次减1）中转的线路。

接着，求以上几个方次矩阵的和矩阵

用MATLAB中的函数命令，对矩阵A的所有元素求和，得到

sum _ A=sum（sum（A））=27

即在这n个城市的飞行售票系统中，城市节点之间所有的直达线路与一转和二转线路总和为27条，即售票代理公司最多需要为所有航线设计27种不同样式的飞机票面。

三、哥尼斯堡七桥问题

有了网络图的邻接矩阵，我们还可以去研究著名的“哥尼斯堡七桥问题”，它是图论学中一个经典的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，如图2.6所示。问题是要从这四块陆地中的任何一块出发，通过每一座桥正好一次，再回到起点。

当然可以通过试验法去尝试解决这个问题，但该城居民的任何尝试均未成功。瑞士数学家欧拉（L.Euler，1707～1783）为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“无向图”。问题也就成为从任一点出发一笔画出七条线再回到起点，也叫图的“一笔画”问题。

若将该图的顶点从A到D分别标记记为数字1～4，则不难给出图的邻接矩阵

欧拉考察了一般一笔画图的结构特点，给出了一笔画图的一个判定法则：这个图是连通的，且每个点都与偶数条弧线相关联，就是前面提到的图上每一个顶点的度数必须都是偶数。

将这个判定法则应用于七桥问题，事实上邻接矩阵（对称矩阵）元素按行分别相加，得到每个顶点的度数，其中第1、第2个顶点的度数均为奇数，就得到了“不可能走通”的结论。欧拉不但彻底解决了问题，而且开创了图论学研究的先河。

如果在网络图的邻接矩阵C中，其元素不是1或0，而是两地之间的距离，即

式中，元素+∞代表两地之间没有直达线路。这样的矩阵D就称为带权的邻接矩阵。有了带权的邻接矩阵，我们就可以在复杂的网络图中，解决任何两地之间的最短距离计算等问题。

在图像与图论等领域中类似的实际问题探讨中，如果没有矩阵概念，问题就无法表达，更无法去研究。可见矩阵概念与理论是多么的重要啊。