第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 頂點(diǎn)度和計(jì)數(shù)34
計(jì)數(shù)和雙射35
極值問(wèn)題38
圖序列44
習(xí)題47
1.4 有向圖53
定義和例子53
頂點(diǎn)度58
歐拉有向圖60
定向和競(jìng)賽圖61
習(xí)題63
第2章 樹(shù)和距離67
2.1 基本性質(zhì)67
樹(shù)的性質(zhì)68
樹(shù)和圖中的距離70
不相交生成樹(shù)（選學(xué)）73
習(xí)題75
2.2 生成樹(shù)和枚舉81
樹(shù)的枚舉81
圖的生成樹(shù)83
分解和優(yōu)美標(biāo)記87
分叉和歐拉有向圖（選學(xué)）89
習(xí)題92
2.3 最優(yōu)化和樹(shù)95
最小生成樹(shù)95
最短路徑97
計(jì)算機(jī)科學(xué)中的樹(shù)（選學(xué)）100
習(xí)題103
第3章 匹配和因子107
3.1 匹配和覆蓋107
最大匹配108
Hall匹配條件110
最小–最大定理112
獨(dú)立集和覆蓋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開(kāi)花算法（選學(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ò)流問(wèn)題176
最大網(wǎng)絡(luò)流176
整數(shù)流181
供應(yīng)和需求（選學(xué)）184
習(xí)題188
第5章 圖的著色191
5.1 頂點(diǎn)著色和上界191
定義和實(shí)例191
上界194
Brooks定理197
習(xí)題199
5.2 k–色圖的結(jié)構(gòu)204
大色數(shù)圖205
極值問(wèn)題和Turán定理207
顏色–臨界圖210
強(qiáng)制細(xì)分212
習(xí)題214
5.3 計(jì)數(shù)方面的問(wèn)題219
真著色的計(jì)數(shù)219
弦圖224
完美圖點(diǎn)滴226
無(wú)環(huán)定向的計(jì)數(shù)（選學(xué)）228
習(xí)題229
第6章 可平面圖233
6.1 嵌入和歐拉公式233
平面作圖233
對(duì)偶圖236
歐拉公式241
習(xí)題243
6.2 可平面圖的特征246
Kuratowski定理的預(yù)備知識(shí)247
凸嵌入248
可平面性測(cè)試（選學(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
鯊魚(yú)圖（選學(xué)）304
流和環(huán)覆蓋（選學(xué)）307
習(xí)題314
第8章 其他主題（選學(xué)）319
8.1 完美圖319
完美圖定理320
弦圖的再研究323
其他類型的完美圖328
非完美圖334
強(qiáng)完美圖猜想340
習(xí)題344
8.2 擬陣349
遺傳系統(tǒng)和示例349
擬陣的性質(zhì)354
生成函數(shù)358
擬陣的對(duì)偶性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 其他極值問(wèn)題396
圖的編碼397
分叉和流言404
序列著色和可選擇性408
使用路徑和環(huán)的劃分413
周長(zhǎng)416
習(xí)題422
8.5 隨機(jī)圖425
存在性和期望值426
幾乎所有圖均具有的性質(zhì)430
閾值函數(shù)432
演變和圖參數(shù)436
連通度、團(tuán)和著色439
鞅442
習(xí)題448
8.6 圖的特征值452
特征多項(xiàng)式453
實(shí)對(duì)稱矩陣的線性代數(shù)456
特征值和圖參數(shù)458
正則圖的特征值460
特征值和擴(kuò)張圖463
強(qiáng)正則圖464
習(xí)題467
附錄A 數(shù)學(xué)基礎(chǔ)471
附錄B 最優(yōu)化和復(fù)雜度493
附錄C 部分習(xí)題的提示507
附錄D 術(shù)語(yǔ)表515
附錄E 補(bǔ)充閱讀材料533
附錄F 參考文獻(xiàn)567
作者索引569
術(shù)語(yǔ)索引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
鄂公網(wǎng)安備 42010302001612號(hào) 