第八章 一些特殊的圖

第八章一些特殊的圖第一頁，共四十四頁，2022年，8月28日8.2歐拉圖1736年瑞士數(shù)學(xué)家歐拉發(fā)表了圖論的第一篇著名論文“哥尼斯堡七橋問題”(下稱七橋問題)。這個(gè)問題是這樣的：哥尼斯堡城有一條橫貫全城的普雷格爾河，城的各部分用七橋聯(lián)結(jié)，每逢節(jié)假日，有些城市居民進(jìn)行環(huán)城周游，于是便產(chǎn)生了能否“從某地出發(fā)，通過每橋恰好一次，在走遍了七橋后又返回到原處”的問題。第二頁，共四十四頁，2022年，8月28日圖第三頁，共四十四頁，2022年，8月28日

反復(fù)的奔走試行和失敗，使人們對成功的可能發(fā)生疑惑，猜想問題無解，但又誰也說不清其中道理，于是有好事者去請教年輕的數(shù)學(xué)家歐拉(Euler)，剛開始?xì)W拉也看不出這是一個(gè)數(shù)學(xué)問題,1736年，29歲的歐拉把這一問題化成數(shù)學(xué)問題，嚴(yán)格地論證了上述“七橋問題”無解，并由此開創(chuàng)了圖論與拓?fù)鋵W(xué)的思維方式和諸多概念與理論，1736年遂被公認(rèn)為圖論學(xué)科的歷史元年，歐拉被尊為圖論與拓?fù)鋵W(xué)之父.第四頁，共四十四頁，2022年，8月28日在圖畫出了哥尼斯堡城圖，城的四塊陸地部分以A，B，C，和D標(biāo)記。歐拉巧妙地把哥尼斯堡城圖化為圖所示圖G，他把陸地設(shè)為圖G中的結(jié)點(diǎn)，把橋畫成相應(yīng)地聯(lián)結(jié)陸地即結(jié)點(diǎn)的邊。于是，通過哥尼斯堡城中每座橋恰好一次問題，等價(jià)于在圖G中從某一結(jié)點(diǎn)出發(fā)找出一條鏈，它通過每條邊恰好一次后回到原出發(fā)結(jié)點(diǎn)，亦即等價(jià)于在圖G中尋找一個(gè)圈，它通過G中每一條邊恰好一次。第五頁，共四十四頁，2022年，8月28日圖第六頁，共四十四頁，2022年，8月28日歐拉圖2．歐拉圖（歐拉回路與歐拉圖）經(jīng)過圖中每條邊一次且僅一次并且行遍圖中所有頂點(diǎn)的通路，稱為歐拉通路．若歐拉通路為回路，則稱它為歐拉回路．具有歐拉回路的圖稱為歐拉圖．具有歐拉通路的圖稱為半歐拉圖．第七頁，共四十四頁，2022年，8月28日歐拉通路判定定理定理8.4無向圖G具有歐拉通路當(dāng)且僅當(dāng)G連通且沒有或有兩個(gè)奇度頂點(diǎn)．若無奇度頂點(diǎn)，則歐拉通路為回路;若有兩個(gè)奇度頂點(diǎn)，則它們是每條歐拉通路的兩個(gè)端點(diǎn)．歐拉圖判定定理定理8.5無向圖G為歐拉圖當(dāng)且僅當(dāng)G連通且無奇度頂點(diǎn)．第八頁，共四十四頁，2022年，8月28日歐拉通路第九頁，共四十四頁，2022年，8月28日歐拉回路第十頁，共四十四頁，2022年，8月28日11110(a)1292834756因上圖是歐拉圖，故能沿著一條（不唯一的）歐拉回路一筆畫，且能回到出發(fā)點(diǎn)1，2，3，4，7，8，10，11，12，2，5，4，6，5，12，9，6，8，9，11，1.第十一頁，共四十四頁，2022年，8月28日第十二頁，共四十四頁，2022年，8月28日應(yīng)用1：一筆畫問題許多智力題要求用筆連續(xù)移動(dòng)，不離開紙面，每邊只能畫一次，不允許重復(fù)，將圖形畫出，稱該圖能一筆畫。利用歐拉回路和通路來解決這樣的智力題。例如能否將穆罕默德短彎刀一筆畫？第十三頁，共四十四頁，2022年，8月28日歐拉回路：a,b,d,g.h,j,i,h,k,g,f,d,c,b.e.i.f,e,a.第十四頁，共四十四頁，2022年，8月28日螞蟻比賽問題甲、乙兩只螞蟻分別位于右下圖中的結(jié)點(diǎn)a，b處，并設(shè)圖中的邊長度是相等的。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過圖中的所有邊最后到達(dá)結(jié)點(diǎn)c處。如果它們的速度相同，問誰先到達(dá)目的地？在圖中，僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)b，c，因而存在從b到c的歐拉通路。cb(乙)a(甲)第十五頁，共四十四頁，2022年，8月28日螞蟻比賽問題

