本書全面介紹了圖論的基本概念、基本定理和算法，幫助讀者理解并掌握圖的結(jié)構(gòu)和解決圖論問題的技巧。另外，書中包含很多圖論的新研究成果，并介紹了一些懸而未決的圖論問題。證明與應(yīng)用并舉是本書的一個重要特點，書中對所有定理和命題給出了完整的證明，同時討論了大量的實例和應(yīng)用，并提供了1 200多道習(xí)題。本書可以作為高等院校數(shù)學(xué)系本科生和研究生、計算機專業(yè)和其他專業(yè)研究生的圖論課程教材，也可以作為有關(guān)教師和工程技術(shù)人員的參考書。
本書全面介紹了圖論的基本概念、基本定理和算法，幫助讀者理解并掌握圖的結(jié)構(gòu)和解決圖論問題的技巧。另外，書中包含很多圖論的新研究成果，并介紹了一些懸而未決的圖論問題。證明與應(yīng)用并舉是本書的一個重要特點，書中對所有定理和命題給出了完整的證明，同時討論了大量的實例和應(yīng)用，并提供了1 200多道習(xí)題。本書可以作為高等院校數(shù)學(xué)系本科生和研究生、計算機專業(yè)和其他專業(yè)研究生的圖論課程教材，也可以作為有關(guān)教師和工程技術(shù)人員的參考書。
圖論是訓(xùn)練離散數(shù)學(xué)證明技巧的樂園，其結(jié)果在計算科學(xué)、社會科學(xué)和自然科學(xué)等多個領(lǐng)域具有廣泛應(yīng)用．本書可作為本科生或低年級研究生1~2個學(xué)期的圖論課程的教材．本書不要求任何圖論的預(yù)備知識．盡管本書包含許多算法和應(yīng)用，但重點是講解圖的結(jié)構(gòu)和解決圖論問題的技巧．
目前在圖論方面已經(jīng)有許多教科書．由J. A.Bondy和U.S.R.Murty撰寫的優(yōu)秀教材《Graph Theory with Applications》(Macmillan/North-Holland［1976］)把重點放在證明和應(yīng)用兩個方面，本書的草稿參照了該書．圖論至今仍是一門年輕的學(xué)科，應(yīng)該如何介紹圖論的題材，大家仍然沒有一致的看法．主題的挑選和順序的安排，證明方法、目標(biāo)和基本題目的選擇等，一直是眾說紛紜．作者在多次修改本書的過程中認識到，對于這些問題做決定是很困難的．本書是作者對這些爭議的一點貢獻．
第2版
第2版的修訂主要是為了更易于學(xué)生學(xué)習(xí)和更便于教師教學(xué)．本書的總體內(nèi)容沒有很大的變化，但是對內(nèi)容的表述方式做了修改，使其更容易理解，這一點在本書的前幾部分尤其明顯．有關(guān)第2版所做的某些修改，稍后將詳細討論，此處僅做一下概述．
非選學(xué)節(jié)中的選學(xué)材料現(xiàn)在用*號標(biāo)明．這些內(nèi)容不會在后續(xù)內(nèi)容中使用，因而可以跳過．忽略多數(shù)選修內(nèi)容以后，本書可以作為一學(xué)期的圖論教學(xué)內(nèi)容．如某一小節(jié)標(biāo)記為“選學(xué)”，則整個小節(jié)的內(nèi)容都是可選修的，而不再標(biāo)記該小節(jié)中的各個項．
對于缺乏基礎(chǔ)知識的學(xué)生，附錄A概述了有關(guān)集合、邏輯、歸納法、計數(shù)、二項式系數(shù)、關(guān)系和鴿巢原理等方面的相關(guān)知識．
對于很多證明都重新進行了更細致的敘述，并增加了更多的例子．
增加了350多道習(xí)題，其中多數(shù)是第1～7章中的比較容易的題目．這樣，本書的總習(xí)題量超過了1 200道．
增加了100多幅插圖．本書的插圖總量超過了400幅．為區(qū)別插圖中包括的幾種類型的邊，書中把原有的實線和虛線改變?yōu)榇志�和實線，增加了插圖的清晰度．
相對簡單的問題都集中放在各節(jié)習(xí)題的前面部分，用來作為熱身練習(xí)．一些習(xí)題進行了改寫，使其語義更加清楚．
對習(xí)題的提示做了補充，增加了一個“部分習(xí)題的提示”的附錄．
為了易于查找，概念術(shù)語都用黑體字給出，其中絕大多數(shù)都出現(xiàn)在概念定義中．
為了易于查找，術(shù)語都集中在附錄D中．
有關(guān)歐拉回路、有向圖和Turán定理的內(nèi)容經(jīng)過了重新編排，以提高學(xué)習(xí)效率．
第6章和第7章交換了順序以便先介紹平面性的思想，與復(fù)雜度有關(guān)的部分經(jīng)過改編安排在附錄中．
改正了專業(yè)術(shù)語的錯誤，并更加強調(diào)與本書內(nèi)容直接相關(guān)的術(shù)語．
特點
本書的特點就是使學(xué)生能夠深入理解本書的內(nèi)容．本書包括對證明技巧的討論、1 200多道習(xí)題、400多幅插圖以及許多例子．本書正文中出現(xiàn)的結(jié)論都有詳細完整的證明．
很多本科生在開始學(xué)習(xí)圖論前很少了解證明技巧，附錄A提供的數(shù)學(xué)基礎(chǔ)知識有助于初學(xué)者提高這方面的技巧．如果初學(xué)者在理解和書寫證明時有困難，請結(jié)合第1章仔細閱讀附錄A．雖然本書前面的一些章節(jié)仍然討論了一些證明技巧（特別是歸納法），但是更多的背景知識（特別是集合、函數(shù)、關(guān)系和初等計數(shù)）已經(jīng)安排在附錄A中．
大多數(shù)習(xí)題都需要證明．很多本科生在論證問題方面的實踐不足，這將影響他們對于圖論和其他數(shù)學(xué)知識的興趣．即使拋開數(shù)學(xué)，論證問題方面的智能訓(xùn)練也是極其重要的，作者希望學(xué)生喜歡這種訓(xùn)練．在求解問題時，學(xué)生應(yīng)該注意語言的使用（“說出的即是你要表達的”），而且表達準(zhǔn)確（“表達的即是你要說出的”）．
雖然圖論中許多術(shù)語本身就表明了它們各自的定義，但太多的專業(yè)術(shù)語定義會影響內(nèi)容的可讀性．?dāng)?shù)學(xué)家喜歡一開始就給出一系列定義，但學(xué)生們大都愿意熟練掌握一個概念后再去接受下一個概念，這樣他們會學(xué)得更好．學(xué)生的這個意愿和審稿者的建議使作者推遲了很多定義的給出，直到需要的時候．例如，笛卡兒積的定義在5.1節(jié)的著色問題部分給出，線圖的定義則分別在4.2節(jié)的Menger定理部分和7.1節(jié)的邊著色部分給出，誘導(dǎo)子圖的定義和連接的定義分別推遲到1.2節(jié)和3.1節(jié)給出．
書中已經(jīng)改變了對有向圖介紹的位置，將其推遲到了1.4節(jié)．如果在介紹圖的同時介紹有向圖，會使學(xué)生產(chǎn)生迷惑．在第1章的最后介紹有向圖的內(nèi)容結(jié)構(gòu)相對容易學(xué)習(xí)，學(xué)生能夠在了解兩種圖的差別的同時加強對基本概念的理解．在連通性問題上，本書仍會將這兩個模型放在一起討論．
本書比其他圖論書籍包含更多的內(nèi)容．作為“其他主題”的可選章節(jié)，最后一章匯集了很多圖論最新研究結(jié)果，使得本書適合不同層次的讀者使用．本科生的教學(xué)內(nèi)容可以由前七章組成（去掉大部分選學(xué)內(nèi)容），第8章可作為對相應(yīng)主題感興趣的學(xué)生的閱讀材料．研究生的教學(xué)內(nèi)容可以采用如下結(jié)構(gòu)：第1章和第2章作為推薦閱讀材料，在課堂上使學(xué)生快速進入第3章的學(xué)習(xí)，并講授第8章的一些主題．第8章以及前面章節(jié)的選學(xué)內(nèi)容也可作為高級圖論課程的基本內(nèi)容．
很多圖論中的結(jié)論都有多個證明，這樣有助于提高學(xué)生采用多種方法處理問題的靈活性．對于同一個問題，本書可能在注記中談及一些不同的證明方法，另外一些留作練習(xí)．
很多習(xí)題都有提示，一些提示在習(xí)題中直接給出，另一些在附錄C中給
道格拉斯?B. 韋斯特（Douglas B. West） 美國伊利諾伊大學(xué)厄巴納分校數(shù)學(xué)系教授。1978年他于馬薩諸塞理工學(xué)院獲得數(shù)學(xué)專業(yè)博士學(xué)位。他的研究方向為離散數(shù)學(xué)中的極值問題、結(jié)構(gòu)問題以及算法問題。除本書外，他還著有Mathematical Thinking：Problem-Solving and Proofs、Combinatorial Mathematics和The Art of Combinatorics等書。
第1章 基本概念1
1.1 什么是圖1
定義1
圖模型3
矩陣和同構(gòu)6
分解和特殊圖11
習(xí)題14
1.2 路徑、環(huán)和跡19
圖的連通性20
二部圖24
歐拉回路26
習(xí)題31
1.3 頂點度和計數(shù)34
計數(shù)和雙射35
極值問題38
圖序列44
習(xí)題47
1.4 有向圖53
定義和例子53
頂點度58
歐拉有向圖60
定向和競賽圖61
習(xí)題63
第2章 樹和距離67
2.1 基本性質(zhì)67
樹的性質(zhì)68
樹和圖中的距離70
不相交生成樹（選學(xué)）73
習(xí)題75
2.2 生成樹和枚舉81
樹的枚舉81
圖的生成樹83
分解和優(yōu)美標(biāo)記87
分叉和歐拉有向圖（選學(xué)）89
習(xí)題92
2.3 最優(yōu)化和樹95
最小生成樹95
最短路徑97
計算機科學(xué)中的樹（選學(xué)）100
習(xí)題103
第3章 匹配和因子107
3.1 匹配和覆蓋107
最大匹配108
Hall匹配條件110
最小–最大定理112
獨立集和覆蓋113
支配集（選學(xué)）116
習(xí)題118
3.2 算法和應(yīng)用123
最大二部匹配123
加權(quán)二部匹配125
穩(wěn)定匹配（選學(xué)）130
快速二部匹配（選學(xué)）132
習(xí)題134
3.3 一般圖中的匹配136
Tutte 1-因子定理136
圖的f-因子（選學(xué)）140
Edmonds開花算法（選學(xué)）142
習(xí)題145
第4章 連通度和路徑149
4.1 割和連通度149
連通度149
邊–連通度152
塊155
習(xí)題158
4.2 k–連通圖161
2–連通圖161
有向圖的連通度164
k–連通圖和k–邊連通圖166
Menger定理的應(yīng)用170
習(xí)題172
4.3 網(wǎng)絡(luò)流問題176
最大網(wǎng)絡(luò)流176
整數(shù)流181
供應(yīng)和需求（選學(xué)）184
習(xí)題188
第5章 圖的著色191
5.1 頂點著色和上界191
定義和實例191
上界194
Brooks定理197
習(xí)題199
5.2 k–色圖的結(jié)構(gòu)204
大色數(shù)圖205
極值問題和Turán定理207
顏色–臨界圖210
強制細分212
習(xí)題214
5.3 計數(shù)方面的問題219
真著色的計數(shù)219
弦圖224
完美圖點滴226
無環(huán)定向的計數(shù)（選學(xué)）228
習(xí)題229
第6章 可平面圖233
6.1 嵌入和歐拉公式233
平面作圖233
對偶圖236
歐拉公式241
習(xí)題243
6.2 可平面圖的特征246
Kuratowski定理的預(yù)備知識247
凸嵌入248
可平面性測試（選學(xué)）252
習(xí)題255
6.3 可平面性的參數(shù)257
可平面圖的著色257
交叉數(shù)261
具有更高虧格的表面（選學(xué)）266
習(xí)題269
第7章 邊和環(huán)273
7.1 線圖和邊著色273
邊著色274
線圖的特征（選學(xué)）279
習(xí)題282
7.2 哈密頓環(huán)286
必要條件287
充分條件288
有向圖中的環(huán)（選學(xué)）293
習(xí)題294
7.3 可平面性、著色和環(huán)299
Tait定理300
Grinberg定理302
鯊魚圖（選學(xué)）304
流和環(huán)覆蓋（選學(xué)）307
習(xí)題314
第8章 其他主題（選學(xué)）319
8.1 完美圖319
完美圖定理320
弦圖的再研究323
其他類型的完美圖328
非完美圖334
強完美圖猜想340
習(xí)題344
8.2 擬陣349
遺傳系統(tǒng)和示例349
擬陣的性質(zhì)354
生成函數(shù)358
擬陣的對偶性360
擬陣的子式和可平面圖363
擬陣的交366
擬陣的并369
習(xí)題372
8.3 Ramsey理論378
鴿巢原理的再研究378
Ramsey定理380
Ramsey數(shù)383
關(guān)于圖的Ramsey理論386
Sperner引理和帶寬388
習(xí)題392
8.4 其他極值問題396
圖的編碼397
分叉和流言404
序列著色和可選擇性408
使用路徑和環(huán)的劃分413
周長416
習(xí)題422
8.5 隨機圖425
存在性和期望值426
幾乎所有圖均具有的性質(zhì)430
閾值函數(shù)432
演變和圖參數(shù)436
連通度、團和著色439
鞅442
習(xí)題448
8.6 圖的特征值452
特征多項式453
實對稱矩陣的線性代數(shù)456
特征值和圖參數(shù)458
正則圖的特征值460
特征值和擴張圖463
強正則圖464
習(xí)題467
附錄A 數(shù)學(xué)基礎(chǔ)471
附錄B 最優(yōu)化和復(fù)雜度493
附錄C 部分習(xí)題的提示507
附錄D 術(shù)語表515
附錄E 補充閱讀材料533
附錄F 參考文獻567
作者索引569
術(shù)語索引575
Contents
Preface xi
Chapter 1 Fundamental Concepts
1.1 What Is a Graph?
The Definition, 1
Graphs as Models, 3
Matrices and Isomorphism, 6
Decomposition and Specia] Graphs, 11
Exercises, 14
1.2 Paths, Cycles, and Trails 19
Connection in Graphs, 20
Bipartite Graphs, 24
Eulerian Circuits, 26
Exercises, 31
1.3 Vertex Degrees and Counting 34
Counting and Bijections, 35
Extremal Problems, 38
Graphic Sequences, 44
Exercises, 47
1.4 Directed Graphs 53
Definitions and Examples, 53
Vertex Degrees, 58
Eulerian Digraphs, 60
Orientations and Tournaments, 61
Exercises, 63
Chapter 2 Trees and Distance
2.1 Basic Properties
Properties of Trees, 68
Distance in Trees and Graphs, 70
Disjoint Spanning Trees (optional), 73
Exercises, 75
2.2 Spanning Trees and Enumeration
Enumeration of Trees, 81
Spanning Trees in Graphs, 83
D
書單推薦
