圖論及其應(yīng)用

《圖論及其應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、信息與通信工程研究生系列教材圖論及其應(yīng)用孫惠泉編著北京內(nèi)容簡(jiǎn)介本書系統(tǒng)介紹了圖論的基本知識(shí)，如樹、連通性、遍歷問題、匹配、頂點(diǎn)著色、邊著色、平面圖和網(wǎng)絡(luò)等。作為正文的補(bǔ)充，書中收集了大量經(jīng)典的習(xí)題，并在書后附有提示及解答，以便自學(xué)。與一般圖論書不同的是，本書指明了許多應(yīng)用中常見的圖論問題是ＮＰ困難問題，便于讀者在科研工作中及時(shí)注意這種問題。本書力求立論嚴(yán)謹(jǐn)、簡(jiǎn)明易懂，只要是有一定數(shù)學(xué)基礎(chǔ)的高中畢業(yè)生都可看懂。本書特別強(qiáng)調(diào)推理（而且還是在離散對(duì)象上的推理）的重要性，因?yàn)檫@是培養(yǎng)獨(dú)立科研能力的必由之路。本書可作為大學(xué)信息類及計(jì)算機(jī)

2、類碩士研究生及高年級(jí)本科生的圖論教材或參考書，也可作為其他相關(guān)專業(yè)科技工作者及圖論愛好者的學(xué)習(xí)參考書。圖書在版編目（ＣＩＰ）數(shù)據(jù)圖論及其應(yīng)用／孫惠泉編著．—北京：科學(xué)出版社，２００４?。ㄐ畔⑴c通信工程研究生系列教材）ＩＳＢＮ７０３０１３８６６Ｘ?、瘢畧D…?、颍畬O…　Ⅲ．圖論研究生教材?、簦希保担罚抵袊?guó)版本圖書館ＣＩＰ數(shù)據(jù)核字（２００４）第０６８５８０號(hào)責(zé)任編輯：匡敏姚慶爽／責(zé)任校對(duì)：宋玲玲責(zé)任印制：張克忠／封面設(shè)計(jì)：陳敬出版北京東黃城根北街１６號(hào)郵政編碼：１００７１７ｈｔｔｐ：／／ｗｗｗ．ｓｃｉｅｎｃｅｐ．ｃｏｍ印

3、刷科學(xué)出版社發(fā)行各地新華書店經(jīng)銷２００４年９月第一版開本：Ｂ５（７２０×１０００）２００６年８月第三次印刷印張：１７１／４印數(shù)：４５０１—６０００　　　　字?jǐn)?shù)：３４００００定價(jià)：２７．００元（如有印裝質(zhì)量問題，我社負(fù)責(zé)調(diào)換枙環(huán)偉枛）前言本書是作者在給北京郵電大學(xué)研究生和本科生講授了二十多年“圖論及其應(yīng)用”課程的基礎(chǔ)上，將教學(xué)資料及體會(huì)整理編寫而成的。通過這些年的教學(xué)，除了因許多圖論算法已包含在數(shù)據(jù)結(jié)構(gòu)等教科書中，以及教學(xué)時(shí)間不足等原因外，筆者越來越感到應(yīng)該把側(cè)重點(diǎn)放在訓(xùn)練學(xué)生掌握?qǐng)D論基本證明方法上。如果一個(gè)學(xué)生學(xué)完這門課后，仍

4、然不能自己判定自己做的作業(yè)是對(duì)或錯(cuò)，那么可以說他沒有學(xué)好這····門課。掌握了基本證明方法也就有了這方面的自學(xué)能力，這將使學(xué)生在科研工作中，面對(duì)圖論（網(wǎng)絡(luò)）的新舊結(jié)論以及專業(yè)知識(shí)縱橫交錯(cuò)的復(fù)雜對(duì)象，會(huì)感到更自主、更自在。為此，在定理證明中，筆者往往不滿足于一個(gè)證明，但凡有來自名家的經(jīng)典證明，書中一般都會(huì)收錄其中。因此，第一個(gè)證明總是“正統(tǒng)的”，其他證明只好請(qǐng)讀者“自取”。書中的附錄及打號(hào)的章節(jié)也屬“自取”部分。甩掉這些內(nèi)容后，６０學(xué)時(shí)的教學(xué)并不輕松，其根源是掌握基本證明方法要有不少揣摩和適應(yīng)的功夫。此外，筆者對(duì)許多ＮＰ完全或

5、ＮＰ困難的圖論問題，在相關(guān)的章節(jié)中都及時(shí)加以指出，以便在設(shè)計(jì)算法時(shí)明確方向，這是本書的另一重要特色。習(xí)題是學(xué)好圖論的必由之路，不但要多做，而且要做好。凡是序號(hào)用黑體字標(biāo)出的習(xí)題，都應(yīng)盡量做。本書除了有題解外，對(duì)打號(hào)的習(xí)題還有提示。題解主要是為自學(xué)的讀者提供參考。大多數(shù)習(xí)題都是較容易的，有些只是對(duì)正文的一個(gè)補(bǔ)充，因此一般讀者應(yīng)盡量不要看題解，自己做往往比看題解更省時(shí)省力，何況看題解的效果并不好。此外，筆者還把一部分內(nèi)容轉(zhuǎn)移到了習(xí)題中。雖然筆者盡量完善本書，但由于時(shí)間倉(cāng)促，疏漏之處仍在所難免，敬請(qǐng)讀者不吝施教，不勝感謝。本書的出

6、版得到了北京郵電大學(xué)以郭軍教授為首的信息工程學(xué)院院領(lǐng)導(dǎo)的大力支持，以及胡正名、阮傳概、陸傳賚諸教授和羅群、王維嘉、卓新建等同事的關(guān)心和幫助，特此一并表示感謝?？茖W(xué)出版社匡敏女士為本書的出版做了不少工作，在此一并致謝。孫惠泉２００４年６月１８日于北京·ｉ·目錄前言第１章圖的基本概念………………………………………………………………１　?。保薄D的概念……………………………………………………………１　?。保病⊥瑯?gòu)…………………………………………………………………５　?。保场D的矩陣和頂點(diǎn)的度………………………………………………９

7、　?。保础∽訄D…………………………………………………………………１１　　１．５　路和連通性…………………………………………………………１４　?。保丁∪Α保浮　。保贰∽疃搪穯栴}…………………………………………………………１９第２章樹…………………………………………………………………………２３　?。玻薄浜透钸叀玻场　。玻病∵吀詈玩I……………………………………………………………２８　?。玻场「铧c(diǎn)………………………………………

8、…………………………３４　?。玻础∵B線問題……………………………………………………………３６　?。玻瞪蓸涞挠?jì)數(shù)及Ｃａｙｌｅｙ公式……………………………………３９第３章連通度……………………………………………………………………４２　　３．１　連通度…………