在圖中，存在從b到c的歐拉通路，且螞蟻乙從b到c只要走一條邊數(shù)為9的歐拉通路；

而螞蟻甲要想走完所有的邊到達(dá)c，至少要先走一條邊從a到達(dá)b，再走一條歐拉通路因而，它至少要走10條邊，才能到達(dá)c，所以乙必勝。cb(乙)a(甲)第十六頁，共四十四頁，2022年，8月28日應(yīng)用2:中國郵路問題問題：一個(gè)郵遞員從郵局出發(fā),走遍所有街道,把郵件送到每個(gè)收件人手中,最后回到郵局,要怎樣走,使全程路線最短。轉(zhuǎn)化為圖論問題：以街道為邊,以街道交叉點(diǎn)為結(jié)點(diǎn),以街道的長度為邊上的權(quán),在帶權(quán)圖G=<V,E,W>上,找出一個(gè)經(jīng)過所有邊至少一次的回路,并使得該回路的權(quán)和達(dá)到最小。第十七頁，共四十四頁，2022年，8月28日說明：1、該回路未必是Euler回路,邊允許重復(fù)。2、中國管梅谷教授1962年提出了這個(gè)問題,著名數(shù)學(xué)家J.埃德蒙和他的合作者給出了一個(gè)解答。指出如果圖G有m條邊,則所求回路至少是m條邊,最多不超過2m條邊,并且每邊在回路中至多出現(xiàn)兩次。第十八頁，共四十四頁，2022年，8月28日有向歐拉圖定理8.6有向圖D為半歐拉圖當(dāng)且僅當(dāng)D連通，且除兩個(gè)頂點(diǎn)外，其余頂點(diǎn)的入度等于出度，這兩個(gè)例外的頂點(diǎn)中，一個(gè)的入度比出度大1，另一個(gè)的入度比出度小1．

定理8.7有向圖D為歐拉圖當(dāng)且僅當(dāng)D連通且每個(gè)頂點(diǎn)的入度等于出度．第十九頁，共四十四頁，2022年，8月28日判斷有向圖是否有歐拉路V1V2V3V4(a)圖a)中（結(jié)點(diǎn)v1的入度比出度大1，結(jié)點(diǎn)v3的出度比入度大1，且除了這兩個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)的入度等于出度）因此，存在一條的歐拉通路

v3v1v2v3v4v1；第二十頁，共四十四頁，2022年，8月28日V8V2V4V6(c)V1V3V5V7圖(c)中所有結(jié)點(diǎn)的入度等于出度，有歐拉回路

v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是歐拉圖。第二十一頁，共四十四頁，2022年，8月28日第二十二頁，共四十四頁，2022年，8月28日歐拉圖應(yīng)用：計(jì)算機(jī)鼓輪設(shè)計(jì)旋轉(zhuǎn)鼓的表面分成8塊扇形，如圖所示。圖中陰影區(qū)表示用導(dǎo)電材料制成，空白區(qū)用絕緣材料制成，分別用二進(jìn)制信號1或0表示。終端a、b和c是接地或不是接地.因此，鼓的位置可用二進(jìn)制信號表示。試問應(yīng)如何選取這8個(gè)扇形的材料使每轉(zhuǎn)過一個(gè)扇形都得到一個(gè)不同的二進(jìn)制信號，即每轉(zhuǎn)一周，能得到000至111的8個(gè)數(shù)。第二十三頁，共四十四頁，2022年，8月28日第二十四頁，共四十四頁，2022年，8月28日第二十五頁，共四十四頁，2022年，8月28日解：每轉(zhuǎn)一個(gè)扇形，信號a1a2a3變成a2a3a4

