☆☆☆☆☆




點擊這裡下載

類似圖書 點擊查看全場最低價

---

內容簡介

　　《有嚮圖的理論、算法及其應用》作者從近30年關於有嚮圖理論研究的數韆篇論文中精選瞭具有理論意義、重要算法及其實際應用的結果，涵蓋瞭有嚮圖理論中從基本到較為高深的重要專題。主要內容有：有嚮圖的基本知識和理論、連通性、圖的定嚮、網絡流、哈密爾頓性的深入研究、有嚮圖的路和圈、子模流、競賽圖的推廣以及有嚮圖的推廣、Menger定理和NP完全問題等。書中介紹瞭有嚮圖研究中數十個未解決的問題和猜想，盡可能為讀者在主要方嚮上提供新的研究成果。對於計算機科學領域的學者來說，書中的大量算法以及實際應用的例子提供瞭難得的幫助。此外，配備瞭練習題700多道、方便查詢的參考文獻762篇，以及記號和術語索引等。
　　《有嚮圖的理論、算法及其應用》適閤數學及應用數學、離散數學、運籌學、計算機科學等專業的本科生、研究生、教師及研究人員閱讀，也可供人工智能、社會科學以及工程技術人員參考。

內頁插圖

目錄

第1章 基本術語及結論
1．1 集閤、子集、矩陣和嚮量
1．2 有嚮圖、有嚮子圖、鄰集和度數
1．3 有嚮圖的同構及其基本運算
1．4 途徑、跡、路、圈和路圈有嚮子圖
1．5 強連通性和單側連通性
1．6 無嚮圖、雙定嚮和定嚮性
1．7 混閤圖和超圖
1．8 有嚮圖和無嚮圖的分類
1．9 算法簡介
1．9．1 算法及其復雜性
1．9．2 NP完全問題和NP睏難問題
1．10 應用：求解2可滿足性問題
1．11 習題

第2章 距離
2．1 關於距離的術語和記號
2．2 最短路結構
2．3 尋找有嚮圖距離的算法
2．3．1 寬度優先搜索（BFS）
2．3．2 無圈有嚮圖
2．3．3 Dijkstra算法
2．3．4 Bellman-Ford-Moore算法
2．3．5 Floyd-Warshall算法
2．4 半徑、齣半徑和直徑之間的不等式
2．4．1 強有嚮圖的半徑和直徑
2．4．2 齣半徑和直徑的極值
2．5 定嚮圖的最大有限直徑
2．6 多重圖定嚮的最小直徑
2．7 完全多重圖的最小直徑定嚮
2．8 圖擴張的最小直徑定嚮
2．9 笛卡兒積圖的最小直徑定嚮
2．10 有嚮圖中的王
2．10．1 競賽圖的2王
2．10．2 半完全多部分有嚮圖中的王
2．10．3 廣義競賽圖中的王
2．11 應用：單行道問題和閑話問題
2．11．1 單行道問題和有嚮圖的定嚮
2．11．2 閑話問題
2．12 應用：旅行售貨員問題的指數鄰集局部搜索
2．12．1 TSP局部搜索
2．12．2 TSP的綫性時間可搜索指數鄰集
2．12．3 分配鄰集
2．12．4 關於TSP的鄰集結構有嚮圖的直徑
2．13 習題

第3章 網絡流
3．1 定義及基本性質
3．1．1 流及流平衡嚮量
3．1．2 剩餘網絡
3．2 網絡模型的簡約
3．2．1 消除下界
3．2．2 單源單收點網絡
3．2．3 循環
3．2．4 頂點上有費用及下界的網絡
3．3 流分解
3．4 討論剩餘網絡
3．5 最大流問題
3．5．1 Ford-Fullkerson算法
3．5．2 最大流與綫性規劃
3．6 尋找最大（s，t）流的多項式算法
3．6．1 沿最短增廣路的流增廣
3．6．2 在分層網絡和Dinic算法中的塊化流
3．6．3 前置流推進算法
3．7 單位容量網絡和簡單網絡
3．7．1 單位容量網絡
3．7．2 簡單網絡
3．8 循環與可行流
3．9 最小值可行（s，t）流
3．10 最小費用流
3．10．1 刻畫最小費用流
3．10．2 創建最優化解
3．11 流的應用
3．11．1 二部分圖的最大匹配
3．11．2 有嚮中國郵遞員問題
3．11．3 尋找具有預先指定度的有嚮子圖
3．11．4 有嚮多重圖的路圈因子
3．11．5 覆蓋指定頂點的圈有嚮子圖
3．12 分配問題和運輸問題
3．13 習題

第4章 有嚮圖類
第5章 哈密爾頓性及其相關問題
第6章 深入研究哈密爾頓性
第7章 全連通性
第8章 圖的定嚮
第9章 不交路和不交樹
第10章 有嚮圖的圈結構
第11章 有嚮圖的推廣
第12章 一些重要的專題
參考文獻
記號索引
術語索引
譯後記
《現代數學譯叢》已齣版書目

前言/序言

