圖論與網(wǎng)絡(luò)最優(yōu)化算法

前言

　　圖論與網(wǎng)絡(luò)最優(yōu)化算法是一門提供離散數(shù)學(xué)模型的應(yīng)用數(shù)學(xué)學(xué)科。隨著計(jì)算機(jī)在社會(huì)中作用的變大，其應(yīng)用日益廣泛，應(yīng)用遍及系統(tǒng)工程、電工學(xué)、交通運(yùn)輸、城市規(guī)劃、生產(chǎn)管理、經(jīng)濟(jì)、通信、計(jì)算機(jī)等各個(gè)領(lǐng)域，人工智能、模式識(shí)別、計(jì)算機(jī)操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)等都涉及圖論?！　”窘滩牡膶W(xué)習(xí)主要有以下4個(gè)方面的作用：　　1.思維的體操。其中含有廣泛的數(shù)學(xué)思想和數(shù)學(xué)方法，諸如優(yōu)化、分類、數(shù)形結(jié)合、轉(zhuǎn)化的思想、分解的思想、歸納、演繹和逆推等。這是其他工科數(shù)學(xué)所無(wú)法比擬的，對(duì)培養(yǎng)我們的數(shù)學(xué)機(jī)敏性與成熟性大有益處?！　?.算法設(shè)計(jì)者的翅膀。圖論算法是算法設(shè)計(jì)與分析中的重要組成部分，其中包含常用的算法設(shè)計(jì)基本方法，如搜索技術(shù)、分支定界法、回溯法、貪婪法及各種啟發(fā)式算法，算法的時(shí)間復(fù)雜性分析，近似算法的近似程度分析也融入其中?！　?.綜合應(yīng)用能力形成的催化劑。書(shū)中幾乎每章末都有關(guān)于圖論理論和算法在實(shí)際中的各種應(yīng)用，也含有一些具有一定靈活性和創(chuàng)造性的應(yīng)用案例，配有大量頗具啟發(fā)性和趣味性的習(xí)題。圖論與代數(shù)、運(yùn)籌學(xué)密切相關(guān)，概率統(tǒng)計(jì)與網(wǎng)絡(luò)交叉有活動(dòng)網(wǎng)絡(luò)，這些都有助于我們綜合運(yùn)用數(shù)學(xué)能力的提高。圖論中的圖具有最復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，如果將其中的算法編程實(shí)現(xiàn)，編程能力可上一個(gè)新的臺(tái)階?！　?.描述和解決離散問(wèn)題的有利工具。在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、通信和電力領(lǐng)域經(jīng)常能看到許多網(wǎng)絡(luò)，如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計(jì)算機(jī)通信網(wǎng)及輸電線網(wǎng)等。還有許多看不見(jiàn)的網(wǎng)絡(luò)，各種關(guān)系網(wǎng)，如狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時(shí)間先后次序關(guān)系等，這些網(wǎng)絡(luò)都可歸結(jié)為圖論的研究對(duì)象——圖。其中存在大量問(wèn)題，如生產(chǎn)計(jì)劃、投資計(jì)劃和設(shè)備更新等問(wèn)題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問(wèn)題，這些都可借助于圖論這個(gè)工具來(lái)加以解決。

內(nèi)容概要

本書(shū)共分9章：圖與網(wǎng)絡(luò)的基本概念、樹(shù)及其算法、連通性、路徑算法、匹配、行遍性問(wèn)題、平面圖、圖的著色及網(wǎng)絡(luò)流問(wèn)題。其中包含較豐富的實(shí)際應(yīng)用案例與算例，每章末均附有較多難易程度不同的習(xí)題，另外還附有少量涉及網(wǎng)絡(luò)建模與計(jì)算的大型綜合應(yīng)用題。    本書(shū)是一本理論與應(yīng)用相結(jié)合的基礎(chǔ)教材，可作為高等工科院校系統(tǒng)工程、管理工程、自動(dòng)控制、通信與計(jì)算機(jī)科學(xué)、城市規(guī)劃等專業(yè)高年級(jí)本科生或研究生的教材和教學(xué)參考書(shū)，也可供有關(guān)專業(yè)的科研人員自學(xué)。

