Graph Theory, with an Algorithmic Perspective
| 作者 | 張鎮華 |
|---|---|
| 出版社 | 五楠圖書用品股份有限公司 |
| 商品描述 | 演算法觀點的圖論：圖論（GraphTheory）起源於1736年LeonhardEuler解答七橋問題的一篇文章，經過兩百年的孕育，1936年Kőnig寫出第一本圖論專書，正式宣告這門學問誕生。此 |
內容簡介
內容簡介 圖論（Graph Theory）起源於1736年Leonhard Euler解答七橋問題的一篇文章，經過兩百年的孕育，1936年Kőnig寫出第一本圖論專書，正式宣告這門學問誕生。此後，隨著生產管理、軍事、交通運輸、電腦和通訊網路等各領域的應用需求，圖論呈現爆炸性的發展。 在圖論的各種研究方法中，較重要的有拓樸方法、機率方法、代數方法、演算法。有效的演算法能協助電腦達到快速計算，對實用端有很大的好處。從數學的觀點來看，演算法其實是數學歸納法的化身，所以它可以用來幫忙證明定理；反過來說，一些定理的歸納法證明，也常能轉化成演算法。本書在各處盡可能地展現數學歸納法和演算法的一體兩面特性。 全書分為兩部分，第一部分包含樹圖、匹配、連通度、平面圖、圖著色等圖論的基礎知識；第二部分則包含一些著名的專題，例如完美圖、Ramsey理論、極值圖論、擬陣理論等。適合相關領域教師授課時使用，亦可提供有興趣的讀者作為參考之用。
作者介紹
作者介紹 ■作者簡介張鎮華1952年生於南投縣草屯鎮；1982年取得康乃爾大學運籌學博士學位；1983年回國，先後任教於中央大學數學系、交通大學應用數學系、臺灣大學數學系；2017年退休。主要研究領域在離散數學及組合最優化，特別是圖論及其演算法，發表的兩百多篇論文涵蓋圖的控制集、圖著色、群試理論等。
產品目錄
產品目錄 序符號表第一部 基礎篇1 通論1.1 圖論緣起：話說1736年1.2 圖的定義1.3 路徑1.4 Euler圖1.5 Euler迴路的應用1.6 度序列1.7 證明Brouwer定點定理1.8 習題1.9 參考文獻2 演算法簡介2.1 演算法起源2.2 演算法的複雜度2.3 資料結構2.4 表列和圖的表示法2.5 Euler迴路的案例2.6 聯集尋找問題2.7 習題2.8 參考文獻3 樹3.1 樹是簡單但重要的圖3.2 樹的基本性質3.3 樹的中心問題3.4 樹或圖的遍歷搜尋法3.5 生成樹計數3.6 最小生成樹3.7 習題3.8 參考文獻4 匹配4.1 婚姻問題面面觀4.2 匹配和完美匹配4.3 二分圖匹配4.4 加權二分圖匹配4.5 一般圖匹配4.6 Edmonds花被演算法4.7 穩定婚姻問題4.8 習題4.9 參考文獻5 圖的連通度5.1 團結在一起5.2 連通度和邊連通度5.3 2-連通圖5.4 k-連通圖和Menger定理5.5 最小連通圖5.6 網路流問題5.7 習題5.8 參考文獻6 平面圖6.1 老死不相往來的誓言6.2 平面圖6.3 Euler多面體公式6.4 Kuratowski定理6.5 外圍平面圖6.6 平面程度的度量6.7 習題6.8 參考文獻7 圖著色7.1 地圖著色7.2 點著色數和它的上界7.3 點著色數的下界7.4 平面圖著色7.5 邊著色7.6 列表著色7.7 習題7.8 參考文獻8 Hamilton圈8.1 環遊世界8.2 有Hamilton圈的必要條件8.3 有Hamilton圈的充分條件8.4 平面圖的Hamilton圈8.5 有向圖的Hamilton圈8.6 推銷員問題8.7 習題8.8 參考文獻第二部 專題篇9 完美圖9.1 Shannon零錯容量9.2 完美圖定義和猜想9.3 可比圖：第一類傳統完美圖9.4 弦圖：第二類傳統完美圖9.5 檢驗弦圖9.6 完美圖定理9.7 通往強完美圖定理的道路9.8 習題9.9 參考文獻10 Ramsey理論10.1 幸福結局問題10.2 第二層Ramsey數10.3 Ramsey定理10.4 圖Ramsey數10.5 任意長度等差數列10.6 證明van der Waerden定理10.7 習題10.8 參考文獻11 極值圖論11.1 令人瘋狂的樂趣11.2 禁用完全圖11.3 禁用完全二分圖11.4 禁用完全多分圖11.5 禁用路徑圖11.6 禁用圈圖11.7 習題11.8 參考文獻12 機率方法12.1 計數的藝術12.2 機率空間12.3 期望值12.4 更動法12.5 二階矩法和門檻函數12.6 局部引理12.7 習題12.8 參考文獻13 代數方法13.1 圖論和代數關係密切13.2 圖的特徵值13.3 圖參數和特徵值的關係13.4 特殊圖的特徵值13.5 強正則圖13.6 組合零點定理13.7 習題13.8 參考文獻14 擬陣14.1 擬陣起源14.2 繼承系統14.3 擬陣基本性質14.4 對偶擬陣14.5 擬陣和平面圖14.6 擬陣相交14.7 擬陣和14.8 習題14.9 參考文獻15 NP-完全問題15.1 難中之難、無過此難15.2 Turing機器15.3 Cook定理15.4 點覆蓋、獨立集和點團15.5 路徑和圈15.6 著色問題15.7 習題15.8 參考文獻索引
商品規格
| 書名 / | 演算法觀點的圖論 |
|---|---|
| 作者 / | 張鎮華 |
| 簡介 / | 演算法觀點的圖論：圖論（GraphTheory）起源於1736年LeonhardEuler解答七橋問題的一篇文章，經過兩百年的孕育，1936年Kőnig寫出第一本圖論專書，正式宣告這門學問誕生。此 |
| 出版社 / | 五楠圖書用品股份有限公司 |
| ISBN13 / | 9789863502586 |
| ISBN10 / | 9863502588 |
| EAN / | 9789863502586 |
| 誠品26碼 / | 2681518483004 |
| 頁數 / | 476 |
| 開數 / | 18K |
| 注音版 / | 否 |
| 裝訂 / | P:平裝 |
| 語言 / | 1:中文 繁體 |
| 級別 / | N:無 |