圖書描述
圖論（Graph Theory）起源於1736年Leonhard Euler解答七橋問題的一篇文章，經過兩百年的孕育，1936年Kőnig寫齣第一本圖論專書，正式宣告這門學問誕生。此後，隨著生産管理、軍事、交通運輸、電腦和通訊網路等各領域的應用需求，圖論呈現爆炸性的發展。
在圖論的各種研究方法中，較重要的有拓樸方法、機率方法、代數方法、演算法。有效的演算法能協助電腦達到快速計算，對實用端有很大的好處。從數學的觀點來看，演算法其實是數學歸納法的化身，所以它可以用來幫忙證明定理；反過來說，一些定理的歸納法證明，也常能轉化成演算法。本書在各處盡可能地展現數學歸納法和演算法的一體兩麵特性。
全書分為兩部分，第一部分包含樹圖、匹配、連通度、平麵圖、圖著色等圖論的基礎知識；第二部分則包含一些著名的專題，例如完美圖、Ramsey理論、極值圖論、擬陣理論等。適閤相關領域教師授課時使用，亦可提供有興趣的讀者作為參考之用。
在圖論的各種研究方法中，較重要的有拓樸方法、機率方法、代數方法、演算法。有效的演算法能協助電腦達到快速計算，對實用端有很大的好處。從數學的觀點來看，演算法其實是數學歸納法的化身，所以它可以用來幫忙證明定理；反過來說，一些定理的歸納法證明，也常能轉化成演算法。本書在各處盡可能地展現數學歸納法和演算法的一體兩麵特性。
全書分為兩部分，第一部分包含樹圖、匹配、連通度、平麵圖、圖著色等圖論的基礎知識；第二部分則包含一些著名的專題，例如完美圖、Ramsey理論、極值圖論、擬陣理論等。適閤相關領域教師授課時使用，亦可提供有興趣的讀者作為參考之用。
著者信息
作者簡介
張鎮華
1952年生於南投縣草屯鎮；1982年取得康乃爾大學運籌學博士學位；1983年迴國，先後任教於中央大學數學係、交通大學應用數學係、颱灣大學數學係；2017年退休。主要研究領域在離散數學及組閤最優化，特彆是圖論及其演算法，發錶的兩百多篇論文涵蓋圖的控製集、圖著色、群試理論等。
張鎮華
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 參考文獻
索引
目次
圖目次
符號錶
第一部 基礎篇
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 參考文獻
索引
圖書序言
序（摘錄）
圖論這門學問有將近三百年的曆史，經由各方學者的研究，已經有很完整的發展，不但有在數學上的深度，在其他領域上也有很多應用。很少有一個數學的分支可以說是哪一年誕生的，而現在大傢公認，Euler在1736年解決Königsberg七橋問題的文章是圖論的起源。
從1736年到1936年這整整兩百年，可以說是圖論的春鞦戰國時代，不同領域的人們在他們各自的崗位上，用不同的名稱、不同的內容，探索和Euler發現的圖類似的概念。著名的包括四色問題[1852]和Hamilton問題[1856]。也有用圖當作工具去解決其他領域中一些問題的結果，例如，Kirchhoff [1847]用圖的概念來研究電的網路方程組問題，Cayley [1857]用樹的概念研究有機化閤物的分子結構問題。進入二十世紀30年代，更齣現瞭許多精彩的結果，例如Menger定理[1927]、Kuratowski定理[1930]和Ramsey定理[1930]等等。到瞭1936年，Kőnig寫齣第一本圖論專著《有限和無限圖的理論》，正式宣告圖論這門學問誕生。
1936年以後，由於生産管理、軍事、交通運輸、電腦和通訊網路等等各方麵許多離散數學問題的齣現，大大促進瞭圖論的發展。特彆是1970年代以後，大型電腦的齣現，使得大規模問題的求解成為可能，圖論和它在許多領域的應用呈現「爆炸性的發展」，各式各樣圖論的書籍以幾何級數的速度産生，本書就是其中之一。在圖的理論方麵，膾炙人口的結果包含：Appel、Haken和Koch [1977]藉由電腦的幫助，透過「放電論證法」證明四色問題；Robertson和Seymour從1983年到2004年在Journal of Combinatorial Theory, Series B發錶一連串20篇，總共超過500頁的文章，奠定瞭次圖（graph minor）相關的重要理論；Chudnovsky、Robertson、Seymour和Thomas [2006]在Annals of Mathematics發錶瞭一篇長達179頁的論文，證明瞭Berge在1960 年代提齣的著名的「強完美圖猜測」。
從研究圖論的方法來說，一些數學其他分支的工具，常常被用來解決圖論的問題。一個有名的例子是，Lovász [1978]利用代數拓樸的方法解決瞭Kneser猜測[1955]，這等同於決定瞭Kneser圖的著色數。另一個有名的例子是，Erdős開創瞭機率方法在圖論上的應用，這個方法經由Alon和Spencer的推廣宣傳，現在已經成為圖論（或更一般來說，組閤數學）的重要方法。另外，Tutte用代數上的Pfaffian當作工具，給齣一個圖有完美匹配的刻畫，雖然現在人們已經可以不用代數方法證明；Tutte原來的證明，對於近代利用平行演算法求最大匹配的數目仍有極大幫助。由於圖的本質上是離散的，所以演算法在圖論的研究上隨處可見。
這本書要特彆強調演算法在圖論所扮演的角色。從圖論在其他領域的應用方麵來說，把實際問題化成圖論模型，設計齣有效的演算法，再經由電腦的快速計算，對實用端有很大的好處。從數學的眼光來看，雖然在演算法理論中有各式各樣好聽的名詞：動態規劃、分治法、修剪和搜尋法、貪求法等等，但是它們的內在本質都是數學歸納法。圖論中的許多定理基本上都可以用數學歸納法證明，所以證明本身也蘊藏著演算法，有時候，利用演算法或是它的精神也可以提供有用的證明。這本書要在各處盡可能地展現數學歸納法和演算法的一體兩麵特性。另外，對於各個定理盡量提供目前已知的最簡單、最直接的證明，對於一部分定理也提供多種不同的證明方法和角度，希望能刺激讀者們的思考和迴饋。
這本書分成兩部分。第一部分從第1章到第8章，包含圖論的基礎知識，可以當作一個學期的教材；對於進度比較快，而沒有第二學期的課堂，可以適當選擇第二部分的某些章節加入授課；對於進度比較慢的課堂，可以適當捨去各章後麵的一兩節，例如打*號的節次。第二部分從第9章到第15章，包含圖論一些常見的專題，可以當作第二學期的教材，必要的時候，可以輔以最新的論文；這部分沒有打*號節次的建議，主要是由授課老師自行斟酌。
本人曆年來在中央大學、交通大學、颱灣大學開授圖論課程，每次挑選教科書都不容易找到符閤自己想法的書，因為有些定理明明可以直接由定義不難證明齣來，偏偏有些書就要繞一大圈。從正確性來說，倒是沒問題，但是從對一件事情瞭解的角度來說，似乎沒有看到證明的最主要部分，未達到「洞察本質」的精神，就常在課堂上或一些場閤「批判」這些證明方法，心中也偶爾有何不自己寫一本書的念頭。中央大學數學係廖勝強教授有一次就建議，何不寫一本中文的圖論教科書，除瞭讓大學老師授課使用，也可以給一些聰明的高中生自修使用，並且提供給有興趣的各類讀者參考。
圖論這門學問有將近三百年的曆史，經由各方學者的研究，已經有很完整的發展，不但有在數學上的深度，在其他領域上也有很多應用。很少有一個數學的分支可以說是哪一年誕生的，而現在大傢公認，Euler在1736年解決Königsberg七橋問題的文章是圖論的起源。
從1736年到1936年這整整兩百年，可以說是圖論的春鞦戰國時代，不同領域的人們在他們各自的崗位上，用不同的名稱、不同的內容，探索和Euler發現的圖類似的概念。著名的包括四色問題[1852]和Hamilton問題[1856]。也有用圖當作工具去解決其他領域中一些問題的結果，例如，Kirchhoff [1847]用圖的概念來研究電的網路方程組問題，Cayley [1857]用樹的概念研究有機化閤物的分子結構問題。進入二十世紀30年代，更齣現瞭許多精彩的結果，例如Menger定理[1927]、Kuratowski定理[1930]和Ramsey定理[1930]等等。到瞭1936年，Kőnig寫齣第一本圖論專著《有限和無限圖的理論》，正式宣告圖論這門學問誕生。
1936年以後，由於生産管理、軍事、交通運輸、電腦和通訊網路等等各方麵許多離散數學問題的齣現，大大促進瞭圖論的發展。特彆是1970年代以後，大型電腦的齣現，使得大規模問題的求解成為可能，圖論和它在許多領域的應用呈現「爆炸性的發展」，各式各樣圖論的書籍以幾何級數的速度産生，本書就是其中之一。在圖的理論方麵，膾炙人口的結果包含：Appel、Haken和Koch [1977]藉由電腦的幫助，透過「放電論證法」證明四色問題；Robertson和Seymour從1983年到2004年在Journal of Combinatorial Theory, Series B發錶一連串20篇，總共超過500頁的文章，奠定瞭次圖（graph minor）相關的重要理論；Chudnovsky、Robertson、Seymour和Thomas [2006]在Annals of Mathematics發錶瞭一篇長達179頁的論文，證明瞭Berge在1960 年代提齣的著名的「強完美圖猜測」。
從研究圖論的方法來說，一些數學其他分支的工具，常常被用來解決圖論的問題。一個有名的例子是，Lovász [1978]利用代數拓樸的方法解決瞭Kneser猜測[1955]，這等同於決定瞭Kneser圖的著色數。另一個有名的例子是，Erdős開創瞭機率方法在圖論上的應用，這個方法經由Alon和Spencer的推廣宣傳，現在已經成為圖論（或更一般來說，組閤數學）的重要方法。另外，Tutte用代數上的Pfaffian當作工具，給齣一個圖有完美匹配的刻畫，雖然現在人們已經可以不用代數方法證明；Tutte原來的證明，對於近代利用平行演算法求最大匹配的數目仍有極大幫助。由於圖的本質上是離散的，所以演算法在圖論的研究上隨處可見。
這本書要特彆強調演算法在圖論所扮演的角色。從圖論在其他領域的應用方麵來說，把實際問題化成圖論模型，設計齣有效的演算法，再經由電腦的快速計算，對實用端有很大的好處。從數學的眼光來看，雖然在演算法理論中有各式各樣好聽的名詞：動態規劃、分治法、修剪和搜尋法、貪求法等等，但是它們的內在本質都是數學歸納法。圖論中的許多定理基本上都可以用數學歸納法證明，所以證明本身也蘊藏著演算法，有時候，利用演算法或是它的精神也可以提供有用的證明。這本書要在各處盡可能地展現數學歸納法和演算法的一體兩麵特性。另外，對於各個定理盡量提供目前已知的最簡單、最直接的證明，對於一部分定理也提供多種不同的證明方法和角度，希望能刺激讀者們的思考和迴饋。
這本書分成兩部分。第一部分從第1章到第8章，包含圖論的基礎知識，可以當作一個學期的教材；對於進度比較快，而沒有第二學期的課堂，可以適當選擇第二部分的某些章節加入授課；對於進度比較慢的課堂，可以適當捨去各章後麵的一兩節，例如打*號的節次。第二部分從第9章到第15章，包含圖論一些常見的專題，可以當作第二學期的教材，必要的時候，可以輔以最新的論文；這部分沒有打*號節次的建議，主要是由授課老師自行斟酌。
本人曆年來在中央大學、交通大學、颱灣大學開授圖論課程，每次挑選教科書都不容易找到符閤自己想法的書，因為有些定理明明可以直接由定義不難證明齣來，偏偏有些書就要繞一大圈。從正確性來說，倒是沒問題，但是從對一件事情瞭解的角度來說，似乎沒有看到證明的最主要部分，未達到「洞察本質」的精神，就常在課堂上或一些場閤「批判」這些證明方法，心中也偶爾有何不自己寫一本書的念頭。中央大學數學係廖勝強教授有一次就建議，何不寫一本中文的圖論教科書，除瞭讓大學老師授課使用，也可以給一些聰明的高中生自修使用，並且提供給有興趣的各類讀者參考。
圖書試讀
用户评价
相关图书
本站所有內容均為互聯網搜尋引擎提供的公開搜索信息，本站不存儲任何數據與內容，任何內容與數據均與本站無關，如有需要請聯繫相關搜索引擎包括但不限於百度，google,bing,sogou 等
© 2025 twbook.tinynews.org All Rights Reserved. 灣灣書站 版權所有