有向圖的理論、算法及其應(yīng)用

前言

圖論是離散數(shù)學(xué)中普及最廣的學(xué)科之一，不僅是由于它自身理論的迅速發(fā)展，而且是因為它在實際中有著大量的重要應(yīng)用。近幾十年來的許多深刻的理論結(jié)果也導(dǎo)致了圖論學(xué)科的快速成長。然而，作為一個研究領(lǐng)域，圖論仍然還是一門相對年輕的學(xué)科。圖的理論可以分為無向圖理論和有向圖理論兩大分支。雖然這兩大理論分支有著大量且重要的應(yīng)用，但由于諸多的原因，無向圖比有向圖得到更為廣泛的研究。首先因為無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖），所以，凡能夠表述為無向圖和有向圖的問題通常用有向圖的方法解決較為容易；另一個原因是，不像無向圖的情形，除了幾本重要的書包含兩類圖的傳統(tǒng)和近期的結(jié)果，近25年來沒有一本專門介紹關(guān)于有向圖研究的完整結(jié)果的著作。在一般的教科書中，大多數(shù)作者用一章來講述有向圖，或者只有少量的有向圖基本知識與結(jié)論。盡管如此，在近30年中，有向圖理論還是得到了長足的發(fā)展。超過3000篇的研究論文不僅涵蓋了具有理論意義的結(jié)果，而且包括了重要的算法及其應(yīng)用。為了實際的需要，本書概括了有向圖的基本知識，并從深層次的角度介紹了理論和算法這兩個方面的研究成果及應(yīng)用。本書竭力為專題研究填補(bǔ)文獻(xiàn)與實用手冊間的溝壑。書中的基本內(nèi)容是針對具有大學(xué)數(shù)學(xué)基礎(chǔ)知識的讀者，然后在幾個研究領(lǐng)域（包括連通性、圖的定向、子模流、有向圖的路和圈、競賽圖的推廣以及有向圖的推廣等）的主要方向上逐步到達(dá)最新的研究成果。我們?yōu)楸緯鋫淞顺^700道練習(xí)題、大量應(yīng)用以及適宜討論的專題。對于我們所期望的不同群體的讀者（研究生、本科生、離散數(shù)學(xué)研究者、計算機(jī)科學(xué)中各個領(lǐng)域的研究者、運籌學(xué)研究、人工智能、社會科學(xué)以及工程技術(shù)人員等）來說，書中所有的專題不可能對全體讀者均有同等的意義。然而，我們相信，每位讀者都能從這本書里找到吸引自己的有趣專題。顯然，本書不可能是關(guān)于有向圖的百科全書，但是，我們盡可能地提供了許多有意義的結(jié)論。書中數(shù)量眾多的證明和技巧為讀者詳細(xì)地說明了有向圖理論和算法中所使用的各種各樣的方法和手段。

內(nèi)容概要

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

作者簡介

作者：(丹麥)J.邦詹森 譯者：(英國)G.古廷

書籍目錄

第1章  基本術(shù)語及結(jié)論  1.1  集合、子集、矩陣和向量  1.2  有向圖、有向子圖、鄰集和度數(shù)  1.3  有向圖的同構(gòu)及其基本運算  1.4  途徑、跡、路、圈和路圈有向子圖  1.5  強(qiáng)連通性和單側(cè)連通性  1.6  無向圖、雙定向和定向性  1.7  混合圖和超圖  1.8  有向圖和無向圖的分類  1.9  算法簡介    1.9.1  算法及其復(fù)雜性    1.9.2  NP完全問題和NP困難問題  1.10  應(yīng)用：求解2可滿足性問題  1.11  習(xí)題第2章  距離第3章  網(wǎng)絡(luò)流第4章  有向圖類第5章  哈密爾頓性及其相關(guān)問題第6章  深入研究哈密爾頓性第7章  全連通性第8章  圖的定向第9章  不交路和不交樹第10章  有向圖的圈結(jié)構(gòu)第11章  有向圖的推廣第12章  一些重要的專題參考文獻(xiàn)記號索引術(shù)語索引譯后記《現(xiàn)代數(shù)學(xué)譯叢》已出版書目

章節(jié)摘錄

