圖論與網(wǎng)絡(luò)流理論

前言

　　圖論是研究集合元素間二元關(guān)系的學(xué)科分支，這種關(guān)系可用拓?fù)鋱D形來(lái)表示。圖論研究這些拓?fù)鋱D形的各種結(jié)構(gòu)性質(zhì)，如連通性、可遍行性、可平面性、匹配性質(zhì)、染色性質(zhì)、某些特殊結(jié)構(gòu)、特殊的頂點(diǎn)子集和邊子集以及圖形上流的性質(zhì)?！　v經(jīng)數(shù)百年的發(fā)展，特別是得益于計(jì)算機(jī)科學(xué)和信息科學(xué)的有力推動(dòng)，圖論與網(wǎng)絡(luò)流理論已形成了一門(mén)既有趣又有用、既成熟又活躍的學(xué)科分支，其理論自成一體，不需要大量的預(yù)備知識(shí)，各組成部分有關(guān)聯(lián)，但又相互獨(dú)立，具有自己典型的方法，內(nèi)容充滿(mǎn)思想性和技巧性，是十分適合進(jìn)行邏輯思維訓(xùn)練的“智力體操”。許多易懂不易解的難題，形成了圖論與網(wǎng)絡(luò)流理論的獨(dú)特魅力，對(duì)研究者和學(xué)習(xí)者具有巨大的挑戰(zhàn)性。圖論與網(wǎng)絡(luò)流理論的應(yīng)用十分廣泛，在運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)與技術(shù)、信息科學(xué)、生命科學(xué)、自動(dòng)控制、工程建設(shè)以及能源、交通、電子、通信、化學(xué)、物流、管理、社會(huì)科學(xué)等眾多領(lǐng)域都能找到其應(yīng)用范例。圖論與網(wǎng)絡(luò)流理論中有大量典型的模型和算法，是許多學(xué)科中值得借鑒的模型庫(kù)和算法基礎(chǔ)。圖論與網(wǎng)絡(luò)流理論中有大量的ⅣP一難解問(wèn)題，因而它是算法理論和設(shè)計(jì)的重要參照系和試驗(yàn)田。　　本書(shū)是圖論與網(wǎng)絡(luò)流理論的一本入門(mén)讀物，書(shū)中較為系統(tǒng)地闡述圖論與網(wǎng)絡(luò)流理論的基本概念、方法和定理，介紹該領(lǐng)域一些重要的問(wèn)題以及典型的算法，展示圖論與網(wǎng)絡(luò)流理論模型與方法的廣泛應(yīng)用，試圖為學(xué)習(xí)者從事有關(guān)方面的理論研究打下基礎(chǔ)，也為進(jìn)行應(yīng)用研究的讀者提供一種有力的工具。　　本書(shū)根據(jù)筆者多年為研究生授課的講義整理編寫(xiě)而成。成書(shū)時(shí)盡量考慮了內(nèi)容的多學(xué)科適用性，力求深入淺出，既照顧初學(xué)者的入門(mén)需要，又考慮研究者的需求，既重視理論分析，又注意應(yīng)用舉例和內(nèi)容延伸，既體現(xiàn)數(shù)學(xué)推理的嚴(yán)密性，又展示算法設(shè)計(jì)與分析的靈活性，基礎(chǔ)知識(shí)的闡述與應(yīng)用技巧的介紹并重。在選材和內(nèi)容編排上力求系統(tǒng)全面，做到主體內(nèi)容精煉、外延廣泛。在文字表述上力求條理清晰、通俗易懂?！　”緯?shū)立足基礎(chǔ)、面向研究和應(yīng)用前沿。幾乎每一章都是一個(gè)研究專(zhuān)題，在相應(yīng)章節(jié)中指出重要的研究方向，并配有大量反映最新研究進(jìn)展和成果的參考文獻(xiàn)，以便讀者可以從入門(mén)很快進(jìn)入到該專(zhuān)題的研究前沿。

內(nèi)容概要

