【正文】 u標(biāo)記為不可用。若不是虛邊，用并查集檢查其是否為對(duì)角線。3． 在鄰接表中找到和u相連的兩個(gè)頂點(diǎn)為v1和v2。初始化附加圖C。添加一條邊和判斷一對(duì)點(diǎn)的連通性兩種操作的均攤復(fù)雜度為O(α(n))。綜上所述，在這些桶中查找和調(diào)整一個(gè)度為2的結(jié)點(diǎn)所需的時(shí)間復(fù)雜度為O(1)。在雙向鏈表中的插入和刪除結(jié)點(diǎn)，時(shí)間復(fù)雜度都是O(1)。在每個(gè)桶中用雙向鏈接表存儲(chǔ)下不同的結(jié)點(diǎn)。由于頂點(diǎn)的度數(shù)只減少不增加，而且真正有效的度數(shù)只有1和2，所以可以建立四個(gè)桶來替代堆。這樣在保證查找復(fù)雜度仍然是O(1)的情況下，存儲(chǔ)空間比鄰接矩陣小了很多。還要用一個(gè)哈希表存下所有的邊，用于查找任意兩個(gè)點(diǎn)是否相連。值得注意的是，當(dāng)圖C中已經(jīng)有了n 1條邊時(shí)，剩下的那條邊會(huì)被判斷成對(duì)角線，但此時(shí)已經(jīng)能夠確定多邊形頂點(diǎn)的標(biāo)號(hào)序列了。如何判斷從Hi+1到Hj1的頂點(diǎn)是否已經(jīng)被刪除呢？這時(shí)構(gòu)造的附加圖C就起到了作用！若從Hi+1到Hj1的頂點(diǎn)已經(jīng)被刪除，則這些頂點(diǎn)在原多邊形上相應(yīng)的邊都已經(jīng)添加到圖C中，Hi到Hj在圖C中一定存在一條路徑。一條邊（Hi, Hj）當(dāng)且僅當(dāng)成為某個(gè)多邊形的邊時(shí)，它才有可能被移除。最后，圖C便是要求的原始多邊形。如此反復(fù)，直到圖中不存在度為2的點(diǎn)。然后按照同樣的方法把Hj從圖G’刪除，得到一個(gè)新圖……。圖G’和圖G具有同樣的性質(zhì)，因此也至少存在一個(gè)度為2的點(diǎn)，令其為Hj。也就是說，可以把Hi從圖G中刪除，若Hi1 和Hi+1之間沒有邊相連，就添加一條新邊（Hi1,Hi+1）（虛邊），得到新圖G’。而(Hi1, Hi)和(Hi, Hi+1)兩條邊都是多邊形的邊，將這兩條邊添加到一個(gè)附加圖C中（附加圖C一開始只有n個(gè)頂點(diǎn)，對(duì)應(yīng)著多邊形的頂點(diǎn)，頂點(diǎn)之間沒有邊相連）。由于圖中一定存在一個(gè)頂點(diǎn)u，它的度數(shù)為2。將以u(píng)為頂點(diǎn)的三角形從多邊形上刪除，剩下的圖形仍然是一個(gè)多邊形。 分而治之繼續(xù)挖掘圖G的性質(zhì)發(fā)現(xiàn)，由于圖G中的對(duì)角線是不相交的，那么必定存在一個(gè)頂點(diǎn)u，它的度數(shù)為2。所以總的復(fù)雜度為O(n2)。這時(shí)的新圖C便是圖G中的哈密頓回路，因此只要對(duì)其進(jìn)行一次遍歷就可以得到多邊形頂點(diǎn)的標(biāo)號(hào)序列了。如果a能夠到達(dá)圖G’中的其它點(diǎn)，那么就說明圖G’是連通的，(u, v)是多邊形的邊；否則，圖G’不連通，(u, v)是多邊形的對(duì)角線。因此，得到算法一：算法一：1．枚舉圖中的每條邊(u, v)，進(jìn)行如下判斷：將u和v兩個(gè)頂點(diǎn)從圖G中刪除得到新圖G’。 利用邊的連通性，如果一條邊是對(duì)角線，那么將對(duì)角線的兩個(gè)端點(diǎn)從圖G中刪除，圖G一定會(huì)變成兩個(gè)互不可達(dá)的連通分塊；而如果一條邊是多邊形上的邊，那么將這條邊的兩個(gè)端點(diǎn)刪除，圖G將仍然是連通的。問題的目標(biāo)就是要找到這個(gè)哈密頓回路。因此哈密頓回路上的邊都是由多邊形上的邊組成，而多邊形的邊只有n條，可知哈密頓回路也就只有一條。由此可知，在圖G中只存在惟一的一條哈密頓回路。而且十分明顯的是，圖G是一個(gè)平面圖，根據(jù)歐拉公式，圖中邊的數(shù)量級(jí)為O(n)。那么一個(gè)可能的頂點(diǎn)標(biāo)號(hào)順序?yàn)?1, 3, 5, 2, 4)。鮑比必須猜出頂點(diǎn)順（逆）時(shí)針的標(biāo)號(hào)序列，任意一個(gè)符合條件的序列即可。然后她在多邊形中畫了幾個(gè)不相交的對(duì)角線（公共點(diǎn)為頂點(diǎn)不算相交）。例二：愛麗絲和鮑勃（ACM Central European Programming Contest 2001 Problem A : Alice and Bob）題目描述：愛麗絲和鮑勃在玩一個(gè)游戲。建立模型仿佛是為算法設(shè)計(jì)搭建一個(gè)平臺(tái)，接下來的工作是在這個(gè)平臺(tái)上充分挖掘和利用原題的性質(zhì)，設(shè)計(jì)一個(gè)解決問題的好算法。圖論模型更多的是思考的一種過渡，使思路變得清晰，就像一座燈塔，指引你到成功的彼岸。新題新作，應(yīng)該創(chuàng)新思路，深入分析問題的各種性質(zhì)，將這些性質(zhì)結(jié)合在一起，從而尋找到最能體現(xiàn)問題本質(zhì)的圖論模型。正所謂“磨刀不誤砍柴功”，在設(shè)計(jì)算法之前，選擇一個(gè)正確的圖論模型往往能夠起到事半功倍的效果，不僅能降低算法設(shè)計(jì)的難度，還使設(shè)計(jì)出的算法簡單高效。正是由于回歸到問題的本質(zhì)，后面才能用DFS充分挖掘平面圖的性質(zhì)，得到最優(yōu)復(fù)雜度的算法。 小結(jié)方法一利用網(wǎng)絡(luò)流模型直接的體現(xiàn)了原題的網(wǎng)絡(luò)（有向無環(huán)）特性，解法具有一般性，但是沒有充分的體現(xiàn)出原題的平面圖性質(zhì)。因?yàn)樵}給出的圖是平面圖，根據(jù)歐拉定理，邊數(shù)|E|和域數(shù)(或者說面數(shù))|F|都是O(n)級(jí)別的。 黑色end計(jì)算上述算法的復(fù)雜度：，復(fù)雜度為O(|E|)；，并且進(jìn)行遞推求解。 pre[vh] (是黑色，說明是域的邊界上的結(jié)點(diǎn)；灰色就是極高點(diǎn)) 遞推求出右邊界的f(x) (pre回溯的邊是左邊界，是右邊界)pre[v] 223。 vvh 223。 灰色while v是u后繼結(jié)點(diǎn) do （按照從左到右的順序擴(kuò)展u的后繼結(jié)點(diǎn)v）if C[v] 是白色then beginpre[v] 223。擴(kuò)展它的父結(jié)點(diǎn)用pre記錄。每個(gè)結(jié)點(diǎn)的顏色用C[u]來記錄。 相應(yīng)的算法設(shè)計(jì)可以用DFS深度優(yōu)先遍歷實(shí)現(xiàn)平面圖中域的尋找。若x在某個(gè)最長反鏈中，那么反鏈中和x相鄰且在x左邊的邊，只有可能在域F的左邊界上。設(shè)f(x)表示在邊x左邊的平面區(qū)域中以x結(jié)尾的最長反鏈的長度。圖22123459681013121171415極高點(diǎn)圖23極低點(diǎn)。所謂的域，是由從一個(gè)點(diǎn)到另一個(gè)點(diǎn)（一個(gè)是極高點(diǎn)，一個(gè)是極低點(diǎn)）的兩條不同路徑（兩條路徑?jīng)]有公共邊）圍成的一個(gè)曲面，在這個(gè)曲面里沒有其他的點(diǎn)和邊（如圖23所示），記作F。如果用一條線將最長反鏈所對(duì)應(yīng)的邊從左到右連起來（如圖22所示），那么這條線不會(huì)與平面圖中的其它邊相交。如何求解最長的反鏈呢？事實(shí)上，這和原題給出的平面圖有很大關(guān)系，接下來，返回到原圖上繼續(xù)討論。根據(jù)Dilworth定理，問題轉(zhuǎn)化成求E中最長的反鏈的大小。在E中，有m = M。直接計(jì)算鏈的個(gè)數(shù)似乎并不容易，好在有Dilworth定理揭示了鏈與反鏈的關(guān)系，從而使得問題的目標(biāo)進(jìn)一步轉(zhuǎn)化。當(dāng)且僅當(dāng)va = ub時(shí)，有a ≤c b。令a、b為E中的兩個(gè)元素，設(shè)。 構(gòu)筑原問題的偏序集模型有了上文有關(guān)偏序集的概念，不難搭建出原問題的偏序集模型：令原圖表示的偏序集為(X, ≤)，而新構(gòu)造的偏序集為(E, ≤)。反鏈?zhǔn)荅的一個(gè)子集A，在偏序關(guān)系≤下，它的每一對(duì)元素都是不可比的。鏈：鏈?zhǔn)荅的一個(gè)子集C，在偏序關(guān)系≤下，它的每一對(duì)元素都是可比的，即C是E的一個(gè)全序子集。若偏序集中的兩個(gè)元素有a c b，那么對(duì)應(yīng)到圖中的兩個(gè)結(jié)點(diǎn)a和b，就有一條從b到a的有向邊(b, a)。若a c b，那么a和b之間連一條邊。偏序集中的元素用平面上的點(diǎn)來表示。若X是一個(gè)有限集，由偏序集的傳遞性易知，任一個(gè)偏序關(guān)系都可以用多個(gè)覆蓋關(guān)系表示出來，也就是說可以用覆蓋關(guān)系有效的表示偏序關(guān)系。令a和b是偏序集(X, ≤)中的兩個(gè)元素。集合X上的一個(gè)偏序關(guān)系R，如果使得X中的任意一對(duì)元素都是可比的，那么該偏序R就是一個(gè)全序。含偏序≤的偏序集X用(X, ≤)表示。若有a ≤ b，且a ≠ b，那么就記作a b或者b a。符合這些特性的關(guān)系叫做偏序，通常用≤標(biāo)記R。b) 對(duì)于X中的所有的x和y，只要有x R y且x ≠ y，就有，即R是反對(duì)稱的。是否存在更好的模型描述此圖呢？為了更好的揭示問題的本質(zhì)，下面引入偏序集。 以偏序集為模型題目中強(qiáng)調(diào)了每個(gè)點(diǎn)都有不同的橫縱坐標(biāo)，圖是有向無環(huán)平面圖。此算法實(shí)際效率很高，能夠迅速的通過測試數(shù)據(jù)。求最大流時(shí)，可以用樸素的增廣路算法，復(fù)雜度為O(|E|C)，C是進(jìn)行增廣的次數(shù)。然后在可行流上進(jìn)行修改，從匯點(diǎn)到源點(diǎn)求一個(gè)最大可行反向流，就得到了一個(gè)最小可行流。找到一條從s到i的路徑和一條從j到t的路徑。因此解決這個(gè)問題只需要建立一個(gè)有容量下界的網(wǎng)絡(luò)，然后求這個(gè)網(wǎng)絡(luò)的最小可行流。題目中的路徑是網(wǎng)絡(luò)中從源點(diǎn)到匯點(diǎn)的流。