插圖：第1章 基本術(shù)語及結(jié)論本書的大部分術(shù)語和記號在這一章中介紹，其中大量的例子、圖示和結(jié)論將有助于讀者更好地理解這些術(shù)語和記號。本章中簡單而又重要的結(jié)論形成有向圖的一組基本定理，我們使用常規(guī)標(biāo)準(zhǔn)的術(shù)語和記號。因此，讀者在快速閱讀本章之后就可以學(xué)習(xí)其他章節(jié)，對于那些不熟悉的術(shù)語和記號均可以在所閱讀的章節(jié)或者從書后的索引里找到。1.1節(jié)復(fù)習(xí)集合和矩陣的基本術(shù)語和記號。1.2節(jié)介紹有向圖、有向偽圖、有向子圖、賦權(quán)有向偽圖、鄰集、半度以及其他關(guān)于有向圖理論的若干基本概念。1.3節(jié)介紹有向圖的同構(gòu)和有向圖之間的運算。在1.4節(jié)中，我們要認(rèn)識途徑、跡、路和圈，并學(xué)習(xí)競賽圖和無圈圖的一些性質(zhì)。強(qiáng)連通、單側(cè)連通的概念和無向圖將分別放在1.5節(jié)和l。6節(jié)中介紹。此外，歐拉有向多重圖、具有入（出）分支的有向圖以及具有強(qiáng)有向性的圖也放在1.6節(jié)中介紹。1.7節(jié)學(xué)習(xí)混合圖和超圖。1.8節(jié)介紹幾類重要的有向圖和無向圖。在1.9節(jié)中給出算法的初步認(rèn)識。最后一節(jié)的內(nèi)容是介紹求解2可滿足性問題的一個應(yīng)用。

后記

譯稿交付出版社，我們卻沒有如釋重負(fù)之感。《有向圖的理論、算法及其應(yīng)用》一書的容量十分龐大：書中引用的論文和書籍762篇（本），還不包括書中涉及的私人通信里未發(fā)表的文章等。全書12章，共有151個引理，465個定理，100個推論，89個命題，26個問題，54個猜想以圾三十余個算法。書中有很多沒有用正規(guī)格式表述的結(jié)論、未解決的問題和猜想，還有那些嵌入在證明內(nèi)的算法等，我們均沒有一一進(jìn)行統(tǒng)計。值得注意的是，在700多道習(xí)題中，部分習(xí)題是正文中沒有提及的結(jié)論、算法和問題等。本書中的有向圖理論幾乎涵蓋了當(dāng)今有向圖理論的主要研究專題，如哈密爾頓圈問題、最短路問題、網(wǎng)絡(luò)流理論等。書中關(guān)于哈密爾頓圈問題的深入研究，為讀者介紹了各種各樣關(guān)聯(lián)到哈密爾頓問題及其推廣的專題；Mengel定理在研究K（弧）強(qiáng)有向圖的應(yīng)用和推廣，如Edmonds分枝定理和K鏈接問題等，將十分有助于啟發(fā)我們研究問題的思路和認(rèn)識研究對象的方式，有益于我們設(shè)計研究方案或提出進(jìn)攻困難問題的方向。本書作者南丹麥大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)系J。邦詹森教授和倫敦大學(xué)皇家霍洛威學(xué)院計算機(jī)科學(xué)系G.古廷（Gregory Gutin）教授在內(nèi)容編排和寫作設(shè)計方面獨具匠心，由淺顯基本的結(jié)論逐步過渡到當(dāng)今有向圖理論中某些專題研究的前沿。他們力圖使讀者不僅理解、掌握有向圖的成熟理論，而且有能力投入到有向圖中未解決問題的研究主流里。加上書后的參考文獻(xiàn)、精煉的記號和一詳盡的術(shù)語，我們認(rèn)為這是一本兼顧教學(xué)和研究雙重任務(wù)的高度專業(yè)性書籍。本書的重要特色之一是提供了大量的證明技巧和方法。例如，Madei的撕裂技巧、多重插入技巧、兩類問題之間的簡約或等價轉(zhuǎn)換、算法式論證、網(wǎng)絡(luò)流模型、集合函數(shù)的子模流、擬陣算法等。書中使用了一些代數(shù)、組合、概率和線性規(guī)劃等學(xué)科中的部分方法，如Ramsey定理、ErdSs Szekeres定理、阿貝爾群、布爾變量、對偶定理等，為讀者的自行研究提供了大量的工具。作者指出，無向圖在一定程度上是有向圖的一個特殊類（對稱有向圖）。所以，無向圖理論和有向圖理論的有機(jī)結(jié)合也是值得我們考慮和研究的一個方面。

編輯推薦

《有向圖的理論算法及其應(yīng)用》概括了有向圖的基本知識，并從深層次的角度介紹了理論和算法這兩個方面的研究成果及應(yīng)用。書中的基本內(nèi)容是針對具有大學(xué)數(shù)學(xué)基礎(chǔ)知識的讀者，然后在幾個研究領(lǐng)域（包括連通性、圖的定向、子模流、有向圖的路和圈、競賽圖的推廣以及有向圖的推廣等）的主要方向上逐步到達(dá)最新的研究成果?！队邢驁D的理論算法及其應(yīng)用》配備了超過700道練習(xí)題、大量應(yīng)用以及適宜討論的專題。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    有向圖的理論、算法及其應(yīng)用 PDF格式下載

---