本書系統地介紹了圖論的基本概念、基本定理和算法，同時還介紹了一些懸而未決的圖論問題和圖論的新研究成果，旨在幫助讀者理解并掌握圖的結構和解決圖論問題的技巧。全書包含８章和７個附錄。第１～４章介紹圖的概念、樹和距離、匹配問題和圖的分解問題、圖的連通性等基本內容；第５～８章分別介紹了組合圖論、拓撲圖論的知識，圖論中的邊和環，以及圖論的其他主題。書中配有大量例題和超過１２００道習題，使讀者容易理解書中的概念和定理，并掌握證明技巧。本書內容豐富，具有很多可選擇閱讀的章節，可以供不同層次的讀者使用。
本書系統地介紹了圖論的基本概念、基本定理和算法，同時還介紹了一些懸而未決的圖論問題和圖論的新研究成果，旨在幫助讀者理解并掌握圖的結構和解決圖論問題的技巧。
本書作者是Illinois大學數學系的資深教授Douglas B. West。他長期從事圖論理論和組合優化方面的研究工作，發表論文100多篇。他的其他著作，如《Mathematical Thinking: Problem-Solving and Proofs》、《Combinatorial Mathematics》和《The Art of Combinatorics》，也深受讀者的喜愛。本書出版于20世紀90年代末，是一部圖論方面的優秀教材，一直是Illinois大學數學系本科生和研究生圖論課程的教科書。
第1章 基本概念
1.1 什么是圖
1.1.1 定義
1.1.2 圖模型
1.1.3 矩陣與同構
1.1.4 分解和特殊圖
1.1.5 習題
1.2 路徑、 環和跡
1.2.1 圖的連通
1.2.2 二分圖
1.2.3 歐拉回路
1.2.4 習題
1.3 頂點度和計數
1.3.1 計數和雙射
1.3.2 極值問題 第1章 基本概念
1.1 什么是圖
1.1.1 定義
1.1.2 圖模型
1.1.3 矩陣與同構
1.1.4 分解和特殊圖
1.1.5 習題
1.2 路徑、 環和跡
1.2.1 圖的連通
1.2.2 二分圖
1.2.3 歐拉回路
1.2.4 習題
1.3 頂點度和計數
1.3.1 計數和雙射
1.3.2 極值問題
1.3.3 圖解序列
1.3.4 習題
1.4 有向圖
1.4.1 定義和例子
1.4.2 頂點度
1.4.3 歐拉有向圖
1.4.4 定向圖和競賽圖
1.4.5 習題
第2章 樹和距離
2.1 基本性質
2.1.1 樹的性質
2.1.2 樹和圖中的距離
2.1.3 不相交生成樹（選學）
2.1.4 習題
2.2 生成樹和枚舉
2.2.1 樹的枚舉
2.2.2 圖的生成樹
2.2.3 分解和優美標記
2.2.4 分叉與歐拉有向圖（選學）
2.2.5 習題
2.3 優化和樹
2.3.1 最小生成樹
2.3.2 最短路徑
2.3.3 計算機科學中的樹（選學）
2.3.4 習題
第3章 匹配和因子
3.1 匹配與覆蓋
3.1.1 最大匹配
3.1.2 Hall匹配條件
3.1.3 最小最大定理
3.1.4 獨立集與覆蓋
3.1.5 支配集(選學)
3.1.6 習題
3.2 算法及應用
3.2.1 最大二分匹配
3.2.2 加權二分匹配
3.2.3 穩定匹配（選學）
3.2.4 快速二分匹配（選學）
3.2.5 習題
3.3 一般圖中的匹配
3.3.1 Tutte 1-因子定理
3.3.2 圖的f-因子（選學）
3.3.3 Edmonds開花算法（選學）
3.3.4 習題
第4章 連通度和路徑
4.1 割與連通度
4.1.1 連通度
4.1.2 邊連通度通常
4.1.3 塊
4.2 k-通圖
4.2.1 2.連通圖
4.2.2 有向圖的連通度
4.2.3 k.通圖與k.邊連通圖
4.2.4 Menger定理的應用
4.2.5 習題
4.3 網絡流問題
4.3.1 最大網絡流
4.3.2 整數流
4.3.3 供應與需求(選學)
4.3.4 習題
第5章 圖的著色
5.1 頂點著色和上界
5.1.1 定義和實例
5.1.2 上界
5.1.3 Brooks定理
5.1.4 習題
5.2 k-色圖的構造
5.2.1 大色數圖
5.2.2 極值問題與Turan定理
5.2.3 顏色臨界圖
5.2.4 強制細分
5.2.5 習題
5.3 計數方面的問題
5.3.1 真著色的計數
5.3.2 弦圖
5.3.3 完美圖點滴
5.3.4 環定向的計數(選學)
5.3.5 習題
第6章 可平面圖
6.1 嵌入與歐拉公式
6.1.1 平面作圖
6.1.2 對偶圖
6.1.3 歐拉（Euler）公式
6.1.4 習題
6.2 可平面圖的特征
6.2.1 Kuratowski定理的預備知識
6.2.2 凸嵌入
6.2.3 可平面性的測試(選學)
6.2.4 習題
6.3 可平面性的參數
6.3.1 可平面圖的著色
6.3.2 交叉數
6.3.3 具有更高虧格的表面(選學)
6.3.4 習題
第7章 邊和環
7.1 線圖與邊著色
7.1.1 邊著色
7.1.2 線圖的性質(選學)
7.1.3 習題
7.2 哈密頓環
7.2.1 必要條件
7.2.2 充分條件
7.2.3 有向圖中的環(選學)
7.2.4 習題
7.3 可平面性、 著色與環
7.3.1 Tait定理
7.3.2 Grinberg定理
7.3.3 鯊魚圖(選學)
7.3.4 流與環覆蓋(選學)
7.3.5 習題
第8章 其他主題
8.1 完美圖
8.1.1 完全圖定理
8.1.2 弦圖的再研究
8.1.3 其他完美圖類
8.1.4 非完美圖
8.1.5 強完美圖猜想
8.1.6 習題
8.2 擬陣
8.2.1 遺傳系統及示例
8.2.2 擬陣的性質
8.2.3 生成函數
8.2.4 擬陣的對偶
8.2.5 擬陣的子式與可平面對偶
8.2.6 擬陣的交
8.2.7 擬陣的并
8.2.8 習題
8.3 拉姆齊理論
8.3.1 鴿巢原理的再研究
8.3.2 拉姆齊(Ramsey)定理
8.3.3 拉姆齊數
8.3.4 圖的拉姆齊理論
8.3.5 Sperner引理和帶寬
8.3.6 習題
8.4 其他極值問題
8.4.1 圖的編碼
8.4.2 分叉和流言
8.4.3 序列著色和可選擇性
8.4.4 由路徑和環構成的劃分
8.4.5 周長
8.4.6 習題
8.5 隨機圖
8.5.1 存在性和數學期望
8.5.2 幾乎所有圖均具有的性質
8.5.3 閾值函數
8.5.4 圖的演變和圖的參數
8.5.5 連通度、 團和著色
8.5.6 鞅
8.5.7 習題
8.6 圖的特征值
8.6.1 特征多項式
8.6.2 線性代數和實對稱陣
8.6.3 特征值和圖參數
8.6.4 正則圖的特征值
8.6.5 特征值與擴張圖
8.6.6 強正則圖
8.6.7 習題
附錄A 數學基礎
附錄B 最優化和復雜度
附錄C 部分習題提示
附錄D 術語表
附錄E 補充閱讀
附錄F 參考文獻
附錄G 術語對照表
劉茂紅所著的《中國互聯網產業組織實證研究》從網絡經濟發展入手，在借鑒研究中國工業集中度決定因素的基礎上，通過文獻分析和邏輯推理，解決了中國網絡經濟發展中的一系列實證性問題。本文條理清晰，說理明確，運用的數據及模型都能直觀的體現中國互聯網產業的市場行為，為我國網絡經濟的發展奠定了理論與實證基礎。譯 者 序
1736年， 瑞士數學家L.Euler在他的一篇論文中討論了Knigsberg七橋問題， 由此產生了一個全新的數學分支——圖論（graph theory）。在經歷了200多年的發展之后， 圖論已經積累了大量的理論和結果， 其應用領域也逐步擴大。最初， 圖論主要用來討論游戲中遇到的問題；19世紀晚期， 圖論已經被用來研究電網絡方程組和有機化學中的分子結構； 20世紀中葉以后， 借助于計算機， 圖論又被用來求解生產管理、 軍事、 交通運輸、 計算機和通信網絡等領域中的許多離散性問題， 同時圖論中一些著名問題也借助于計算機得到了證明。如今， 圖論本身及其在物理、 化學、 運籌學、 計算機科學、 電子學、 信息論、 控制論、 網絡理論、 社會科學和管理科學等領域中的應用越來越受到人們的重視。因此， 作為理工科相關專業的學生， 全面系統地學習圖論中的概念、 基本定理和算法， 并了解圖論中一些懸而未決的問題是十分必要的。本書為學習和掌握這些知識提供了一部優秀的教科書。
本書由Douglas B.West教授所著。Douglas B.West教授是Illinois大學數學系的資深教授， 長期從事圖論理論和組合優化方面的研究工作。他的其他著作， 如Mathematical Thinking: ProblemSolving and Proofs，Combinatorial Mathematics和The Art of Combinatorics， 也深受讀者的喜愛。本書一直是Illinois大學數學系本科生和研究生圖論課程的教科書。本書的翻譯和出版， 對于國內讀者學習并應用圖論知識具有重要意義。有幸承擔該書的翻譯工作， 我們感到十分榮幸。
本書旨在介紹圖論的基本概念、基本定理和算法， 幫助讀者理解掌握圖的結構和解決圖論問題的技巧。本書在系統介紹圖論的基本概念、基本定理和算法的同時， 還介紹了一些懸而未決的圖論問題， 并配置了大量的例題和習題。圖論中許多問題都有多個證明， 作者對這些證明進行了精心選擇。縱觀全書， 作者深入淺出、全面地介紹了圖論的證明技巧。證明與應用實例并舉是本書的一個重要特點， 使讀者容易理解書中的概念和定理。該書配置了大量習題， 總量超過1200道。通過這些習題， 讀者可以深刻理解圖論的基本概念和證明技巧， 并能夠學習到正文未包括的知識。
與其他圖論教材相比， 本書包含了更多的基本內容， 具有更多可供選擇閱讀的章節， 包含了更多的新研究結果和懸而未決的問題， 并且特別強調圖論論證方法的學習和掌握。基本內容可以幫助讀者建立圖論的知識框架， 掌握圖論的基本證明方法。選讀內容是對基本知識的有益補充和延伸， 而最新的研究成果和懸而未決的問題則可以幫助讀者接觸圖論研究的前沿。因此，本書可供不同層次的讀者使用。它可以作為高等院校數學系本科生、 研究生， 計算機專業和其他專業研究生的圖論課程教材， 也可以作為有關教師和工程技術人員參考書。
本書由哈爾濱工業大學駱吉洲和李建中合作翻譯完成。譯者在深刻理解本書的基礎上力求準確， 對于發現的多處筆誤和印刷錯誤，在翻譯時進行了更正。在本書的翻譯過程中， 譯者得到了多位同事和朋友的幫助， 他們提出了很多中肯的意見和建議， 使譯者受益良多。在此一并致謝！ 同時也向提出寶貴意見的所有讀者表示感謝。
限于水平， 譯文中疏漏和錯誤難免， 敬請讀者批評指正。
前 言
圖論是訓練離散數學證明技巧的樂園， 其結果在計算科學、社會科學和自然科學等各個領域具有廣泛應用。本書為本科生或研究生提供了一個或兩個學期的圖論課程內容。本書不要求任何圖論的預備知識。盡管本書包含了許多算法和應用， 但重點是理解圖的結構和分析圖論問題的技巧。
目前已經有許多圖論的教科書。由J.A.Bondy和U.S.R.Murty撰寫的經典教材《圖論及應用》（Graph Theory with Applications,Macmillan/NorthHolland\[1976\]）突出了證明和應用兩個方面， 故本書的原型參照了該書。圖論至今仍是一個年輕的學科， 應該如何介紹圖論的知識， 大家仍然沒有一致的看法。內容的選擇和順序的安排， 證明方法的選擇， 目標的選擇， 習題的選擇等一直是有爭議問題。對本書多次修改使我懂得了對于上述問題做出決策是多么得困難。本書是我對上述有爭議問題的一點貢獻。
關于第二版
第二版的修訂采用了更簡潔的行文方式， 以方便學生學習和教師教學。全書總體內容沒有太大變化， 只是對內容的表述方式做了修改， 使其更易理解， 這一點在本書的前幾部分尤其明顯。有關第二版的變化， 稍后將詳細論述， 在此僅做一個概述。
● 必修內容中出現的選修內容現在用“*”號區分。這些內容不會在后續內容中使用， 因而可以跳過。忽略多數選修內容以后， 本書可以作為一學期的圖論教學內容。當某一小節被標記為“可選”時， 該小節的全部內容都是選修的， 這時不再標記該小節中的各個項。
● 對于缺乏基礎知識的學生， 附錄A概述了有關集合、邏輯、歸納法、計數、二項式系數、關系和鴿巢原理等方面的相關知識。
● 重新敘述和分析了很多證明， 并增加了更多的例子。
● 增加了350多道習題， 其中多數是第1～7章中比較容易的題目。這樣， 本書的總習題量超過了1200道。
● 增加了100多幅插圖。本書的插圖總量超過了400幅。為區別插圖中包括的幾種類型的邊框， 本書把原有的實線和虛線改變為粗線和實線， 提高了插圖的清晰度。
● 相對簡單的問題都集中放在各節習題的前面部分， 用來作為熱身練習。一些習題被改寫， 使其語義更清楚。
● 對習題的提示做了補充， 增加了一個“部分習題提示”的附錄。
● 為了易于查找， 在附錄D中給出了全書的術語表。
● 有關歐拉回路、有向圖和Turn定理的內容被重新編排， 以提高學習的效率。
● 第6章和第7章調換了順序以便先介紹平面性的思想。與復雜性有關的部分改編為附錄。
● 改正了專業術語中的錯誤， 并更加強調與本書內容直接相關的術語。
本書特點
本書特點就是使學生能夠深入理解本書的內容。本書包括對證明技巧的討論、 1200多道習題、 400多幅插圖以及許多例子。本書正文中出現的結論都有詳細完整的證明。
很多本科學生在開始學習圖論前都很少涉足證明技巧， 附錄A提供的背景閱讀材料有助于初學者。如果初學者在理解和書寫證明時有困難， 應該結合第1章仔細閱讀附錄A。雖然本書前面的一些章節仍然討論了一些證明技巧（特別是歸納法）， 但是更多的背景知識已經放到附錄A中。
多數的習題需要證明。很多本科學生在論證問題方面的實踐不足， 這將影響他們對于圖論和其他數學知識的興趣。拋開數學而言， 論證問題方面的智能訓練也是極其重要的。我希望學生喜歡這種訓練。學生在求解問題時， 應該注意語言的使用（“說出的即是你要表達的”）， 而且表達準確（“表達的即是你要說出的”）。
雖然圖論中許多名詞本身就表明了它們各自的定義， 但太多的專業術語定義會阻礙閱讀的流暢性。數學家喜歡一開始就給出一系列的定義。但學生們大都愿意在熟練掌握一個概念后再去接受下一個概念， 這樣他們會學得更好。學生的這個意愿和審稿者的建議使我推遲了很多定義的給出， 直到需要的時候。例如， 笛卡兒積的定義出現在5.1節的著色問題部分， 線圖的定義則分別出現在4.2節的Menger定理部分和7.1節的邊著色部分， 誘導子圖的定義和連接的定義分別被推遲到1.2節和3.1節。
書中將有向圖的介紹推遲到1.4節。如果在介紹圖的同時介紹有向圖， 會使學生產生迷惑。在第1章的最后介紹有向圖比較容易學習， 能夠在了解兩種圖的差別的同時加強對基本概念的理解。在連通性問題上， 本書仍將這兩個模型放在一起討論。
本書比其他圖論書籍包含了更多的內容。作為“其他主題”的可選擇章節， 最后一章聚集很多圖論的新的研究結果， 使得本書能供不同層次的讀者使用。本科生的教學內容可以由前7章組成（去掉大部分選修內容）， 第8章可作為有興趣的學生的主題閱讀材料。研究生的教學內容可以如下構成： 第1章和第2章作為推薦閱讀材料， 在課堂上快速進入第3章， 并講授第8章的一些主題內容。第8章及前面章節的選修內容也可作為高級圖論課程的基本內容。
圖論中很多結果都存在多種證明， 這將有助于提高學生采用多種方法處理問題的靈活性。對于同一個問題， 本書可能在注記中談及一些不同的證明方法， 另外一些留作練習。
很多習題都有提示， 一些提示在習題中直接給出， 另一些在附錄C中給出。標記了“－”的問題比較簡單， 標記了“＋”的問題將比較難。標記了“+”的問題不應該作為本科學生的作業。標記了“！”的問題特別有價值和啟發性。標記了“*”的問題將涉及可選內容。
每組習題都以標記“－”的習題開始， 根據相關章節內容的先后順序排列。這些習題的結束由一組點標記。這部分習題要么是檢查對概念的理解， 要么是對這部分內容的結論的直接應用。作者在課堂上推薦做一些這樣的練習作為熱身， 在完成主要作業題（多數這樣的習題標記了“！”）之前檢查學生對基本概念的理解。多數標記“－”的問題是很好的考試題。如果在考試中使用其他習題， 從附錄C中提供一些提示是很好的做法。
涉及多個概念的習題出現在最后一個相關概念介紹完之后。正文中一個概念介紹完后有時會有指針指向與該概念相關的習題， 全書有很多這樣的指針。每小節對本節習題的引用僅由該習題的相應編號給出， 對其他習題的交叉引用將通過其章、節和習題編號給出。
內容組織和修改
在第一版中， 我力求內容的承接關系以及證明難度和算法復雜性循序漸進。
在第二版中， 我繼續保持這種風格。歐拉回路和哈密頓環仍在不同章節， 并離得更遠。歐拉回路的簡單介紹在1.2節，
新書資訊