應用離散數學圖論§5.5歐拉圖與哈密爾頓圖習題5.51．判斷圖5.31中哪些圖是歐拉圖那些圖不是。對不是歐拉圖地至少要加多少條新邊才能成為歐拉圖？對是歐拉圖地,用Fleury算法求出歐拉回路。圖5.31習題1地圖解:（a）是歐拉圖。如下圖為頂點號與邊地標記,則歐拉回路為（e1,e2,e6,e10,e12,e11,e7,e8,e9,e5,e4,e3）e5e41e12e23e5e4e3(e6e9e845e9e8e7e106e117e128。（b）不是歐拉圖。需求加4條新邊才能成歐拉回路。（c）是歐拉圖。如下圖為頂點號與邊地標記,則歐拉回路為（1,2,3,4,5,6,1,8,7,10,11,7,9,1）121110119e2111011978378e46e4（d）不是歐拉圖。需求加2條新邊才能成歐拉回路。2．畫一個歐拉圖,使它具有:（1）偶數個頂點,偶數條邊。 （2）奇數個頂點,奇數條邊。（3）偶數個頂點,奇數條邊。 （4）奇數個頂點,偶數條邊。解四個圖按順序分別如下:3．在（≥）個長度大于或等于3地無公共點地環(huán)型圖之間至少加多少條邊才能使它們組成一個簡單歐拉圖。解:環(huán)形圖中每個點地度是2,要形成歐拉回路,就要使新圖是一個連通圖,并且每個點地度仍保度偶數,因此,要讓新圖是歐拉圖,則至少要加k條邊。4．證明:可以從連通圖中任意一點出發(fā),通過這個圖中每條邊恰好兩次,回到出發(fā)點。解將每條邊都增加一條平行邊,則得到一個多重圖,此多重圖地每個頂點地度數都是偶數,所以存在歐拉閉跡。在歐拉閉跡中,將通過平行邊改成第二次通過原來地邊,定理即得證。5．完全圖是歐拉圖嗎？是哈密爾頓圖嗎？完全二部圖是歐拉圖嗎？是哈密爾頓圖嗎？解 （1） Kp Kp（p≥3）為哈密爾頓圖（（v1,v2,v3,……,vp）即是一個哈密爾頓回路）。（2）因為Km,n中頂點地度數要么為m,要么為n,所以 Km,n 因為Km,n地頂點數為m+n,而任意兩點地度數之與為2m或2n或m+n。當m=n時,u,vV,有d(u)+d(v)≥p,根據P284定理4,知Km,n為哈密爾頓圖。當m≠n時,我們不妨設m＜n,此時若去掉一邊地m個頂點,則得到n個孤立點,根據P284定理5,知Km,n不是哈密爾頓圖。所以 Km,n 6．證明彼得松（Petersen）圖（圖5.10(G1)）既不是歐拉圖,也不是哈密爾頓圖。并回答,至少加幾條邊才能使它成為歐拉圖？又至少加幾條邊才能使它變成哈密爾頓圖？證明:該圖中都是奇點,所以不是歐拉圖。并且無法得到生成回路,也不是哈密爾頓圖。把原來沒有邊地頂點兩兩加邊,則至少要加5條邊才能成為歐拉圖。至少要加二條邊才能變成哈密爾頓圖,如加邊（8,9）,（10,6）,則可以得到生成回路（1,5,4,3,2,7,9,8,10,6,1）7．設是連通圖,證明:若中有橋或割點,則不是哈密爾頓圖。證:用反證法,如果圖G是哈密爾頓圖,則必存在哈密爾頓回路,,即所有結點均在一個基本回路中,此時刪除任意一個結點圖G必連通,于是它地任何點均不是割點,矛盾,即有割點地圖不是哈密爾頓圖?；?設v為割點,則p(Gv)2>|{v}|=1.根據定理,G不是哈密頓圖.(2)若G是完全圖K2(K2有橋),它顯然不是哈密頓圖.除K2外,其它地有橋連通圖均有割點.由(1),得證G不是哈密爾頓圖.8．（1）證明圖5.32(a)是半哈密爾頓圖;（2）判斷圖5.32(b)是否為哈密爾頓圖？是否為半哈密爾頓圖？解:圖(a)可以得到哈密爾頓通路,但沒有哈密爾回路,因為最上面地點地度只有1,所以是半哈密爾頓圖。圖(b)既不是哈密爾頓圖,也不是半哈密爾頓圖。9．5階完全賦權圖如圖5.33所示,求圖中地最短哈密爾頓回路。圖5.32習題8地圖圖5.33習題9地圖解:最短地哈密爾頓回路為（a,e,b,d,c,a）,權值為31.10．時,這個人能排成一列,使得中間地任何人都認識兩旁地人,而最右邊地人（最左邊地人）認識左邊（或右邊）地人。當≥時,這個人能排成一個圓圈,使得每個人都認識兩旁地人。解:設人地集合為圖地頂點集合,若兩人相識,則其間連一條邊。這樣得到地圖是人地相識圖。顯然是一個簡單圖,圖中頂點地度恰好表示該人認識地其它人地個數。利用圖,原題就抽象為下面地圖論問題:在具有個頂點簡單圖種,若,,其余地頂點都與或相鄰,則中存在哈密爾頓路或哈密爾頓回路。若與認識,則,（2）若與不認識,則對任意地頂點,當且時,與都認識。否則若不認識,即與都不認識,從而與合起來至多認識其余地個人,矛盾。于是與都認識,由地任意性可知（a）當時,,于是無論認識與否都有根據定理知中存在