書(shū)籍目錄

第一章  圖與網(wǎng)絡(luò)的基本概念  §1  緒論  §2  一些基本概念  §3  圖的矩陣表示  §4  圖在計(jì)算機(jī)中的存儲(chǔ)  §5  計(jì)算復(fù)雜性與算法  習(xí)題1第二章  樹(shù)  §1  路徑與連通  §2  有向圖的連通  §3  圖的搜索  §4  樹(shù)及其性質(zhì)  §5  生成樹(shù)算法  §6  有向樹(shù)  習(xí)題2第三章  連通性  §1  連通度  §2  割邊、割集、割點(diǎn)  §3  塊與塊劃分  §4  可靠網(wǎng)絡(luò)的設(shè)計(jì)  習(xí)題3第四章  路徑算法  §1  最短路徑問(wèn)題  §2  最短路徑問(wèn)題的一些擴(kuò)展  §3  最優(yōu)路徑  §4  關(guān)鍵路徑  §5  最短路徑算法的應(yīng)用  習(xí)題4第五章  匹配  §1  匹配的概念  §2  匹配基本定理  §3  二部圖的最大基數(shù)匹配  §4  二部圖的最大權(quán)匹配  §5  一般圖的最大權(quán)匹配  §6  一般圖的最大權(quán)匹配  §7  匹配的應(yīng)用  習(xí)題5第六章  行遍性問(wèn)題  §1  歐拉圖  §2  中國(guó)郵遞員問(wèn)題  §3  有向歐拉圖  §4  中國(guó)郵遞員問(wèn)題的應(yīng)用與推廣  §5  哈米爾頓圖  §6  有向哈米爾頓圖  §7  哈米爾頓圖的尋跡  §8  流動(dòng)推銷員問(wèn)題  §9  TSP的近似算法  §10  TPS的分枝定界法  §11  旅行推銷員問(wèn)題的應(yīng)用  習(xí)題6第七章  平面圖  §1  平面圖的概念  §2  歐拉公式  §3  平面圖的對(duì)偶圖  §4  庫(kù)拉托夫斯基定理  §5  可平面性算法  §6  圖的交叉和厚度  習(xí)題7第八章  圖的著色  §1  邊色數(shù)  §2  時(shí)間表問(wèn)題  §3  支配集與獨(dú)立集  §4  支配數(shù)、覆蓋數(shù)和獨(dú)立數(shù)的計(jì)算  §5  支配集與獨(dú)立集的應(yīng)用  §6  點(diǎn)色數(shù)  §7  色多項(xiàng)式  §8  色數(shù)的應(yīng)用和算法  習(xí)題8第九章  網(wǎng)絡(luò)流問(wèn)題  §1  流與截集  §2  最大流最小截集定理  §3  ford和fulkcrson標(biāo)記法  §4  Dinits法  §5  最大流問(wèn)題的應(yīng)用與推廣  §6  最小費(fèi)用流  §7  有向圖的中國(guó)郵遞員問(wèn)題  習(xí)題9參考文獻(xiàn)

章節(jié)摘錄

