圖論及其算法

前言

　　圖論是研究離散對(duì)象二元關(guān)系中關(guān)系結(jié)構(gòu)的一個(gè)數(shù)學(xué)分支，與群論、矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等其他數(shù)學(xué)分支有著密切的聯(lián)系，其廣闊的應(yīng)用領(lǐng)域涵蓋了計(jì)算機(jī)科學(xué)、化學(xué)、物理學(xué)、運(yùn)籌學(xué)、信息論、控制論、經(jīng)濟(jì)學(xué)、心理學(xué)、環(huán)境保護(hù)領(lǐng)域等。同時(shí)，隨著這些學(xué)科的發(fā)展，特別是計(jì)算機(jī)科學(xué)的快速發(fā)展，又促進(jìn)了圖論的發(fā)展?！　D論是一門極有趣味的學(xué)科，它最吸引人的地方是蘊(yùn)含了豐富不俗的思想、漂亮的圖形和巧妙的證明，它涉及的問(wèn)題廣泛，問(wèn)題外表雖簡(jiǎn)單樸素，本質(zhì)上卻十分復(fù)雜深刻；其解決問(wèn)題的方法千變?nèi)f化，靈活多樣。因此，各專業(yè)的學(xué)生都應(yīng)該具有一定的圖論基礎(chǔ)，從而掌握一種強(qiáng)大而靈活的工具來(lái)分析和處理自己學(xué)科領(lǐng)域的問(wèn)題。目前，圖論已經(jīng)成為計(jì)算機(jī)科學(xué)、數(shù)學(xué)、運(yùn)籌學(xué)、組合優(yōu)化、機(jī)電等學(xué)科的基本課程之一?！　”緯榻B了圖論的基本概念、基本定理和算法，共分9章。主要內(nèi)容包括圖的基本概念、樹(shù)、距離與連通性、圖的遍歷問(wèn)題、圖的匹配與獨(dú)立集、圖的染色、平面圖、網(wǎng)絡(luò)流和圖參數(shù)A（H）值等。本書將有向圖和無(wú)向圖融為一個(gè)整體，不僅介紹了圖論的基本原理，也介紹了如何應(yīng)用圖論方法解決實(shí)際問(wèn)題，還強(qiáng)調(diào)了圖論算法，配有適當(dāng)?shù)睦}和習(xí)題，并在書后附有部分習(xí)題的參考答案?！　”緯×藝?guó)內(nèi)外許多優(yōu)秀圖論著作的精華，結(jié)合了編者多年的教學(xué)經(jīng)驗(yàn)和本科生的特點(diǎn)，內(nèi)容力求精煉，所有的證明和算法簡(jiǎn)潔明了，通俗易懂，易于學(xué)生學(xué)習(xí)和教師的教學(xué)?！　∮捎趫D論不強(qiáng)調(diào)數(shù)值計(jì)算而強(qiáng)調(diào)證明技巧和解釋的清晰，所以許多問(wèn)題都有多個(gè)證明，編者對(duì)這些證明精心選擇，深入淺出地介紹了圖論的證明技巧?！　D論和計(jì)算機(jī)科學(xué)之間有著千絲萬(wàn)縷的聯(lián)系。由于算法的研究是計(jì)算機(jī)科學(xué)的核心，所以算法在現(xiàn)代圖論中占有舉足輕重的地位。本書介紹了圖論算法及其應(yīng)用，計(jì)算機(jī)專業(yè)在教學(xué)中還可以引導(dǎo)學(xué)生編寫程序，上機(jī)實(shí)踐。　　由于圖論是一門新興的學(xué)科，所以國(guó)內(nèi)外許多圖論書籍出現(xiàn)了多個(gè)版本的術(shù)語(yǔ)和符號(hào)。本書在介紹圖論的基本概念、術(shù)語(yǔ)和結(jié)論時(shí)，選擇了最為通俗易懂的語(yǔ)言加以描述，符號(hào)力求清晰、簡(jiǎn)潔、通用。在主題的挑選、順序的安排和題目的選擇上，遵循認(rèn)知規(guī)律和由淺入深的原則，使讀者能輕松愉快地進(jìn)入圖論的系統(tǒng)學(xué)習(xí)和研究。在內(nèi)容的編排上，各章之間既相互聯(lián)系又自成體系，便于讀者學(xué)習(xí)和查閱，同時(shí)體現(xiàn)了教材的系統(tǒng)性和科學(xué)性?！　∪珪卜?章，第1、2、9章由哈爾濱學(xué)院理學(xué)院李明哲編寫，第3、4、7章由牡丹江師范學(xué)院數(shù)學(xué)系金俊編寫，第5、6、8章由黑龍江科技學(xué)院理學(xué)院石端銀編寫，全書由李明哲主持編寫并負(fù)責(zé)統(tǒng)稿。哈爾濱學(xué)院蓋功琪仔細(xì)審閱了本書，并提出了許多寶貴意見(jiàn)?！　≡诒緯木帉戇^(guò)程中得到了哈爾濱學(xué)院軟件學(xué)院院長(zhǎng)賈宗福教授的熱誠(chéng)幫助和指導(dǎo)，本書作為黑龍江省高教學(xué)會(huì)高等教育科學(xué)研究“十一五”規(guī)劃課題（項(xiàng)目編號(hào)：115C一901）的研究成果，在編寫過(guò)程中得到了?？蒲刑幍膸椭椭笇?dǎo)，在此表示衷心的感謝?！　∮捎谒接邢?，書中不妥之處在所難免，殷切希望廣大讀者批評(píng)指正。

