圖的鄰接矩陣及應用

論文編號:YYSX233  論文字數:4991,頁數:09

圖的鄰接矩陣及應用
 
[摘 要]  圖在現實生活中的應用無處不在，諸如運籌學，信息論，控制論，博弈論，計算機科學等都是以圖來解決實際問題和理論問題的。特別是計算機的誕生使得圖論本身也得到了很大的發展。本文從圖的基本問題路徑問題開始，用探究的方式從鄰接矩陣的角度總結出了一般性結論，并用歸納法做了嚴格的證明。在此基礎上，給出了圖的連通性等價條件，給出了具體的判定圖的連通性的方法，并給出了具體的例子，說明了用鄰接矩陣的方法研究圖的路徑問題和連通性問題可靠有效。
[關鍵詞] 鄰接矩陣  可達矩陣  連通性

 在現實世界中有許多現象、許多事物、許多狀態是用某種圖形來描述的。因此在很早人們就對圖有廣泛的研究，使得圖的理論十分豐富。隨著計算機科學的發展，圖論本身更得到了充分的發展。在圖的問題中，圖的連通性和兩點間路徑是一個基本的且在實際中經常遇到的問題，對這個問題的研究有多種方法，本文從圖的鄰接矩陣的角度對這個問題進行了探究。