|
![C{VQ5PGUX1A${]4JKPAUPGA.png](http://tools.fath-pk.cn/files/105410/1507/55558326604_m.png)
前言 圖論是組合數(shù)學(xué)的一個(gè)重要分支，與其他的數(shù)學(xué)分支，如群論、矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系。凡有二元關(guān)系的系統(tǒng)，應(yīng)用圖論均可建立一種合適的數(shù)學(xué)模型，因而圖論在許多學(xué)科領(lǐng)域，如計(jì)算機(jī)科學(xué)、通訊科學(xué)、運(yùn)籌學(xué)、電網(wǎng)絡(luò)分析、化學(xué)、物理、管理以及社會(huì)科學(xué)等領(lǐng)域具有重要地位和廣泛應(yīng)用。此外，圖論的理論與方法也是數(shù)學(xué)競(jìng)賽、數(shù)學(xué)建模等的理論基礎(chǔ)和工具。因此在本書的大部分章節(jié)中介紹了一些應(yīng)用實(shí)例，特別在第9章收集了若干圖論在數(shù)學(xué)建模中的應(yīng)用案例，讀者可以從中掌握利用圖論解決實(shí)際問(wèn)題的基本方法和技巧。目前，圖論已成為計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、組合優(yōu)化、機(jī)電等學(xué)科的基本課程之一，國(guó)內(nèi)外許多高校不僅對(duì)數(shù)學(xué)系的本科學(xué)生開設(shè)了圖論課程，也面向其他專業(yè)學(xué)生開設(shè)了圖論選修課程。 本書是在卜月華編寫的《圖論及其應(yīng)用》的基礎(chǔ)上，根據(jù)浙江省重點(diǎn)建設(shè)教材的要求并結(jié)合本科學(xué)生的特點(diǎn)和多年來(lái)的教學(xué)實(shí)踐，由卜月華、王維凡和呂新忠重新編寫而成。全書共分9章，前6章由卜月華編寫整理，第7章由王維凡編寫整理，第8章和第9章由呂新忠編寫整理。內(nèi)容不僅涉及圖論的基本概念和基本理論，還力求突出圖論方法的應(yīng)用，尤其是在數(shù)學(xué)競(jìng)賽和數(shù)學(xué)建模中的應(yīng)用。為使讀者在使用本書時(shí)能自覺(jué)地調(diào)動(dòng)學(xué)習(xí)積極性，更好地領(lǐng)悟圖論的本質(zhì)，每章后都配置了豐富而有趣的習(xí)題。本書適合作為高等院校各專業(yè)圖論課程的教材或參考書，也可以作為大學(xué)生數(shù)學(xué)建模集訓(xùn)的參考讀物。 在本書的再版過(guò)程中，編者參閱了國(guó)內(nèi)外許多優(yōu)秀的圖論專著、教材及學(xué)術(shù)論文，特別參考了宋增民教授編著的《圖論與網(wǎng)絡(luò)最優(yōu)化》一書，許多使用過(guò)初版《圖論及其應(yīng)用》一書的教師也對(duì)這一次再版工作提出了寶貴意見(jiàn)。在此編者表示衷心的感謝。 本書是浙江省重點(diǎn)建設(shè)教材，在出版過(guò)程中得到了浙江師范大學(xué)的教育部綜合改革試點(diǎn)專業(yè)“數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)”的大力支持，在此深表感謝。 由于編者水平有限，在編寫過(guò)程中對(duì)內(nèi)容雖經(jīng)反復(fù)推敲與修改，仍不可避免存在一些錯(cuò)誤與疏漏，懇請(qǐng)同行專家、使用本教材的教師和學(xué)生以及其他讀者不吝賜教，提出寶貴意見(jiàn)。 編者 2015年1月 目錄 1圖的基本概念1 1.1圖論發(fā)展史1 1.2圖的定義2 1.3頂點(diǎn)的度5 1.4子圖與圖的運(yùn)算9 1.5一些特殊的圖11 1.6圖的矩陣表示15 1.7有向圖21 1.8Brouwer不動(dòng)點(diǎn)定理24 習(xí)題126 2圖的連通性29 2.1路和圈29 2.2連通圖35 2.3連通度39 2.4可靠通訊網(wǎng)絡(luò)的構(gòu)造45 2.5最短路問(wèn)題47 2.6單行道路系統(tǒng)的構(gòu)造57 習(xí)題258 3樹61 3.1樹的基本性質(zhì)61 3.2生成樹68 3.3最優(yōu)生成樹73 3.4樹形圖76 習(xí)題386 4Euler環(huán)游和Hamilton圈89 4.1Euler環(huán)游89 4.2中國(guó)郵路問(wèn)題95 4.3Hamilton圖99 4.4旅行售貨員問(wèn)題108 習(xí)題4112 5圖的對(duì)集和獨(dú)立集116 5.1對(duì)集116 5.2二分圖的對(duì)集122 5.3二分圖最大對(duì)集算法128 5.4最優(yōu)分派問(wèn)題129 5.5獨(dú)立集和覆蓋132 5.6Ramsey數(shù)137 習(xí)題5144 6平面圖147 6.1平面圖及平面嵌入147 6.2平面圖性質(zhì)149 6.3幾類特殊的平面圖158 6.4圖的曲面嵌入161 習(xí)題6164 7圖的染色166 7.1頂點(diǎn)染色167 7.2邊染色173 7.3列表染色181 7.4全染色186 7.5染色方法189 7.5.1權(quán)轉(zhuǎn)移方法189 7.5.2概率方法192 7.5.3代數(shù)方法193 習(xí)題7195 8網(wǎng)絡(luò)流197 8.1基本概念和基本定理197 8.2最大流問(wèn)題的算法201 8.3最小費(fèi)用流問(wèn)題205 8.4最小費(fèi)用流的算法208 8.4.1原始算法208 8.4.2對(duì)偶算法209 8.5計(jì)劃評(píng)審方法和關(guān)鍵路線法211 8.5.1PERT網(wǎng)絡(luò)圖的一些基本概念212 8.5.2建立PERT網(wǎng)絡(luò)圖的準(zhǔn)則和注意事項(xiàng)213 8.5.3 PERT網(wǎng)絡(luò)圖的合并與簡(jiǎn)化214 8.5.4PERT網(wǎng)絡(luò)圖的計(jì)算215 習(xí)題8219 9圖論在數(shù)學(xué)建模中的應(yīng)用220 9.1模型1：婚配問(wèn)題220 9.1.1問(wèn)題分析220 9.1.2模型建立220 9.1.3模型的求解221 9.2模型2:鎖具裝箱問(wèn)題222 9.2.1分析與建模222 9.2.2模型的求解222 9.3模型3：最優(yōu)截?cái)嗲懈顔?wèn)題223 9.4模型4：賽程安排227 9.4.1問(wèn)題分析227 9.4.2圖論模型的建立228 9.4.3完美賽程的編制方法230 9.4.4其他問(wèn)題233 9.5模型5：乒乓球比賽隊(duì)員出場(chǎng)順序安排233 9.5.1實(shí)力強(qiáng)弱的理解233 9.5.2模型的建立與求解234 9.6模型6：災(zāi)情巡視路線236 9.6.1問(wèn)題假設(shè)237 9.6.2模型的建立與求解237 習(xí)題9241 參考文獻(xiàn)244 |
精品新書
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
 |
 |
