圖論算法及其MATLAB實現(xiàn)

前言

　　圖論算法廣泛應(yīng)用于物理、化學(xué)、運籌學(xué)、計算機科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、管理科學(xué)、社會科學(xué)等眾多學(xué)科領(lǐng)域。隨著這些學(xué)科的發(fā)展，特別是計算機科學(xué)的快速發(fā)展，又大大促進(jìn)了圖論和其他學(xué)科的發(fā)展。　　圖論算法是計算機科學(xué)的核心。近幾年，隨著強有力的MATLAB等數(shù)學(xué)軟件的迅速發(fā)展，圖論算法在數(shù)學(xué)和計算機等各學(xué)科方面的應(yīng)用越來越廣泛，從而使各學(xué)科的研究者越來越多地重視圖論算法及其MATLAB實現(xiàn)和典型案例，而市場上又缺少這方面的指導(dǎo)性書籍?！　”緯鴮D論的基礎(chǔ)知識、圖論的著名問題以及相應(yīng)的MATI.AB程序代碼和簡單實例完美地結(jié)合在一起，力求語言簡潔易懂，問題廣泛有趣，算法科學(xué)，實例淺顯，增強MATLAB實現(xiàn)的技巧性和操作性。讀者可以通過簡單案例，把圖論的重要算法與MALLAB編程完美結(jié)合?！　”緯η髢?nèi)容豐富，各章節(jié)相互聯(lián)系，具備指導(dǎo)性書籍的系統(tǒng)性、科學(xué)性、實用性和引導(dǎo)性；同時，各章又相對獨立，自成體系，為讀者提供極大方便。　　本書的創(chuàng)新之處在于，每一章均以著名實際問題為引入點，以圖論算法為指導(dǎo)線，運用簡單案例達(dá)到與MATLAB實現(xiàn)的完美結(jié)合，真正讓各層次的讀者學(xué)會運用圖論理論解決實際問題，從而培養(yǎng)讀者的圖論思維，使讀者驚嘆圖論方法的美妙與魅力。最后還為讀者提供了當(dāng)今圖論標(biāo)號方面等未解決的問題?！　”緯鴮⒃诿恳徽鹿?jié)中給出著名圖論的算法步驟及其一般MATLAB程序；同時，緊隨每個案例分析，均給出解決問題的。MATLAB源程序，這樣對于初學(xué)者來說，具有很強的編程操作性?！　”緯窃谥袊刭|(zhì)大學(xué)（北京）王海英多年專業(yè)講義的基礎(chǔ)上重新修訂編寫而成，其中，山東體育學(xué)院體育運動學(xué)校的李傳濤完成了本書程序的編寫工作；中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)院的黃強完成了本書全部程序的調(diào)試、修改和圖形繪制等工作，褚寶增教授完成全書的定稿和校正工作。作者相信，此書將開啟圖論算法與MATLAB完美結(jié)合的首頁，也將為更多有實際需求的讀者提供更多的指導(dǎo)?！　∈指兄x中國地質(zhì)大學(xué)（北京）2008年教學(xué)研究與教學(xué)改革立項的支持（項目題目：數(shù)學(xué)知識、數(shù)學(xué)建模與MATIAB等數(shù)學(xué)軟件在實踐中相互結(jié)合的理論研究）！感謝北京航空航天大學(xué)出版社的認(rèn)可、建議和關(guān)心！此外，本文的算法思想均離不開古今中外圖論算法研究的完美理論與應(yīng)用，感謝這些圖論研究者們！

內(nèi)容概要

本書系統(tǒng)介紹了圖論重要算法的思想及其MATLAB實現(xiàn)。    全書分為相對獨立的9章，每章都是解決一類問題的算法思想及其MATLAB實現(xiàn)，首先介紹有關(guān)基礎(chǔ)知識，然后給出相關(guān)著名實際問題及解決此問題的算法思想，最后給出MATLAB實現(xiàn)。第1章主要介紹圖論的基礎(chǔ)知識，同時也給出了可達(dá)矩陣的計算，以及關(guān)聯(lián)矩陣和鄰接矩陣的相互轉(zhuǎn)換等重要算法及其MATLAB實現(xiàn)；第2～8章分別介紹最短路、連通圖、樹、Euler圖和Hamilton圖、匹配、網(wǎng)絡(luò)中的流、最小費用流等相關(guān)問題，而且均給出了有關(guān)問題的解決算法及其MATLAB實現(xiàn)；第9章主要介紹染色問題，本章不僅介紹了幾種傳統(tǒng)的染色思想，而且還給出了當(dāng)今研究領(lǐng)域中非?；钴S的非傳統(tǒng)染色思想，并分別給出其MATLAB實現(xiàn)。    本書可供數(shù)學(xué)、計算機科學(xué)、工程科學(xué)等學(xué)科中相關(guān)專業(yè)的大學(xué)生、研究生閱讀，也可供相關(guān)專業(yè)研究人員參考。

