圖的鄰接矩陣的教學設(shè)計

廖云華 劉建剛 謝小良

摘 要：鄰接矩陣不僅是代數(shù)圖論的基石，也是圖論與計算機程序間的橋梁，因此鄰接矩陣具有重要的意義。但一般運籌學教材中對鄰接矩陣只是簡單介紹其概念，學生感覺不到鄰接矩陣的重要性，更不知道如何應用鄰接矩陣去解決運籌學和圖論中的問題。為了讓學生更好地理解和掌握鄰接矩陣，我們對鄰接矩陣教學內(nèi)容進行了設(shè)計，在教學實踐中取得好的效果。

關(guān)鍵詞：鄰接矩陣;圖的矩陣表示;運籌學

中圖分類號：G4 文獻標識碼：Adoi：10.19311/j.cnki.16723198.2021.06.071

任給一個圖，都存在唯一的鄰接矩陣與之對應;反之，任給一個鄰接矩陣，也存在唯一的圖與之對應。所以，圖與鄰接矩陣之間具有一一對應關(guān)系。由于矩陣在計算機中可以用一個二維數(shù)組表示，于是一個圖也就可以在計算機中用一個二維數(shù)組表示，使得能夠利用計算機編程解決一些困難的圖論問題，例如著名的四色定理。鄰接矩陣在圖論與計算機程序之間架設(shè)了橋梁，具有重要的理論意義和應用價值。本文擬對鄰接矩陣的性質(zhì)與應用進行教學設(shè)計，提升鄰接矩陣的教學效果。

1 鄰接矩陣的概念與性質(zhì)

鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。G是一個圖，V（G）為G的頂點集，E（G）為G的邊集。設(shè)G中有n個頂點v1，v2，…，vn;A=aijn×n為圖G的鄰接矩陣，其中，

aij=1，vivj∈E（G）;0，vivjE（G）.

鄰接矩陣具有下面幾個重要性質(zhì)。

性質(zhì)1 設(shè)A為圖G的鄰接矩陣，則圖G中頂點vi，vj之間長為k的途徑的條數(shù)等于Ak中的i行j列元素akij。

性質(zhì)2A2中的（i，i）元是頂點vi的度;A3中的（i，i）元是包含頂點vi的三角形的數(shù)目的二倍;A3的跡圖G中的三角形的數(shù)目的六倍。

2 鄰接矩陣的應用

一個農(nóng)夫帶著一只狼，一只羊和一筐白菜，欲從河和北岸坐船到南岸。由于船太小，農(nóng)夫每次最多只能帶一樣東西過河。如果沒有農(nóng)夫看管的話，狼會吃羊，羊會吃白菜，但狼不會吃白菜。設(shè)計一個方案，使農(nóng)夫能將所有東西運過河。

農(nóng)夫過河問題是一個經(jīng)典的算法設(shè)計問題，但在這里我們使用圖論中的鄰接矩陣來解決這個問題。首先，對河流兩岸進行描述，設(shè)N表示北岸，S表示南岸。然后，對兩岸的狀態(tài)進行描述，可用4位二進制數(shù)順序分別表示農(nóng)夫、狼、羊和白菜的位置狀態(tài)，用0表示不在，1表示在。例如，（N1010）表示農(nóng)夫和羊在北岸，同時也表明狼和白菜在南岸。共有32個狀態(tài)，但根據(jù)題意，滿足狼、羊、菜三者之間都和平相處的安全狀態(tài)只有20個。由于只有農(nóng)夫能撐船，我們只需要考慮有農(nóng)夫的安全狀態(tài)，這樣的安全狀態(tài)只有如下10個：

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

以V=v1，v2，…，vn為頂點集，一次渡河前后南北兩岸的兩個狀態(tài)之間連邊，我們得到了各狀態(tài)間的關(guān)系示意圖（見圖1）。

該圖的鄰接矩陣為：

A=0A1A10

其中，

A1=0000100110001110011100100

由性質(zhì)1，我們應考慮最小的k，使得Ak中第6行1列的元素不為0，此時k為最少的渡河次數(shù)，Ak中第6行1列的元素為最佳路徑的數(shù)目。

經(jīng)過計算，k=7，此時A7中第6行1列的元素為2，所以需要7次渡河，有2條最佳路徑。然后，利用逆向搜索法，確定兩條最佳路徑為v1v10v3v7v4v8v5v6和v1v10v3v9v2v8v5v6。對應的方案分別為：

方案1：

v1N111帶羊去南岸v10S1010獨回北岸v3N1101帶狼去南岸v7S1110帶羊回北岸

v4N1011帶菜去南岸v8S1101獨回北岸v5N1010帶羊去南岸v6S1111

方案2：

v1N111帶羊去南岸v10S1010獨回北岸v3N1101帶菜去南岸v9S1011帶羊回北岸

v2N1110帶狼去南岸v8S1101獨回北岸v5N1010帶羊去南岸v6S1111

參考文獻

[1]劉亞國.圖論中鄰接矩陣的應用[J].忻州師范學院學報，2008，24（2）：1819.

[2]胡運權(quán)，郭耀煌.運籌學教程（第五版）[M].北京：清華大學出版社，2018.

[3]謝小良，王扉，唐玲，等.運籌學教程[M].北京：高等教育出版社，2013.

[4]徐俊明.圖論及其應用（第二版）[M].合肥：中國科學技術(shù)大學出版社，2010.