圖論及其應(yīng)用

前言

　　現(xiàn)實生活中，許多問題都可歸結(jié)為一個由點和線組成的圖形的問題。例如，由點代表車站，線代表鐵路線的鐵路網(wǎng)絡(luò)圖；點代表路口，線代表街道的城市交通圖；點代表管道接頭，線代表管道的自來水供水系統(tǒng)；點代表電網(wǎng)絡(luò)的結(jié)點，線代表結(jié)點間的電氣元件的電網(wǎng)絡(luò)圖等等。圖論正是研究這些由點和線組成的“圖形”問題的一門學(xué)科?！　D論起源于18世紀，其第一篇論文是由Euler（1707-1782）于1736年所完成。這篇論文不僅解決了一個當(dāng)時還沒有解決的著名問題——哥尼斯堡（KOnigsberg）七橋問題（見第四章），也使歐拉成為了圖論和拓撲學(xué)的創(chuàng)始入。圖論誕生后，特別是近30年來發(fā)展十分迅速，應(yīng)用也十分廣泛。其應(yīng)用已涉及物理學(xué)、化學(xué)、運籌學(xué)、計算機科學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會科學(xué)以及管理科學(xué)等諸多領(lǐng)域。由于圖論與計算機科學(xué)緊密相聯(lián)系，近若干年來，計算機科學(xué)、計算機網(wǎng)絡(luò)的迅猛發(fā)展，更拓展了圖論的應(yīng)用發(fā)展空間。在計算機的許多領(lǐng)域內(nèi)，它都占有一席之地。圖論在其他數(shù)學(xué)分支中，如矩陣論、群論中也有其重要的應(yīng)用?！　”緯歉鶕?jù)作者多年從事圖論教學(xué)的經(jīng)驗并結(jié)合國內(nèi)外優(yōu)秀教材的長處和圖論的新近發(fā)展?fàn)顩r編寫而成的。書中著重介紹了圖論及其應(yīng)用中的一些基本概念、基本理論和基本方法，同時也對一些擴展問題展開了討論，并注意到了適當(dāng)?shù)胤从硤D論研究中一些近期的研究問題和研究結(jié)果。全書共十章，分別討論圖的基本概念、樹、圖的連通度、Euler圖與Hamilton圖、匹配與因子分解、平面圖、圖的著色、Ramsey定理、有向圖以及代數(shù)圖論中的一些基本內(nèi)容。

內(nèi)容概要

本書是一本有一定學(xué)術(shù)參考價值的理工科研究生教學(xué)用書。它是根據(jù)作者多年從事研究生圖論教學(xué)的經(jīng)驗，并結(jié)合國內(nèi)外優(yōu)秀教材的長處和圖論的新近發(fā)展?fàn)顩r編寫而成。全書共十章，分別討論圖的基本概念、樹、圖的連通度、Enler圖與Hamilton圖、匹配與因子分解、平面圖、圖的著色、Ramsey定理、有向圖以及代數(shù)圖論中的一些內(nèi)容。其內(nèi)容詳盡，既有基本內(nèi)容，又有提高內(nèi)容；不僅較為全面地介紹了圖論中的一些基本概念，基本理論和基本方法，而且還反映了近期圖論及其應(yīng)用中的一些研究課題和結(jié)論。     本書論證簡明，敘述清晰，內(nèi)容深入淺出，循序漸進，便于教學(xué)。書中還配有較多數(shù)量的典型例題和習(xí)題，既可作為研究生教學(xué)用書，也可作為本科高年級學(xué)生的教材以及有關(guān)科技工作者的參考書。

書籍目錄

第一章 圖的基本概念  §1.1 圖和簡單圖  §1.2 子圖與圖的運算  §1.3 路與圖的連通性  §1.4 最短路及其算法  §1.5 圖的代數(shù)表示及其特征  §1.6 極圖  §1.7 交圖與團圖  習(xí)題1第二章 樹  §2.1 樹的概念與性質(zhì)  §2.2 樹的中心與形心  §2.3 生成樹  §2.4 最小生成樹  習(xí)題2第三章 圖的連通度  §3.1 割邊，割點和塊  §3.2 連通度  §3.3 應(yīng)用  §3.4 圖的寬距離和寬直徑  習(xí)題3第四章 Euler圖與Hamilton圖  §4.1 Euler圖  §4.2 高效率計算機鼓輪的設(shè)計  §4.3 中國郵遞員問題  §4.4 Hamilton圖  §4.5 度極大非Hamilton圖  §4.6 旅行售貨員問題  §4.7 超Hamilton圖  §4.8 E圖和H圖的聯(lián)系  §4.9 無限圖中的Euler，Hamilton問題  習(xí)題4第五章 匹配與因子分解  §5.1 匹配  §5.2 偶圖的匹配與覆蓋  §5.3 TLltte定理與完美匹配  §5.4 因子分解  §5.5 最優(yōu)匹配與匈牙利算法  §5.6 匹配在矩陣理論中的應(yīng)用  習(xí)題5第六章 平面圖  §6.1 平面圖  §6.2 一些特殊平面圖及平面圖的對偶圖  §6.3 平面圖的判定及涉及平面性的不變量  §6.4 平面性算法  習(xí)題6第七章 圖的著色  §7.1 圖的邊著色  §7.2 頂點著色  §7.3 與色數(shù)有關(guān)的幾類圖  §7.4 完美圖  §7.5 著色的計數(shù)與色多項式  §7.6 List著色  §7.7 全著色  §7.8 著色的應(yīng)用  習(xí)題7第八章 Ramsey定理  §8.1 獨立集和覆蓋  §8.2 Raxnsey定理  §8.3 廣義Ramsey數(shù)  §8.4 應(yīng)用  習(xí)題8第九章 有向圖  §9.1 有向圖及其連通性  §9.2 有向樹……第十章 圖、群與矩陣主要參考文獻

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    圖論及其應(yīng)用 PDF格式下載

---