圖的鄰接矩陣的教學(xué)設(shè)計(jì)

廖云華 劉建剛 謝小良

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

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

中圖分類號(hào)：G4 文獻(xiàn)標(biāo)識(shí)碼：Adoi：10.19311/j.cnki.16723198.2021.06.071

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

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

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

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

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

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

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

2 鄰接矩陣的應(yīng)用

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

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

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

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

該圖的鄰接矩陣為：

A=0A1A10

其中，

A1=0000100110001110011100100

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

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

方案1：

v1N111帶羊去南岸v10S1010獨(dú)回北岸v3N1101帶狼去南岸v7S1110帶羊回北岸

v4N1011帶菜去南岸v8S1101獨(dú)回北岸v5N1010帶羊去南岸v6S1111

方案2：

v1N111帶羊去南岸v10S1010獨(dú)回北岸v3N1101帶菜去南岸v9S1011帶羊回北岸

v2N1110帶狼去南岸v8S1101獨(dú)回北岸v5N1010帶羊去南岸v6S1111

參考文獻(xiàn)

[1]劉亞國.圖論中鄰接矩陣的應(yīng)用[J].忻州師范學(xué)院學(xué)報(bào)，2008，24（2）：1819.

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

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

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