歐拉圖和哈密爾頓圖

歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖歐拉路徑/回路一.歐拉回路：一般不限于簡單圖，一般指無向圖原問題：“右邊的圖中是否存在包含每條邊一次且恰好一次的回路？”原問題等價于：歐拉圖

CDABACBDEg.哥尼斯堡七橋問題<定義>歐拉回路，歐拉通路圖G的一個回路/通路,它經(jīng)過G中每條邊恰好一次，則回路/通路稱為歐拉回路/通路。定義：如果圖G中含歐拉回路，則圖G稱為歐拉圖。定義：如果圖G中僅有歐拉通路，但沒有歐拉回路，則圖G稱為半歐拉圖。

例“一筆劃”問題——G中有歐拉通路？實例上圖中，(1),(4)為歐拉圖我們定義奇點是指跟這個點相連的邊數(shù)目有奇數(shù)個的點。對于能夠一筆畫的圖，我們有以下兩個定理。

定理1：存在歐拉路的條件：圖是連通的，有且只有2個奇點。

定理2：存在歐拉回路的條件：圖是連通的，有0個奇點。兩個定理的正確性是顯而易見的，既然每條邊都要經(jīng)過一次，那么對于歐拉路，除了起點和終點外，每個點如果進入了一次，顯然一定要出去一次，顯然是偶點。對于歐拉回路，每個點進入和出去次數(shù)一定都是相等的，顯然沒有奇點。

歐拉圖

練習1、下圖是某展覽館的平面圖，一個參觀者能否不重復地穿過每一扇門？如果不能，請說明理由。如果能，應從哪開始走？

歐拉圖右圖中只有A，D兩個奇點，是一筆畫，所以答案是肯定的，應該從A或D展室開始走。

歐拉圖

例一個郵遞員投遞信件要走的街道如下左圖所示，圖中的數(shù)字表示各條街道的千米數(shù)，他從郵局出發(fā)，要走遍各街道，最后回到郵局。怎樣走才能使所走的行程最短？全程多少千米？郵局212111

怎么樣使非歐拉圖變?yōu)闅W拉圖？除去奇點！添加邊或刪除邊。怎么樣除去奇點？該題應該采用的辦法？重復某些邊（添加邊）。

歐拉圖解：圖中共有8個奇點，不可能不重復地走遍所有的路。必須在8個奇點間添加4條線，才能消除所有奇點，從而成為能從郵局出發(fā)最后返回郵局的一筆畫。當然要在距離最近的兩個奇點間添加一條連線，如圖中虛線所示，共添加4條連線，這4條連線表示要重復走的路顯然，這樣重復走的路程最短，全程34千米。走法參考下右圖(走法不唯一)。212111

歐拉圖2、右圖中每個小正方形的邊長都是100米。小明沿線段從A點到B點，不許走重復路，他最多能走多少米？該題應該采用的辦法？刪除某些邊，除去奇點對，將A、B變?yōu)榛c！

歐拉圖解：這道題大多數(shù)同學都采用試畫的方法，實際上還是用歐拉圖的判定定理來求解更合理、快捷。首先，圖中有8個奇點，在8個奇點之間至少要去掉4條線段，才能使這8個奇點變成偶點；其次，從A點出發(fā)到B點，A，B兩點必須是奇點，現(xiàn)在A，B都是偶點，必須在及A，B連接的線段中各去掉1條線段，使A，B成為奇點。所以至少要去掉6條線段，也就是最多能走1800米，走法如下圖。

歐拉圖求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對一個奇點執(zhí)行DFS，時間復雜度為O(m+n)，m為邊數(shù)，n是點數(shù)。

歐拉圖算法以下是尋找一個圖的歐拉路的算法實現(xiàn)：樣例輸入:第一行n，m，有n個點，m條邊，以下m行描述每條邊連接的兩點。551223344551樣例輸出:歐拉路或歐拉回路154321

