有向圖的理論、算法及其應用（簡體書）

本書作者從近30年關于有向圖理論研究的數千篇論文中精選了具有理論意義、重要算法及其實際應用的結果，涵蓋了有向圖理論中從最基本到較為高深的重要專題。主要內容有：有向圖的基本知識和理論、連通性、圖的定向、網絡流、哈密爾頓性的深入研究、有向圖的路和圈、子模流、競賽圖的推廣以及有向圖的推廣、Menger定理和NP完全問題等。書中介紹了有向圖研究中數十個未解決的問題和猜想，盡可能為讀者在主要方向上提供最新的研究成果。對于計算機科學領域的學者來說，書中的大量算法以及實際應用的例子提供了難得的幫助。此外，配備了練習題700多道、方便查詢的參考文獻762篇，以及記號和術語索引等。
本書適合數學及應用數學、離散數學、運籌學、計算機科學等專業的本科生、研究生、教師及研究人員閱讀，也可供人工智能、社會科學以及工程技術人員參考。

圖論是離散數學中普及最廣的學科之一，不僅是由於它自身理論的迅速發展，而且是因為它在實際中有著大量的重要應用。近幾十年來的許多深刻的理論結果也導致了圖論學科的快速成長。然而，作為一個研究領域，圖論仍然還是一門相對年輕的學科，
圖的理論可以分為無向圖理論和有向圖理論兩大分支，雖然這兩大理論分支有著大量且重要的應用，但由於諸多的原因，無向圖比有向圖得到更為廣泛的研究。首先因為無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖），所以，凡能夠表述為無向圖和有向圖的問題通常用有向圖的方法解決較為容易；另一個原因是，不像無向圖的情形，除了幾本重要的書包含兩類圖的傳統和近期的結果，近25年來沒有一本專門介紹關於有向圖研究的完整結果的著作，在一般的教科書中，大多數作者用一章來講述有向圖，或者只有少量的有向圖基本知識與結論。
儘管如此，在近30年中，有向圖理論還是得到了長足的發展。超過3000篇的研究論文不僅涵蓋了具有理論意義的結果，而且包括了重要的算法及其應用。為了實際的需要，本書概括了有向圖的基本知識，並從深層次的角度介紹了理論和算法這兩個方面的研究成果及應用。
本書竭力為專題研究填補文獻與實用手冊間的溝壑，書中的基本內容是針對具有大學數學基礎知識的讀者，然後在幾個研究領域（包括連通性、圖的定向、子模流、有向圖的路和圈、競賽圖的推廣以及有向圖的推廣等）的主要方向上逐步到達新的研究成果，我們為本書配備了超過700道練習題、大量應用以及適宜討論的專題，對於我們所期望的不同群體的讀者（研究生、本科生、離散數學研究者、計算機科學中各個領域的研究者、運籌學研究、人工智能、社會科學以及工程技術人員等）來說，書中所有的專題不可能對全體讀者均有同等的意義。然而，我們相信，每位讀者都能從這本書裡找到吸引自己的有趣專題。
顯然，本書不可能是關於有向圖的百科全書，但是，我們盡可能地提供了許多有意義的結論，書中數量眾多的證明和技巧為讀者詳細地說明了有向圖理論和算法中所使用的各種各樣的方法和手段。
強調算法是本書最主要的特色之一，而這一點卻在一些圖論書中被遺憾地省略。首先，算法常常在不少領域的研究中扮演著重要的角色，尤其是在計算機科學和數值計算的研究中。其次，（有向）圖的許多問題本身就是算法問題，因此我們盡可能給出許多結論的構造性證明，利用這些構造性證明，讀者就可以從所研究的問題中提取一些有效的算法，雖然本書描述了許多算法，但鑑於篇幅限制，我們沒有提供全部必需的細節以使得讀者能夠正確地運用這些算法，這屬於計算科學的範疇（常常是極為不平凡的工作），建議讀者去閱讀數據結構方面的書籍。
本書的另一個重要的特色是精選了數量可觀的練習題，它們不僅可以幫助讀者理解，而且可以使讀者能夠通過大量的材料吃透書中所介紹的內容。嘗試解決這些習題（絕大部分是在本書中出現）將有助於讀者掌握所學的專題以及主要的研究技巧，
通過從易到難的廣泛而不間斷地學習和訓練，對於一些專門的問題，如（有向）圖論、組合優化和圖算法，讀者將會發現本書的作用。此外，本書也可以應用於某些熱門課題，如流、圈和連通性等。書中含有大量的解說，以幫助讀者讀懂不易理解的概念和深奧的證明。
出於使這本書成為一個便捷的研究參考書或大學教科書的考慮，我們增添了綜合性的記號和術語索引，可以確信，詳細的術語索引能夠幫助讀者找到所需要的對象而不必通讀整個章節，特別地，書後的索引列出了許多關於公開問題和猜想的條目。本書所討論的每一類有向圖均擁有自己的條目，即在討論這類圖的主要頁上。作為次條目，例如證明技巧條目，我們編制了不同證明技巧的索引，並標註出這些技巧所在的頁碼。
本書涵蓋了有向圖的從相當基本到較為高深範圍的主要且重要的專題。根據我們的經驗，這本書在今後的幾十年內將有助於教學和參考文獻搜索，我們在下面通過敘述一些重要的內容給出本書的輪廓，需要詳細信息的讀者可以參見目錄或書後的術語索引。
第1章包括了本書所使用的大部分術語、記號以及一些基本結論，它們不僅在其他章節中被頻繁地使用，而且被用作解釋有向圖的概念。進而，我們還將介紹幾個基於這些結論的有向圖的應用，並在本章的末尾處給出一個具體的應用。關於算法及其複雜性的基本概念也在這一章裡一併介紹，依據綜合性術語和記號索引，讀者不必讀完整個第1章後才進入其他章節的閱讀與學習。
第2章和第3章討論距離和網絡中的流。儘管這兩個專題的概念是基本的，然而，有向圖中距離以及網絡流的理論和算法特徵卻是相當重要的，因為它們對有向圖的其他理論問題和大量實際問題有著高度的可應用性，尤其是作為強有力的模型工具。
關於距離，我們首先介紹賦權和未賦權有向圖中最短路問題以及幾個傳統算法。第2章的主要內容是有向圖中距離參數的最小化和大化，我們將用下列問題結束這一章：單行道問題、閒話問題、指數鄰集局部搜索，並介紹一個關於組合優化問題尋找沂似優化懈的方法。

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