圖論導引

內(nèi)容概要

本書全面介紹了圖論的基本概念、基本概念、基本定理和算法，幫助讀者理解并掌握圖的結(jié)構(gòu)和解決圖論問題的技巧，另外，書中包含很多圖論的新研究成果，并介紹了一些懸而未決的圖論問題，證明與應用并舉是本書的一個重要特點，書中對所有定理和命題給出了完整的證明，同時討論大量的實例和應用，并提供了1200多道習題。    本書可以作為高等院校數(shù)學系本科生和研究生、計算機專業(yè)和其他專業(yè)研究生的圖論課程教材，也可以作為有關(guān)教師和工程技術(shù)人員的參考書。

作者簡介

Douglas B.West，美國伊利諾伊大學厄巴納分校數(shù)學系教授。1978年他于馬薩諸塞理工學院獲得數(shù)學專業(yè)博士學位。他的研究方向為離散數(shù)學中的極值問題、結(jié)構(gòu)問題以及算法問題。除本書外，他還著有《Mathematical Thinking:Problem-Solving and Proofs》、《Combinatorial Methema

書籍目錄

目錄譯者序前言符號表第1章  基本概念  1.1  什么是圖    定義    圖模型    矩陣和同構(gòu)    分解和特殊圖    習題  1.2  路徑、環(huán)和跡    圖的連通性    二部圖    歐拉回路    習題  1.3  頂點度和計數(shù)    計數(shù)和雙射    極值問題    圖序列    習題  1.4  有向圖    定義和例子    頂點度    歐拉有向圖-    定向和競賽圖    習題第2章  樹和距離  2.1  基本性質(zhì)    樹的性質(zhì)    樹和圖中的距離    不相交生成樹(選學)    習題  2.2  生成樹和枚舉    樹的枚舉    網(wǎng)的牛成樹    分解和優(yōu)美標記    分叉和歐拉有向圖(選學)    習題  2.3  最優(yōu)化和樹    最小生成樹    最短路徑    計算機科學中的樹(選學)    習題第3章  匹配和因子  3.1  匹配和覆蓋    最大匹配    Hall匹配條件    最小最大定理    獨立集和覆蓋    支配集(選學)    習題  3.2  算法和應用    最大二部匹配    加權(quán)二部肛配    穩(wěn)定匹配(選學)    快速二部匹配(選學)    習題  3.3  一般圖巾的匹配    Tutte l-因子定理    圖的f-因子(選學)    Edmonds開花算法(選學)    習題第4章  連通度和路徑  4.1  割和連通度    連通度    邊一連通度    塊    習題  4.2  k一連通圖    2一連通圖    有向圖的連通度    k一連通圖和k-邊連通圖    Menger定理的應用    習題  4.3  網(wǎng)絡(luò)流問題    最大網(wǎng)絡(luò)流    整數(shù)流    供應和需求(選學)    習題第5章  圖的著色  5.1  頂點著色和上界    定義和實例    七界    Brooks定理    習題  5.2  k一色圖的結(jié)構(gòu)    大色數(shù)圖    極值問題和Turin定理    顏色臨界圖    強制細分    習題  5.3  計數(shù)方面的問題    真著色的計數(shù)    弦圖    完美圖點滴    無環(huán)定向的計數(shù)(選學)    習題第6章  可平面圖  6.1  嵌入和歐拉公式    平面作圖    對偶圖    歐拉公式    習題  6.2  可平面圖的特征    Kuratowski定理的預備知識    凸嵌入    可平面性測試(選學)    習題  6.3  可平面性的參數(shù)    可平面圖的著色    交叉數(shù)    具有更高虧格的表面(選學)     習題第7章  邊和環(huán)  7.1  線圖和邊著色    邊著色    線圖的特征(選學)    習題  7.2  哈密頓環(huán)    必要條件    充分條件    有向圖中的環(huán)(選學)    習題  7.3  可甲面性、著色和環(huán)    Tail定理    Grinberg定理    鯊魚圖(選學)    流和環(huán)覆蓋(選學)    習題第8章  其他主題(選學)  8.1  完莢圖    完美圖定理    弦圖的再研究    其他類型的完美圖    非完美圖    強完美圖猜想    習題  8.2  擬陣    遺傳系統(tǒng)和示例    擬陣的性質(zhì)    生成函數(shù)    擬陣的對偶性    擬陣的子式和可平面圖    擬陣的交    擬陣的并    習題  8.3  Ramsey理論    鴿巢原埋的再研究    Ramsey定理    Ramsey數(shù)    關(guān)于圖的Ramsey理論    Sperner引理和帶寬    習題  8.4  其他極值問題    圖的編碼    分叉和流言    序列著色和可選擇性    使用路徑和環(huán)的劃分    周長    習題  8.5  隨機圖    存在性和期望值    幾乎所有圖均具有的性質(zhì)    閾值函數(shù)    演變和圖參數(shù)    連通度、團和著色    鞅    習題  8.6  圖的特征值    特征多項式    實對稱矩陣的線性代數(shù)    特征值和圖參數(shù)    正則圖的特征值    特征值和擴張圖    強正則圖    習題附錄A  數(shù)學基礎(chǔ)附錄B  最優(yōu)化和復雜度附錄C  部分習題的提示附錄D  術(shù)語表附錄E  補充閱讀材料附錄F  參考文獻

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    圖論導引 PDF格式下載

---