歐拉圖算法【參考程序】Euler.cpp#include<iostream>#include<cstring>usingnamespacestd;#definemaxn101intg[maxn][maxn];//此圖用鄰接矩陣存儲intdu[maxn];//記錄每個點的度，就是相連的邊的數(shù)目intcircuit[maxn];//用來記錄找到的歐拉路的路徑intn,e,circuitpos,i,j,x,y,start;voidfind_circuit(inti)//這個點深度優(yōu)先遍歷過程尋找歐拉路{intj;for(j=1;j<=n;j++)if(g[i][j]==1)//從任意一個及它相連的點出發(fā){g[j][i]=g[i][j]=0;find_circuit(j);}circuit[++circuitpos]=i;//記錄下路徑}

歐拉圖算法intmain(){memset(g,0,sizeof(g));cin>>n>>e;for(i=1;i<=e;i++){cin>>x>>y;g[y][x]=g[x][y]=1;du[x]++;//統(tǒng)計每個點的度du[y]++;}start=1;//如果有奇點，就從奇點開始尋找，這樣找到的就是for(i=1;i<=n;i++)//歐拉路。沒有奇點就從任意點開始，if(du[i]%2==1)//這樣找到的就是歐拉回路。(因為每一個點都是偶點)start=i;circuitpos=0;find_circuit(start);for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<'';cout<<endl;return0;}

歐拉圖算法注意以上程序具有一定的局限性，對于下面這種情況它不能很好地處理：上圖具有多個歐拉回路，而本程序只能找到一個回路。讀者在遇到具體問題時，還應對程序作出相應的修改。

歐拉圖算法2、鏟雪車snow【問題描述】隨著白天越來越短夜晚越來越長，我們不得不考慮鏟雪問題了。整個城市所有的道路都是雙車道，因為城市預算的削減，整個城市只有1輛鏟雪車。鏟雪車只能把它開過的地方（車道）的雪鏟干凈，無論哪兒有雪，鏟雪車都得從停放的地方出發(fā)，游歷整個城市的街道?，F(xiàn)在的問題是：最少要花多少時間去鏟掉所有道路上的雪呢？【輸入格式】輸入數(shù)據(jù)的第1行表示鏟雪車的停放坐標（x,y），x，y為整數(shù)，單位為米。下面最多有100行，每行給出了一條街道的起點坐標和終點坐標，所有街道都是筆直的，且都是雙向一個車道。鏟雪車可以在任意交叉口、或任何街道的末尾任意轉(zhuǎn)向，包括轉(zhuǎn)U型彎。鏟雪車鏟雪時前進速度為20km/h，不鏟雪時前進速度為50km/h。保證：鏟雪車從起點一定可以到達任何街道?！据敵龈袷健?/p>

鏟掉所有街道上的雪并且返回出發(fā)點的最短時間，精確到分種。【輸入樣例】

1

00

001000010000

5000-10000500010000

5000100001000010000【輸出樣例】

3:55【注解】

3小時55分鐘3、騎馬修柵欄【問題描述】農(nóng)民John每年有很多柵欄要修理。他總是騎著馬穿過每一個柵欄并修復它破損的地方。

John是一個及其他農(nóng)民一樣懶的人。他討厭騎馬，因此從來不兩次經(jīng)過一個一個柵欄。你必須編一個程序，讀入柵欄網(wǎng)絡的描述，并計算出一條修柵欄的路徑，使每個柵欄都恰好被經(jīng)過一次。John能從任何一個頂點(即兩個柵欄的交點)開始騎馬，在任意一個頂點結(jié)束。每一個柵欄連接兩個頂點，頂點用1到500標號(雖然有的農(nóng)場并沒有500個頂點)。一個頂點上可連接任意多(>=1)個柵欄。所有柵欄都是連通的(也就是你可以從任意一個柵欄到達另外的所有柵欄)。你的程序必須輸出騎馬的路徑(用路上依次經(jīng)過的頂點號碼表示)。我們?nèi)绻演敵龅穆窂娇闯墒且粋€500進制的數(shù)，那么當存在多組解的情況下，輸出500進制表示法中最小的一個(也就是輸出第一個數(shù)較小的，如果還有多組解，輸出第二個數(shù)較小的，等等)。輸入數(shù)據(jù)保證至少有一個解?！据斎敫袷健縡ence.in第1行:一個整數(shù)F(1<=F<=1024)，表示柵欄的數(shù)目第2到F+1行:每行兩個整數(shù)i,j(1<=i,j<=500)表示這條柵欄連接i與j號頂點。【輸出格式】fence.out輸出應當有F+1行，每行一個整數(shù)，依次表示路徑經(jīng)過的頂點號。注意數(shù)據(jù)可能有多組解，但是只有上面題目要求的那一組解是認為正確的。【輸入樣例】【輸出樣例】91223344245255657461234254657哈密爾頓圖問題也是由一則游戲引入的：1859年，愛爾蘭數(shù)學家Hamilton提出的，如圖的正十二面體，以12個正五邊形為面。又稱為正則柏拉圖體。這些正五邊形的三邊相交及20個頂點的一個多面體。Hamilton用正十二面體代表地球。游戲題的內(nèi)容是：沿著正十二面體的棱尋找一條旅行路線，通過每個城市恰好一次又回到出發(fā)城市。這便是Hamilton回路問題。哈密爾頓圖

歐拉回路是指不重復地走過所有路徑的回路，而哈密爾頓環(huán)是指不重復地走過所有的點，并且最后還能回到起點的回路定義：通過圖G的每個結(jié)點一次且僅一次的環(huán)稱為哈密爾頓環(huán)。具有哈密爾頓環(huán)的圖稱為哈密爾頓圖。通過圖G的每個結(jié)點一次且僅一次的開路稱為哈密爾頓路。具有哈密爾頓路的圖稱為半哈密爾頓圖。

例半哈密爾頓圖

哈密爾頓圖

哈密爾頓圖N哈密爾頓圖周游世界的游戲——的解哈密頓圖

哈密頓圖哈密頓圖無哈密頓通路存在哈密頓通路實例在上圖中，(1),(2)是哈密頓圖;實例

已知有關(guān)人員a,b,c,d,e,f,g的有關(guān)信息

a：說英語；

b：說英語或西班牙語；

c；說英語，意大利語和俄語；

d：說日語和西班牙語

e：說德語和意大利語；

f：說法語、日語和俄語；

g：說法語和德語.試問：上述7人中是否任意兩人都能交談？

(可借助其余5人中組成的譯員鏈幫助) 解設7個人為7個結(jié)點,將兩個懂同一語言的人之間連一條邊(即他們能直接交談),這樣就得到一個簡單圖G,問題就轉(zhuǎn)化為G是否連通.如圖所示,因為G的任意兩個結(jié)點是連通的,所以G是連通圖.因此,上述7個人中任意兩個人能交談.

a：說英語；b：說英語或西班牙語；C:說英語,意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.abcdefg解一解二abcdefg英英西日法德意如果題目改為：試問這7個人應如何安排座位,才能使每個人都能及他身邊的人交談？解：用結(jié)點表示人，用邊表示連接的兩個人能說講一種語言，夠造出哈密頓圖如右上圖所示。a：說英語；b：說英語或西班牙語；c；說英語，意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語.判斷H-圖任何一個H_圖都可以看成是一個基本回路，再加上其他若干條邊H_圖的充分條件和必要條件均有，但尚無充要條件H_圖的必要條件定理：若圖G=（V，E）是哈密爾頓圖，則對于V的任意一個非空子集V1，有p（G–V1）≤|V1|

這里p（G–V1）表示從G中刪除V1（刪除S中的各結(jié)點及相關(guān)聯(lián)的邊）后所剩圖的分圖（連通分支）數(shù)。|V1|表示V1中的結(jié)點數(shù)。推論若圖G=（V，E）是半哈密爾頓圖，則對于V的任意一個非空子集V1，有p（G–V1）≤|V1|＋1.H_圖的必要條件例.有H_通路，無H_回路設S={v1,v4}，

|S|=2

W(G-S)=3

2

=

|S|

例

在圖（a）中去掉結(jié)點u以后p（G–{u}）=2，（b）中去掉結(jié)點u1和u2以后，p（G–{u1，u2}）=3，由此可以判定，這兩個圖都不是哈密爾頓圖。u1u1u1(a)(b)H_圖的必要條件但必須要說明的是滿足定理條件的不一定是哈密頓圖。如下圖著名的彼得森(Petersen)圖是滿足定理條件的，但不是哈密頓圖。利用哈密頓圖的必要條件可以用來判定某些圖不是哈密頓圖,但不便于應用。因為要檢查G的頂點集V的所有子集。H_圖的必要條件必要條件的局限性

——只能判定一個圖不是哈密爾頓圖下圖(Petersen圖)滿足上述必要條件。

Petersen圖不是H_圖。H-圖的充分條件[定理]簡單G有n個結(jié)點，n3，若G中任二點度數(shù)和大于等于n，則G有H-圖注意此為充分條件，非必要條件例.N邊形，n5任一對結(jié)點度數(shù)和=4<5但它顯然是H_圖例.Kn是完全圖

d(vi)+d(vj)=(n-1)+(n-1)=2n-2n(n3)∴Kn是H-圖至今沒有一個像歐拉圖的充要條件那樣關(guān)于哈密頓圖、半哈密頓圖的充分必要條件但能體會到是邊多還是邊少是哈密頓圖的可能大？只要圖中邊足夠多，G易為H_圖只要圖中成對節(jié)點度數(shù)足夠大，G易為H_圖使用簡單的深度優(yōu)先搜索，就能求出一張圖中所有的哈密爾頓環(huán)。下面給出一段參考程序：#include<iostream>#include<cstring>usingnamespacestd;intstart,length,x,n;boolvisited[101],v1[101];intans[101],num[101];intg[101][101];voidprint(){inti;for(i=1;i<=length;i++)cout<<''<<ans[i];cout<<endl;}voiddfs(intlast,inti)//圖用數(shù)組模擬鄰接表存儲，訪問點i，last表示上次訪問的點{visited[i]=true;//標記為已經(jīng)訪問過v1[i]=true;//標記為已在一張圖中出現(xiàn)過ans[++length]=i;//記錄下答案for(intj=1;j<=num[i];j++){if(g[i][j]==x&&g[i][j]!=last)//回到起點，構(gòu)成哈密爾頓環(huán){ ans[++length]=g[i][j];print();//這里說明找到了一個環(huán)，則輸出ans數(shù)組。 length--; break; }if(!visited[g[i][j]])dfs(i,g[i][j]);//遍歷及i相關(guān)聯(lián)的所有未訪問過的頂點}length--;visited[i]=false;//這里是回溯過程，注意v1的值不恢復。}intmain(){memset(visited,false,sizeof(visited));memset(v1,false,sizeof(v1));for(x=1;x<=n;x++)//每一個點都作為起點嘗試訪問，因為不是從任何一點開始都能找過整個圖的if(!v1[x])//如果點x不在之前曾經(jīng)被訪問過的圖里。{length=0;//定義一個ans數(shù)組存答案，length記答案的長度。dfs(x);}return0;}POJ2488-AKnight'sJourney【騎士游歷】DescriptionBackground

Theknightisgettingboredofseeingthesameblackandwhitesquaresagainandagainandhasdecidedtomakeajourney

aroundtheworld.Wheneveraknightmoves,itistwosquaresinonedirectionandonesquareperpendiculartothis.Theworldofaknightisthechessboardheislivingon.Ourknightlivesonachessboardthathasasmallerareathanaregular8*8board,butitisstillrectangular.Canyouhelpthisadventurousknighttomaketravelplans?

Problem

Findapathsuchthattheknightvisitseverysquareonce.Theknightcanstartandendonanysquareoftheboard.InputTheinputbeginswithapositiveintegerninthefirstline.Thefollowinglinescontainntestcases.Eachtestcaseconsistsofasinglelinewithtwopositiveintegerspandq,suchthat1<=p*q<=26.Thisrepresentsap*qchessboard,wherepdescribeshowmanydifferentsquarenumbers1,...,pexist,qdescribeshowmanydifferentsquarelettersexist.ThesearethefirstqlettersoftheLatinalphabet:A,...OutputTheoutputforeveryscenariobeginswithalinecontaining"Scenario#i:",whereiisthenumberofthescenariostartingat1.Thenprintasinglelinecontainingthelexicographicallyfirstpaththatvisitsallsquaresofthechessboardwithknightmovesfollowedbyanemptyline.Thepathshouldbegivenonasinglelinebyconcatenatingthenamesofthevisitedsquares.Eachsquarenameconsistsofacapitalletterfollowedbyanumber.

Ifnosuchpathexist,youshouldoutputimpossibleonasingleline.SampleInput3112343SampleOutputScenario#1:A1Scenario#2:impossibleScenario#3:A1B3C1A2B4C2A3B1C3A4B2C4背景騎士厭倦了一次又一次地看到同樣的黑白格子，于是決定去旅行。全世界.每當騎士移動，它是兩個正方形在一個方向和一個正方形垂直于此。一個騎士的世界是棋盤，他是生活在。我們的騎士生活在棋盤上，它的面積比普通的8×8板還小，但它還是長方形的。你能幫助這個冒險的騎士做旅行計劃嗎？問題發(fā)現(xiàn)騎士訪問每平方一次這樣的路徑。騎士可以開始和結(jié)束在任何一方的董事會。POJ2488-AKnight'sJourney【騎士游歷】大致題意:給出一個國際棋盤的大小，判斷馬能否不重復的走過所有格，并記錄下其中按字典序排列的第一種路徑。經(jīng)典的“騎士游歷”問題，DFS即可棋盤上的哈密爾頓回路問題在44或55的縮小了的國際象棋棋盤上，馬(Knight)不可能從某一格開始，跳過每個格子一次，并返回起點。POJ2488-Children'sDiningDescriptionUsuallychildreninkindergartenliketoquarrelwitheachother.Thissituationannoysthechild-carewomen.Forinstant,whendinertimecomes,afierceconflictmaybreakoutwhenacertaincoupleofchildrensittingsidebysidewhoarehostilewitheachother.Althoughtherearen'ttoomanychildrendiningatthesameroundtable,buttherelationshipof"enemy"or"friend"maybeverycomplex.Thechild-carewomendocomeacrossabigproblem.Nowitistimeforyoutohelpthemtofigureoutaproperarrangementofsitting,withwhichnotwo"enemy"childrenisadjacent.

Nowweassumethatthereare2*nchildrenwhositaroundabigtable,andthatnonehasmorethann-1"enemies".InputTheinputisconsistedofseveraltestblocks.Foreachblock,thefirstlinecontainstwointegersnandm(1<=n<=200,0<=m<=n(n-1)).Weusepositiveintegersfrom1to2*ntolabelthechildrendiningroundtable.Thenmlinesfollowed.Eachcontainspositiveintegersiandj(iisnotequaltoj,1<=i,j<=2*n),whichindicatethatchildiandchildjconsidereachotheras"enemy".Inainputblock,asamerelationshipisn'tgivenmorethanonce,whichmeansthatif"ij"hasbeengiven,"ji"willnotbegiven.

Therewillbeablanklinebetweeninputblocks.Andm=n=0indicatestheendofinputandthiscaseshouldn'tbeprocessed.OutputForeachtestblock,iftheproperarrangementexist,youshouldprintalinewithaproperone;otherwise,printalinewith"Nosolution!".SampleInput102212343612132435465641212131425263738484756576800SampleOutput12423116325416723458通常孩子在幼兒園喜歡吵架。這種情況讓照顧孩子的婦女。在用餐時間到來之際，當一對夫婦肩并肩坐在一起時，一場激烈的沖突可能爆發(fā)。雖然沒有太多的孩子在同一個圓桌吃飯，但“敵人”或“朋友”的關(guān)系可能是非常復雜的。照顧孩子的女人遇到一個大問題?，F(xiàn)在是你幫助他們想出一個適當?shù)淖税才诺臅r候了，沒有兩個“敵人”孩子在旁邊?，F(xiàn)在我們假設有2個**的孩子圍坐在一張大桌子旁邊，沒有一個孩子有超過1個“敵人”。POJ2488-Children'sDining題意:

有2*N個小朋友要坐在一張圓桌上吃飯,但是每兩個小朋友之間存在一種關(guān)系,即敵人或者朋友,然后需要讓你安排一個座位次序,使得相鄰的兩個小朋友都不會是敵人.假設每個人最多有N-1個敵人.如果沒有輸出"Nosolution!".思路:

如果按照題意直接建圖,每個點表示一個小朋友,小朋友之間的敵對關(guān)系表示兩個點之間有邊.問題是求小朋友圍著桌子的座次就是求圖中的一個環(huán),但是要求這個環(huán)不能包含所給出的每條邊,所有沒給出的邊卻是可以用的,也就是說本題實際上是在上面建的圖的反圖上求解一個環(huán),使得該環(huán)包含所有點.包含所有點的環(huán)一定是一條哈密頓回路,所以題目就是求所給圖的反圖上的一條哈密頓回路.題目中給了一個特殊條件,就是一共有2*N個小朋友,但是每個人最多有N-1個敵人,也就是說,每個小朋友可以選擇坐在身邊的小朋友數(shù)大于n+1,這就意味著在建立的反圖中,每個點的度數(shù)大于N+1,由定理可知,此圖一定存在哈密頓回路,所以答案不會出現(xiàn)"Nosolution!",即直接構(gòu)造哈密頓回路就可以了.參考文檔/problem?id=2488/problem?id=2438/inuyasha1027/article/details/40892407/Ash-ly/p/5452615.html/lyy289065406/article/details/664766647貨郎擔/旅行推銷員(TSP)問題：貨郎擔問題設有n個城市,城市之間有道路,道路的長度均大于或等于0,可能是∞(城市之間無交通線)。一個旅行商從某個城市出發(fā),要經(jīng)過每個城市一次且僅一次,最后回到出發(fā)的城市,問如何才能使他所走的路線最短？這就是著名的旅行商問題或貨郎擔問題。這個問題可化歸為圖論問題。貨郎擔/旅行推銷員(TSP)問題：設G=<V,E,W>為一個n階完全帶權(quán)圖Kn,各邊的權(quán)非負,且有些邊的權(quán)可能為∞。求G中一條最短的哈密頓回路,這就是貨郎擔問題的數(shù)學模型。在一個賦權(quán)的完全圖中，找出一個具有最小權(quán)的H_回路，也即回路邊的權(quán)之和最小對該賦權(quán)圖上的邊，滿足三角不等式（距離不等式）W(a,b)W(a,c)+W(c,b)例下圖(a)為完全帶權(quán)圖K4,求出其不同的哈密頓回路,并指出最短的哈密頓回路。由貨郎擔問題中不同哈密頓回路的含義可知:求哈密頓回路可從任何頂點出發(fā)。下面先求出從a點出發(fā),考慮順時針及逆時針順序的不同的哈密頓回路。