　　利用圖論的方法解決實(shí)際問(wèn)題時(shí)，通常要借助于計(jì)算機(jī)。怎樣把圖的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)里是一個(gè)首先要解決的問(wèn)題，一般是根據(jù)具體的圖以及將要做的運(yùn)算來(lái)選擇適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)，下面介紹幾種常用的存儲(chǔ)結(jié)構(gòu)?！　?.4.1鄰接矩陣　　用鄰接矩陣表示圖，較容易判定兩個(gè)頂點(diǎn)之間是否有邊相連，也容易求出各頂點(diǎn)的次數(shù)。鄰接矩陣可用二維數(shù)組來(lái)表示，如果是無(wú)向圖，由于對(duì)稱性，僅需存人上三角矩陣?！　∴徑泳仃嚨闹饕秉c(diǎn)是占用的空間較大，要占用O（n2）空間（n為圖的頂點(diǎn)數(shù)），而且用直接法將鄰接矩陣初始化也將占用較多的時(shí)間，因而很難改進(jìn)算法的時(shí)間復(fù)雜性與空間復(fù)雜性的量級(jí)?！　?duì)無(wú)重邊的圖，其鄰接矩陣是（0，1）矩陣，一種有效的改進(jìn)方法是用二進(jìn)制位向量來(lái)表示一個(gè)鄰接矩陣的行（或列），有的編程語(yǔ)言提供了“位操作”運(yùn)算，如“與”“或”“非”和“異或”等。因此，可以把一個(gè)機(jī)器字看成不是一個(gè)“數(shù)”，而是每一位是互相獨(dú)立的向量，這樣的機(jī)器字是一個(gè)二進(jìn)制的位向量，用來(lái)表示鄰接矩陣的行（或列），若對(duì)其進(jìn)行位操作，運(yùn)算速度要快得多。位向量的數(shù)據(jù)結(jié)構(gòu)也有缺點(diǎn)，當(dāng)行的元素?cái)?shù)目大于計(jì)算機(jī)字長(zhǎng)時(shí)，要用兩個(gè)以上的機(jī)器字聯(lián)合表示，運(yùn)算就不方便了?！　?.4.2關(guān)聯(lián)矩陣　　用關(guān)聯(lián)矩陣表示圖，能迅速指出與某一頂點(diǎn)v關(guān)聯(lián)的是哪些邊，而且還可指出某條邊關(guān)聯(lián)的是哪兩個(gè)頂點(diǎn)，對(duì)于有風(fēng)吹草動(dòng)圖還能區(qū)分出入次和出次。關(guān)聯(lián)矩陣一般是用一個(gè)二維數(shù)組Mnm來(lái)表示，這需要很大的存儲(chǔ)空間，如存入一個(gè)100個(gè)頂點(diǎn)、500條邊的圖，則需近50K的內(nèi)存，而其中很多元素是零。特別是稀疏矩陣，空間的浪費(fèi)相當(dāng)大。不過(guò)如果空間不緊張，這種存儲(chǔ)方式還是可取的，因?yàn)樗色@得時(shí)間高效的算法，空間的損失可從時(shí)間的獲益得到補(bǔ)償，但是空間不夠，可采用比較緊湊的數(shù)據(jù)結(jié)構(gòu)，然后通過(guò)運(yùn)算，轉(zhuǎn)換成關(guān)聯(lián)矩陣，當(dāng)然，有時(shí)當(dāng)關(guān)聯(lián)矩陣是（0，1）矩陣時(shí)，也可用二進(jìn)制位向量來(lái)表示關(guān)聯(lián)矩陣的行（或列）。

編輯推薦

　　圖論與網(wǎng)絡(luò)最優(yōu)化算法是一門提供離散數(shù)學(xué)模型的應(yīng)用數(shù)學(xué)學(xué)科。隨著計(jì)算機(jī)在社會(huì)中作用的變大，其應(yīng)用日益廣泛，應(yīng)用遍及系統(tǒng)工程、電工學(xué)、交通運(yùn)輸、城市規(guī)劃、生產(chǎn)管理、經(jīng)濟(jì)、通信、計(jì)算機(jī)等各個(gè)領(lǐng)域，人工智能、模式識(shí)別、計(jì)算機(jī)操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)等都涉及圖論?！　”緯?shū)則主要向你介紹了圖與網(wǎng)絡(luò)的基本概念、樹(shù)及其算法、連通性、路徑算法、匹配、行遍性問(wèn)題、平面圖、圖的著色及網(wǎng)絡(luò)流問(wèn)題。其中包含較豐富的實(shí)際應(yīng)用案例與算例。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    圖論與網(wǎng)絡(luò)最優(yōu)化算法 PDF格式下載

---