圖論簡明教程

簡介

《圖論簡明教程》是一本通俗易懂的圖論入門教材。全書共分11章，其中第1章回顧了圖論所需的數學基礎知識；第2章講解了圖論領域的各種基本概念；後面的8章講解了幾類特殊的圖及套用，並給出了一些重要而常用的算法；最後一章討論兩個附加的專題：Ramsey理論和圖支配。為了便於讀者理解和掌握基本理論，書中不僅提供了豐富的例題，而且每節後配有大量習題，並在書的最後提供部分習題的答案。

本書具有系統性、理論性和實用性強的特點，可作為大專院校計算機科學、數學、社會科學、商學以及工程學等專業的教科書，亦可供其他科技工作者作為參考書目。本書起點低，不需要高等數學的知識，所以也可以作為中學生奧林匹克競賽相關學科的課外讀物。

作者介紹

FredBuckley和MartyLewinter分別任教於Baruch大學和Purchase大學，他們的研究領域包括圖論、經典幾何學、數論以及數學史。

創作背景

圖論是一門極有趣味的學問，其廣闊的套用領域涵蓋了人類學、計算機科學、化學、環境保護、流體動力學、心理學、社會學、交通管理、電信領域等等。在20世紀，隨著運籌學的出現，圖論更是為確立其卓越的地位起到了十分重要的作用。嚴格地講，圖論是組合數學的一個分支，例如，它交叉運用了拓撲學、群論和數論。圖論中定理和證明的難度高低不等，有的簡單易懂，有的幾乎不可理解，然而圖論終究還只是研究點和線的學問。圖論的套用非常廣泛，不僅局限於數學和計算機科學，因此各專業的學生都應該打下一定的圖論基礎，這樣他們就會多掌握一種強大而靈活的工具來分析和處理自己學科領域中的問題。這本教材主要面向本科水平的讀者，使他們能比較容易理解。我們僅僅假設讀者具有一定的代數基礎，因此，本書敞開了一座大門，無論數學、計算機科學、社會科學、商學還是工程學專業的學生，只要有需求，你都能儘早地接觸這個精彩而頗有裨益的研究領域。雖然這是一本易懂的教材，但讀的時候還是應該拿上紙和筆--這不是睡前的休閒讀物。書中的習題有易有難，能夠體現相應章節的內容。書後有解答或提示，其涵蓋了大部分的習題。此外，應該意識到，數學不是一項觀賞性質的體育賽事(當然當您看到有人對某個重要結論做出了簡單得驚人的證明，您也一定會覺得這是一件激動人心的事)，請務必要做習題，否則當您讀到最後一章時，第一章的內容就會被忘到腦後。能夠做完較難習題的勤勉的學生會得到很大益處--為今後的圖論研究打下堅實基礎，他們也會有能力將圖論的思想套用到紛亂複雜的現實問題中去。在第1章，我們討論了必備的基礎概念，讀者應該熟練掌握這些內容。我們雖然稱這一章為複習，但其內容仍然十分完備，提供了必要的數學工具來幫助讀者理解全書其餘部分的內容。因此這一章講了集合、函式、奇偶性、數學歸納法、證明技巧、計數原理、排列組合、Pascal三角形和組合恆等式。對於不熟悉證明技巧的學生來說，本章對他們會有很大的幫助。而對於基礎比較紮實的學生，老師可有選擇地跳過本章的部分甚至全部內容。如前所述，圖論的套用極為廣泛。在第2章中，我們將介紹圖論中最基本的概念，同時也將展示圖論的一些套用領域。當然，我們也會在後面看到許多其他的套用。有一類非常重要的圖值得我們用單獨的一章(第3章)來介紹，這就是樹。由於結構簡單，樹常常被用作新理論的試驗場。樹的概念起源於許多領域，例如分析商務層次、求具有最小代價的運輸網路等等，此外樹也是計算機科學中的一種十分重要的數據結構。樹是更大的一類圖的特例，這類圖稱作二分圖。在第3章中，我們講述了樹、二分圖以及它們的套用。最後，本章以工作分配問題結束。距離的概念在圖論的理論和實踐中套用很廣泛，許多有關圖的操作都需要使用距離，例如同構判定、凸面問題。另外，距離也是許多對稱概念的基礎。許多圖中心的概念亦由距離來定義，中心的概念在場地布局問題中起著關鍵的作用。圖論的眾多算法都與距離相關，這些算法往往需要在圖中搜尋各種長度的路。距離也在連通性問題中扮演著重要的角色，而連通性問題涉及到計算機網路的可靠性和健壯性問題，因而占有十分關鍵的地位。在第4章，我們將討論關於距離和連通性的一些重要概念和結論，然後作為總結，我們將解決一個場地布局問題，並給出計算機網路的可靠性概念。圖論中許多的理論和實際問題都需要我們以某種方法遍歷整個圖。例如在某些問題中，我們的目標是求出一條跡或迴路，滿足經過每條邊一次且僅一次；在另一些問題中，我們可能需要求出一條路或圈，滿足經過每個結點一次且僅一次。我們在第5章中討論這些問題，然後以兩個著名的問題結束，這兩個問題是中國郵遞員問題和旅行售貨員問題。許多由圖論描述的現實問題都需要把結點集或邊集劃分為一些不相交的子集，使同一子集中的所有元素互不相鄰。這類問題中比較常見的有：安排會議或考試的日程以免衝突，還有安排化學品的存儲以避免互相反應。這些問題都與第6章的主題一圖著色相關。矩陣是由數字組成的矩形表。在計算機中存儲圖的一種最簡單的方法就是用矩陣，或者說數組，這是矩陣在計算機科學中的對應數據結構。圖論有效地利用了矩陣，將其作為檢測結構和其他性質的工具。在第7章中，我們首先複習了矩陣的一些基本概念，然後講述了矩陣在圖論中的一些套用。圖論和計算機科學之間有著千絲萬縷的聯繫，因此算法在現代圖論中占有舉足輕重的地位，以至好幾本著作都專注於圖的算法。在第8章中，我們將簡單地介紹一下圖論算法及其套用。首先給出了重要的廣度優先搜尋和深度優先搜尋算法，然後考察了圖著色和樹編碼算法，其他一些算法也在行文中有所體現。我們將不在這裡考察算法的效率和NP完全性，但是建議有興趣的讀者參考一下Buckley和Harary、Chartrand和Oellermann還有Gould對這些問題的討論。如果能在平面內將圖畫出且使其邊各不相交叉，那么這個圖就是可平面化的。可平面圖曾經受到了多年的廣泛關注，其原因在於一個長期困惑人們的問題--四色猜想，這個問題最終花費了一百多年的時間才得到證明。時至今日，可平面圖在其套用領域仍然占有很重要的地位，例如在運籌學中的場地布局，或是計算機科學中的印刷電路板設計等問題中，可平面圖都起著至關重要的作用。在第9章中我們就來討論可平面圖及其性質。簡單的圖論模型不足以刻畫某些現實問題，我們已經見過不少這樣的實例。在第10章，我們將考慮另一些結構。有向圖和圖類似，只是邊有方向。有些問題中，流(信息、交通、液體、電子等)的方向性比較重要，有向圖就是對這種問題建模的。當有向邊上存在流量的大小限制後，就得到了網路。一類特殊的沒有圈的有向圖稱統籌圖，它的邊上有權，表示工作持續時間。這種有向圖用來安排複雜工程的各項工作。在第10章，將介紹不同種類的有向圖及特點，也將研究網路流問題並給出求最大流的算法，最後討論統籌圖及其套用。

圖論簡明教程

基本介紹

簡介

作者介紹

創作背景

目錄

相關詞條

熱門詞條