本書(shū)系統(tǒng)地闡述圖論與網(wǎng)絡(luò)流理論的基本概念、方法和定理，介紹該領(lǐng)域重要的問(wèn)題以及典型的算法，展示圖論與網(wǎng)絡(luò)流模型及方法的廣泛應(yīng)用。全書(shū)立足基礎(chǔ)、兼顧理論與應(yīng)用，選材精煉，貼近研究和應(yīng)用前沿，注重思想和方法。主要內(nèi)容包括圖的基本概念、最短路及最小生成樹(shù)、連通性、匹配、Euler圖、Hamilton圖、支配集、獨(dú)立集、覆蓋集、圖的染色、平面圖、有向圖、網(wǎng)絡(luò)流等方面的理論與算法。每章配有大量習(xí)題和前沿性的專(zhuān)題參考文獻(xiàn)。    本書(shū)可作為數(shù)學(xué)、運(yùn)籌學(xué)、系統(tǒng)科學(xué)各專(zhuān)業(yè)碩士研究生或本科高年級(jí)學(xué)生的教材或參考書(shū)，也可供物理學(xué)、化學(xué)、生命科學(xué)、計(jì)算機(jī)科學(xué)與技術(shù)、電子科學(xué)與技術(shù)、信息科學(xué)與網(wǎng)絡(luò)工程、資源與環(huán)境、物流與交通運(yùn)輸、管理科學(xué)與工程、過(guò)程工程、自動(dòng)控制等學(xué)科專(zhuān)業(yè)的本科生、研究生使用，還可供相關(guān)領(lǐng)域的科研工作者、廣大圖論愛(ài)好者參考。

書(shū)籍目錄

第一章  圖的基本概念  §1.1  圖的基本概念  §1.2  最短路問(wèn)題  §1.3  樹(shù)及其性質(zhì)  §1.4  生成樹(shù)與最小生成樹(shù)  §1.5  圖的中心與中位點(diǎn)  §1.6  圖的矩陣表示  習(xí)題一  參考文獻(xiàn)第二章  圖的連通性  §2.  1割點(diǎn)和割邊  §2.2  連通度和邊連通度  §2.3  2連通圖的性質(zhì)  §2.4  Menger定理  §2.5  可靠通信網(wǎng)絡(luò)的設(shè)計(jì)  習(xí)題二  參考文獻(xiàn)第三章  匹配理論  §3.1  匹配與最大匹配  §3.2  完美匹配  §3.3  二部圖的匹配  §3.4  二部圖中最大匹配與最大權(quán)匹配的算法  習(xí)題三  參考文獻(xiàn)第四章  Euler圖與Hamilton圖  §4.1  Euler圖  §4.2  中國(guó)郵遞員問(wèn)題（Chinese Postman Problem）  §4.3  Hamilton圖  §4.4  旅行商問(wèn)題（rnaveling Salesman Problem，TSP）  習(xí)題四  參考文獻(xiàn)第五章  支配集、獨(dú)立集、覆蓋集和Ramsey數(shù)  §5.1  支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集  §5.2  邊獨(dú)立集與邊覆蓋集  §5.3  支配集、點(diǎn)獨(dú)立集、點(diǎn)覆蓋集的求法  §5.4  Ramsey數(shù)  習(xí)題五  參考文獻(xiàn)第六章  染色理論  §6.1  邊染色  §6.2  點(diǎn)染色  §6.3  色多項(xiàng)式  §6.4  完美圖  §6.5  圖的邊染色算法和點(diǎn)染色算法  習(xí)題六  參考文獻(xiàn)第七章  平面圖  §7.1  平面圖的概念  §7.2  Euler公式及其應(yīng)用  §7.3  可平面圖的判斷  §7.4  平面圖的對(duì)偶圖  §7.5  外可平面圖  §7.6  不可平面圖的幾個(gè)研究方向簡(jiǎn)介  §7.7  平面圖的面染色和四色猜想  習(xí)題七  參考文獻(xiàn)第八章  有向圖  §8.1  有向圖的基本概念  §8.2  有向路與有向圈  §8.3  有向圖的連通性及無(wú)向圖的強(qiáng)連通定向  §8.4  Euler有向圖和Hamilton有向圖  §8.5  競(jìng)賽圖  §8.6  根樹(shù)及其應(yīng)用  習(xí)題八  參考文獻(xiàn)第九章  網(wǎng)絡(luò)流理論與算法  §9.1  網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念  §9.2  最大流問(wèn)題及其標(biāo)號(hào)算法  §9.3  求最大流的Dinic算法  §9.4  求最大流的推拉流算法  §9.5  最大流問(wèn)題的一些擴(kuò)展  §9.6  最小費(fèi)用流問(wèn)題  習(xí)題九  參考文獻(xiàn)名詞索引

編輯推薦

　　《圖論與網(wǎng)絡(luò)流理論》是圖論與網(wǎng)絡(luò)流理論的一本入門(mén)讀物。書(shū)中較為系統(tǒng)地闡述了圖論與網(wǎng)絡(luò)流理論的基本概念、方法和定理，介紹了該領(lǐng)域一些重要的問(wèn)題以及典型的算法，展示了圖論與網(wǎng)絡(luò)流理論模型與方法的廣泛應(yīng)用，試圖為學(xué)習(xí)者從事有關(guān)方面的理論研究打下基礎(chǔ)，也為進(jìn)行應(yīng)用研究的讀者提供一種有力的工具。

圖書(shū)封面

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

無(wú)

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

---

    圖論與網(wǎng)絡(luò)流理論 PDF格式下載

---