，前者右兩位決定了后者的左兩位。因此，我們可把所有兩位二進(jìn)制數(shù)作結(jié)點(diǎn)，從每一個(gè)頂點(diǎn)a1a2到a2a3引一條有向邊a1a2a3表示這個(gè)3位二進(jìn)制數(shù)，作出表示所有可能的碼變換的有向圖（見下圖）。第二十六頁，共四十四頁，2022年，8月28日第二十七頁，共四十四頁，2022年，8月28日第二十八頁，共四十四頁，2022年，8月28日于是問題轉(zhuǎn)化為在這個(gè)有向圖上求一條歐拉回路。這個(gè)有向圖的4個(gè)頂點(diǎn)的次數(shù)都是出度、入度各為2，根據(jù)定理8.6，歐拉回路存在，比如是一條歐拉回路，對應(yīng)于這個(gè)回路的布魯英序列：00011101，因此材料應(yīng)按此序列分布。第二十九頁，共四十四頁，2022年，8月28日上面的例子可以將鼓輪推廣到具有n個(gè)觸點(diǎn)的情形.第三十頁，共四十四頁，2022年，8月28日小結(jié)：歐拉圖半歐拉圖和歐拉圖共性：1、過每邊一次且僅一次；2、連通。半歐拉圖和歐拉圖個(gè)性：半歐拉圖：1、無向圖，僅有零個(gè)或兩個(gè)奇度數(shù)結(jié)點(diǎn)；2、有向圖，其中有兩個(gè)結(jié)點(diǎn)，一個(gè)入度比出度大

1，另一個(gè)出度比入度大1。歐拉圖：1、無向圖，所有結(jié)點(diǎn)的度數(shù)都為偶數(shù)；2、有向圖，所有結(jié)點(diǎn)的入度等于出度。第三十一頁，共四十四頁，2022年，8月28日多產(chǎn)的數(shù)學(xué)家歐拉

歐拉1707年出生在瑞士的巴塞爾（Basel）城，13歲就進(jìn)巴塞爾大學(xué)讀書，得到當(dāng)時(shí)最有名的數(shù)學(xué)家約翰·伯努利（JohannBernoulli，1667-1748年）的精心指導(dǎo)．（LeonhardEuler公元1707-1783年）第三十二頁，共四十四頁，2022年，8月28日歐拉淵博的知識，無窮無盡的創(chuàng)作精力和空前豐富的著作，都是令人驚嘆不已的！他從19歲開始發(fā)表論文，直到76歲，半個(gè)多世紀(jì)寫下了浩如煙海的書籍和論文．到今幾乎每一個(gè)數(shù)學(xué)領(lǐng)域都可以看到歐拉的名字，從初等幾何的歐拉線，多面體的歐拉定理，立體解析幾何的歐拉變換公式，四次方程的歐拉解法到數(shù)論中的歐拉函數(shù)，微分方程的歐拉方程，級數(shù)論的歐拉常數(shù)，變分學(xué)的歐拉方程，復(fù)變函數(shù)的歐拉公式等等，數(shù)也數(shù)不清．他對數(shù)學(xué)分析的貢獻(xiàn)更獨(dú)具匠心，《無窮小分析引論》一書便是他劃時(shí)代的代表作，當(dāng)時(shí)數(shù)學(xué)家們稱他為"分析學(xué)的化身"．第三十三頁，共四十四頁，2022年，8月28日歐拉是科學(xué)史上最多產(chǎn)的一位杰出的數(shù)學(xué)家，據(jù)統(tǒng)計(jì)他那不倦的一生，共寫下了886本書籍和論文，其中分析、代數(shù)、數(shù)論占40%，幾何占18%，物理和力學(xué)占28%，天文學(xué)占11%，彈道學(xué)、航海學(xué)、建筑學(xué)等占3%，彼得堡科學(xué)院為了整理他的著作，足足忙碌了四十七年．第三十四頁，共四十四頁，2022年，8月28日歐拉著作的驚人多產(chǎn)并不是偶然的，他可以在任何環(huán)境中工作，他常常抱著孩子在膝上完成論文，也不顧孩子在旁邊喧嘩．他那頑強(qiáng)的毅力和孜孜不倦的治學(xué)精神，使他在雙目失明以后，也沒有停止對數(shù)學(xué)的研究，在失明后的17年間，他還口述了幾本書和400篇左右的論文．19世紀(jì)偉大數(shù)學(xué)家高斯（Gauss，1777-1855年）曾說："研究歐拉的著作永遠(yuǎn)是了解數(shù)學(xué)的最好方法．"第三十五頁，共四十四頁，2022年，8月28日

