目錄
第1章 基本術(shù)語(yǔ)及結(jié)論 1
1.1 集合、子集、矩陣和向量 1
1.2 有向圖、有向子圖、鄰集和度數(shù) 2
1.3 有向圖的同構(gòu)及其基本運(yùn)算 6
1.4 途徑、跡、路、剛和路圈有向子圖 10
1.5 強(qiáng)連通性和單側(cè)連通性 15
1.6 無(wú)向圖、雙定向和定向性 17
1.7 混合圖和超圖 21
1.8 有向圖和無(wú)向圖的分類 23
1.9 算法簡(jiǎn)介 26
1.9.1 算法及其復(fù)雜性 26
1.9.2 NP完全問題和NP困難問題 30
1.10 應(yīng)用：求解2可滿足性問題 32
習(xí)題 35
第2章 距離 40
2.1 關(guān)于距離的術(shù)語(yǔ)和記號(hào) 40
2.2 最短路結(jié)構(gòu) 42
2.3 尋找有向圖距離的算法 44
2.3.1 寬度優(yōu)先搜索（BFS） 44
2.3.2 無(wú)圈有向圖 46
2.3.3 Dijkstra算法 47
2.3.4 Bellman-Ford-Moore算法 48
2.3.5 Floyd-Warshall算法 51
2.4 半徑、山半徑和直徑之間的不等式 52
2.4.1 強(qiáng)有向圖的半徑和直徑 52
2.4.2 出半徑和直徑的極值 53
2.5 定向圖的最大有限直徑 54
2.6 多重圖定向的最小直徑 55
2.7 完全多重圖的最小直徑定向 59
2.8 圖擴(kuò)張的最小直徑定向 61
2.9 笛卡兒積圖的最小直徑定向 63
2.10 有向圖中的王 66
2.10.1 競(jìng)賽圖的2王 66
2.10.2 半完全多部分有向圖中的王 66
2.10.3 廣義競(jìng)賽圖中的王 68
2.11 應(yīng)用：?jiǎn)涡械绬栴}和閑話問題 69
2.11.1 單行道問題和有向圖的定向 69
2.11.2 閑話問題 71
2.12 應(yīng)用：旅行售貨員問題的指數(shù)鄰集局部搜索 72
2.12.1 TSP局部搜索 72
2.12.2 TSP的線性時(shí)間叮搜索指數(shù)鄰集 74
2.12.3 分配鄰集 75
2.12.4 關(guān)于TSP的鄰集結(jié)構(gòu)有向圖的直徑 76
2.13 習(xí)題 78
第3章 網(wǎng)絡(luò)流 82
3.1 定義及基本性質(zhì) 82
3.1.1 流及流平衡向量 83
3.1.2 剩余網(wǎng)絡(luò) 85
3.2 網(wǎng)絡(luò)模型的簡(jiǎn)約 86
3.2.1 消除下界 86
3.2.2 單源單收點(diǎn)網(wǎng)絡(luò) 86
3.2.3 循環(huán) 87
3.2.4 頂點(diǎn)上有費(fèi)用及下界的網(wǎng)絡(luò) 88
3.3 流分解 90
3.4 時(shí)論剩余網(wǎng)絡(luò) 91
3.5 最大流問題 93
3.5.1 Ford-Fullkerson算法 96
3.5.2 最大流與線性規(guī)劃 98
3.6 尋找最大（s，t）流的多項(xiàng)式算法 99
3.6.1 沿最短增廣路的流增廣 99
3.6.2 在分層網(wǎng)絡(luò)和Dinic算法中的塊化流 100
3.6.3 前置流推進(jìn)算法 101
3.7 單位容量網(wǎng)絡(luò)和簡(jiǎn)單網(wǎng)絡(luò) 105
3.7.1 單位容量網(wǎng)絡(luò) 106
3.7.2 簡(jiǎn)單網(wǎng)絡(luò) 107
3.8 循環(huán)與可行流 108
3.9 最小值可行（s，I）流 110
3.10 最小費(fèi)用流 111
3.10.1 刻畫最小費(fèi)用流 113
3.10.2 創(chuàng)建最優(yōu)化解 116
3.11 流的應(yīng)用 118
3.11.1 部分圖的最大匹配 118
3.11.2 有向中國(guó)郵遞員問題 121
3.11.3 尋找具有預(yù)先指定度的有向子圖 l23
3.11.4 有向多重圖的路圈因子 124
3.11.5 覆蓋指定頂點(diǎn)的圈有向子圖 126
3.12 分配問題和運(yùn)輸問題 127
3.13 習(xí)題 l36
第4章 有向圖類 148
4.1 深度優(yōu)先搜索 148
4.2 無(wú)圈有向圖中的頂點(diǎn)無(wú)圈序 151
4.3 可傳遞有向圖、可傳遞閉包和簡(jiǎn)約 153
4.4 強(qiáng)有向圖 155
4.5 線有向圖 158
4.6 de Bruijn有向圖和Kautz有向圖及其特征 l62
4 7 系列平行有向圖 165
4.8 擬可傳遞有向圖 169
4.9 路重合性質(zhì)和路可重合有向圖 171
4.10 局部入半完全有向圖和局部山半完全有向圖 173
4.11 局部半完全有向圖 175
4.11.1 圓有向圖 175
4.11.2 非強(qiáng)局部半完全有向圖 179
4.11.3 強(qiáng)圓可分解局部半完全有向圖 l8l
4.11.4 局部半完全有向圖類 183
4.12 全φi可分解有向圖 l85
4.13 相交有向圖 187
4.14 平而有向圖 189
4.15 應(yīng)用：高斯消去法 l9l
4.16 習(xí)題 l93
第5章 哈密爾頓性及其相關(guān)問題 l96
5.1 有向圖哈密爾頓性的必要條件 197
5.1.1 路收縮 197
5.1.2 擬哈密爾頓性 198
5.1.3 偽哈密爾頓性和1擬哈密爾頓性 200
5.1.4 關(guān)于偽哈密爾頓性和擬哈密爾頓性的算法 201
5.2 路覆蓋數(shù) 201
5.3 無(wú)圈有向圖的路因子及其應(yīng)用 203
5.4 路可重合有向圖的哈密爾頓路與圈 204
5.5 局部入半完全有向圖的哈密爾頓路和圈 205
5.6 具有度約束條件的有向圖的哈密爾頓圈和路 20?
5.6.1 充分性條件 207
5.6.2 多重插入技巧 211
5.6.3 定理5.6.1和定理5.6.5的證明 213
5.7 半完全多部分有向圖中的最長(zhǎng)路和最長(zhǎng)路圈 215
5.7.1 基本結(jié)論 215
5.7.2 良圈因子定理 217
5.7.3 引理5.7.12的推論 220
5.7.4 Yeo不可約圈有向子圖定理及其應(yīng)用 222
5.8 擴(kuò)張局部半完全有向圖的最長(zhǎng)路和最長(zhǎng)圈 226
5.9 擬可傳遞有向圖中的哈密爾頓路和圈 227
5.10 擬可傳遞有向圖中頂點(diǎn)最重路和最重圈 230
5.11 有向圖類的哈密爾頓路和圈 234
5.12 習(xí)題 236
第6章 深入研究哈密爾頓性 241
6.1 具有預(yù)先指定起（終）點(diǎn)的哈密爾頓路 242
6.2 弱哈密爾頓連通有向圖 243
6.2.1 關(guān)于擴(kuò)張競(jìng)賽圖的結(jié)論 244
6.2.2 關(guān)于局部半完全有向圖的結(jié)論 248
6.3 哈密爾頓連通有向圖 251
6.4 在半完全有向圖中尋找（x，y）哈密爾頓路 253
6.5 有向圖的泛圈性 256
6.5.1 度約束有向圖的（頂點(diǎn)）泛圈性 256
6.5.2 擴(kuò)張半完全有向圖和擬可傳遞有向圖的泛圈性 257
6.5.3 泛局部半完全有向圖和頂點(diǎn)泛局部半完全有向圖 260
6.5.4 關(guān)于圖泛圈性的其他結(jié)果 263
6.5.5 有向圖的圈可擴(kuò)張性 264
6.6 弧泛圈性 265
6 7 包含或避開預(yù)先指定弧的哈密爾頓圈 267
6.7.1 包含預(yù)先指定弧的哈密爾頓圈 268
6 7 2 避開預(yù)先指定弧的哈密爾頓圈 270
6.7.3 避開2圈中弧的哈密爾頓圈 272
6.8 弧不交的哈密爾頓路和圈 273
6.9 定向的哈密爾頓路和圈 275
6.10 用少量圈覆蓋一個(gè)有向圖的全部頂點(diǎn) 280
6.10.1 具有固定圈數(shù)目的圈因子 280
6.10.2 父于路和圈的支撐結(jié)構(gòu)中α（D）的作用 282
6.11 最小強(qiáng)支撐有向子圖 283
6.11.1 關(guān)于一般有向圖的一個(gè)下界 284
6.11.2 關(guān)于擴(kuò)張半完全有向圖的MSSS問題 285
6.11.3 關(guān)于擬可傳遞有向圖的MSSS問題 286
6.11.4 可分解有向圖的MSSS問題 287
6.12 應(yīng)用：TSP直觀探索法的控制數(shù) 288
6.13 習(xí)題 290
第7章 全連通性 294
7.1 附加的概念和預(yù)備知識(shí) 295
7.2 耳朵分解 297
7.3 Menger定理 300
7.4 應(yīng)用：確定弧強(qiáng)連通度和頂點(diǎn)強(qiáng)連通度 303
7.5 撕裂運(yùn)算 305
7.6 最優(yōu)化增長(zhǎng)弧強(qiáng)連通性 309
7.7 最優(yōu)化增長(zhǎng)頂點(diǎn)強(qiáng)連通性 312
7.7.1 單行對(duì) 313
7.7.2 最優(yōu)化的k強(qiáng)增廣 315
7.7.3 特殊類有向圖 316
7.7.4 保持k強(qiáng)連通性的撕裂 318
7.8 弧強(qiáng)連通性的一個(gè)推廣 320
7.9 弧反轉(zhuǎn)和頂點(diǎn)強(qiáng)連通性 322
7.10 最小k（�。�強(qiáng)有向多重圖 325
7.10.1 最小良弧強(qiáng)有向多重圖 326
7.10.2 最小k強(qiáng)有向圖 329
7.11 臨界k強(qiáng)有向圖 333
7.12 弧強(qiáng)連通性與最小度 334
7.13 特殊類有向圖的連通性性質(zhì) 335
7.14 有向圖的高連通定向 337
7.15 拼裝割集 341
7.16 應(yīng)用：關(guān)于k（�。�強(qiáng)連通性的小認(rèn)證 344
7.16.1 尋找強(qiáng)連通性的小認(rèn)證 345
7.16.2 尋找k強(qiáng)認(rèn)證（k>1） 346
7.16.3 關(guān)于弧強(qiáng)連通性認(rèn)證 348
7.17 習(xí)題 349
第8章 圖的定向 353
8.1 幾類有向圖的底圖 353
8.1.1 可傳遞有向圖和擬可傳遞有向圖的底圖 353
8.1.2 局部半完全有向圖的底圖 356
8.1.3 正常循環(huán)弧圖的局部競(jìng)賽圖定向 358
8.1.4 局部入半完全有向圖的底圖 360
8.2 快速識(shí)別局部半完全有向圖 364
8.3 無(wú)偶圈定向 367
8.4 圖的著色與定向 369
8.5 定向與無(wú)處零整流 371
8.6 達(dá)到高弧強(qiáng)連通性的定向 375
8 7 具有度約束的定向 378
8 7 1 具有預(yù)先指定度序列的定向 378
8.7.2 對(duì)頂點(diǎn)予集的限制 382
8.8 子模流 383
8.8.1 子模流模型 383
8.8.2 可行子模流的存在性 385
8.8.3 最小費(fèi)用子模流 388
8.8.4 子模流的應(yīng)用 388
8.9 混合圖的定向 392
8.10 習(xí)題 396
第9章 不交路和不交樹 402
9.1 補(bǔ)充定義 403
9.2 不交路問題 403
9.2.1 k路問題的復(fù)雜性 404
9.2.2 有向圖是良鏈接的充分性條件 408
9.2.3 無(wú)圈有向圖的k路問題 410
9.3 競(jìng)賽圖和廣義競(jìng)賽圖的鏈接問題 413
9.3.1 具有（局部）連通性的充分性條件 413
9.3.2 半完全有向圖的2路問題 417
9.3.3 廣義競(jìng)賽圖的2路問題 418
9.4 平面有向圖的鏈接問題 42l
9.5 弧不交分枝 424
9.5.1 Edmonds分枝定理的重要性 426
9.6 邊不交的混合分枝 429
9 7 弧不交的路問題 430
9.7.1 無(wú)圈有向多重圖中弧不交的路 432
9 7 2 歐拉有向多重圖中弧不交的路 433
9 7 3 競(jìng)賽圖和廣義競(jìng)賽圖中弧不交的路 438
9.8 整多物品流 44l
9.9 弧不交的出分枝和入分枝 442
9.10 最小費(fèi)用分枝 447
9.10.1 擬陣相交的表述 447
9.10.2 有關(guān)最小費(fèi)用分枝問題推廣的一個(gè)算法 448
9.10.3 最小覆蓋樹形圖問題 453
9.11 添加新弧以增加有根弧強(qiáng)連通性 455
9.12 刊題 456
第10章 有向圖的圈結(jié)構(gòu) 462
10.1 有向圖的向量空間 462
10.2 關(guān)于路和圈的多項(xiàng)式算法 466
10.3 不交圈和反饋弧集 469
10.3.1 不交圈和反饋集問題的復(fù)雜性 469
10.3.2 最大出度至少為k的有向圖中不交圈 470
10.3.3 有向圖的反饋集和線性序 472
10.4 不交圈對(duì)反饋集的比較 476
10.4.1 參數(shù)vi和Ti的關(guān)系 476
10.4.2 Younger猜想的解決 477
10.5 應(yīng)用：Markov鏈的周期 480
10.6 模p下的k長(zhǎng)圈 482
10.6.1 模下k長(zhǎng)圈存在性問題的復(fù)雜度 482
10.6.2 模p下k長(zhǎng)圈存在的充分性條件 483
10 7 半完全多部分有向圖中的“短”圈 486
10.8 半完全多部分有向圖中圈對(duì)路的比較 489
10.9 圍長(zhǎng) 493
10.10 有關(guān)圈的補(bǔ)充專題 495
10.10.1 圈的弦 495
10.10.2 Adam猜想 496
10.11 習(xí)題 498
第11章 有向圖的推廣 501
11.1 邊著色多重圖中的正常著色跡 501
11.1.1 正常著色歐拉跡 503
11.1.2 正常著色圈 506
11.1.3 邊著色多重圖的連通性 509
11.1.4 邊著色二部分多重闖的交錯(cuò)圈 512
11.1.5 2邊著色完全多重圖的最長(zhǎng)交錯(cuò)路和圈 514
11.1.6 c邊著色完全圖中正常著色哈密爾頓路（c≥3） 520
11.1 7 c邊著色完全圖中正常著色哈密爾頓圈（c≥3） 521
11.2 弧著色有向多重圖 525
11.2.1 交錯(cuò)有向圈問題的復(fù)雜性 526
11.2.2 函數(shù)f（n）和函數(shù)g（n） 529
11.2.3 弱歐拉弧著色有向多重圖 531
11.3 超競(jìng)賽圖 532
11.3.1 超競(jìng)賽圖的出度序列 533
11.3.2 哈密爾頓路 534
11.3.3 哈密爾頓圈 535
11.4 應(yīng)用：遺傳學(xué)中的交錯(cuò)哈密爾頓圈 536
11.4.1 定理11.4.1的證明 538
11.4.2 定理11.4.2的證明 539
11.5 習(xí)題 540
第12章 些重要的專題 542
12.1 Seymour第二鄰集猜想 542
12.2 配對(duì)比較有向圖的頂點(diǎn)排序 545
12.2.1 配對(duì)比較有向圖 545
12.2.2 Kano-Sakamoto排序法 547
12.2.3 半完全PCD的頂點(diǎn)排序 548
12.2.4 相互序 549
12.2.5 關(guān)于向前序和向后序的算法及其復(fù)雜性 549
12.3 （k，l）核 552
12.3.1 核 552
12.3.2 擬核 554
12.4 完全二部分有向圖的列表邊著色 555
12.5 同態(tài)——著色的一個(gè)推廣 558
12.6 有向圖獨(dú)立性的其他度量法 563
12.7 擬陣 565
12.7.1 擬陣的對(duì)偶 567
12.7.2 擬陣的貪婪算法 567
12.7.3 獨(dú)立性問答器 569
12.7.4 擬陣的并 569
12.7.5 二個(gè)擬陣的相交 570
12.7.6 多個(gè)擬陣的相交 57l
12.8 為NP困難問題尋找好解 572
12.9 習(xí)題 575
參考文獻(xiàn) 580
記號(hào)索引 616
術(shù)語(yǔ)索引 625
譯后記 661
《現(xiàn)代數(shù)學(xué)譯叢》已出版書目 663