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

內(nèi)容概要

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

作者簡(jiǎn)介

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

書(shū)籍目錄

第一卷第1章 引言第2章 歐拉圖理論的三個(gè)支柱第3章 基本概念和預(yù)備知識(shí)3.1 混合圖與它們的基本要素3.2 圖與混合有向圖的子圖3.3 導(dǎo)出子圖3.4 路徑、跡、路、圈、樹(shù);連通度3.5 相容性,K*v的循環(huán)序和對(duì)應(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章 歐拉跡的各種類(lèi)型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-正則圖中的哈密頓圈之間的對(duì)偶性6.3.2 歐拉圖中的A-跡和哈密頓圈6.3.3 如何找出A-跡:一些復(fù)雜性討論和算法的建議6.3.4 關(guān)于非交叉歐拉跡和A-跡的注記以及另一問(wèn)題6.4 習(xí)題第7章 歐拉跡的變換7.1 圖中任意歐拉跡的變換7.2 特殊的歐拉跡的變換7.2.1 特殊類(lèi)型的歐拉跡和κ1-變換的應(yīng)用7.3 有向圖中的歐拉跡的變換7.4 最終注解及一些未解決的問(wèn)題7.5 習(xí)題參考文獻(xiàn)第二卷第8章 各種類(lèi)型的閉覆蓋途徑8.1 雙跡8.2 圖中的值-真途徑和整流8.3 中國(guó)郵遞員問(wèn)題8.3.1 關(guān)于圖上的中國(guó)郵遞員問(wèn)題8.3.2 有向郵遞員問(wèn)題8.3.3 混合郵遞員問(wèn)題8.3.4 帶風(fēng)向的郵遞員問(wèn)題和最后注記8.4 習(xí)題第9章 歐拉跡及其數(shù)目9.1 有向圖和(混合)圖的奇偶性的結(jié)果9.1.1 矩陣代數(shù)的一個(gè)應(yīng)用9.2 計(jì)數(shù)初涉9.2.1 矩陣樹(shù)定理9.2.2 有向圖和圖的歐拉跡計(jì)數(shù)9.2.3 關(guān)于歐拉定向的數(shù)目9.2.4 拜斯特定理的應(yīng)用和推廣9.2.5 其他說(shuō)明9.3 習(xí)題第10章 歐拉跡和圈分解的算法及迷宮搜索算法10.1 歐拉跡的算法10.2 圈分解算法10.3 迷宮10.4 習(xí)題參考文獻(xiàn)對(duì)第一卷的更正和補(bǔ)錄人名譯名表

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

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

無(wú)

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

---

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

---