歐拉圖與相關(guān)專題

內(nèi)容概要

本書是迄今為止唯一的一本全面闡述歐拉圖理論的主要研究成果和研究方法及其與其他圖論問題之間的聯(lián)系的專著。本書包含兩卷共十章。第一卷從歐拉的哥尼斯堡七橋問題開始，由淺入深地介紹了歐拉問題的起源，給出圖的基本概念和預(yù)備知識，然后相繼地介紹了無向圖、有向圖以及混合圖中歐拉跡的結(jié)構(gòu)性定理，歐拉跡的若干推廣，各種類型的歐拉跡，歐拉跡的變換。在第二卷中，詳盡地介紹了著名的中國郵遞員問題，歐拉跡的計數(shù)問題，最后討論了與歐拉問題相關(guān)的算法和計算復(fù)雜性。每章后面配有習(xí)題，幫助讀者理解和掌握本章的主要內(nèi)容。
本書適合從事圖論研究的研究生和科研工作者使用，也是其他數(shù)學(xué)和計算機(jī)科學(xué)研究人員很好的參考書。

作者簡介

作者：（美國）費萊施納(Fleischner,H.) 譯者：孫志人 李皓 劉桂真 劉振宏 等

書籍目錄

第一卷第1章 引言第2章 歐拉圖理論的三個支柱第3章 基本概念和預(yù)備知識3.1 混合圖與它們的基本要素3.2 圖與混合有向圖的子圖3.3 導(dǎo)出子圖3.4 路徑、跡、路、圈、樹;連通度3.5 相容性,K*v的循環(huán)序和對應(yīng)的歐拉跡3.6 匹配、1-因子、2-因子、1-因子分解、2-因子分解、二部圖3.7 圖的曲面嵌入、同構(gòu)3.8 平面圖的著色3.9 哈密頓圈3.10 關(guān)聯(lián)矩陣和鄰接矩陣、流和張力3.11 算法及其復(fù)雜性3.12 注記第4章 特征定理和推論4.1 圖4.2 有向圖4.3 混合圖4.4 習(xí)題第5章 再論歐拉跡及其推廣展望5.1 跡分解,路、圈分解5.2 奇偶性結(jié)果5.3 雙跡5.4 交叉邊界:圖的分拆5.5 習(xí)題第6章 歐拉跡的各種類型6.1 回避特定轉(zhuǎn)移的歐拉跡6.1.1 有向圖中P(D)相容歐拉跡6.1.2 雙歐拉有向圖中的反歐拉跡和圖的雙歐拉定向6.1.3 有向圖中的D0-偏好歐拉跡6.2 兩兩相容歐拉跡6.2.1 有向圖中的兩兩相容歐拉跡6.3 平面歐拉圖中的A-跡6.3.1 平面歐拉圖中的A-跡和平面3-正則圖中的哈密頓圈之間的對偶性6.3.2 歐拉圖中的A-跡和哈密頓圈6.3.3 如何找出A-跡:一些復(fù)雜性討論和算法的建議6.3.4 關(guān)于非交叉歐拉跡和A-跡的注記以及另一問題6.4 習(xí)題第7章 歐拉跡的變換7.1 圖中任意歐拉跡的變換7.2 特殊的歐拉跡的變換7.2.1 特殊類型的歐拉跡和κ1-變換的應(yīng)用7.3 有向圖中的歐拉跡的變換7.4 最終注解及一些未解決的問題7.5 習(xí)題參考文獻(xiàn)第二卷第8章 各種類型的閉覆蓋途徑8.1 雙跡8.2 圖中的值-真途徑和整流8.3 中國郵遞員問題8.3.1 關(guān)于圖上的中國郵遞員問題8.3.2 有向郵遞員問題8.3.3 混合郵遞員問題8.3.4 帶風(fēng)向的郵遞員問題和最后注記8.4 習(xí)題第9章 歐拉跡及其數(shù)目9.1 有向圖和(混合)圖的奇偶性的結(jié)果9.1.1 矩陣代數(shù)的一個應(yīng)用9.2 計數(shù)初涉9.2.1 矩陣樹定理9.2.2 有向圖和圖的歐拉跡計數(shù)9.2.3 關(guān)于歐拉定向的數(shù)目9.2.4 拜斯特定理的應(yīng)用和推廣9.2.5 其他說明9.3 習(xí)題第10章 歐拉跡和圈分解的算法及迷宮搜索算法10.1 歐拉跡的算法10.2 圈分解算法10.3 迷宮10.4 習(xí)題參考文獻(xiàn)對第一卷的更正和補錄人名譯名表

