圖論及其在計(jì)算機(jī)科學(xué)中的應(yīng)用

內(nèi)容概要

內(nèi)容提要
本書(shū)分成兩部分。第一部分對(duì)圖論的基本概念做了簡(jiǎn)明論述和深入討
論，包括圖、通路和回路、樹(shù)、割集和割點(diǎn)、有向圖和二分圖等。第二部分是圖
論在計(jì)算機(jī)科學(xué)中的應(yīng)用，包括最小支撐樹(shù)、最短通路、最大匹配、網(wǎng)絡(luò)流、中
國(guó)郵遞員問(wèn)題和旅行售貨員等問(wèn)題的算法和計(jì)算機(jī)實(shí)現(xiàn)。
書(shū)中穿插著一些有名的圖論問(wèn)題和生動(dòng)的例子，使讀者能理解和掌握如
何用圖論的基本知識(shí)解決實(shí)際問(wèn)題。每章后面編排了適量習(xí)題，幫助讀者通
過(guò)練習(xí)掌握書(shū)本內(nèi)容。既是一本好教材，又是一本好的科技讀物。
本書(shū)可作為理工各科高年級(jí)本科生和研究生教材和參考書(shū)，也可供教師
和有關(guān)工程技術(shù)人員及科研人員參考。

書(shū)籍目錄

目錄
前言
第一章 引論
第一節(jié) 幾個(gè)有名的圖論問(wèn)題
第二節(jié) 什么是圖？
第三節(jié) 哥尼斯堡七橋問(wèn)題的解
習(xí)題
第二章 通路和回路
第一節(jié) 同構(gòu)圖
第二節(jié) 子圖
第三節(jié) 邊鏈、通路和回路
第四節(jié) 連通圖、非連通和成分
第五節(jié) 歐拉圖
第六節(jié) 圖的運(yùn)算
第七節(jié) 歐拉圖的進(jìn)一步討論
第八節(jié) 哈密爾頓通路和回路
習(xí)題
第三章 有向圖
第一節(jié) 什么是有向圖？
第二節(jié) 有向圖的種類
第三節(jié) 成對(duì)比較和競(jìng)賽
第四節(jié) 在邏輯上的應(yīng)用
習(xí)題
第四章 樹(shù)
第一節(jié) 樹(shù)的概念和認(rèn)識(shí)
第二節(jié) 樹(shù)的性質(zhì)
第三節(jié) 根樹(shù)和二元樹(shù)
第四節(jié) 支撐樹(shù)
第五節(jié) 基本回路
第六節(jié) 怎樣找出所有的生成樹(shù)
習(xí)題
第五章 割集和割點(diǎn)
第一節(jié) 割集
第二節(jié) 割集的性質(zhì)
第三節(jié) 圖中所有的割集
第四節(jié) 基本回路和割集
習(xí)題
第六章 圖的矩陣表示
第一節(jié) 關(guān)聯(lián)矩陣
第二節(jié) 回路矩陣
第三節(jié) 基本回路矩陣和回路矩陣的秩
第四節(jié) 割集矩陣
第五節(jié) Af、Bf和Cf之間的關(guān)系
第六節(jié) 在開(kāi)關(guān)網(wǎng)絡(luò)中的應(yīng)用
第七節(jié) 鄰接矩陣
第八節(jié) 最小支撐樹(shù)
習(xí)題
第七章 平面圖
第一節(jié) 公用設(shè)備問(wèn)題
第二節(jié) 平面圖概念
第三節(jié) 地圖四色問(wèn)題
第四節(jié) 歐拉公式
第五節(jié) 分塊問(wèn)題
第六節(jié) 兩個(gè)典型的非平面圖
第七節(jié) 五色定理
習(xí)題
第八章 最短通路算法
第一節(jié) 最短通路問(wèn)題
第二節(jié) Dijkstra算法
第三節(jié) 任意兩點(diǎn)間的最短通路
習(xí)題
第九章 覆蓋和匹配
第一節(jié) 二分圖
第二節(jié) 覆蓋
第三節(jié) 匹配
第四節(jié) 匈牙利算法
第五節(jié) 庫(kù)恩－蒙克萊斯算法
習(xí)題
第十章 網(wǎng)絡(luò)的最大流問(wèn)題
第一節(jié) 網(wǎng)絡(luò)流的基本概念
第二節(jié) 最大流基本定理
第三節(jié) 標(biāo)號(hào)法
第四節(jié) 最小費(fèi)用流問(wèn)題
習(xí)題
第十一章 中國(guó)郵遞員問(wèn)題
習(xí)題
第十二章 旅行售貨員問(wèn)題
第一節(jié) TSP 的表示
第二節(jié) 分支和界限方法
第三節(jié) 快速TSP 算法
習(xí)題
參考文獻(xiàn)

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

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

---

    圖論及其在計(jì)算機(jī)科學(xué)中的應(yīng)用 PDF格式下載

---