書籍檢索: : Google Books
 

 


 
演算法觀點的圖論

張鎮華 著

2017年10月
平裝 / 23*17cm / 476頁 / 單色(黑) / 中文

叢書系列教科書
ISBN: 978-986-350-258-6
GPN: 1010601642
定價500

線上購買:
線上試閱: Google Books
 

簡介
作者
目次
序言

圖論(Graph Theory)起源於1736年Leonhard Euler解答七橋問題的一篇文章,經過兩百年的孕育,1936年Kőnig寫出第一本圖論專書,正式宣告這門學問誕生。此後,隨著生產管理、軍事、交通運輸、電腦和通訊網路等各領域的應用需求,圖論呈現爆炸性的發展。

在圖論的各種研究方法中,較重要的有拓樸方法、機率方法、代數方法、演算法。有效的演算法能協助電腦達到快速計算,對實用端有很大的好處。從數學的觀點來看,演算法其實是數學歸納法的化身,所以它可以用來幫忙證明定理;反過來說,一些定理的歸納法證明,也常能轉化成演算法。本書在各處盡可能地展現數學歸納法和演算法的一體兩面特性。

全書分為兩部分,第一部分包含樹圖、匹配、連通度、平面圖、圖著色等圖論的基礎知識;第二部分則包含一些著名的專題,例如完美圖、Ramsey理論、極值圖論、擬陣理論等。適合相關領域教師授課時使用,亦可提供有興趣的讀者作為參考之用。

※本書第一版部分內容經作者修訂,詳細請參閱下方連結(最終更新時間 2018.6.24):
 
Graph theory originated from a 1736 paper by Leohard Euler where he solved the Königsberg Bridge Problem. The discipline is finally officially established after two hundred years’ development. 
 
Among various research methods of graph theory, the key ones are topology, probability theory, algebraic method, and algorithm. Efficient algorithm can assist the computer to perform fast calculation and is practically valuable. From the mathematical perspective, algorithm is in fact a form of mathematical induction and therefore it can be used to prove theorems. Conversely, an inductive proof of a theorem can be converted into algorithm. This book demonstrates thoroughly that mathematical induction and algorithm are two sides of the same coin.