第1章 基本概念1
1.1 什么是圖1
定義1
圖模型3
矩陣和同構6
分解和特殊圖11
習題14
1.2 路徑、環(huán)和跡19
圖的連通性20
二部圖24
歐拉回路26
習題31
1.3 頂點度和計數(shù)34
計數(shù)和雙射35
極值問題38
圖序列44
習題47
1.4 有向圖53
定義和例子53
頂點度58
歐拉有向圖60
定向和競賽圖61
習題63
第2章 樹和距離67
2.1 基本性質67
樹的性質68
樹和圖中的距離70
不相交生成樹（選學）73
習題75
2.2 生成樹和枚舉81
樹的枚舉81
圖的生成樹83
分解和優(yōu)美標記87
分叉和歐拉有向圖（選學）89
習題92
2.3 最優(yōu)化和樹95
最小生成樹95
最短路徑97
計算機科學中的樹（選學）100
習題103
第3章 匹配和因子107
3.1 匹配和覆蓋107
最大匹配108
Hall匹配條件110
最小–最大定理112
獨立集和覆蓋113
支配集（選學）116
習題118
3.2 算法和應用123
最大二部匹配123
加權二部匹配125
穩(wěn)定匹配（選學）130
快速二部匹配（選學）132
習題134
3.3 一般圖中的匹配136
Tutte 1-因子定理136
圖的f-因子（選學）140
Edmonds開花算法（選學）142
習題145
第4章 連通度和路徑149
4.1 割和連通度149
連通度149
邊–連通度152
塊155
習題158
4.2 k–連通圖161
2–連通圖161
有向圖的連通度164
k–連通圖和k–邊連通圖166
Menger定理的應用170
習題172
4.3 網(wǎng)絡流問題176
最大網(wǎng)絡流176
整數(shù)流181
供應和需求（選學）184
習題188
第5章 圖的著色191
5.1 頂點著色和上界191
定義和實例191
上界194
Brooks定理197
習題199
5.2 k–色圖的結構204
大色數(shù)圖205
極值問題和Turán定理207
顏色–臨界圖210
強制細分212
習題214
5.3 計數(shù)方面的問題219
真著色的計數(shù)219
弦圖224
完美圖點滴226
無環(huán)定向的計數(shù)（選學）228
習題229
第6章 可平面圖233
6.1 嵌入和歐拉公式233
平面作圖233
對偶圖236
歐拉公式241
習題243
6.2 可平面圖的特征246
Kuratowski定理的預備知識247
凸嵌入248
可平面性測試（選學）252
習題255
6.3 可平面性的參數(shù)257
可平面圖的著色257
交叉數(shù)261
具有更高虧格的表面（選學）266
習題269
第7章 邊和環(huán)273
7.1 線圖和邊著色273
邊著色274
線圖的特征（選學）279
習題282
7.2 哈密頓環(huán)286
必要條件287
充分條件288
有向圖中的環(huán)（選學）293
習題294
7.3 可平面性、著色和環(huán)299
Tait定理300
Grinberg定理302
鯊魚圖（選學）304
流和環(huán)覆蓋（選學）307
習題314
第8章 其他主題（選學）319
8.1 完美圖319
完美圖定理320
弦圖的再研究323
其他類型的完美圖328
非完美圖334
強完美圖猜想340
習題344
8.2 擬陣349
遺傳系統(tǒng)和示例349
擬陣的性質354
生成函數(shù)358
擬陣的對偶性360
擬陣的子式和可平面圖363
擬陣的交366
擬陣的并369
習題372
8.3 Ramsey理論378
鴿巢原理的再研究378
Ramsey定理380
Ramsey數(shù)383
關于圖的Ramsey理論386
Sperner引理和帶寬388
習題392
8.4 其他極值問題396
圖的編碼397
分叉和流言404
序列著色和可選擇性408
使用路徑和環(huán)的劃分413
周長416
習題422
8.5 隨機圖425
存在性和期望值426
幾乎所有圖均具有的性質430
閾值函數(shù)432
演變和圖參數(shù)436
連通度、團和著色439
鞅442
習題448
8.6 圖的特征值452
特征多項式453
實對稱矩陣的線性代數(shù)456
特征值和圖參數(shù)458
正則圖的特征值460
特征值和擴張圖463
強正則圖464
習題467
附錄A 數(shù)學基礎471
附錄B 最優(yōu)化和復雜度493
附錄C 部分習題的提示507
附錄D 術語表515
附錄E 補充閱讀材料533
附錄F 參考文獻567
作者索引569
術語索引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號 