線上閱讀
本書提供兩種檔案格式,請選擇開啟:
EPUB彈性排版,可依載具大小自動斷行或換頁,較適合小螢幕閱讀。
書籍內容
TOP
圖論(Graph Theory)起源於1736年Leonhard Euler解答七橋問題的一篇文章,經過兩百年的孕育,1936年Kőnig寫出第一本圖論專書,正式宣告這門學問誕生。此後,隨著生產管理、軍事、交通運輸、電腦和通訊網路等各領域的應用需求,圖論呈現爆炸性的發展。
在圖論的各種研究方法中,較重要的有拓樸方法、機率方法、代數方法、演算法。有效的演算法能協助電腦達到快速計算,對實用端有很大的好處。從數學的觀點來看,演算法其實是數學歸納法的化身,所以它可以用來幫忙證明定理;反過來說,一些定理的歸納法證明,也常能轉化成演算法。本書在各處盡可能地展現數學歸納法和演算法的一體兩面特性。
本書2017年初版後經由許多熱心朋友的建議,在修訂版中除將各細微處修改以外,各章比較大的更動如下:
●加強Ulam猜想的討論以及相關習題。
●第二章,增加堆積排序的說明,並將圖的連續空間儲存法由習題移至內文。
●第三章,大幅增加習題。
●第五章,增加利用最大流最小截的強對偶等式證明Kőnig定理。
●第七章,加強解釋貪求著色法,以及放電理論用以證明度數和的一個定理的證明的修正。
●第九章,強完美圖定理敘述的修正。
●第十章,利用Radziszowski動態調查文章[2017]第15版,更新一些R(p, q)值,並新增一些小圖的R(G,H)值。
●第十一章,增加對於禁用完全圖的Turán定理的一個新證明。
●第十五章,更新Turing機器的歷史介紹,並增加相對應的參考文獻。
在圖論的各種研究方法中,較重要的有拓樸方法、機率方法、代數方法、演算法。有效的演算法能協助電腦達到快速計算,對實用端有很大的好處。從數學的觀點來看,演算法其實是數學歸納法的化身,所以它可以用來幫忙證明定理;反過來說,一些定理的歸納法證明,也常能轉化成演算法。本書在各處盡可能地展現數學歸納法和演算法的一體兩面特性。
本書2017年初版後經由許多熱心朋友的建議,在修訂版中除將各細微處修改以外,各章比較大的更動如下:
●加強Ulam猜想的討論以及相關習題。
●第二章,增加堆積排序的說明,並將圖的連續空間儲存法由習題移至內文。
●第三章,大幅增加習題。
●第五章,增加利用最大流最小截的強對偶等式證明Kőnig定理。
●第七章,加強解釋貪求著色法,以及放電理論用以證明度數和的一個定理的證明的修正。
●第九章,強完美圖定理敘述的修正。
●第十章,利用Radziszowski動態調查文章[2017]第15版,更新一些R(p, q)值,並新增一些小圖的R(G,H)值。
●第十一章,增加對於禁用完全圖的Turán定理的一個新證明。
●第十五章,更新Turing機器的歷史介紹,並增加相對應的參考文獻。