廖云華 劉建剛 謝小良
摘 要:鄰接矩陣不僅是代數(shù)圖論的基石,也是圖論與計算機程序間的橋梁,因此鄰接矩陣具有重要的意義。但一般運籌學(xué)教材中對鄰接矩陣只是簡單介紹其概念,學(xué)生感覺不到鄰接矩陣的重要性,更不知道如何應(yīng)用鄰接矩陣去解決運籌學(xué)和圖論中的問題。為了讓學(xué)生更好地理解和掌握鄰接矩陣,我們對鄰接矩陣教學(xué)內(nèi)容進行了設(shè)計,在教學(xué)實踐中取得好的效果。
關(guān)鍵詞:鄰接矩陣;圖的矩陣表示;運籌學(xué)
中圖分類號:G4 文獻標識碼:Adoi:10.19311/j.cnki.16723198.2021.06.071
任給一個圖,都存在唯一的鄰接矩陣與之對應(yīng);反之,任給一個鄰接矩陣,也存在唯一的圖與之對應(yīng)。所以,圖與鄰接矩陣之間具有一一對應(yīng)關(guān)系。由于矩陣在計算機中可以用一個二維數(shù)組表示,于是一個圖也就可以在計算機中用一個二維數(shù)組表示,使得能夠利用計算機編程解決一些困難的圖論問題,例如著名的四色定理。鄰接矩陣在圖論與計算機程序之間架設(shè)了橋梁,具有重要的理論意義和應(yīng)用價值。本文擬對鄰接矩陣的性質(zhì)與應(yīng)用進行教學(xué)設(shè)計,提升鄰接矩陣的教學(xué)效果。
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 鄰接矩陣的應(yīng)用
一個農(nóng)夫帶著一只狼,一只羊和一筐白菜,欲從河和北岸坐船到南岸。由于船太小,農(nóng)夫每次最多只能帶一樣?xùn)|西過河。如果沒有農(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,我們應(yīng)考慮最小的k,使得Ak中第6行1列的元素不為0,此時k為最少的渡河次數(shù),Ak中第6行1列的元素為最佳路徑的數(shù)目。
經(jīng)過計算,k=7,此時A7中第6行1列的元素為2,所以需要7次渡河,有2條最佳路徑。然后,利用逆向搜索法,確定兩條最佳路徑為v1v10v3v7v4v8v5v6和v1v10v3v9v2v8v5v6。對應(yīng)的方案分別為:
方案1:
v1N111帶羊去南岸v10S1010獨回北岸v3N1101帶狼去南岸v7S1110帶羊回北岸
v4N1011帶菜去南岸v8S1101獨回北岸v5N1010帶羊去南岸v6S1111
方案2:
v1N111帶羊去南岸v10S1010獨回北岸v3N1101帶菜去南岸v9S1011帶羊回北岸
v2N1110帶狼去南岸v8S1101獨回北岸v5N1010帶羊去南岸v6S1111
參考文獻
[1]劉亞國.圖論中鄰接矩陣的應(yīng)用[J].忻州師范學(xué)院學(xué)報,2008,24(2):1819.
[2]胡運權(quán),郭耀煌.運籌學(xué)教程(第五版)[M].北京:清華大學(xué)出版社,2018.
[3]謝小良,王扉,唐玲,等.運籌學(xué)教程[M].北京:高等教育出版社,2013.
[4]徐俊明.圖論及其應(yīng)用(第二版)[M].合肥:中國科學(xué)技術(shù)大學(xué)出版社,2010.