內(nèi)容概要

　　本書為圖論的入門教材，介紹了圖論的基本概念、基本定理和算法，共分9章。主要內(nèi)容包括圖的基本概念、樹(shù)、距離與連通性、圖的遍歷問(wèn)題、圖的匹配與獨(dú)立集、圖的染色、平面圖、網(wǎng)絡(luò)流、圖參數(shù)A（H）值等。本書將有向圖和無(wú)向圖融為一個(gè)整體，不僅介紹了圖論的基本原理，而且介紹了如何應(yīng)用圖論方法解決實(shí)際問(wèn)題，還強(qiáng)調(diào)了圖論算法，配有適當(dāng)?shù)睦}和習(xí)題，并在書后附有部分習(xí)題的參考答案。本書概念清楚，立論嚴(yán)謹(jǐn)，所有的證明和算法簡(jiǎn)潔明了，通俗易懂?！　”緯勺鳛楦叩仍盒Ｓ?jì)算機(jī)、數(shù)學(xué)、信息、電子、管理等專業(yè)的教材，還可作為相關(guān)專業(yè)人員的參考書。

書籍目錄

出版說(shuō)明前言第1章　圖的基本概念　1.1圖論發(fā)展簡(jiǎn)史　1.2圖的概念　　1.2.1圖　　1.2.2子圖　　1.2.3一些重要類型的圖　1.3頂點(diǎn)的度和圖的同構(gòu)　　1.3.1頂點(diǎn)的度　　1.3.2圖的同構(gòu)　1.4圖的運(yùn)算　　1.4.1并與和　　1.4.2笛卡兒積　　1.4.3超立方體　　1.4.4網(wǎng)格　　1.4.5邊收縮　　1.4.6線圖　1.5路和連通　　1.5.1路和回路的定義　　1.5.2連通性　1.6有向圖　　1.6.1有向圖的概念　　1.6.2有向圖的度　　1.6.3有向網(wǎng)絡(luò)　　1.6.4有向圖的連通性　1.7圖的矩陣表示　　1.7.1關(guān)聯(lián)矩陣　　1.7.2鄰接矩陣　　1.7.3距離矩陣　　1.7.4連通矩陣　　1.7.5特殊類型圖的鄰接矩陣　　1.7.6有向圖的矩陣表示　1.8習(xí)題第2章　樹(shù)　2.1樹(shù)的基本性質(zhì)　　2.1.1樹(shù)的概念　　2.1.2樹(shù)的性質(zhì)　　2.1.3樹(shù)的度序列與同構(gòu)　　2.1.4樹(shù)的葉子數(shù)　　2.1.5有向樹(shù)　2.2生成樹(shù)　　2.2.1生成樹(shù)的概念　　2.2.2生成樹(shù)的計(jì)數(shù)　2.3最優(yōu)生成樹(shù)　　2.3.1Kruskal算法　　2.3.2Prim算法　　2.3.3破圈法　2.4深度優(yōu)先搜索與廣度優(yōu)先搜索　　2.4.1深度優(yōu)先搜索　　2.4.2廣度優(yōu)先搜索　2.5最優(yōu)二元樹(shù)與前綴碼　　2.5.1最優(yōu)二元樹(shù)　　2.5.2前綴碼　2.6樹(shù)的Prtifer編碼　2.7習(xí)題第3章　距離與連通性　3.1圖的距離　　3.1.1離徑、中心、半徑與直徑　　3.1.2樹(shù)的中心　　3.1.3自補(bǔ)圖與距離　3.2圖的連通性　　3.2.1點(diǎn)連通度、邊連通度　　3.2.2點(diǎn)、邊連通度的性質(zhì)　　3.2.3塊　3.3連通圖　　3.3.1k-連通圖　　3.3.22-連通圖　　3.3.3Menger定理　3.4最短路算法　　3.4.1從一個(gè)始點(diǎn)到一個(gè)終點(diǎn)的最短路　　3.4.2任意兩點(diǎn)間的最短路　3.5習(xí)題

