算法合集之《圖論模型的建立與轉(zhuǎn)化》.doc

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