圖論導引(原書第2版‧典藏版)（簡體書）

本書全面介紹了圖論的基本概念、基本定理和算法，幫助讀者理解並掌握圖的結構和解決圖論問題的技巧。另外，書中包含很多圖論的新研究成果，並介紹了一些懸而未決的圖論問題。證明與應用並舉是本書的一個重要特點，書中對所有定理和命題給出了完整的證明，同時討論了大量的實例和應用，並提供了1200多道習題。

道格拉斯·B.韋斯特（Douglas B.West）

美國伊利諾伊大學厄巴納分校數學系教授。1 978年他於馬薩諸塞理工學院獲得數學專業博士學位。他的研究方向為離散數學中的極值問題、結構問題以及算法問題。除該書外，他還著有《Mathematical Thinking： Problem-Solving and Proofs》《Combinatorial Mathematics》和《The Art of Combinatorics》等書。

1736年，瑞士數學家L.Euler（歐拉）在他的一篇論文中討論了哥尼斯堡（Konigsberg）七橋問題，由此誕生了一個全新的數學分支——圖論（Graph Theory）。在經歷了200多年的發展之後，圖論已經積累了大量的理論和結果，其應用領域也逐步擴大，最初，圖論主要用來討論遊戲中遇到的問題；19世紀末期，圖論已經用來研究電網絡方程組和有機化學中的分子結構；20世紀中葉以後，借助於計算機，圖論又用來求解生產管理、軍事、交通運輸、計算機以及通信網絡等領域中的許多離散性問題，同時圖論中的一些著名問題也藉助於計算機得到了證明．如今，圖論本身及其在物理學、化學、運籌學、計算機科學、電子學、信息論、控制論、網絡理論、社會科學和管理科學等領域中的應用越來越受到人們的重視，因此，作為理工科相關專業的學生，全面系統地學習圖論中的概念、基本定理和算法並了解圖論中的一些懸而未決的問題是十分必要的。
本書是一部優秀的圖論教科書，由Douglas B.West教授所著，目前已經是第2版了。Douglas B.West教授是伊利諾伊大學數學系的資深教授，長期從事圖論理論和組合優化方面的研究工作，發表了100多篇論文。
本書旨在介紹圖論的基本概念、基本定理和算法，幫助讀者理解並掌握圖的結構和解決圖論問題的技巧。另外，本書包含很多圖論的新研究結果，並介紹了一些懸而未決的圖論問題．證明與應用並舉是本書的一個重要特點，圖論中的許多問題都有多個證明，作者對這些證明進行了精心選擇，深入淺出地介紹了圖論的證明技巧；本書還設計了大量習題，總量超過1200道，通過這些習題，讀者可以深刻理解圖論的基本概念和證明技巧，並能夠補充正文未包括的知識。
本書可以作為高等院校數學系本科生和研究生、計算機專業和其他專業研究生的圖論課程教材，也可以作為有關教師和工程技術人員的參考書。
限於譯者水平，譯文中難免存在疏漏和錯誤，望廣大讀者批評指正。

譯者序
前言
符號表

第1章 基本概念
1．1 什麼是圖
定義
圖模型
矩陣和同構
分解和特殊圖
習題
1．2 路徑、環和跡
圖的連通性
二部圖
歐拉回路
習題
1．3 頂點度和計數
計數和雙射
極值問題
圖序列
習題
1．4 有向圖
定義和例子
頂點度
歐拉有向圖
定向和競賽圖
習題

第2章 樹和距離
2．1 基本性質
樹的性質
樹和圖中的距離
不相交生成樹（選學）
習題
2．2 生成樹和枚舉
樹的枚舉
圖的生成樹
分解和優美標記
分叉和歐拉有向圖（選學）
習題
2．3 最優化和樹
最小生成樹
最短路徑
計算機科學中的樹（選學）
習題

第3章 匹配和因子
3．1 匹配和覆蓋
最大匹配
Hall匹配條件
最小一最大定理
獨立集和覆蓋
支配集（選學）
習題
3．2 算法和應用
最大二部匹配
加權二部匹配
穩定匹配（選學）
快速二部匹配（選學）
習題
3．3 一般圖中的匹配
Tutte 1一因子定理
圖的f-因子（選學）
Edmonds開花算法（選學）
習題

第4章 連通度和路徑
4．1 割和連通度
連通度
邊一連通度
塊
習題
4．2 k-連通圖
2-連通圖
有向圖的連通度
k-連通圖和k-邊連通圖
Menger定理的應用
習題
4．3 網絡流問題
最大網絡流
整數流
供應和需求（選學）
習題

第5章 圖的著色
5．1 頂點著色和上界
定義和實例
上界
Brooks定理
習題
5．2 k-色圖的結構
大色數圖
極值問題和Turan定理
顏色一臨界圖
強制細分
習題
5．3 計數方面的問題
真著色的計數
弦圖
完美圖點滴
無環定向的計數（選學）
習題

第6章 可平面圖
6．1 嵌入和歐拉公式
平面作圖
對偶圖
歐拉公式
習題
6．2 可平面圖的特征
Kuratowski定理的預備知識
凸嵌入
可平面性測試（選學）
習題
6．3 可平面性的參數
可平面圖的著色、交叉數
具有更高虧格的表面（選學）
習題

第7章 邊和環
7．1 線圖和邊著色
邊著色
線圖的特征（選學）
習題
7．2 哈密頓環
必要條件
充分條件
有向圖中的環（選學）
習題
7．3 可平面性、著色和環Tait定理
Grinberg定理
鯊魚圖（選學）
流和環覆蓋（選學）
習題

第8章 其他主題（選學）
8．1 完美圖
完美圖定理
弦圖的再研究
其他類型的完美圖
非完美圖
強完美圖猜想
習題
8．2 擬陣
遺傳系統和示例
擬陣的性質
生成函數
擬陣的對偶性
擬陣的子式和可平面圖
擬陣的交
擬陣的並
習題
8．3 Ramsey理論
鴿巢原理的再研究
Ramsey定理
Ramsey數
關於圖的Ramsey理論
Sperner引理和帶寬
習題
8．4 其他極值問題
圖的編碼
分叉和流言
序列著色和可選擇性
使用路徑和環的劃分
周長
習題
8．5 隨機圖
存在性和期望值
幾乎所有圖均具有的性質
閾值函數
演變和圖參數
連通度、團和著色
鞅
習題
8．6 圖的特征值
特征多項式
實對稱矩陣的線性代數
特征值和圖參數
正則圖的特征值
特征值和擴張圖
強正則圖
習題

附錄A 數學基礎
附錄B 最優化和復雜度
附錄C 部分習題的提示
附錄D 術語表
附錄E 補充閱讀材料
附錄F 參考文獻