書籍目錄

第1章　圖論的基礎(chǔ)知識　1.1　圖論的起源　1.2　著名的圖論學(xué)者——歐拉　1.3　圖　1.4　特殊圖類　1.5　有向圖　1.6　圖的矩陣表示　　1.6.1　鄰接矩陣　　1.6.2　關(guān)聯(lián)矩陣　1.7　圖論的基本性質(zhì)和定理　1.8　計算有向圖的可達(dá)矩陣的算法及其MATLAB實現(xiàn)　1.9　關(guān)聯(lián)矩陣和鄰接矩陣的相互轉(zhuǎn)換算法及其MATLAB實現(xiàn)　習(xí)題一第2章 最短路　2.1　路　2.2　最短路問題　2.3　求連通圖最短距離矩陣的算法及其MATLAB實現(xiàn)　2.4　求兩點間最短路的Dijkstra算法及其MATLAB實現(xiàn)　　2.4.1　Dijkstra算法　　2.4.2　Dijkstra算法的MATLAB實現(xiàn)　2.5　求兩點間最短路的改進(jìn)的Dijkstra算法及其MATLAB實現(xiàn)　　2.5.1　Dijkstra矩陣算法Ⅰ　　2.5.2　Dijkstra矩陣算法Ⅱ　2.6　求兩點間最短路的WarshallFloyd算法及其MATLAB實現(xiàn)　　2.6.1　Floyd算法的基本思想　　2.6.2　Floyd算法的基本步驟　　2.6.3　WarshallFloyd算法的MATLAB實現(xiàn)　2.7　求任意兩點間最短路的算法及其MATLAB實現(xiàn)　2.8　求從一固定點到其他所有點最短路的算法及其MATLAB實現(xiàn)　2.9　求必須通過指定兩個點的最短路的算法及其MATLAB實現(xiàn)　2.10　求圖的兩頂點間最短路與次短路的算法及其MATLAB實現(xiàn)　2.11　求最大可靠路的算法及其MATLAB實現(xiàn)　2.12　求最大期望容量路的算法及其MATLAB實現(xiàn)　習(xí)題二第3章 連通圖　3.1　判斷圖的連通性算法及其MATLAB實現(xiàn)　3.2　連通圖的中心和加權(quán)中心的算法及其MATLAB實現(xiàn)　3.3　連通無向圖一般中心的算法及其MATLAB實現(xiàn)　習(xí)題三第4章　樹　4.1　樹及其性質(zhì)　4.2　割點、割邊、割集　4.3　二元樹與Huffman樹　　4.3.1　有序二元樹　　4.3.2　Huffman樹　4.4　求Huffman樹及其MATLAB實現(xiàn)　4.5　廣度優(yōu)先搜索算法及其MATLAB實現(xiàn)　4.6　深度優(yōu)先搜索算法及其MATLAB實現(xiàn)　4.7　求割點算法及其MATLAB實現(xiàn)　4.8　生成樹及其個數(shù)　4.9　求無向圖的生成樹算法及其MATLAB實現(xiàn)　4.10　求有向圖的生成樹算法及其MATLAB實現(xiàn)　4.11　求有向連通圖的外向樹與內(nèi)向樹數(shù)目的算法及其MATLAB實現(xiàn)　4.12　最小生成樹問題　4.13　求最小生成樹的Kruskal算法及其MATLAB實現(xiàn)　　4.13.1　Kruskal算法的基本思想　　4.13.2　Kruskal算法的MATLAB實現(xiàn)　4.14　求最小生成樹的Prim算法及其MATLAB實現(xiàn)　　4.14.1　Prim算法的基本思想　　4.14.2　Prim算法的MATLAB實現(xiàn)　習(xí)題四第5章　Euler圖和Hamilton圖第6章 匹配問題及其算法第7章 網(wǎng)絡(luò)流的算法第8章 最小費用流及BusackerGowan迭代算法第9章 圖的染色參考文獻(xiàn)

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    圖論算法及其MATLAB實現(xiàn) PDF格式下載

---