　　圖論是離散數學中普及最廣的學科之一，不僅是由於它自身理論的迅速發展，而且是因為它在實際中有著大量的重要應用。近幾十年來的許多深刻的理論結果也導緻瞭圖論學科的快速成長。然而，作為一個研究領域，圖論仍然還是一門相對年輕的學科，
　　圖的理論可以分為無嚮圖理論和有嚮圖理論兩大分支，雖然這兩大理論分支有著大量且重要的應用，但由於諸多的原因，無嚮圖比有嚮圖得到更為廣泛的研究。首先因為無嚮圖在一定程度上是有嚮圖的一個特殊類（對稱有嚮圖），所以，凡能夠錶述為無嚮圖和有嚮圖的問題通常用有嚮圖的方法解決較為容易；另一個原因是，不像無嚮圖的情形，除瞭幾本重要的書包含兩類圖的傳統和近期的結果，近25年來沒有一本專門介紹關於有嚮圖研究的完整結果的著作，在一般的教科書中，大多數作者用一章來講述有嚮圖，或者隻有少量的有嚮圖基本知識與結論。
　　盡管如此，在近30年中，有嚮圖理論還是得到瞭長足的發展。超過3000篇的研究論文不僅涵蓋瞭具有理論意義的結果，而且包括瞭重要的算法及其應用。為瞭實際的需要，本書概括瞭有嚮圖的基本知識，並從深層次的角度介紹瞭理論和算法這兩個方麵的研究成果及應用。
　　本書竭力為專題研究填補文獻與實用手冊間的溝壑，書中的基本內容是針對具有大學數學基礎知識的讀者，然後在幾個研究領域（包括連通性、圖的定嚮、子模流、有嚮圖的路和圈、競賽圖的推廣以及有嚮圖的推廣等）的主要方嚮上逐步到達新的研究成果，我們為本書配備瞭超過700道練習題、大量應用以及適宜討論的專題，對於我們所期望的不同群體的讀者（研究生、本科生、離散數學研究者、計算機科學中各個領域的研究者、運籌學研究、人工智能、社會科學以及工程技術人員等）來說，書中所有的專題不可能對全體讀者均有同等的意義。然而，我們相信，每位讀者都能從這本書裏找到吸引自己的有趣專題。
　　顯然，本書不可能是關於有嚮圖的百科全書，但是，我們盡可能地提供瞭許多有意義的結論，書中數量眾多的證明和技巧為讀者詳細地說明瞭有嚮圖理論和算法中所使用的各種各樣的方法和手段。
　　強調算法是本書最主要的特色之一，而這一點卻在一些圖論書中被遺憾地省略。首先，算法常常在不少領域的研究中扮演著重要的角色，尤其是在計算機科學和數值計算的研究中。其次，（有嚮）圖的許多問題本身就是算法問題，因此我們盡可能給齣許多結論的構造性證明，利用這些構造性證明，讀者就可以從所研究的問題中提取一些有效的算法，雖然本書描述瞭許多算法，但鑒於篇幅限製，我們沒有提供全部必需的細節以使得讀者能夠正確地運用這些算法，這屬於計算科學的範疇（常常是極為不平凡的工作），建議讀者去閱讀數據結構方麵的書籍。
　　本書的另一個重要的特色是精選瞭數量可觀的練習題，它們不僅可以幫助讀者理解，而且可以使讀者能夠通過大量的材料吃透書中所介紹的內容。嘗試解決這些習題（絕大部分是在本書中齣現）將有助於讀者掌握所學的專題以及主要的研究技巧，
　　通過從易到難的廣泛而不間斷地學習和訓練，對於一些專門的問題，如（有嚮）圖論、組閤優化和圖算法，讀者將會發現本書的作用。此外，本書也可以應用於某些熱門課題，如流、圈和連通性等。書中含有大量的解說，以幫助讀者讀懂不易理解的概念和深奧的證明。
　　齣於使這本書成為一個便捷的研究參考書或大學教科書的考慮，我們增添瞭綜閤性的記號和術語索引，可以確信，詳細的術語索引能夠幫助讀者找到所需要的對象而不必通讀整個章節，特彆地，書後的索引列齣瞭許多關於公開問題和猜想的條目。本書所討論的每一類有嚮圖均擁有自己的條目，即在討論這類圖的主要頁上。作為次條目，例如證明技巧條目，我們編製瞭不同證明技巧的索引，並標注齣這些技巧所在的頁碼。
　　本書涵蓋瞭有嚮圖的從相當基本到較為高深範圍的主要且重要的專題。根據我們的經驗，這本書在今後的幾十年內將有助於教學和參考文獻搜索，我們在下麵通過敘述一些重要的內容給齣本書的輪廓，需要詳細信息的讀者可以參見目錄或書後的術語索引。
　　第1章包括瞭本書所使用的大部分術語、記號以及一些基本結論，它們不僅在其他章節中被頻繁地使用，而且被用作解釋有嚮圖的概念。進而，我們還將介紹幾個基於這些結論的有嚮圖的應用，並在本章的末尾處給齣一個具體的應用。關於算法及其復雜性的基本概念也在這一章裏一並介紹，依據綜閤性術語和記號索引，讀者不必讀完整個第1章後纔進入其他章節的閱讀與學習。
　　第2章和第3章討論距離和網絡中的流。盡管這兩個專題的概念是基本的，然而，有嚮圖中距離以及網絡流的理論和算法特徵卻是相當重要的，因為它們對有嚮圖的其他理論問題和大量實際問題有著高度的可應用性，尤其是作為強有力的模型工具。
　　關於距離，我們首先介紹賦權和未賦權有嚮圖中最短路問題以及幾個傳統算法。第2章的主要內容是有嚮圖中距離參數的最小化和大化，我們將用下列問題結束這一章：單行道問題、閑話問題、指數鄰集局部搜索，並介紹一個關於組閤優化問題尋找沂似優化懈的方法。
有嚮圖的理論、算法及其應用 下載 mobi epub pdf txt 電子書

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

評分☆☆☆☆☆

類似圖書 點擊查看全場最低價

查看全網最低價