1725年約翰·伯努利的兒子丹尼爾·伯努利赴俄國，并向沙皇喀德林一世推薦了歐拉，這樣，在1727年5月17日歐拉來到了彼得堡．1733年，年僅26歲的歐拉擔(dān)任了彼得堡科學(xué)院數(shù)學(xué)教授．1735年，歐拉解決了一個(gè)天文學(xué)的難題（計(jì)算慧星軌道），這個(gè)問題經(jīng)幾個(gè)著名數(shù)學(xué)家?guī)讉€(gè)月的努力才得到解決，而歐拉卻用自己發(fā)明的方法，三天便完成了．然而過度的工作使他得了眼病，并且不幸右眼失明了，這時(shí)他才28歲．第三十六頁，共四十四頁，2022年，8月28日

1741年歐拉應(yīng)普魯士彼德烈大帝的邀請，到柏林擔(dān)任科學(xué)院物理數(shù)學(xué)所所長，直到1766年，后來在沙皇喀德林二世的誠懇敦聘下重回彼得堡，不料沒有多久，左眼視力衰退，最后完全失明．不幸的事情接踵而來，1771年彼得堡的大火災(zāi)殃及歐拉住宅，帶病而失明的64歲的歐拉被圍困在大火中，雖然他被別人從火海中救了出來，但他的書房和大量研究成果全部化為灰燼了．第三十七頁，共四十四頁，2022年，8月28日沉重的打擊，仍然沒有使歐拉倒下，他發(fā)誓要把損失奪回來．在他完全失明之前，還能朦朧地看見東西，他抓緊這最后的時(shí)刻，在一塊大黑板上疾書他發(fā)現(xiàn)的公式，然后口述其內(nèi)容，由他的學(xué)生特別是大兒子A·歐拉（數(shù)學(xué)家和物理學(xué)家）筆錄．歐拉完全失明以后，仍然以驚人的毅力與黑暗搏斗，憑著記憶和心算進(jìn)行研究，直到逝世，竟達(dá)17年之久．第三十八頁，共四十四頁，2022年，8月28日歐拉的風(fēng)格是很高的，拉格朗日是稍后于歐拉的大數(shù)學(xué)家，從19歲起和歐拉通信，討論等周問題的一般解法，這引起變分法的誕生．等周問題是歐拉多年來苦心考慮的問題，拉格朗日的解法，博得歐拉的熱烈贊揚(yáng)，1759年10月2日歐拉在回信中盛稱拉格朗日的成就，并謙虛地壓下自己在這方面較不成熟的作品暫不發(fā)表，使年青的拉格朗日的工作得以發(fā)表和流傳，并贏得巨大的聲譽(yù)．他晚年的時(shí)候，歐洲所有的數(shù)學(xué)家都把他當(dāng)作老師，著名數(shù)學(xué)家拉普拉斯（Laplace）曾說過："歐拉是我們的導(dǎo)師．第三十九頁，共四十四頁，2022年，8月28日作為這樣一位科學(xué)巨人，在生活中他并不是一個(gè)呆板的人。他性情溫和，性格開朗，也喜歡交際。歐拉結(jié)過兩次婚，有13個(gè)孩子。他熱愛家庭的生活，常常和孩子們一起做科學(xué)游戲，講故事。"歐拉充沛的精力保持到最后一刻，1783年9月18日下午，歐拉為了慶祝他計(jì)算氣球上升定律的成功，請朋友們吃飯，那時(shí)天王星剛發(fā)現(xiàn)不久，歐拉寫出了計(jì)算天王星軌道的要領(lǐng)，還和他的孫子逗笑，喝完茶后，突然疾病發(fā)作，煙斗從手中落下，口里喃喃地說："我死了"，歐拉終于"停止了生命和計(jì)算"．第四十頁，共四十四頁，2022年，8月28日在普及教育和科研中，歐拉意識到符號的簡化和規(guī)則化既有有助于學(xué)生的學(xué)習(xí)，又有助于數(shù)學(xué)的發(fā)展，所以歐拉創(chuàng)立了許多新的符號。如1734年用f(x)

表示函數(shù)，1736年用e

表示自然對數(shù)的底，1748年用sin

、cos，（1753年）tg等表示三角函數(shù)，1755年用∑表示求和，1777年用i表示虛數(shù)等。1736年，圓周率π雖然不是歐拉首創(chuàng)，但卻是經(jīng)過歐拉的倡導(dǎo)才得以廣泛流行。第四十一頁，共四十四頁，2022年，8