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

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

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

定理1：存在歐拉路的條件：圖是連通的，有且只有2個(gè)奇點(diǎn)。

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

歐拉圖

練習(xí)1、下圖是某展覽館的平面圖，一個(gè)參觀者能否不重復(fù)地穿過每一扇門？如果不能，請(qǐng)說(shuō)明理由。如果能，應(yīng)從哪開始走？

歐拉圖右圖中只有A，D兩個(gè)奇點(diǎn)，是一筆畫，所以答案是肯定的，應(yīng)該從A或D展室開始走。

歐拉圖

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

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

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

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

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

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

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

歐拉圖算法【參考程序】Euler.cpp#include<iostream>#include<cstring>usingnamespacestd;#definemaxn101intg[maxn][maxn];//此圖用鄰接矩陣存儲(chǔ)intdu[maxn];//記錄每個(gè)點(diǎn)的度，就是相連的邊的數(shù)目intcircuit[maxn];//用來(lái)記錄找到的歐拉路的路徑intn,e,circuitpos,i,j,x,y,start;voidfind_circuit(inti)//這個(gè)點(diǎn)深度優(yōu)先遍歷過程尋找歐拉路{intj;for(j=1;j<=n;j++)if(g[i][j]==1)//從任意一個(gè)及它相連的點(diǎn)出發(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)計(jì)每個(gè)點(diǎn)的度du[y]++;}start=1;//如果有奇點(diǎn)，就從奇點(diǎn)開始尋找，這樣找到的就是for(i=1;i<=n;i++)//歐拉路。沒有奇點(diǎn)就從任意點(diǎn)開始，if(du[i]%2==1)//這樣找到的就是歐拉回路。(因?yàn)槊恳粋€(gè)點(diǎn)都是偶點(diǎn))start=i;circuitpos=0;find_circuit(start);for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<'';cout<<endl;return0;}

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

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

鏟掉所有街道上的雪并且返回出發(fā)點(diǎn)的最短時(shí)間，精確到分種?！据斎霕永?/p>

1

00

001000010000

5000-10000500010000

5000100001000010000【輸出樣例】

3:55【注解】

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

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

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

例半哈密爾頓圖

哈密爾頓圖

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

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

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

a：說(shuō)英語(yǔ)；

b：說(shuō)英語(yǔ)或西班牙語(yǔ)；

c；說(shuō)英語(yǔ)，意大利語(yǔ)和俄語(yǔ)；

d：說(shuō)日語(yǔ)和西班牙語(yǔ)

e：說(shuō)德語(yǔ)和意大利語(yǔ)；

f：說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)；

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

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

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

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

|S|=2

W(G-S)=3

2

=

|S|

例

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

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

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

d(vi)+d(vj)=(n-1)+(n-1)=2n-2n(n3)∴Kn是H-圖至今沒有一個(gè)像歐拉圖的充要條件那樣關(guān)于哈密頓圖、半哈密頓圖的充分必要條件但能體會(huì)到是邊多還是邊少是哈密頓圖的可能大？只要圖中邊足夠多，G易為H_圖只要圖中成對(duì)節(jié)點(diǎn)度數(shù)足夠大，G易為H_圖使用簡(jiǎn)單的深度優(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ù)組模擬鄰接表存儲(chǔ)，訪問點(diǎn)i，last表示上次訪問的點(diǎn){visited[i]=true;//標(biāo)記為已經(jīng)訪問過v1[i]=true;//標(biāo)記為已在一張圖中出現(xiàn)過ans[++length]=i;//記錄下答案for(intj=1;j<=num[i];j++){if(g[i][j]==x&&g[i][j]!=last)//回到起點(diǎn)，構(gòu)成哈密爾頓環(huán){ ans[++length]=g[i][j];print();//這里說(shuō)明找到了一個(gè)環(huán)，則輸出ans數(shù)組。 length--; break; }if(!visited[g[i][j]])dfs(i,g[i][j]);//遍歷及i相關(guān)聯(lián)的所有未訪問過的頂點(diǎn)}length--;visited[i]=false;//這里是回溯過程，注意v1的值不恢復(fù)。}intmain(){memset(visited,false,sizeof(visited));memset(v1,false,sizeof(v1));for(x=1;x<=n;x++)//每一個(gè)點(diǎn)都作為起點(diǎn)嘗試訪問，因?yàn)椴皇菑娜魏我稽c(diǎn)開始都能找過整個(gè)圖的if(!v1[x])//如果點(diǎn)x不在之前曾經(jīng)被訪問過的圖里。{length=0;//定義一個(gè)ans數(shù)組存答案，length記答案的長(zhǎng)度。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背景騎士厭倦了一次又一次地看到同樣的黑白格子，于是決定去旅行。全世界.每當(dāng)騎士移動(dòng)，它是兩個(gè)正方形在一個(gè)方向和一個(gè)正方形垂直于此。一個(gè)騎士的世界是棋盤，他是生活在。我們的騎士生活在棋盤上，它的面積比普通的8×8板還小，但它還是長(zhǎng)方形的。你能幫助這個(gè)冒險(xiǎn)的騎士做旅行計(jì)劃嗎？問題發(fā)現(xiàn)騎士訪問每平方一次這樣的路徑。騎士可以開始和結(jié)束在任何一方的董事會(huì)。POJ2488-AKnight'sJourney【騎士游歷】大致題意:給出一個(gè)國(guó)際棋盤的大小，判斷馬能否不重復(fù)的走過所有格，并記錄下其中按字典序排列的第一種路徑。經(jīng)典的“騎士游歷”問題，DFS即可棋盤上的哈密爾頓回路問題在44或55的縮小了的國(guó)際象棋棋盤上，馬(Knight)不可能從某一格開始，跳過每個(gè)格子一次，并返回起點(diǎn)。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通常孩子在幼兒園喜歡吵架。這種情況讓照顧孩子的婦女。在用餐時(shí)間到來(lái)之際，當(dāng)一對(duì)夫婦肩并肩坐在一起時(shí)，一場(chǎng)激烈的沖突可能爆發(fā)。雖然沒有太多的孩子在同一個(gè)圓桌吃飯，但“敵人”或“朋友”的關(guān)系可能是非常復(fù)雜的。照顧孩子的女人遇到一個(gè)大問題?，F(xiàn)在是你幫助他們想出一個(gè)適當(dāng)?shù)淖税才诺臅r(shí)候了，沒有兩個(gè)“敵人”孩子在旁邊?，F(xiàn)在我們假設(shè)有2個(gè)**的孩子圍坐在一張大桌子旁邊，沒有一個(gè)孩子有超過1個(gè)“敵人”。POJ2488-Children'sDining題意:

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

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