《有向圖的理論算法及其套用》作者從近30年關於有向圖理論研究的數千篇論文中精選了具有理論意義、重要算法及其實際套用的結果，涵蓋了有向圖理論中從最基本到較為高深的重要專題。主要內容有：有向圖的基本知識和理論、連通性、圖的定向、網路流、哈密爾頓性的深入研究、有向圖的路和圈、子模流、競賽圖的推廣以及有向圖的推廣、Menger定理和NP完全問題等。書中介紹了有向圖研究中數十個未解決的問題和猜想，儘可能為讀者在主要方向上提供最新的研究成果。對於計算機科學領域的學者來說，書中的大量算法以及實際套用的例子提供了難得的幫助。此外，配備了練習題700多道、方便查詢的參考文獻762篇，以及記號和術語索引等。《有向圖的理論算法及其套用》適合數學及套用數學、離散數學、運籌學、計算機科學等專業的本科生、研究生、教師及研究人員閱讀，也可供人工智慧、社會科學以及工程技術人員參考。
基本介紹
- 書名：有向圖的理論算法及其套用
- 譯者：G.古廷
- 出版日期：2009年1月1日
- 語種：簡體中文
- ISBN：9787030228048
- 作者：J.邦詹森
- 出版社：科學出版社
- 頁數：661頁
- 開本：16
- 品牌：科學出版社
內容簡介,作者簡介,圖書目錄,後記,序言,
內容簡介
《有向圖的理論算法及其套用》概括了有向圖的基本知識，並從深層次的角度介紹了理論和算法這兩個方面的研究成果及套用。書中的基本內容是針對具有大學數學基礎知識的讀者，然後在幾個研究領域（包括連通性、圖的定向、子模流、有向圖的路和圈、競賽圖的推廣以及有向圖的推廣等）的主要方向上逐步到達最新的研究成果。《有向圖的理論算法及其套用》配備了超過700道練習題、大量套用以及適宜討論的專題
作者簡介
作者：(丹麥)J.邦詹森 譯者：(英國)G.古廷
圖書目錄
第1章 基本術語及結論
1.1 集合、子集、矩陣和向量
1.2 有向圖、有向子圖、鄰集和度數
1.3 有向圖的同構及其基本運算
1.4 途徑、跡、路、圈和路圈有向子圖
1.5 強連通性和單側連通性
1.6 無向圖、雙定向和定向性
1.7 混合圖和超圖
1.8 有向圖和無向圖的分類
1.9 算法簡介
1.9.1 算法及其複雜性
1.9.2 NP完全問題和NP困難問題
1.10 套用：求解2可滿足性問題
1.11 習題
第2章 距離
2.1 關於距離的術語和記號
2.2 最短路結構
2.3 尋找有向圖距離的算法
2.3.1 寬度優先搜尋（BFS）
2.3.2 無圈有向圖
2.3.3 Dijkstra算法
2.3.4 Bellman-Ford-Moore算法
2.3.5 Floyd-Warshall算法
2.4 半徑、出半徑和直徑之間的不等式
2.4.1 強有向圖的半徑和直徑
2.4.2 出半徑和直徑的極值
2.5 定向圖的最大有限直徑
2.6 多重圖定向的最小直徑
2.7 完全多重圖的最小直徑定向
2.8 圖擴張的最小直徑定向
2.9 笛卡兒積圖的最小直徑定向
2.10 有向圖中的王
2.10.1 競賽圖的2王
2.10.2 半完全多部分有向圖中的王
2.10.3 廣義競賽圖中的王
2.11 套用：單行道問題和閒話問題
2.11.1 單行道問題和有向圖的定向
2.11.2 閒話問題
2.12 套用：旅行售貨員問題的指數鄰集局部搜尋
2.12.1 TSP局部搜尋
2.12.2 TSP的線性時間可搜尋指數鄰集
2.12.3 分配鄰集
2.12.4 關於TSP的鄰集結構有向圖的直徑
2.13 習題
第3章 網路流
3.1 定義及基本性質
3.1.1 流及流平衡向量
3.1.2 剩餘網路
3.2 網路模型的簡約
3.2.1 消除下界
3.2.2 單源單收點網路
3.2.3 循環
3.2.4 頂點上有費用及下界的網路
3.3 流分解
3.4 討論剩餘網路
3.5 最大流問題
3.5.1 Ford-Fullkerson算法
3.5.2 最大流與線性規劃
3.6 尋找最大（s,t）流的多項式算法
3.6.1 沿最短增廣路的流增廣
3.6.2 在分層網路和Dinic算法中的塊化流
3.6.3 前置流推進算法
3.7 單位容量網路和簡單網路
3.7.1 單位容量網路
3.7.2 簡單網路
3.8 循環與可行流
3.9 最小值可行（s,t）流
3.10 最小費用流
3.10.1 刻畫最小費用流
3.10.2 創建最最佳化解
3.11 流的套用
3.11.1 二部分圖的最大匹配
3.11.2 有向中國郵遞員問題
3.11.3 尋找具有預先指定度的有向子圖
3.11.4 有向多重圖的路圈因子
3.11.5 覆蓋指定頂點的圈有向子圖
3.12 分配問題和運輸問題
3.13 習題
第4章 有向圖類
4.1 深度優先搜尋
4.2 無圈有向圖中的頂點無圈序
4.3 可傳遞有向圖、可傳遞閉包和簡約
4.4 強有向圖
4.5 線有向圖
4.6 de Bruijn有向圖和Kautz有向圖及其特徵
4.7 系列平行有向圖
4.8 擬可傳遞有向圖
4.9 路重合性質和路可重合有向圖
4.10 局部入半完全有向圖和局部出半完全有向圖
4.11 局部半完全有向圖
4.11.1 圓有向圖
4.11.2 非強局部半完全有向圖
4.11.3 強圓可分解局部半完全有向圖
4.11.4 局部半完全有向圖類
4.12 全Φi可分解有向圖
4.13 相交有向圖
4.14 平面有向圖
4.15 套用：高斯消去法
4.16 習題
第5章 哈密爾頓性及其相關問題
5.1 有向圖哈密爾頓性的必要條件
5.1.1 路收縮
5.1.2 擬哈密爾頓性
5.1.3 偽哈密爾頓性和1擬哈密爾頓性
5.1.4 關於偽哈密爾頓性和擬哈密爾頓性的算法
5.2 路覆蓋數
5.3 無圈有向圖的路因子及其套用
5.4 路可重合有向圖的哈密爾頓路與圈
5.5 局部入半完全有向圖的哈密爾頓路和圈
5.6 具有度約束條件的有向圖的哈密爾頓圈和路
5.6.1 充分性條件
5.6.2 多重插入技巧
5.6.3 定理5.6.1和定理5.6.5的證明
5.7 半完全多部分有向圖中的最長路和最長路圈
5.7.1 基本結論
5.7.2 良圈因子定理
5.7.3 引理5.7.12的推論
5.7.4 Yeo不可約圈有向子圖定理及其套用
5.8 擴張局部半完全有向圖的最長路和最長圈
5.9 擬可傳遞有向圖中的哈密爾頓路和圈
5.10 擬可傳遞有向圖中頂點最重路和最重圈
5.11 有向圖類的哈密爾頓路和圈
5.12 習題
第6章 深入研究哈密爾頓性
6.1 具有預先指定起（終）點的哈密爾頓路
6.2 弱哈密爾頓連通有向圖
6.2.1 關於擴張競賽圖的結論
6.2.2 關於局部半完全有向圖的結論
6.3 哈密爾頓連通有向圖
6.4 在半完全有向圖中尋找（x,y）哈密爾頓路
6.5 有向圖的泛圈性
6.5.1 度約束有向圖的（頂點）泛圈性
6.5.2 擴張半完全有向圖和擬可傳遞有向圖的泛圈性
6.5.3 泛局部半完全有向圖和頂點泛局部半完全有向圖
6.5.4 關於圖泛圈性的其他結果
6.5.5 有向圖的圈可擴張性
6.6 弧泛圈性
6.7 包含或避開預先指定弧的哈密爾頓圈
6.7.1 包含預先指定弧的哈密爾頓圈
6.7.2 避開預先指定弧的哈密爾頓圈
6.7.3 避開2圈中弧的哈密爾頓圈
6.8 弧不交的哈密爾頓路和圈
6.9 定向的哈密爾頓路和圈
6.10 用少量圈覆蓋一個有向圖的全部頂點
6.10.1 具有固定圈數目的圈因子
6.10.2 關於路和圈的支撐結構中α（D）的作用
6.11 最小強支撐有向子圖
6.11.1 關於一般有向圖的一個下界
6.11.2 關於擴張半完全有向圖的MSSS問題
6.11.3 關於擬可傳遞有向圖的MSSS問題
6.11.4 可分解有向圖的MSSS問題
6.12 套用：TSP直觀探索法的控制數
6.13 習題
第7章 全連通性
7.1 附加的概念和預備知識
7.2 耳朵分解
7.3 Menger定理
7.4 套用：確定弧強連通度和頂點強連通度
7.5 撕裂運算
7.6 最最佳化增長弧強連通性
7.7 最最佳化增長頂點強連通性
7.7.1 單行對
7.7.2 最最佳化的k強增廣
7.7.3 特殊類有向圖
7.7.4 保持k強連通性的撕裂
7.8 弧強連通性的一個推廣
7.9 弧反轉和頂點強連通性
7.10 最小k（弧）強有向多重圖
7.10.1 最小k弧強有向多重圖
7.10.2 最小k強有向圖
7.11 臨界k強有向圖
7.12 弧強連通性與最小度
7.13 特殊類有向圖的連通性性質
7.14 有向圖的高連通定向
7.15 拼裝割集
7.16 套用：關於k（弧）強連通性的小認證
7.16.1 尋找強連通性的小認證
7.16.2 尋找k強認證（k>1）
7.16.3 關於弧強連通性認證
7.17 習題
第8章 圖的定向
8.1 幾類有向圖的底圖
8.1.1 可傳遞有向圖和擬可傳遞有向圖的底圖
8.1.2 局部半完全有向圖的底圖
8.1.3 正常循環弧圖的局部競賽圖定向
8.1.4 局部入半完全有向圖的底圖
8.2 快速識別局部半完全有向圖
8.3 無偶圈定向
8.4 圖的著色與定向
8.5 定向與無處零整流
8.6 達到高弧強連通性的定向
8.7 具有度約束的定向
8.7.1 具有預先指定度序列的定向
8.7.2 對頂點子集的限制
8.8 子模流
8.8.1 子模流模型
8.8.2 可行子模流的存在性
8.8.3 最小費用子模流
8.8.4 子模流的套用
8.9 混合圖的定向
8.10 習題
第9章 不交路和不交樹
9.1 補充定義
9.2 不交路問題
9.2.1 k路問題的複雜性
9.2.2 有向圖是k連結的充分性條件
9.2.3 無圈有向圖的k路問題
9.3 競賽圖和廣義競賽圖的連結問題
9.3.1 具有（局部）連通性的充分性條件
9.3.2 半完全有向圖的2路問題
9.3.3 廣義競賽圖的2路問題
9.4 平面有向圖的連結問題
9.5 弧不交分枝
9.5.1 Edmonds分枝定理的重要性
9.6 邊不交的混合分枝
9.7 弧不交的路問題
9.7.1 無圈有向多重圖中弧不交的路
9.7.2 歐拉有向多重圖中弧不交的路
9.7.3 競賽圖和廣義競賽圖中弧不交的路
9.8 整多物品流
9.9 弧不交的出分枝和入分枝
9.10 最小費用分枝
9.10.1 擬陣相交的表述
9.10.2 有關最小費用分枝問題推廣的一個算法
9.10.3 最小覆蓋樹形圖問題
9.11 添加新弧以增加有根弧強連通性
9.12 習題
第10章 有向圖的圈結構
10.1 有向圖的向量空間
10.2 關於路和圈的多項式算法
10.3 不交圈和反饋弧集
10.3.1 不交圈和反饋集問題的複雜性
10.3.2 最大出度至少為k的有向圖中不交圈
10.3.3 有向圖的反饋集和線性序
10.4 不交圈對反饋集的比較
10.4.1 參數Vi和Ti的關係
10.4.2 Younger猜想的解決
10.5 套用：Markov鏈的周期
10.6 模p下的k長圈
10.6.1 模p下k長圈存在性問題的複雜度
10.6.2 模p下k長圈存在的充分性條件
10.7 半完全多部分有向圖中的"短"圈
10.8 半完全多部分有向圖中圈對路的比較
10.9 圍長
10.10 有關圈的補充專題
10.10.1 圈的弦
10.10.2 ádám猜想
10.11 習題
第11章 有向圖的推廣
11.1 邊著色多重圖中的正常著色跡
11.1.1 正常著色歐拉跡
11.1.2 正常著色圈
11.1.3 邊著色多重圖的連通性
11.1.4 邊著色二部分多重圖的交錯圈
11.1.5 2邊著色完全多重圖的最長交錯路和圈
11.1.6 c邊著色完全圖中正常著色哈密爾頓路（c≥3）
11.1.7 c邊著色完全圖中正常著色哈密爾頓圈（c≥3）
11.2 弧著色有向多重圖
11.2.1 交錯有向圈問題的複雜性
11.2.2 函式f（n）和函式g（n）
11.2.3 弱歐拉弧著色有向多重圖
11.3 超競賽圖
11.3.1 超競賽圖的出度序列
11.3.2 哈密爾頓路
11.3.3 哈密爾頓圈
11.4 套用：遺傳學中的交錯哈密爾頓圈
11.4.1 定理11.4.1的證明
11.4.2 定理11.4.2的證明
11.5 習題
第12章 一些重要的專題
12.1 Seymour第二鄰集猜想
12.2 配對比較有向圖的頂點排序
12.2.1 配對比較有向圖
12.2.2 Kano-Sakamoto排序法
12.2.3 半完全PCD的頂點排序
12.2.4 相互序
12.2.5 關於向前序和向後序的算法及其複雜性
12.3 （k,l）核
12.3.1 核
12.3.2 擬核
12.4 完全二部分有向圖的列表邊著色
12.5 同態——著色的一個推廣
12.6 有向圖獨立性的其他度量法
12.7 擬陣
12.7.1 擬陣的對偶
12.7.2 擬陣的貪婪算法
12.7.3 獨立性問答器
12.7.4 擬陣的並
12.7.5 二個擬陣的相交
12.7.6 多個擬陣的相交
12.8 為NP困難問題尋找好解
12.9 習題
參考文獻
記號索引
術語索引
譯後記
《現代數學譯叢》已出版書目
1.1 集合、子集、矩陣和向量
1.2 有向圖、有向子圖、鄰集和度數
1.3 有向圖的同構及其基本運算
1.4 途徑、跡、路、圈和路圈有向子圖
1.5 強連通性和單側連通性
1.6 無向圖、雙定向和定向性
1.7 混合圖和超圖
1.8 有向圖和無向圖的分類
1.9 算法簡介
1.9.1 算法及其複雜性
1.9.2 NP完全問題和NP困難問題
1.10 套用：求解2可滿足性問題
1.11 習題
第2章 距離
2.1 關於距離的術語和記號
2.2 最短路結構
2.3 尋找有向圖距離的算法
2.3.1 寬度優先搜尋（BFS）
2.3.2 無圈有向圖
2.3.3 Dijkstra算法
2.3.4 Bellman-Ford-Moore算法
2.3.5 Floyd-Warshall算法
2.4 半徑、出半徑和直徑之間的不等式
2.4.1 強有向圖的半徑和直徑
2.4.2 出半徑和直徑的極值
2.5 定向圖的最大有限直徑
2.6 多重圖定向的最小直徑
2.7 完全多重圖的最小直徑定向
2.8 圖擴張的最小直徑定向
2.9 笛卡兒積圖的最小直徑定向
2.10 有向圖中的王
2.10.1 競賽圖的2王
2.10.2 半完全多部分有向圖中的王
2.10.3 廣義競賽圖中的王
2.11 套用：單行道問題和閒話問題
2.11.1 單行道問題和有向圖的定向
2.11.2 閒話問題
2.12 套用：旅行售貨員問題的指數鄰集局部搜尋
2.12.1 TSP局部搜尋
2.12.2 TSP的線性時間可搜尋指數鄰集
2.12.3 分配鄰集
2.12.4 關於TSP的鄰集結構有向圖的直徑
2.13 習題
第3章 網路流
3.1 定義及基本性質
3.1.1 流及流平衡向量
3.1.2 剩餘網路
3.2 網路模型的簡約
3.2.1 消除下界
3.2.2 單源單收點網路
3.2.3 循環
3.2.4 頂點上有費用及下界的網路
3.3 流分解
3.4 討論剩餘網路
3.5 最大流問題
3.5.1 Ford-Fullkerson算法
3.5.2 最大流與線性規劃
3.6 尋找最大（s,t）流的多項式算法
3.6.1 沿最短增廣路的流增廣
3.6.2 在分層網路和Dinic算法中的塊化流
3.6.3 前置流推進算法
3.7 單位容量網路和簡單網路
3.7.1 單位容量網路
3.7.2 簡單網路
3.8 循環與可行流
3.9 最小值可行（s,t）流
3.10 最小費用流
3.10.1 刻畫最小費用流
3.10.2 創建最最佳化解
3.11 流的套用
3.11.1 二部分圖的最大匹配
3.11.2 有向中國郵遞員問題
3.11.3 尋找具有預先指定度的有向子圖
3.11.4 有向多重圖的路圈因子
3.11.5 覆蓋指定頂點的圈有向子圖
3.12 分配問題和運輸問題
3.13 習題
第4章 有向圖類
4.1 深度優先搜尋
4.2 無圈有向圖中的頂點無圈序
4.3 可傳遞有向圖、可傳遞閉包和簡約
4.4 強有向圖
4.5 線有向圖
4.6 de Bruijn有向圖和Kautz有向圖及其特徵
4.7 系列平行有向圖
4.8 擬可傳遞有向圖
4.9 路重合性質和路可重合有向圖
4.10 局部入半完全有向圖和局部出半完全有向圖
4.11 局部半完全有向圖
4.11.1 圓有向圖
4.11.2 非強局部半完全有向圖
4.11.3 強圓可分解局部半完全有向圖
4.11.4 局部半完全有向圖類
4.12 全Φi可分解有向圖
4.13 相交有向圖
4.14 平面有向圖
4.15 套用：高斯消去法
4.16 習題
第5章 哈密爾頓性及其相關問題
5.1 有向圖哈密爾頓性的必要條件
5.1.1 路收縮
5.1.2 擬哈密爾頓性
5.1.3 偽哈密爾頓性和1擬哈密爾頓性
5.1.4 關於偽哈密爾頓性和擬哈密爾頓性的算法
5.2 路覆蓋數
5.3 無圈有向圖的路因子及其套用
5.4 路可重合有向圖的哈密爾頓路與圈
5.5 局部入半完全有向圖的哈密爾頓路和圈
5.6 具有度約束條件的有向圖的哈密爾頓圈和路
5.6.1 充分性條件
5.6.2 多重插入技巧
5.6.3 定理5.6.1和定理5.6.5的證明
5.7 半完全多部分有向圖中的最長路和最長路圈
5.7.1 基本結論
5.7.2 良圈因子定理
5.7.3 引理5.7.12的推論
5.7.4 Yeo不可約圈有向子圖定理及其套用
5.8 擴張局部半完全有向圖的最長路和最長圈
5.9 擬可傳遞有向圖中的哈密爾頓路和圈
5.10 擬可傳遞有向圖中頂點最重路和最重圈
5.11 有向圖類的哈密爾頓路和圈
5.12 習題
第6章 深入研究哈密爾頓性
6.1 具有預先指定起（終）點的哈密爾頓路
6.2 弱哈密爾頓連通有向圖
6.2.1 關於擴張競賽圖的結論
6.2.2 關於局部半完全有向圖的結論
6.3 哈密爾頓連通有向圖
6.4 在半完全有向圖中尋找（x,y）哈密爾頓路
6.5 有向圖的泛圈性
6.5.1 度約束有向圖的（頂點）泛圈性
6.5.2 擴張半完全有向圖和擬可傳遞有向圖的泛圈性
6.5.3 泛局部半完全有向圖和頂點泛局部半完全有向圖
6.5.4 關於圖泛圈性的其他結果
6.5.5 有向圖的圈可擴張性
6.6 弧泛圈性
6.7 包含或避開預先指定弧的哈密爾頓圈
6.7.1 包含預先指定弧的哈密爾頓圈
6.7.2 避開預先指定弧的哈密爾頓圈
6.7.3 避開2圈中弧的哈密爾頓圈
6.8 弧不交的哈密爾頓路和圈
6.9 定向的哈密爾頓路和圈
6.10 用少量圈覆蓋一個有向圖的全部頂點
6.10.1 具有固定圈數目的圈因子
6.10.2 關於路和圈的支撐結構中α（D）的作用
6.11 最小強支撐有向子圖
6.11.1 關於一般有向圖的一個下界
6.11.2 關於擴張半完全有向圖的MSSS問題
6.11.3 關於擬可傳遞有向圖的MSSS問題
6.11.4 可分解有向圖的MSSS問題
6.12 套用：TSP直觀探索法的控制數
6.13 習題
第7章 全連通性
7.1 附加的概念和預備知識
7.2 耳朵分解
7.3 Menger定理
7.4 套用：確定弧強連通度和頂點強連通度
7.5 撕裂運算
7.6 最最佳化增長弧強連通性
7.7 最最佳化增長頂點強連通性
7.7.1 單行對
7.7.2 最最佳化的k強增廣
7.7.3 特殊類有向圖
7.7.4 保持k強連通性的撕裂
7.8 弧強連通性的一個推廣
7.9 弧反轉和頂點強連通性
7.10 最小k（弧）強有向多重圖
7.10.1 最小k弧強有向多重圖
7.10.2 最小k強有向圖
7.11 臨界k強有向圖
7.12 弧強連通性與最小度
7.13 特殊類有向圖的連通性性質
7.14 有向圖的高連通定向
7.15 拼裝割集
7.16 套用：關於k（弧）強連通性的小認證
7.16.1 尋找強連通性的小認證
7.16.2 尋找k強認證（k>1）
7.16.3 關於弧強連通性認證
7.17 習題
第8章 圖的定向
8.1 幾類有向圖的底圖
8.1.1 可傳遞有向圖和擬可傳遞有向圖的底圖
8.1.2 局部半完全有向圖的底圖
8.1.3 正常循環弧圖的局部競賽圖定向
8.1.4 局部入半完全有向圖的底圖
8.2 快速識別局部半完全有向圖
8.3 無偶圈定向
8.4 圖的著色與定向
8.5 定向與無處零整流
8.6 達到高弧強連通性的定向
8.7 具有度約束的定向
8.7.1 具有預先指定度序列的定向
8.7.2 對頂點子集的限制
8.8 子模流
8.8.1 子模流模型
8.8.2 可行子模流的存在性
8.8.3 最小費用子模流
8.8.4 子模流的套用
8.9 混合圖的定向
8.10 習題
第9章 不交路和不交樹
9.1 補充定義
9.2 不交路問題
9.2.1 k路問題的複雜性
9.2.2 有向圖是k連結的充分性條件
9.2.3 無圈有向圖的k路問題
9.3 競賽圖和廣義競賽圖的連結問題
9.3.1 具有（局部）連通性的充分性條件
9.3.2 半完全有向圖的2路問題
9.3.3 廣義競賽圖的2路問題
9.4 平面有向圖的連結問題
9.5 弧不交分枝
9.5.1 Edmonds分枝定理的重要性
9.6 邊不交的混合分枝
9.7 弧不交的路問題
9.7.1 無圈有向多重圖中弧不交的路
9.7.2 歐拉有向多重圖中弧不交的路
9.7.3 競賽圖和廣義競賽圖中弧不交的路
9.8 整多物品流
9.9 弧不交的出分枝和入分枝
9.10 最小費用分枝
9.10.1 擬陣相交的表述
9.10.2 有關最小費用分枝問題推廣的一個算法
9.10.3 最小覆蓋樹形圖問題
9.11 添加新弧以增加有根弧強連通性
9.12 習題
第10章 有向圖的圈結構
10.1 有向圖的向量空間
10.2 關於路和圈的多項式算法
10.3 不交圈和反饋弧集
10.3.1 不交圈和反饋集問題的複雜性
10.3.2 最大出度至少為k的有向圖中不交圈
10.3.3 有向圖的反饋集和線性序
10.4 不交圈對反饋集的比較
10.4.1 參數Vi和Ti的關係
10.4.2 Younger猜想的解決
10.5 套用：Markov鏈的周期
10.6 模p下的k長圈
10.6.1 模p下k長圈存在性問題的複雜度
10.6.2 模p下k長圈存在的充分性條件
10.7 半完全多部分有向圖中的"短"圈
10.8 半完全多部分有向圖中圈對路的比較
10.9 圍長
10.10 有關圈的補充專題
10.10.1 圈的弦
10.10.2 ádám猜想
10.11 習題
第11章 有向圖的推廣
11.1 邊著色多重圖中的正常著色跡
11.1.1 正常著色歐拉跡
11.1.2 正常著色圈
11.1.3 邊著色多重圖的連通性
11.1.4 邊著色二部分多重圖的交錯圈
11.1.5 2邊著色完全多重圖的最長交錯路和圈
11.1.6 c邊著色完全圖中正常著色哈密爾頓路（c≥3）
11.1.7 c邊著色完全圖中正常著色哈密爾頓圈（c≥3）
11.2 弧著色有向多重圖
11.2.1 交錯有向圈問題的複雜性
11.2.2 函式f（n）和函式g（n）
11.2.3 弱歐拉弧著色有向多重圖
11.3 超競賽圖
11.3.1 超競賽圖的出度序列
11.3.2 哈密爾頓路
11.3.3 哈密爾頓圈
11.4 套用：遺傳學中的交錯哈密爾頓圈
11.4.1 定理11.4.1的證明
11.4.2 定理11.4.2的證明
11.5 習題
第12章 一些重要的專題
12.1 Seymour第二鄰集猜想
12.2 配對比較有向圖的頂點排序
12.2.1 配對比較有向圖
12.2.2 Kano-Sakamoto排序法
12.2.3 半完全PCD的頂點排序
12.2.4 相互序
12.2.5 關於向前序和向後序的算法及其複雜性
12.3 （k,l）核
12.3.1 核
12.3.2 擬核
12.4 完全二部分有向圖的列表邊著色
12.5 同態——著色的一個推廣
12.6 有向圖獨立性的其他度量法
12.7 擬陣
12.7.1 擬陣的對偶
12.7.2 擬陣的貪婪算法
12.7.3 獨立性問答器
12.7.4 擬陣的並
12.7.5 二個擬陣的相交
12.7.6 多個擬陣的相交
12.8 為NP困難問題尋找好解
12.9 習題
參考文獻
記號索引
術語索引
譯後記
《現代數學譯叢》已出版書目
後記
譯稿交付出版社，我們卻沒有如釋重負之感。《有向圖的理論、算法及其套用》一書的容量十分龐大：書中引用的論文和書籍762篇（本），還不包括書中涉及的私人通信里未發表的文章等。全書12章，共有151個引理，465個定理，100個推論，89個命題，26個問題，54個猜想以圾三十餘個算法。書中有很多沒有用正規格式表述的結論、未解決的問題和猜想，還有那些嵌入在證明內的算法等，我們均沒有一一進行統計。值得注意的是，在700多道習題中，部分習題是正文中沒有提及的結論、算法和問題等。
本書中的有向圖理論幾乎涵蓋了當今有向圖理論的主要研究專題，如哈密爾頓圈問題、最短路問題、網路流理論等。書中關於哈密爾頓圈問題的深入研究，為讀者介紹了各種各樣關聯到哈密爾頓問題及其推廣的專題；Mengel定理在研究K（弧）強有向圖的套用和推廣，如Edmonds分枝定理和K連結問題等，將十分有助於啟發我們研究問題的思路和認識研究對象的方式，有益於我們設計研究方案或提出進攻困難問題的方向。
本書作者南丹麥大學數學與計算機科學系J。邦詹森教授和倫敦大學皇家霍洛威學院計算機科學系G.古廷（Gregory Gutin）教授在內容編排和寫作設計方面獨具匠心，由淺顯基本的結論逐步過渡到當今有向圖理論中某些專題研究的前沿。他們力圖使讀者不僅理解、掌握有向圖的成熟理論，而且有能力投入到有向圖中未解決問題的研究主流里。加上書後的參考文獻、精煉的記號和一詳盡的術語，我們認為這是一本兼顧教學和研究雙重任務的高度專業性書籍。
本書的重要特色之一是提供了大量的證明技巧和方法。例如，Madei的撕裂技巧、多重插入技巧、兩類問題之間的簡約或等價轉換、算法式論證、網路流模型、集合函式的子模流、擬陣算法等。書中使用了一些代數、組合、機率和線性規劃等學科中的部分方法，如Ramsey定理、ErdSs Szekeres定理、阿貝爾群、布爾變數、對偶定理等，為讀者的自行研究提供了大量的工具。作者指出，無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖）。所以，無向圖理論和有向圖理論的有機結合也是值得我們考慮和研究的一個方面。
本書中的有向圖理論幾乎涵蓋了當今有向圖理論的主要研究專題，如哈密爾頓圈問題、最短路問題、網路流理論等。書中關於哈密爾頓圈問題的深入研究，為讀者介紹了各種各樣關聯到哈密爾頓問題及其推廣的專題；Mengel定理在研究K（弧）強有向圖的套用和推廣，如Edmonds分枝定理和K連結問題等，將十分有助於啟發我們研究問題的思路和認識研究對象的方式，有益於我們設計研究方案或提出進攻困難問題的方向。
本書作者南丹麥大學數學與計算機科學系J。邦詹森教授和倫敦大學皇家霍洛威學院計算機科學系G.古廷（Gregory Gutin）教授在內容編排和寫作設計方面獨具匠心，由淺顯基本的結論逐步過渡到當今有向圖理論中某些專題研究的前沿。他們力圖使讀者不僅理解、掌握有向圖的成熟理論，而且有能力投入到有向圖中未解決問題的研究主流里。加上書後的參考文獻、精煉的記號和一詳盡的術語，我們認為這是一本兼顧教學和研究雙重任務的高度專業性書籍。
本書的重要特色之一是提供了大量的證明技巧和方法。例如，Madei的撕裂技巧、多重插入技巧、兩類問題之間的簡約或等價轉換、算法式論證、網路流模型、集合函式的子模流、擬陣算法等。書中使用了一些代數、組合、機率和線性規劃等學科中的部分方法，如Ramsey定理、ErdSs Szekeres定理、阿貝爾群、布爾變數、對偶定理等，為讀者的自行研究提供了大量的工具。作者指出，無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖）。所以，無向圖理論和有向圖理論的有機結合也是值得我們考慮和研究的一個方面。
序言
圖論是離散數學中普及最廣的學科之一，不僅是由於它自身理論的迅速發展，而且是因為它在實際中有著大量的重要套用。近幾十年來的許多深刻的理論結果也導致了圖論學科的快速成長。然而，作為一個研究領域，圖論仍然還是一門相對年輕的學科。
圖的理論可以分為無向圖理論和有向圖理論兩大分支。雖然這兩大理論分支有著大量且重要的套用，但由於諸多的原因，無向圖比有向圖得到更為廣泛的研究。首先因為無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖），所以，凡能夠表述為無向圖和有向圖的問題通常用有向圖的方法解決較為容易；另一個原因是，不像無向圖的情形，除了幾本重要的書包含兩類圖的傳統和近期的結果，近25年來沒有一本專門介紹關於有向圖研究的完整結果的著作。在一般的教科書中，大多數作者用一章來講述有向圖，或者只有少量的有向圖基本知識與結論。
儘管如此，在近30年中，有向圖理論還是得到了長足的發展。超過3000篇的研究論文不僅涵蓋了具有理論意義的結果，而且包括了重要的算法及其套用。為了實際的需要，本書概括了有向圖的基本知識，並從深層次的角度介紹了理論和算法這兩個方面的研究成果及套用。
本書竭力為專題研究填補文獻與實用手冊間的溝壑。書中的基本內容是針對具有大學數學基礎知識的讀者，然後在幾個研究領域（包括連通性、圖的定向、子模流、有向圖的路和圈、競賽圖的推廣以及有向圖的推廣等）的主要方向上逐步到達最新的研究成果。我們為本書配備了超過700道練習題、大量套用以及適宜討論的專題。對於我們所期望的不同群體的讀者（研究生、本科生、離散數學研究者、計算機科學中各個領域的研究者、運籌學研究、人工智慧、社會科學以及工程技術人員等）來說，書中所有的專題不可能對全體讀者均有同等的意義。然而，我們相信，每位讀者都能從這本書里找到吸引自己的有趣專題。
顯然，本書不可能是關於有向圖的百科全書，但是，我們儘可能地提供了許多有意義的結論。書中數量眾多的證明和技巧為讀者詳細地說明了有向圖理論和算法中所使用的各種各樣的方法和手段。
圖的理論可以分為無向圖理論和有向圖理論兩大分支。雖然這兩大理論分支有著大量且重要的套用，但由於諸多的原因，無向圖比有向圖得到更為廣泛的研究。首先因為無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖），所以，凡能夠表述為無向圖和有向圖的問題通常用有向圖的方法解決較為容易；另一個原因是，不像無向圖的情形，除了幾本重要的書包含兩類圖的傳統和近期的結果，近25年來沒有一本專門介紹關於有向圖研究的完整結果的著作。在一般的教科書中，大多數作者用一章來講述有向圖，或者只有少量的有向圖基本知識與結論。
儘管如此，在近30年中，有向圖理論還是得到了長足的發展。超過3000篇的研究論文不僅涵蓋了具有理論意義的結果，而且包括了重要的算法及其套用。為了實際的需要，本書概括了有向圖的基本知識，並從深層次的角度介紹了理論和算法這兩個方面的研究成果及套用。
本書竭力為專題研究填補文獻與實用手冊間的溝壑。書中的基本內容是針對具有大學數學基礎知識的讀者，然後在幾個研究領域（包括連通性、圖的定向、子模流、有向圖的路和圈、競賽圖的推廣以及有向圖的推廣等）的主要方向上逐步到達最新的研究成果。我們為本書配備了超過700道練習題、大量套用以及適宜討論的專題。對於我們所期望的不同群體的讀者（研究生、本科生、離散數學研究者、計算機科學中各個領域的研究者、運籌學研究、人工智慧、社會科學以及工程技術人員等）來說，書中所有的專題不可能對全體讀者均有同等的意義。然而，我們相信，每位讀者都能從這本書里找到吸引自己的有趣專題。
顯然，本書不可能是關於有向圖的百科全書，但是，我們儘可能地提供了許多有意義的結論。書中數量眾多的證明和技巧為讀者詳細地說明了有向圖理論和算法中所使用的各種各樣的方法和手段。
