第一章 圖與網(wǎng)絡(luò)的基本概念
§1 緒論
§2 一些基本概念
§3 圖的矩陣表示
§4 圖在計(jì)算機(jī)中的存儲(chǔ)
§5 計(jì)算復(fù)雜性與算法
習(xí)題1
第二章 樹
§1 路徑與連通
§2 有向圖的連通
§3 圖的搜索
§4 樹及其性質(zhì)
§5 生成樹算法
§6 有向樹
習(xí)題2
第三章 連通性
§1 連通度
§2 割邊、割集、割點(diǎn)
§3 塊與塊劃分
§4 可靠網(wǎng)絡(luò)的設(shè)計(jì)
習(xí)題3
第四章 路徑算法
§1 *短路徑問(wèn)題
§2 *短路徑問(wèn)題的一些擴(kuò)展
§3 *優(yōu)路徑
§4 關(guān)鍵路徑
§5 *短路徑算法的應(yīng)用
習(xí)題4
第五章 匹配
§1 匹配的概念
§2 匹配基本定理
§3 二部圖的*大基數(shù)匹配
§4 二部圖的*大權(quán)匹配
§5 一般圖的*大權(quán)匹配
§6 一般圖的*大權(quán)匹配
§7 匹配的應(yīng)用
習(xí)題5
第六章 行遍性問(wèn)題
§1 歐拉圖
§2 中國(guó)郵遞員問(wèn)題
§3 有向歐拉圖
§4 中國(guó)郵遞員問(wèn)題的應(yīng)用與推廣
§5 哈米爾頓圖
§6 有向哈米爾頓圖
§7 哈米爾頓圖的尋跡
§8 流動(dòng)推銷員問(wèn)題
§9 TSP的近似算法
§10 TPS的分枝定界法
§11 旅行推銷員問(wèn)題的應(yīng)用
習(xí)題6
第七章 平面圖
§1 平面圖的概念
§2 歐拉公式
§3 平面圖的對(duì)偶圖
§4 庫(kù)拉托夫斯基定理
§5 可平面性算法
§6 圖的交叉和厚度
習(xí)題7
第八章 圖的著色
§1 邊色數(shù)
§2 時(shí)間表問(wèn)題
§3 支配集與獨(dú)立集
§4 支配數(shù)、覆蓋數(shù)和獨(dú)立數(shù)的計(jì)算
§5 支配集與獨(dú)立集的應(yīng)用
§6 點(diǎn)色數(shù)
§7 色多項(xiàng)式
§8 色數(shù)的應(yīng)用和算法
習(xí)題8
第九章 網(wǎng)絡(luò)流問(wèn)題
§1 流與截集
§2 *大流*小截集定理
§3 ford和fulkcrson標(biāo)記法
§4 Dinits法
§5 *大流問(wèn)題的應(yīng)用與推廣
§6 *小費(fèi)用流
§7 有向圖的中國(guó)郵遞員問(wèn)題
習(xí)題9
參考文獻(xiàn)