算法合集之《圖論模型的建立與轉化》.doc

圖論模型的建立與轉化安徽 徐靜關鍵字：圖論模型、建立、轉化摘要本文主要寫圖論模型的建立與轉化，共分四部分：第一部分引言說明了圖論建模在整個信息學競賽中的地位，以及圖論模型與其它數(shù)學模型的異同，并指出很有研究總結圖論建模的思想、方法及技巧的必要。第二部分提出了圖論模型建立中的兩個要點：對原型中的要素進行適當?shù)娜∩岷瓦x擇合適的理論體系，并分別舉例加以詳細分析，然后從中總結出了圖論建模的總的原則：準確、清晰、簡明。第三部分主要討論了在圖論模型的轉化中，應用得較為廣泛的兩種方法：拆分轉化和補集轉化，并著重分析了前者。文中把前者分為三類：點邊、點點、邊邊，其中詳細分析了第二類。第四部分總結了全文，并指出了進一步研究圖論模型的必要性目錄一 引言2二 圖論模型的建立2I. 要素的取舍 2II. 選擇合適的理論體系 4三 圖論模型的轉化7I. 拆分轉化7II. 補集轉化10四 結語11正文一. 引言信息學競賽以解題為主，整個解題過程中一個重要的步驟就是數(shù)學建模，本文要討論的就是數(shù)學建模的一個分支圖論建模。圖論建模是指對一些客觀事物進行抽象、化簡，并用圖 在本文中，“圖”專指由若干不同頂點與連接其中某些頂點的邊所組成的圖形6，不包括一般的示意圖。來描述事物特征及內在聯(lián)系的過程。建立圖論模型的目的和建立其它的數(shù)學模型一樣，都是為了簡化問題，突出要點，以便更深入地研究問題的本質；它的求解目標可以是最優(yōu)化問題，也可以是存在性或是構造性問題；并且，和幾何模型、運籌學模型一樣，在建立圖論模型的過程中，也需要用到集合、映射、函數(shù)等基本的數(shù)學概念和工具；但圖論模型和其它模型在它們的研究方法上又有著很大的不同，例如我們可以運用典型的圖論算法來對圖論模型進行求解，或是根據(jù)圖論的基本理論來分析圖論模型的性質，這些特殊的算法和理論都是其它模型所不具備的，而且在其它模型中，能用類似于圖這種直觀的結構來描述的也很少。我們學習圖論，一般都是通過書籍，但書上介紹的往往只限于圖論模型的基本要素、一些圖論的相關理論和經典算法等，至于如何建立圖論模型、如何運用這些理論和算法、如何研究圖論問題，都只有靠自己來理解、來領會，并通過實踐來驗證這些理解，通過摸索總結來提高自己的能力。在建立圖論模型的過程中，我們常常會遇到一些困難，例如難以建立點、邊、權關系，或是原型中的一些重要因素無法納入現(xiàn)有模型，或是現(xiàn)有模型雖能表示原型，卻無法求解等等。為了克服這些困難，就需要用到某些獨特的思想、方法和技巧，本文要寫的正是我在學習、實踐中得出的這方面的一點認識。二. 圖論模型的建立在建立模型之前，我們首先要對研究對象進行全面的調查，將原型理想化、簡單化（對于競賽題而言，這一步大部分已經由出題人完成了）；然后對原型進行初步的分析，分清其中的各個要素及求解目標，理出它們之間的聯(lián)系；下一步就是用恰當?shù)哪Ｐ蛠砻枋鲞@些要素及聯(lián)系。I. 要素的取舍在用圖論模型描述研究對象時，為了更突出與求解目標息息相關的要素，降低思考的復雜度，就不可避免地要舍去部分要素。下面我們就通過例1來分析一下。【例1】 導線排布Line7：題目（文檔附件：導線排布.doc）中藍色的一段是問題描述的重點，其中涉及的要素有圓圈、N根導線、2N個端點、編號規(guī)則、導線的交叉等，求解目標是構造一種符合所給的導線交叉情況的導線排布方案。起先，我們對題目描述的導線排布并不熟悉，或許我們能夠畫出幾個無解或是多解的例子，但競賽時我們不可能花更多的時間在熟悉題目上了，這時只有盡快地把我們不熟悉的、難于思考的原型轉化成我們熟知的、便于思考的模型。先來分析求解目標：所謂的構造導線排布方案，也就是找出每根導線兩個端點的編號；而編號要滿足的條件就是導線交叉的情況。那么下一步我們就來分析一下編號與導線交叉之間的關系。記第i根導線兩端點的標號為Ai和Bi（AiB1，A2B2，A1A2（根據(jù)編號規(guī)則），不同的是(a)滿足A2B1，B1B2，(b)滿足B1A2，而(c)滿足B2B1。顯然，這是一種偏序關系（有點不確切，它只滿足反對稱和傳遞性，但不是自反的），而我們的任務就是根據(jù)這種偏序關系求得全序關系，即拓撲排序。(a) (b)(c)圖 二A1B1A2B2A1B1A2B2A1B1A2B2(a)A1A2B1B2(b)A1B1A2B2(c)A1A2B2B1圖 一123412341234我們用圖中的有向邊來表示偏序關系，若有向邊構成環(huán)，則問題無解。以上三種情況對應的有向圖如圖二所示，若兩導線交叉，則如(a)；若不交叉，則必是(b)、(c)其中之一，至于選擇哪一個，就要看它們中哪一個不會導致無解。若(b)無解，就表示圖中除了B1A2這條邊之外，還存在著一條A2B1的路徑，可能的兩種情況如圖三(1)(2)中紅色有向邊所示：(1)表示有編號大于2的導線（(1)中的導線3）與導線1交叉；(2)表示雖然它們都不與導線1交叉，但其中有選擇圖二(c)表示的。(1)(2)(3)圖 三A1B1A2B2A3B3A1B1A2B2A3B3A1B1A2B2A3B3顯然，如果情況(1)出現(xiàn)，那么選擇(b)必然無解；但如果(1)不出現(xiàn)，那么(2)就可以改成圖三(3)（即改用(b)表示導線1、3不交叉，而不是用(c)），這樣就有解了。也就是說，如果導線i與導線j(ij)不交叉，那么是否有編號大于j的導線與導線i交叉決定了(b)是否無解。類似的，我們可以分析出：如果導線i和j (ij)不交叉，那么是否存在一個序列L1m (L1=i，Lm=j)，使得導線Lk -1與導線Lk(11也可以），收益為0；經過上述轉化之后，原問題的求解目標就對應于新模型上流量為M的最大收益流 后面我們將通過“補集轉化”把最大收益流轉化為最小費用流求解。上面舉的兩個例子都是把一個點拆成兩個點，但這與“拆點為邊”是截然不同的。這里是為了把一個點具有的各種性質分離開，有幾種性質需要分離，就要拆成幾個點；而“拆點為邊”是為了使點具有邊的性質，所以總是固定地把一個點拆成兩個，并在兩個新點之間添邊。3 邊邊：這是“拆分轉化”的第3類：把一條邊拆成若干條邊。它和上面的第2類一樣，也是用于因素分離。下面就只簡單地舉例分析一下?！纠?】 容量有上下界的網(wǎng)絡流：這是一個標準的網(wǎng)絡流問題，許多書上都有該問題的解法和相關證明，所以這里就只簡述一下把原圖轉化為一般的最大流模型的過程 至于如何根據(jù)新模型上的最大流求得原圖的可行流，請見參考書籍6P68或8P165。：1 加兩個新頂點：附加源s和附加匯t，作為新的源和匯；2 把原圖上的弧(i,j)拆成三條新?。?i,j)、(s,j)、(i,t)，令Ci,j=Ci,j-Bi,j，Cs,j=Ci, t=Bi,j（Ci,j、Bi,j分別為原圖上弧(i,j)的容量上、下界，Ci,j、Cs,j和Ci, t為新弧的容量上界）；3 在原來的源和匯之間添加兩條容量為+的新弧：(s,t)和(t,s)。 (a) (b) (c)圖 十四ijb,cijc-bstbbsu5,3vt3,14,15,24,2su2vt2332ts+243333在以上三步中，第二步最為關鍵，它實現(xiàn)了把原圖上的容量上界和下界分離開的目的（如圖十四(a)所示）。圖十四(b)和(c)分別是轉化前的原圖和轉化后的新圖。更進一步地，如果點（或邊）的性質隨著時間的推移而變化著，我們也可以用類似于第2類或第3類的方式把它們拆成許多點（或邊），以表示不同時刻不同性質的點。下面我們就來看一看這類“拆分轉化”是如何應用到例6上的。【例6】 家園Homeland（CTSC 99，下面只簡述建模的過程，具體算法分析請見文檔附件：homeland.doc）：仔細分析了題意之后，不難想到建立網(wǎng)絡流模型來解決這題：1 以太空站為點；2 以往返于太空站之間太空船為邊；3 以船的最大載客量為容量上界；求解目標就是在最短時間內把固定流量（人）從源（地球）送到匯（月球）。但這里的時間不同于費用，而且邊隨著時間t的變化存在于不同的點對之間。因此按時間拆點就很有必要：把每個點都拆成t個點；把邊按照時刻的不同分配在相應的新點對間。如此一來，原本動態(tài)變化著的模型就被轉化成了靜態(tài)不變的新模型了。從上面舉的幾個例子可以看出，要分離的性質不同，拆點（邊）的方式也就隨之不同，只有準確地分析出點（邊）要表示的性質，才能轉化得到合適的模型。通過對這三類點和邊的“拆分轉化”的分析和總結不難發(fā)現(xiàn)，它們的目的和應用范圍各異，但方法都是一個“拆”字。在它們的應用上，我們完全不必拘泥于具體形式，只要是建模的需要、解題的需要，就可以按需“拆分”。只要“拆分”得當，上面的三類“拆分轉化”就可以應用得更廣。除了“拆分轉化”之外，“補集轉化”也是一種不依賴于特定模型的轉化方法。前面在例4的分析中，我們留下了一個問題：把流量固定的最大收益流轉化為最小費用流求解。這就要求對邊權進行一定的修改：改所有表示“平地”的點對之間的?。▓D十三中黑色的弧）的費用為1；改所有指向“巖石”或從這些點指出的弧（藍色的?。┑馁M用為0。這樣，原模型上每條流路徑的收益就等于P+Q-2（該路徑的長度）減去路徑上的費用的差。如此也就實現(xiàn)了把最大收益轉化為最小費用的目的。這種用某個特定值減去原權值的轉化技巧，我們就稱作權的“補集轉化”。既然有權的“補集轉化”，自然也有點和邊的“補集轉化”。點和邊的“補集轉化”是指用全集（如圖的點集、邊集或是其它集合）減去某個特定的集合（如題目給定的集合或求解目標集合等）的轉化技巧。下面我們就通過具體例子來分析一下。【例7】 最大獨立集問題及其等價問題：最大獨立集的問題描述如下：給定無向圖G(V,E)，其中AV，且E(i,j)i,jA=，求A，使得A最大。它還有兩個與之等價的問題：1 最小覆蓋問題：一般地，我們都把最大獨立集轉化為最小覆蓋集，然后根據(jù)邏輯運算定律求解（見參考書籍6P57）：令B=VA，則BV，且對于任意一條邊(i,j)E，有iB或jB，所以B是圖G(V,E)的最小覆蓋集。在這個轉化過程中就用到了點的“補集轉化”用點集V減去求解目標集合A，以得到新的目標集合B。2 最大完全子圖問題：問題描述 給定無向圖G(V,E)，其中CV，對于任意兩個點i,jC，且ij，有(i,j)E，求C，使得C最大。當我們已經知道并且能夠證明這個問題是NP完全問題（見參考書籍3P658）時，只要能夠把它轉化為最大獨立集問題求解，也就證明了后者是NP難度的，而這一步轉化中就要用到邊的“補集轉化”：令全集U=(i,j)i,jV，E=UE，則在無向圖G(V,E)中，有CV，且E(i,j) i,jC=，所以C也是圖G的最大獨立集。GG圖 十五123456123456例如圖十五G中，黑色的點構成了最大獨立集，而白色的點就是最小覆蓋集；圖G的點集與G一樣，而邊集E則是E的補集，圖中黑色的點構成了該圖的最大完全子圖的點集。從上面的例子可以看出，“補集轉化”往往都是等價轉化，而且往往都會使求解目標產生一定的變化。無論是點、邊還是權的“補集轉化”，目的都是使模型向著更便于思考和求解的方向轉化。除了上面分析的“拆分轉化”和“補集轉化”外，圖論模型的轉化方法和技巧還有很多，而且它們還可以綜合起來運用，就像在例4中一樣，經過了幾次模型的轉化，最終得到了需要的圖論模型。四. 結語本文主要分析了圖論模型建立中的兩個要點和圖論模型轉化的幾種方法技巧。在實際的建模過程中，它們是密不可分的：正確提取原型中的要素；對應到特定理論體系中相應的元素上；建立起初步的模型；然后根據(jù)需要進行適當?shù)霓D化。至此，一個適于求解的圖論模型才建立成功。在這其中，無論是對建模原則的把握，還是模型轉化方法的運用，都遵循著一點：原型本身的性質決定了模型。如果硬要把原型套到不合適的模型上去，往往反而會破壞原型的關鍵性質，這時，即使建立的模型再怎么巧妙、經典，也是經不住考驗的。圖論算法和理論十分獨特精妙，然而難于隨心所欲地運用；圖論模型的建立和轉化十分靈活，因而難于掌握。因此，對圖論模型的研究并非一朝一夕的事，需要持之以恒。本文只是我個人對圖論建模的一點淺顯認識，也只是一個開始。我相信，隨著認識的進一步加深，集思廣益，圖論模型一定有更廣闊、更精彩的應用。【附錄】本文的重點在于圖論建模，而模型的解答、解釋和檢驗等不在本文討論范圍之內。文中設計到的圖論算法和理論在下列書籍中都有詳細介紹，因此文中也只加以簡要的分析?！緟⒖紩俊? 吳文虎、王建德，實用算法的分析與程序設計，電子工業(yè)出版社，19982 任善強、雷鳴，數(shù)學模型，重慶大學出版社，19983 潘金