章節(jié)摘錄

　　因?yàn)槔碚撐锢韺W(xué)研究的需要，所以在這個(gè)學(xué)科內(nèi)不止一次地發(fā)現(xiàn)過(guò)圖論。烏倫伯克（uhlenbeck）在統(tǒng)計(jì)力學(xué)的研究中用點(diǎn)來(lái)代表分子，兩個(gè)點(diǎn)的鄰接表示存在某種物理形式的最鄰近的相互作用，如磁的吸力或斥力。在李政道和楊振寧的類似解釋中，點(diǎn)代表歐幾里得空間的小立方體，其中每一個(gè)立方體可能被一個(gè)分子占有或者不被分子占有。于是，兩個(gè)點(diǎn)鄰接就表示兩個(gè)空間都被占有。另外，物理學(xué)還用圖論來(lái)作為一種圖形的表示方法。在范曼（Fevnmanon）提出的圖解中，點(diǎn)代表物理粒子，線代表粒子碰撞后的路線?！　≡诟怕收撝?，馬爾可夫鏈的研究引進(jìn)了有向圖，它的意思是：點(diǎn)代表事件，一條從一個(gè)點(diǎn)到另外一個(gè)點(diǎn)的有向線表示這兩個(gè)事件直接相繼有正的概率。研究中，直接定義一個(gè)馬爾可夫鏈?zhǔn)且粋€(gè)網(wǎng)絡(luò)，其中從每一個(gè)點(diǎn)出發(fā)的所有有向線的值的和是1。有向圖有一種類似的表示法出現(xiàn)在數(shù)值分析的矩陣求逆和特征值計(jì)算的部分中，瓦爾加（Varga）給出了一些例子。對(duì)于一個(gè)給定的矩陣，特別是“稀疏的”矩陣，可以用如下的方式構(gòu)成一個(gè)有向圖：用點(diǎn)來(lái)代表給定的矩陣的行與列的指標(biāo)，當(dāng)矩陣的i、j元非零時(shí)有一條從點(diǎn)f到點(diǎn).，的有向線。這種方法與處理馬爾可夫鏈的方法有相似性?！　【€性規(guī)劃與運(yùn)籌學(xué)的領(lǐng)域里也利用圖論的方法研究網(wǎng)絡(luò)上的流的形式。一個(gè)圖的點(diǎn)表示某種貨物可以儲(chǔ)藏或裝船的實(shí)際位置，從一處到另一處的一條有向線和記在這條線上的一個(gè)正數(shù)代表一條運(yùn)輸貨物的水道和它的能力，這個(gè)能力給出可以同時(shí)通過(guò)的最大允許數(shù)量?！　】萍嫉难该桶l(fā)展向圖論提出了越來(lái)越多的需要解決的問(wèn)題，使圖論在科學(xué)界非?；钴S。尤其是計(jì)算機(jī)科學(xué)的快速發(fā)展，為圖論及其算法的實(shí)現(xiàn)提供了強(qiáng)大的計(jì)算與證明的手段，有力地推動(dòng)了圖論的發(fā)展，而圖論在開(kāi)關(guān)理論、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、形式語(yǔ)言、計(jì)算機(jī)網(wǎng)絡(luò)、編譯程序、人工智能等方面亦有顯著貢獻(xiàn)?！　∧壳?，圖論領(lǐng)域形成了兩個(gè)研究方向：一個(gè)是以研究圖的性質(zhì)為主，稱之為抽象圖論；另一個(gè)是以研究圖的算法為主，稱之為算法圖論，也稱為網(wǎng)絡(luò)最優(yōu)化。本書中不僅介紹了圖論的基本原理，還介紹了圖論算法及其應(yīng)用。　　……

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    圖論及其算法 PDF格式下載

---