国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2021-02-04 07:20廖云華劉建剛謝小良
現(xiàn)代商貿(mào)工業(yè) 2021年6期
關(guān)鍵詞:鄰接矩陣運籌學(xué)

廖云華 劉建剛 謝小良

摘 要:鄰接矩陣不僅是代數(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.

猜你喜歡
鄰接矩陣運籌學(xué)
輪圖的平衡性
物流管理專業(yè)運籌學(xué)混合式課堂教學(xué)模式改革研究
消防車路徑優(yōu)化問題的研究
基于鄰接矩陣變型的K分網(wǎng)絡(luò)社團算法
運籌學(xué)課程教學(xué)改革問題研究
基于優(yōu)化軟件LINGO的運籌學(xué)案例實踐教學(xué)研究
淺談對運籌學(xué)專業(yè)教育的一些看法
Inverse of Adjacency Matrix of a Graph with Matrix Weights
占卜·廟算·軍事運籌——談軍事運籌學(xué)的歷史發(fā)展
談企管干部學(xué)習(xí)運籌學(xué)
纳雍县| 高要市| 周宁县| 高州市| 望奎县| 合阳县| 新昌县| 云南省| 秦皇岛市| 巴彦淖尔市| 泽州县| 长寿区| 安国市| 都昌县| 金乡县| 台山市| 郸城县| 临武县| 绍兴县| 江源县| 黑龙江省| 全南县| 泽州县| 班玛县| 营口市| 花莲县| 蓝山县| 白山市| 郁南县| 昔阳县| 江华| 新余市| 宣汉县| 吐鲁番市| 公主岭市| 黎平县| 华亭县| 滨海县| 图们市| 肇源县| 阳城县|