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

前言

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

內(nèi)容概要

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

書籍目錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---