图論及其演算法.PDF

圖論及 其演算 法 圖論及 其演算 法 圖論及 其演算 法 張 鎮華 張 鎮華 張 鎮華 蔡牧村 蔡牧村 蔡牧村 台 大 台 數 學系 大 台 數 學系 大 數 學系 i 序 iii 目錄 第 1 章 通論 1 4.3 加權二分圖匹配 71 1.1 圖的定義3 4.4 一般圖匹配 73 1.2 路徑 7 4.5 Edmonds 的花被演算法 75 1.3 Euler 圖 10 4.6 穩定婚姻問題 80 1.4 應用 14 習題 82 1.5 度序列 16 附註 85 習題 21 參考文獻 85 附註 23 第 5 章 連通 87 參考文獻 24 5.1 連通度與邊連通度 87 第 2 章 淺談演算法 25 5.2 2-連通圖 92 2.1 演算法之複雜度 25 5.3 k-連通性與 Menger 定理 97 2.2 資料結構 30 5.4 最小連通圖 100 2.3 一個案例：聯集尋找問題 34 習題 102 習題 36 附註 104 附註 38 參考文獻 104 參考文獻 38 第 6 章 平面圖 105 第 3 章 樹 41 6.1 平面圖 106 3.1 基本性質 42 6.2 Euler 多面體公式 110 3.2 中心問題45 6.3 Kuratowski 定理 113 3.3 生成樹之建立 48 6.4 外圍平面圖 118 3.4 生成樹計數 51 6.5 平面程度的度量 121 3.5 最小生成樹 55 習題 126 習題 58 附註 128 附註 59 參考文獻 128 參考文獻 60 第 7 章 圖著色 131 第 4 章 匹配 61 7.1 點著色 133 4.1 匹配與完美匹配 61 7.2 平面圖著色 140 4.2 二分圖匹配 65 7.3 邊著色 146 iv 目錄