章節(jié)摘錄

版權(quán)頁：插圖：第1章 引言 冠尼希（D′enesK¨onig）的書Theoriederendichenund Unendlichen Graphen（《有限圖與無限圖的理論》）[K¨  ONI36a]于1936年第一次出版時，只用248頁（不包括前言、目錄和參考文獻(xiàn)）就囊括了自歐拉（L。Euler）發(fā)表哥尼斯堡七橋問題的解的文章以來，200年中圖論領(lǐng)域的大部分內(nèi)容。 實際上，歐拉把他的文章提交給圣彼得堡科學(xué)院是在1735年8月26日，但 他的文章“Solutioproblematisadgeometriamsituspertinentis”一直到1741年才發(fā)表在Commentarii Academiae Scientiarum Imperialis Petropolitanae上。由于這個Commentarii注明的日期是1736年，所以圖論作為數(shù)學(xué)的一個分支一般被認(rèn)為誕生在1736年。 然而，D。K¨onig在他的前言中指出：他的書中所考慮的圖論僅限制在所謂的絕對圖中（現(xiàn)在稱為抽象圖），除幾個例外的情形，他沒有討論拓?fù)鋱D論（他稱為相對圖論）和計數(shù)圖論。 D。K¨onig的書問世以后，特別是第二次世界大戰(zhàn)結(jié)束以后，圖論得到了飛速發(fā)展。專門發(fā)表組合論文的期刊越來越多，它們所涉及的文章中大約有一半是圖論文章。例如，《圖論雜志》創(chuàng)刊于1977年。圖論研究的繁榮不僅反映在圖論書籍?dāng)?shù)目的增長上，而且反映在這些書籍的內(nèi)容上。它們中有很多都聚焦于圖論的一些特殊專題，如拓?fù)鋱D論、代數(shù)圖論以及近年來具有強勁勢頭的算法圖論（該方向的研究是出于計算機(jī)科學(xué)的需要）。由此可見，圖論也遵循著科學(xué)發(fā)展的一般過程。最初，它從一般領(lǐng)域中脫離出來（D。K¨onig的書的子標(biāo)題是“Kombinatorische Topologieder Strekkenkomplexe”――一維復(fù)形組合拓?fù)洌Ｈ缓笏职凑账玫慕Y(jié)果和所用的方法分化為若干不同的分支。圖論的這種發(fā)展可以被Selected Topicsin GraphTheory和Selected Topicsin Graph Theory2（[BEIN78a]，[BEIN83a]）（《圖論專題精選》和《圖論專題精選2》）的出版所見證，其主編是本尼克（L。W。Beineke）和威爾遜（R。J。Wilson）。書中包含了不同作者撰寫的22篇綜述文章。現(xiàn)在《圖論專題精選3》也已出版?！秷D論應(yīng)用》包含了12篇綜述文章，涉及的是圖論在各學(xué)科的應(yīng)用，編者同上。 歐拉解決哥尼斯堡（現(xiàn)為加里寧格勒）七橋問題的文章并未把功勞歸于自己，他在文章中提到了Leibniz（Leibniz）： 幾何學(xué)中除了與數(shù)量有關(guān)并且為人們極為重視的那個分支外，還有 一個目前幾乎一無所知的分支這就是Leibniz首先提出的位置幾何學(xué)（ge- ometria situs）。 這個分支只涉及位置的確定及其性質(zhì)，它不涉及度量，也 不作計算。。 歐拉繼續(xù)說明：目前還不十分清楚哪些問題與位置幾何學(xué)有關(guān)，也不清楚解決它們要用什么方法。但是他肯定，哥尼斯堡七橋問題就是這樣一個問題，因為它的解只涉及位置，而沒有用任何計算[WILS85a]。 事實上，早在1679年，Leibniz在他給惠更斯（Huygens）的信（摘自[WILS85a]）中說：“我不滿足于代數(shù)，因為代數(shù)里既沒有幾何中最簡短的證明，也沒有幾何中最漂亮的構(gòu)造。因此，我認(rèn)為需要另外一種類型的分析，幾何的或線性的，它能像代數(shù)處理數(shù)量大小一樣直接處理位置。” 通過引進(jìn)術(shù)語“位置分析”（analysissitus），Leibniz并沒有奠定一個新的數(shù)學(xué)研究領(lǐng)域，而是指出了一個可能取得進(jìn)展的總的研究方向（對“位置分析”這個術(shù)語的歷史感興趣的讀者，可以參見Wilson的文章[WILS85a]）。在第2章，我們將對圖論的歷史作更多評述。在這里值得一提的是，K¨onig的書大概是圖論早期最豐富的專著（這里“早期”是指1936年K¨onig的書出版以前圖論的發(fā)展時期）。 但為什么要出一本關(guān)于歐拉圖的書？是不是因為最近舉行了圖論（特別是歐拉的文章）250周年的紀(jì)念活動？本書的出版和圖論250周年紀(jì)念日接近純粹是一種巧合（我原計劃在1985年3月底完稿）。但是，正如前言中指出的，歐拉圖方面的文章不僅在數(shù)量上增長極快，而且該專題的統(tǒng)一理論也趨向成熟。這兩個事實成為寫《歐拉圖與相關(guān)專題》一書的必要條件。許多同事也對這件事表示出了興趣，本書和圖論發(fā)展的大趨勢是一致的。雖然這個過程是緩慢的，但是圖論在過去的20多年里確實分化出一些不同分支。 第2章將給出三篇文章的原始版本。大多數(shù)圖論學(xué)家認(rèn)為它們構(gòu)成了歐拉圖理論的主要根基。本書大部分內(nèi)容都致力于與這三篇文章中提出的概念有直接關(guān)系的一些結(jié)果。但與現(xiàn)在圖論的發(fā)展相比，我認(rèn)為只限于歐拉圖的這部分內(nèi)容會太狹隘。這一觀點也體現(xiàn)在我的綜述文章“歐拉圖”里（見[BEIN83a]）。另一方面，這一觀點提出了一個問題：如何確定這樣一本書的材料選擇問題。 由于本書是第一次集中討論歐拉圖，所以我決定盡可能廣地覆蓋這一領(lǐng)域的問題。某些專題我討論得很詳細(xì)，而另一些專題像綜述一樣點到為止。當(dāng)然，這樣做也有一些缺點。在某些情況下，讀者要想了解該專題更多的內(nèi)容，常常不得不去查閱其他的書或本書所引用的原始文獻(xiàn)。另外，本書的某些內(nèi)容會與圖論中的其他分支相重疊，如在中國郵遞員那一章，在1-因子分解起重要作用的地方，以及在計數(shù)、著色和一些其他地方，都有明顯重疊。但是一般來說，恰恰由于現(xiàn)代圖論的發(fā)展，這樣或多或少的重疊是不可避免的。 為了選取恰當(dāng)?shù)牟牧?，我查閱了?shù)百篇文獻(xiàn)。許多參考文獻(xiàn)在本書中并沒有進(jìn)行廣泛的討論。不過本書的目的之一是指出目前研究的各種不同方向?？赡苡械淖x者會感到參考文獻(xiàn)的數(shù)量遠(yuǎn)遠(yuǎn)多于本書討論過的問題，但是書后的參考文獻(xiàn)可以有利于幫助感興趣的讀者延伸到本書內(nèi)容以外的各個研究方向。我查閱了眾多的文獻(xiàn)，希望不要漏掉歐拉圖理論方面的重要內(nèi)容，以彌補我的綜述文章在這方面的不足。 最后的一項要點是，本書是自封閉的，因為我希望它的讀者盡可能多一些。因此，第3章論述了圖論的基礎(chǔ)理論，以滿足后面幾章的需要。要讀懂某些專題，或多或少還需要更廣泛的數(shù)學(xué)知識，這有點使人困擾。因此，本書中盡可能避免使用 “容易導(dǎo)出”，“顯而易見”等語句。許多數(shù)學(xué)家（包括我自己），不止一次地遇到過這種情況：要看明白一個“容易”，還需要筆和紙，并花掉半個小時，甚至更長的時間。因此，在使用了大量圖形來闡明情況的同時，我并未用圖形去代替邏輯證明。但是在某些情形下，某些結(jié)果的完整證明還是留給了讀者，作為不太困難的練習(xí)。因此，本書的內(nèi)容，無論對大學(xué)生還是對研究生來說，作為歐拉圖理論的課程是都已足夠了，即使不熟悉圖論的數(shù)學(xué)家也可以參考。由于本書包含了許多最新的結(jié)果（其中有些結(jié)果只是部分地解決了某些未決問題）、相當(dāng)多的猜想，故圖論方面的研究者們也會感興趣。 再說說算法和復(fù)雜性研究的問題。許多問題（如歐拉跡、圈分解、郵遞員路線和迷宮通路等問題）是用算法陳述的。但是，本書的目的不是要理論化提出一個算法。復(fù)雜性問題也是如此。從理論的觀點來看，問題是否多項式時間可解是很重要的。但在本書中，一個算法的復(fù)雜性是O（n）還是O（n2）是屬于次要的事。我知道許多同事（特別是有這方面傾向的計算機(jī)科學(xué)家和圖論學(xué)家）會對此不滿。 我愿意接受任何人的批判性的意見（肯定的、否定的或是混合的），因為這可以幫助我改進(jìn)工作。我將對所有給我提出意見的各位作出回應(yīng)。 第2章 歐拉圖理論的三個支柱 歐拉關(guān)于哥尼斯堡七橋問題的文章[EULER36a]和Hierholzer關(guān)于構(gòu)造連通歐拉圖的歐拉跡的文章[HIER73a]都有許多不同的譯本。但是，接下來我還是要給出我自己的譯文①。決定這樣做是因為我發(fā)現(xiàn)這些譯本中有一個缺點：它們是“時新”的譯本，多多少少地忽略了文章發(fā)表時的寫作風(fēng)格。因此，從歷史的觀點來看，這些譯本是不夠準(zhǔn)確的，它們無意中曲解了認(rèn)知之路，我的譯本并非一個學(xué)了6年拉丁文的高中生遞交的家庭作業(yè)，也并非出于對版權(quán)的擔(dān)心。 關(guān)于歐拉文章的歷史說明，有興趣的讀者可參見文獻(xiàn)[WILS85a，WILS86a]和[SACH86a，SACH86b]。 一個位置幾何問題的解。  1.幾何學(xué)中有一部分內(nèi)容與數(shù)量有關(guān)，人們對其頗感興趣。除此之外，還有一部分內(nèi)容，人們對它都知之甚少。這部分幾何首先由Leibniz提出，稱為位置幾何。它研究僅由位置就可確定的幾何，并研究位置的性質(zhì)。在這種幾何中，人們不關(guān)心數(shù)量，也不關(guān)心計算。然而，什么問題屬于位置幾何？求解它們要使用什么方法？一直沒有明確的界定。當(dāng)最近有一個問題被提出來時，我確信它屬于位置幾何。它看上去是一個幾何問題，同時又具有這樣的性質(zhì)：不需要確定數(shù)量關(guān)系，通過量的計算也無法解決它。特別地，其求解只需要位置關(guān)系就可以，而計算是無益于事的。因此，作為位置幾何的一個例子，決定在此介紹我解決這類問題的一個方法。 2.據(jù)說這個問題是相當(dāng)有名的，并且與以下敘述有關(guān)：哥尼斯堡是普魯士的一個島，稱為derKneiphof。圍繞它的河被其分為兩支（圖1）。河上架有7座橋a，b，c，d，e，f，g。問題是一個人能否經(jīng)過每座橋一次且恰好一次。據(jù)說有的人否認(rèn)這件事的可能性，而另一些人表示懷疑，但是沒有人能給出確定的答案。我將這一問題推廣到了一般情形：不管河的形狀和支流分布如何，也不管河上多少座橋。 3.下述方法肯定能解哥尼斯堡七橋問題：列出所有可能的行走路線，由此就可以知道是否有某條路線滿足要求。但是由于組合的數(shù)目太大，這種方法是極端困難和辛苦的，而且這種方法很難應(yīng)用于橋數(shù)更多的情形。這種方法會導(dǎo)致許多無關(guān)①感謝維也納奧地利科學(xué)院的H。Reitterer先生，他核對了我對歐拉文章的譯文。 。 原書II。2～I(xiàn)I。11是歐拉文章的影印件，共10頁，摘自于歐拉全集，I7，代數(shù)研究）。這里是歐拉文章的譯文。――譯者 因素的討論，包括復(fù)雜度。排除了這種方法后，我力求尋找其他途徑，一種只判斷符合要求的路線是否存在的途徑，我猜想應(yīng)該存在這樣一個簡單的方法。 4.我的方法基于表示路線的適當(dāng)方式。大寫字母A，B，C，D表示被河分割的區(qū)域。如果一個人從區(qū)域A經(jīng)過橋a或者橋b走到區(qū)域B，就用字母AB表示這個轉(zhuǎn)移。第一個字母表示旅行者從何而來，第二個字母表示穿過橋后到達(dá)的區(qū)域。如果旅行者接著由區(qū)域B經(jīng)過橋f到達(dá)區(qū)域D，這個轉(zhuǎn)移用BD表示。ABD表示這兩個相繼的轉(zhuǎn)移AB和BD，字母B是第一次轉(zhuǎn)移到達(dá)的區(qū)域，也是第二次轉(zhuǎn)移離開的區(qū)域。 5.類似地，若旅行者由區(qū)域D繼續(xù)穿過橋g到達(dá)區(qū)域C，就用4個字母ABDC表示這三個相繼的轉(zhuǎn)移。從ABDC這4個字母中可以看出，旅行者首先出現(xiàn)在區(qū)域A，然后到達(dá)區(qū)域B，再前行到達(dá)區(qū)域D，接著又到達(dá)區(qū)域C。因為這些區(qū)域是被河流分開的，所以旅行者必須穿過三座橋。類似地，相繼穿過4座橋?qū)⒂?個字母表示。無論旅行者穿過多少座橋，這條路都將用一串字母表示，其中字母數(shù)比穿過的橋數(shù)多1。因此，穿過7座橋?qū)⒂?個字母來描述。 6.這種記法并不需要考慮穿過的是哪座橋。當(dāng)一個人可以穿過多座橋從一個區(qū)域到達(dá)另一區(qū)域時，他走哪座橋是無關(guān)緊要的。因此，若一個人能穿過7座橋且每座橋恰好穿過一次，則他的走法可以用8個字母表示。它們的順序必須滿足：前后相繼的A和B將出現(xiàn)兩次，這是因為區(qū)域A和B間有兩座橋a和b相連。類似地，前后相繼的A和C出現(xiàn)兩次，而前后相繼的A和D，B和D，C和D各出現(xiàn)一次。 7.因此，這個問題約化為能否用4個字母A，B，C，D構(gòu)成8個字母的序列，使得序列中相繼字母出現(xiàn)的次數(shù)滿足上述要求。但在試圖找出這樣一個序列之前，需要先考察這種安排是否可能。因為如果能證明這樣的安排是不可能的，那么構(gòu)造此序列的一切努力都是無效的。因此，我研究了一個簡單的規(guī)則，以判斷這個問題和所有類似的問題是否有效。 8.為了發(fā)現(xiàn)這樣的規(guī)則，我考慮了一個具體的區(qū)域A，通向A的橋可能有任意多座（圖2）。在這些橋中，先考慮了一座具體的橋a。如果旅行者穿過橋a，那么他或者跨越這座橋之前在區(qū)域A里，或者跨越橋之后到達(dá)區(qū)域A。因此，為了如上 所述地記錄這次轉(zhuǎn)移，字母A必須出現(xiàn)一次。如果有三座橋a，b，c通向區(qū)域A，并且旅行者要穿過所有這三座橋，那么不管他開始是否在區(qū)域 A里，在他的走法的描述中，字母A都將出現(xiàn)兩次。如果橋的數(shù)目是任一奇數(shù)，那么字母A出現(xiàn)的次數(shù)就為橋數(shù)加1的一半。 9.在哥尼斯堡七橋問題（圖1）中，因為有5座橋通向區(qū)域A，因此，在遍歷這些橋的描述中，字母A必須出現(xiàn)三次。由于有三座橋通向區(qū)域B，故字母B必須出現(xiàn)兩次。類似地，字母D和C都出現(xiàn)兩次。在描述經(jīng)過7座橋的8個字母的序列中，字母A要出現(xiàn)三次，字母B，C，D各要出現(xiàn)兩次，這樣的序列是不存在的。因此，按上述要求通過哥尼斯堡七橋的路線也是不存在的。 10.其他這類問題，假定通向每一個區(qū)域的橋數(shù)都為奇數(shù)，按類似的方法也能夠判斷是否有一條通過每座橋恰好一次的路線。如果字母出現(xiàn)的總數(shù)等于橋數(shù)加1，那么這樣的路線是可能的。但是如果像上述例子一樣，字母出現(xiàn)的總數(shù)大于橋數(shù)加1，那這樣的路線就不存在了。我提出的字母A的出現(xiàn)次數(shù)的法則，不管這些橋是從一個區(qū)域通向A的，還是從不同區(qū)域通向A的，都是有效的。 11.然而，如果通向A的橋數(shù)為偶數(shù)，那就必須考慮旅行者是否是從區(qū)域A出發(fā)的。如果有兩座橋通向區(qū)域A，并且旅行者是從區(qū)域A出發(fā)的，那么字母A就必須出現(xiàn)兩次。第一次表示他穿過一座橋離開區(qū)域A，而第二次表示他穿過另一座橋返回區(qū)域A。但是如果旅行者是從另一區(qū)域出發(fā)的，那么字母A只出現(xiàn)一次，它既表示到達(dá)區(qū)域A，也表示從區(qū)域A離開。 12.假設(shè)有4座橋通向A，并且旅行者從區(qū)域A出發(fā)，那么字母A就在整條路線中出現(xiàn)三次。但是如果旅行者是從另一區(qū)域出發(fā)的，那么字母A只出現(xiàn)兩次。假設(shè)有6座橋通向區(qū)域A，并且旅行者從區(qū)域A出發(fā)，那么字母A就在整條路線中出現(xiàn)4次。但是如果旅行者是從另一區(qū)域出發(fā)的，那么字母A只出現(xiàn)三次。一般地，如果假設(shè)有2n（n∈N）座橋通向區(qū)域A，并且旅行者從區(qū)域A出發(fā)，那么字母A就在整條路線中出現(xiàn)n+1次。但是如果旅行者從另一區(qū)域出發(fā)，那么字母A只出現(xiàn)n次。 13.在這樣一條路線里，其出發(fā)地只能有一個區(qū)域。由通向一個區(qū)域的橋數(shù)，就能算出該區(qū)域出現(xiàn)的次數(shù)。如果橋數(shù)為奇數(shù)，那么這個奇數(shù)加1的一半就是這個區(qū)域出現(xiàn)的次數(shù)；如果橋數(shù)為偶數(shù)，那么這個偶數(shù)的一半就是這個區(qū)域出現(xiàn)的次數(shù)。

編輯推薦

《歐拉圖與相關(guān)專題》是赫伯特?費萊施納先生的重要學(xué)術(shù)著作。在這本書中，費萊施納結(jié)合他多年的研究和對圖論學(xué)科的深刻理解，對歐拉問題進(jìn)行了全面和深刻的闡述，可以說這是歐拉圖唯一的一本高水平專著?！稓W拉圖與相關(guān)專題》適合從事圖論研究的研究生和科研工作者使用，也是其他數(shù)學(xué)和計算機(jī)科學(xué)研究人員很好的參考書。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    歐拉圖與相關(guān)專題 PDF格式下載

---