淺談圖論模型的建立與應(yīng)用【關(guān)鍵字】圖論模型、建立、轉(zhuǎn)化【摘要】在近幾年的信息學(xué)競賽中，圖論題目層出不窮。圖論作為一個新生的數(shù)學(xué)分支，相比其他數(shù)學(xué)分支來說，具有許多自有的特性。利用圖論解題，通常具有高效、簡潔的便利。有了這門工具，并不意味就能很好地解決問題，還在于我們能否熟練地識別與建立一系列的圖論模型。本文通過一些實(shí)例，簡單地介紹一下圖論建模的方法?！菊摹恳詰?yīng)用數(shù)學(xué)知識解題時，首先要通過對實(shí)際問題的分析，研究組建用以描述這個問題的數(shù)學(xué)模型。使用數(shù)學(xué)的理論和方法對模型進(jìn)行分析從而得到結(jié)果，再返回去解決現(xiàn)實(shí)的實(shí)際問題。圖論模型是一類特殊的數(shù)學(xué)模型，建立圖論模型，就是要從問題的原型中，抽取對我們有用的信息和要素，把問題抽象為點(diǎn)、邊、權(quán)的關(guān)系。經(jīng)過圖論建模之后，雜亂無章的信息變得有規(guī)可尋，要素的內(nèi)在聯(lián)系體現(xiàn)在了點(diǎn)、邊、權(quán)的關(guān)系。有不少經(jīng)典的圖論模型可以直接用特定的算法解決，一些復(fù)雜的問題，只要能認(rèn)清問題的本質(zhì)，把握問題的關(guān)鍵，建立合適的圖論模型，往往能轉(zhuǎn)化為我們熟悉的經(jīng)典問題。本文要寫的，正是我在圖論建模方面的一點(diǎn)心得與認(rèn)識。例題分析〖例題1〗HYPERLINKPlacetheRobots(ZOJ)[問題大意]有一個N*M(N,M<=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。機(jī)器人只能放在空地上。在同一行或同一列的兩個機(jī)器人，若它們之間沒有墻，則它們可以互相攻擊。問給定的棋盤，最多可以放置多少個機(jī)器人，使它們不能互相攻擊。[分析]在問題的原型中，草地，墻這些信息不是我們所關(guān)心的，我們關(guān)心的只是空地和空地之間的聯(lián)系。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點(diǎn)，有沖突的空地間連邊，我們可以得到下面的這個圖：那么，問題轉(zhuǎn)化為求圖的最大獨(dú)立集問題。眾所周知，這是NP-完全問題。看來，建立這樣的模型，沒有給問題的求解帶來任何便利，我們必須建立一個行之有效的新模型。我們將每一行，每一列被墻隔開，且包含空地的區(qū)域稱作“塊”。顯然，在每個塊之中，最多只能放一個機(jī)器人。我們把這些塊編上號，如下圖所示：把橫向塊作為X部的頂點(diǎn)，豎向塊作為Y部的頂點(diǎn)，如果兩個塊之間有公共的空地，就在它們之間連邊。這樣，我們得到了下面的二部圖：由于每條邊表示一個空地，有沖突的空地之間必有公共頂點(diǎn)，所以問題轉(zhuǎn)化為二部圖的最大匹配問題。這是圖論中的經(jīng)典問題，可以用匈牙利算法解決。[小結(jié)]比較上面的兩個模型，第一個過于簡單，沒有認(rèn)清問題的本質(zhì)；第二個則充分抓住了問題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。為什么會產(chǎn)生這樣截然不同的結(jié)果呢？其一是由于對問題分析的角度不同，第一種模型以空地為點(diǎn)，第二種模型以空地為邊；其二是由于第一種模型對原型中信息的選取不足，所建立的模型沒有保留原型中重要的性質(zhì)，而第二種模型則保留了原型中“棋盤”這個重要的性質(zhì)。由此可見，對信息的選取，是圖論建模中至關(guān)重要的一步。〖例題2〗出納員的雇傭（ACMTehran2000）[問題描述]Tehran的一家每天24小時營業(yè)的超市，需要一批出納員來滿足它的需要。超市經(jīng)理雇傭你來幫他解決他的問題——超市在每天的不同時段需要不同數(shù)目的出納員（例如：午夜時只需一小批，而下午則需要很多）來為顧客提供優(yōu)質(zhì)服務(wù)。他希望雇傭最少數(shù)目的出納員。經(jīng)理已經(jīng)提供你一天的每一小時需要出納員的最少數(shù)量——R0,R1,...,R23。R0表示從午夜到上午1：00需要出納員的最少數(shù)目，R1表示上午1：00到2：00之間需要的，等等。每一天，這些數(shù)據(jù)都是相同的。有N人申請這項工作，每個申請者I在沒24小時中，從一個特定的時刻開始連續(xù)工作恰好8小時，定義tI（0≤tI≤23）為上面提到的開始時刻。也就是說，如果第I個申請者被錄取，他（她）將從tI時刻開始連續(xù)工作8小時。你將編寫一個程序，輸入RI（I=0..23）和tI（I=1..N），它們都是非負(fù)整數(shù)，計算為滿足上述限制需要雇傭的最少出納員數(shù)目。在每一時刻可以有比對應(yīng)的RI更多的出納員在工作。輸入輸入文件的第一行為測試點(diǎn)個數(shù)（<=20）。每組測試數(shù)據(jù)的第一行為24個整數(shù)表示R0，R1，...，R23（RI≤1000）。接下來一行是N，表示申請者數(shù)目（0≤N≤1000），接下來每行包含一個整數(shù)tI（0≤tI≤23）。兩組測試數(shù)據(jù)之間沒有空行。輸出對于每個測試點(diǎn)，輸出只有一行，包含一個整數(shù)，表示需要出納員的最少數(shù)目。如果無解，你應(yīng)當(dāng)輸出“NoSolution”。[分析]初看本題，很容易使人往貪心、動態(tài)規(guī)劃或網(wǎng)絡(luò)流這些方面思考，但這些算法對于本題都無能為力。由于本題的約束條件很多，為了理清思路，我們先把題目中的約束條件用數(shù)學(xué)語言表達(dá)出來。設(shè)S[i]表示0～i時刻雇傭出納員的總數(shù)，Wi表示在時刻i開始工作的申請者的人數(shù)。那么我們可以將題目中的約束條件轉(zhuǎn)化為下面的不等式組：這樣的不等式組，不禁使我們想到了差分約束系統(tǒng)。對于每條不等式S[i]-S[j]≤K，從頂點(diǎn)ｊ向頂點(diǎn)i引一條權(quán)值為K的有向邊。我們要求的S[23]的最小值，只要求頂點(diǎn)0到頂點(diǎn)23的最短路。但是注意上面第三條不等式：它包含三個未知數(shù)，無法在圖中表示為邊的關(guān)系。思考到這一步，似乎陷入了僵局。難道本題不能用差分約束系統(tǒng)解決嗎？不，我們還需要一些轉(zhuǎn)化。退一步海闊天空，如果把S[23]作為未知數(shù)，那是肯定做不下去的。但是如果把S[23]作為已知數(shù)，那么第三條不等式就只有兩個未知數(shù)S[i],S[i+16]，我們從頂點(diǎn)i+16向頂點(diǎn)i(0≤i≤7)引一條權(quán)值為Ri-S[23]的邊。那么，該不等式組可以完全轉(zhuǎn)化為一個有向圖，未知數(shù)S[i]的解，就是圖中頂點(diǎn)0到頂點(diǎn)i的最短路。而當(dāng)圖中存在負(fù)權(quán)回路時，不等式組無解。上面的解法是把S[23]當(dāng)成了已知數(shù)，而實(shí)際上S[23]不但是未知的，而且正是我們要求的。怎么辦？我們可以用二分法枚舉S[23]的值，逐步縮小范圍，用迭代法判斷是否存在負(fù)權(quán)回路（判定可行性）。如果當(dāng)S[23]取到N仍不可行，則輸出“NoSolution”，否則輸出S[23]的最小值。時間復(fù)雜度為O(243*log2N)。[小結(jié)]本題用到了差分約束系統(tǒng)的理論，在競賽中，這樣的系統(tǒng)并不多見，但是卻可以巧妙的解決一些難題。這類題目的模型都不明顯，需要一定的思考和轉(zhuǎn)化。做這類題目，關(guān)鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最短路或最長路模型。〖例題3〗HYPERLINK貪婪之島（ZOJ）[問題大意]有N（N≤100000）張卡片，每張卡片有三種能力，每種能力的能力值分別為Ai，Bi，Ci。每張卡片可以使用其中一種能力，且每張卡片只能使用一次。現(xiàn)在需要A張卡片使用第一種能力，B張卡片使用第二種能力，C張卡片使用第三種能力（A+B+C≤100）。請計算使用哪些卡片，以及使用卡片的哪項能力，可以使相應(yīng)的能力值之和最大。[分析]最優(yōu)化問題的解法有很多種，比如動態(tài)規(guī)劃，網(wǎng)絡(luò)流等，而本題就是一個比較明顯的網(wǎng)絡(luò)流模型。網(wǎng)絡(luò)流模型中，權(quán)的類型眾多，有流量，容量，還可以有費(fèi)用。在本題中，容量可以作為選取的約束，確保解的合法性；費(fèi)用則表示選取的價值，確保解的最優(yōu)性。因此，更確切地說，本題是一個最大費(fèi)用最大流模型。認(rèn)準(zhǔn)了問題的模型之后，下一步就是構(gòu)圖了。每張卡片i用頂點(diǎn)i表示，另外加三個頂點(diǎn)P1，P2，P3，表示三種能力，還有源點(diǎn)S，匯點(diǎn)T。從源點(diǎn)分別向P1，P2，P3引一條弧，容量分別為A，B，C，費(fèi)用為0。從P1，P2，P3向頂點(diǎn)i(1≤i≤N)分別引一條弧，容量為1，費(fèi)用分別為Ai，Bi，Ci。從頂點(diǎn)i(1≤i≤N)向匯點(diǎn)引一條弧，容量為1，費(fèi)用為0。構(gòu)圖之后，求出從S到T的最大費(fèi)用最大流，再檢查流出P1，P2，P3的弧，并輸出最優(yōu)方案。這樣的算法是十分粗糙的，時間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)，時空均不可行，需要進(jìn)一步優(yōu)化。本題的卡片總數(shù)有十萬之多，而最終要選取的卡片數(shù)不超過100張。如果在構(gòu)圖之前，把沒有用的卡片先刪掉，必將大大提高效率。什么樣的卡片是沒有用的呢？先考慮第一種能力的選?。喝绻讶靠ㄆ吹谝环N能力值從大到小排序，顯然我們應(yīng)該盡量從前面選A張出來，由于每張卡片只能使用一次，所以有可能會和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是B+C張，所以實(shí)際上對我們有用的卡片只是前面的A+B+C張。同理，對于第二種和第三種能力的選取，也只需保留其能力值最大的前A+B+C張卡片。這一步可以在線性時間內(nèi)解決。這是一個既簡單又有效的方法，經(jīng)過這一步處理，保留下來的卡片數(shù)不會超過3(A+B+C)張，頂點(diǎn)數(shù)大大減少，求解最大費(fèi)用最大流的時間復(fù)雜度降為O((A+B+C)3)。至此，算法已經(jīng)優(yōu)化到了一個可以接受的地步，時間復(fù)雜度僅為O(N+(A+B+C)3)。如果還要進(jìn)一步提高效率，可以用更有效的算法刪掉多余的頂點(diǎn)。不過這樣做意義不大，而且也不是本文討論的要點(diǎn)。另外，本題還可以轉(zhuǎn)化為二部圖模型，用最佳匹配算法求解。這一步留給讀者自己思考。[小結(jié)]本題建立的是網(wǎng)絡(luò)流模型。這類模型的算法系數(shù)大，編程復(fù)雜度也大，在競賽中往往作為走投無路時的“候補(bǔ)算法”。但是，網(wǎng)絡(luò)流模型的適用性廣，一些較復(fù)雜，或者約束較多的問題，網(wǎng)絡(luò)流模型可以很好地解決，而基于網(wǎng)絡(luò)流模型的問題又比較明顯，這使得網(wǎng)絡(luò)流模型有著廣泛的應(yīng)用?！究偨Y(jié)】問題是千變?nèi)f化的，如何建立問題的圖論模型并沒有通用的準(zhǔn)則。前面的幾個例子都比較簡單，在更復(fù)雜的問題中，有時我們會感到難以建立適當(dāng)?shù)哪Ｐ?，這時，我們需要在不改變問題原型本身的性質(zhì)的前提下，對原型進(jìn)行抽象，簡化，在此基礎(chǔ)上建立合適，有效的模型。有時，我們建立了問題的一個模型之后，可能會感到難以求解，這時，我們可能需要對模型進(jìn)行修改，轉(zhuǎn)化，或者對原型進(jìn)行更深入的分析，抽取其中較關(guān)鍵的要素，建立一個易于求解的模型。這些都需要我們有豐富的經(jīng)驗(yàn)，靈活的思維以及良好的創(chuàng)造力。【參考文獻(xiàn)】吳文虎、王建德，實(shí)用算法的分析與程序設(shè)計，電子工業(yè)出版社，1998吳文虎、王建德，青少年國際和全國信息學(xué)（計算機(jī)）奧林匹克競賽指導(dǎo)——圖論的算法與程序設(shè)計，清華大學(xué)出版社，1997IOI2003國家集訓(xùn)隊第三階段討論稿【附錄】例題1原題題目來源：ZOJMonthly,October2003ContestPlacetheRobotsRobertisafamousengineer.Onedayhewasgivenataskbyhisboss.Thebackgroundofthetaskwasthefollowing:

