第七節*　矩陣概念應用舉例

從行列式到矩陣概念的出現，歷史上經過了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就稱為帶權的鄰接矩陣。有了帶權的鄰接矩陣，我們就可以在復雜的網絡圖中，解決任何兩地之間的最短距離計算等問題。

在圖像與圖論等領域中類似的實際問題探討中，如果沒有矩陣概念，問題就無法表達，更無法去研究。可見矩陣概念與理論是多么的重要啊。