Givenamapconsistingofsquareblocks.Therewerethreekindsofblocks:Wall,Grass,andEmpty.Hisbosswantedtoplaceasmanyrobotsaspossibleinthemap.Eachrobotheldalaserweaponwhichcouldshoottofourdirections(north,east,south,west)simultaneously.Arobothadtostayattheblockwhereitwasinitiallyplacedallthetimeandtokeepfiringallthetime.ThelaserbeamscertainlycouldpassthegridofGrass,butcouldnotpassthegridofWall.ArobotcouldonlybeplacedinanEmptyblock.Surelythebosswouldnotwanttoseeonerobothurtinganother.Inotherwords,tworobotsmustnotbeplacedinoneline(horizontallyorvertically)unlessthereisaWallbetweenthem.

NowthatyouaresuchasmartprogrammerandoneofRobert'sbestfriends,Heisaskingyoutohelphimsolvingthisproblem.Thatis,giventhedescriptionofamap,computethemaximumnumberofrobotsthatcanbeplacedinthemap.

Input

ThefirstlinecontainsanintegerT(<=11)whichisthenumberoftestcases.

Foreachtestcase,thefirstlinecontainstwointegersmandn(1<=m,n<=50)whicharetherowandcolumnsizesofthemap.Thenmlinesfollow,eachcontainsncharactersof'#','*',or'o'whichrepresentWall,Grass,andEmpty,respectively.

Output

Foreachtestcase,firstoutputthecasenumberinoneline,intheformat:"Case:id"whereidisthetestcasenumber,countingfrom1.Inthesecondlinejustoutputthemaximumnumberofrobotsthatcanbeplacedinthatmap.

SampleInput2

44

o***

*###

oo#o

***o

44

#ooo

o#oo

oo#o

***#

SampleOutputCase:1

3

Case:2

5例題3原題（有改動）題目來源：ZOJSunnyCup2003OnlineContestGreedyIslandGonandKilluaareengagedinagameofGreedyTheywouldliketoknowthemaximumsumoftheAttackvalueinAttackGroup,DefensevalueinDefenseGroupandSpecialvalueinSpecialGroup.Iftherearemultiplesolutions,choosethesolutionwiththemaximumsumofALLthepropertiesof