圖論模型在實(shí)際中的應(yīng)用課件

數(shù)學(xué)建模雷濤羅睿辭王堯汪瑜婧數(shù)學(xué)建模雷濤羅睿辭王堯汪瑜婧1數(shù)學(xué)建模的定義目前還沒有統(tǒng)一的定義數(shù)學(xué)模型是為一種特殊目的而建立的一個(gè)抽象的、簡(jiǎn)化的結(jié)構(gòu)。描述現(xiàn)實(shí)世界的一部分特征表現(xiàn)事物之間的一部分客觀聯(lián)系數(shù)學(xué)建模的定義目前還沒有統(tǒng)一的定義2數(shù)學(xué)模型的分類微分方程模型差分方程模型層次分析模型線性規(guī)劃模型動(dòng)態(tài)規(guī)劃模型圖論模型其它模型數(shù)學(xué)模型的分類微分方程模型3主要內(nèi)容建模的方法和步驟——汪瑜婧圖論模型的建立——羅睿辭圖論模型的選擇和關(guān)系的簡(jiǎn)化 ——雷濤其它數(shù)學(xué)模型舉例——王堯主要內(nèi)容建模的方法和步驟——汪瑜婧4建模的方法和步驟模型準(zhǔn)備模型假設(shè)模型的建立模型求解與分析模型檢驗(yàn)?zāi)Ｐ蛻?yīng)用建模的方法和步驟模型準(zhǔn)備5問題的提出2007CUMCMB題乘公交，看奧運(yùn)給定若干條公交線路，以及在每條公交線路中任意相鄰的兩站之間所花費(fèi)的時(shí)間。并且給定乘客在任意站點(diǎn)換乘的耗時(shí)要求給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法，求出最佳的公交線路.問題的提出2007CUMCMB題乘公交，看奧運(yùn)6模型的假設(shè)對(duì)”最優(yōu)”的理解有三個(gè)具有代表性的指標(biāo)：時(shí)間最短花費(fèi)最少最方便（換乘次數(shù)最少）不同的人群對(duì)最優(yōu)的理解不同,需要根據(jù)實(shí)際定義.可以根據(jù)需要定義代價(jià)函數(shù),三個(gè)指標(biāo)的權(quán)重不同,代價(jià)值也不同。以時(shí)間最短為例模型的假設(shè)對(duì)”最優(yōu)”的理解有三個(gè)具有代表性的指標(biāo)：7模型的建立G=(V,E)每個(gè)車站：G的頂點(diǎn)每條公交線路相鄰兩點(diǎn)的連線：G的邊邊的權(quán)重：耗費(fèi)時(shí)間點(diǎn)的權(quán)重：換乘時(shí)間并不是一個(gè)簡(jiǎn)單圖，兩點(diǎn)間可能有多條邊5937acb(8)模型的建立G=(V,E)5937acb(8)8考慮a經(jīng)過b到c的最短路徑由于有換乘的情況，只記錄任意兩點(diǎn)間的最短路徑是不夠的。并非一個(gè)標(biāo)準(zhǔn)的圖論模型與經(jīng)典最短路徑問題比較567acb(8)Min(a,b)=5Min(b,c)=3Min(a,c)=5+6=113與經(jīng)典最短路徑問題比較567acb(8)Min(a,b9轉(zhuǎn)化成標(biāo)準(zhǔn)的圖論模型每條公交線路抽象為一層層與層之間相連的頂點(diǎn)均代表同一個(gè)車站它們之間的邊(虛線)的權(quán)值為換乘花費(fèi)的時(shí)間

調(diào)用M*M次Dijkstra算法才能得到最優(yōu)解M為公交線路的總數(shù)轉(zhuǎn)化成標(biāo)準(zhǔn)的圖論模型每條公交線路抽象為一層10回顧上圖導(dǎo)致無(wú)法使用標(biāo)準(zhǔn)算法原因:Min(a,b)和Min(b,c)之間需要計(jì)算附加耗時(shí)不用換車的線路成為最佳路徑改進(jìn)的想法:一次性地處理不用換車的情況567acMin(a,b)=5Min(b,c)=3Min(a,c)=5+6=113b(8)回顧上圖567acMin(a,b)=53b(8)11模型的求解標(biāo)準(zhǔn)算法:每次選擇一個(gè)新頂點(diǎn)進(jìn)行擴(kuò)展所有頂點(diǎn)擴(kuò)展完畢即為最優(yōu)解修改后的算法每次對(duì)一個(gè)頂點(diǎn)所能選擇的所有公交線路擴(kuò)展所有不用換乘就能到達(dá)的頂點(diǎn)均在一次中處理所有頂點(diǎn)擴(kuò)展完畢即為最優(yōu)解.模型的求解標(biāo)準(zhǔn)算法:12算法描述一次將擴(kuò)展出多個(gè)頂點(diǎn),用最小值堆保存初始:起點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)S入堆；并賦予標(biāo)志信息Time(S)=0取堆頂,對(duì)此定點(diǎn),逐一枚舉所有不用換乘就能到達(dá)的頂點(diǎn),更新堆中對(duì)應(yīng)點(diǎn)的標(biāo)志信息.不斷重復(fù)取堆頂?shù)倪^程,直到取出的頂點(diǎn)為最終目標(biāo)TTime(T)即為所求算法描述一次將擴(kuò)展出多個(gè)頂點(diǎn),用最小值堆保存13舉例說明算法步驟3245132abcdefg1298159206119225考慮頂點(diǎn)b到頂點(diǎn)g的路徑舉例說明算法步驟3245132abcdefg1298159214問題重述加入步行的因素,即任意兩個(gè)車站之間人都可能通過步行到達(dá),并給出步行的時(shí)間代價(jià).問題重述加入步行的因素,即任意兩個(gè)車站之間人都可能通過步行到15由于每?jī)牲c(diǎn)之間均有步行路徑,每次擴(kuò)展都將涉及到所有頂點(diǎn),復(fù)雜度增加不少改進(jìn)的辦法

預(yù)處理找到兩個(gè)相鄰頂點(diǎn)之間路徑的最小值,如果它加上兩個(gè)頂點(diǎn)的權(quán)值之后后,仍然小于一些其它的路徑,就可以將其它路徑刪除.這樣至少 可以刪除不少步行路徑考慮實(shí)際情況,可設(shè)定步行時(shí)間的上限.567ac加入步行的路徑并給定權(quán)值20由于每?jī)牲c(diǎn)之間均有步行路徑,每次擴(kuò)展都將涉及到所有頂點(diǎn),復(fù)雜16算法的總結(jié)關(guān)鍵在于如何解決換乘的耗時(shí)擴(kuò)展節(jié)點(diǎn)的策略與經(jīng)典算法不同算法實(shí)際用到了分支界限法的思想類似于回溯法，但是求解的目標(biāo)不同。目標(biāo)：找到使目標(biāo)函數(shù)取極值的解。算法的總結(jié)關(guān)鍵在于如何解決換乘的耗時(shí)17分支界限法思想以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹從一個(gè)點(diǎn)開始，每次以一定的策略擴(kuò)展一些結(jié)點(diǎn)。每一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有子結(jié)點(diǎn)，并從活節(jié)點(diǎn)中移除。在產(chǎn)生的子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)被舍棄，其余的加入活結(jié)點(diǎn)表中。分支界限法思想以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜18選擇擴(kuò)展的節(jié)點(diǎn)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)可能有不同的方式隊(duì)列式分支限界法：先入先出的原則優(yōu)先隊(duì)列式分支限界法：選擇優(yōu)先級(jí)最高的節(jié)點(diǎn)進(jìn)行擴(kuò)展最大效益問題：最大值堆最小耗費(fèi)問題：最小值堆選擇擴(kuò)展的節(jié)點(diǎn)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)可能有不同的方式19一個(gè)簡(jiǎn)單的例子印刷電路板將布線區(qū)域劃分為n×m個(gè)方格陣列精確的電路板布線問題要求確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。布線時(shí)電路只能沿直線或直角布線。為避免線路相交，已布線方格做上封閉標(biāo)記，其他線路布線不允許穿過封閉區(qū)域。一個(gè)簡(jiǎn)單的例子印刷電路板將布線區(qū)域劃分為n×m個(gè)方格陣列20abab2111a11b11a11b222211a12212b22211a12212b22332211a12212b2332211a12212b232432211a12212b23432211a12212b2342532211a12212b234532211a12212b23452632211a12212b23456632211a12212b2345662732211a12212b2345676732211a12212b234567672832211a12212b2348567867832211a12212b2348567867829建模步驟的總結(jié)模型的準(zhǔn)備提出問題，搜集數(shù)據(jù)。模型的假設(shè)根據(jù)實(shí)際情況，提出合理的假設(shè)簡(jiǎn)化問題。模型的建立根據(jù)所作的假設(shè)分析對(duì)象的因果關(guān)系，利用對(duì)象的內(nèi)在規(guī)律和適當(dāng)?shù)臄?shù)學(xué)工具，構(gòu)造各個(gè)量間的等式關(guān)系或其它數(shù)學(xué)結(jié)構(gòu)。建模步驟的總結(jié)模型的準(zhǔn)備30建模步驟的總結(jié)模型的分析與求解已建立的模型是否有標(biāo)準(zhǔn)解法轉(zhuǎn)化成標(biāo)準(zhǔn)模型對(duì)已有的標(biāo)準(zhǔn)解法修改，以適應(yīng)模型的求解模型的檢驗(yàn)靈敏性，魯棒性模型的應(yīng)用建模步驟的總結(jié)模型的分析與求解31圖論模型的引入 引例 現(xiàn)有6個(gè)人，任意兩人之間或者相互認(rèn)識(shí)，或者相互不認(rèn)識(shí)，證明這6個(gè)人中，或者有3個(gè)人彼此都認(rèn)識(shí)，或者有3個(gè)人彼此不認(rèn)識(shí)圖論模型的引入 引例32思路一只有6個(gè)人，人數(shù)非常少，可以枚舉任意兩人之間的關(guān)系，然后判斷每一種情況是否符合題意。如果所有情況都滿足，則命題成立。雖然只有6個(gè)人，但是這樣做的時(shí)間復(fù)雜度可不低，枚舉次數(shù)為215

只能借助計(jì)算機(jī)了。。。有沒有人可以直接證明的辦法呢？思路一只有6個(gè)人，人數(shù)非常少，可以枚舉任意兩人之間的關(guān)系，然33思路二有了圖論這個(gè)強(qiáng)大的工具我們還是像往常一樣，以人為頂點(diǎn)，關(guān)系為邊，建圖但是為了以后的直觀，這里圖的建立有一點(diǎn)小小的不同：如果兩個(gè)人之間相互認(rèn)識(shí)，則在這兩個(gè)人(頂點(diǎn))間連一條紅色邊，如果兩個(gè)人不認(rèn)識(shí)，則在這兩個(gè)人(頂點(diǎn))間連一條藍(lán)色邊(下面會(huì)看到這樣做的好處)那么這樣我們就得到了一個(gè)由紅邊和藍(lán)邊組成的6階完全圖我們實(shí)際上要證明的就是這個(gè)圖中或者存在一個(gè)紅三角形(認(rèn)識(shí))，或者存在一個(gè)藍(lán)三角形(不認(rèn)識(shí))思路二有了圖論這個(gè)強(qiáng)大的工具34任取一個(gè)頂點(diǎn)v0，由它連出5條邊到其它的頂點(diǎn)，這五條邊只有紅色和藍(lán)色兩種根據(jù)抽屜原理，肯定有一種顏色的邊有3條或3條以上,不妨設(shè)為紅色viv0vjvk如果vi,vj,vk之間的邊都是藍(lán)邊，則圖中存在一個(gè)藍(lán)三角形如果至少有1條為紅邊，那么它總會(huì)與v0發(fā)出的兩條紅邊組成一個(gè)紅三角形。這樣就證明了這個(gè)命題任取一個(gè)頂點(diǎn)v0，由它連出5條邊到其它的頂點(diǎn)，這五條邊只有紅35現(xiàn)有n根長(zhǎng)度不同的小木棍，每根木棍數(shù)量無(wú)限，取出一些小木棍可以拼出一根長(zhǎng)度為這些小木棍長(zhǎng)度之和的木棍?，F(xiàn)在要求最小的整數(shù)k，使得長(zhǎng)度大于等于k的木棍都能夠被給出的n根小木棍拼出。例如，現(xiàn)在有3根小木棍，長(zhǎng)度分別3,5,7它們可以拼出長(zhǎng)度為3,5,6,7,8,9,10,11,12,13……的木棍，看上去5就是答案，怎么證明呢？可以考慮把能夠拼出來(lái)的木棍長(zhǎng)度x根據(jù)模3的結(jié)果分成3類(0,1,2)對(duì)于xmod3=0,3能夠拼出來(lái)，那么6,9,12……等等模3為0的數(shù)都可以被拼出來(lái)對(duì)于xmod3=1，7能被拼出來(lái)，那么7,10,13……等等都能被拼出來(lái)對(duì)于xmod3=2，5能被拼出來(lái)，那么8,11,14……等等都能被拼出來(lái)也就是說，5確實(shí)是我們要求的答案這個(gè)題看上去似乎毫無(wú)頭緒，那就先看看簡(jiǎn)單的情況吧！現(xiàn)有n根長(zhǎng)度不同的小木棍，每根木棍數(shù)量無(wú)限，取出一些小木棍可36根據(jù)上面的證明，可以發(fā)現(xiàn)一種思路，不妨把上述結(jié)果推廣一下：設(shè)n根木棍的長(zhǎng)度為L(zhǎng)1,L2,…,Ln,不妨設(shè)L1為所有木棍中最短的現(xiàn)在把能夠拼出的木棍長(zhǎng)度根據(jù)模L1的結(jié)果分為L(zhǎng)1類(0,1…L1-1),若某一類中的數(shù)模L1的結(jié)果為i,則它們組成的集合為Si顯然，如果存在一個(gè)集合Si為空，則問題無(wú)解現(xiàn)在考慮所有集合都不為空的情況：設(shè)每個(gè)集合的最小元為b0,b1…bl1-1(集合不為空，肯定存在最小元)那么如何去求題目要求的k呢？根據(jù)上面的證明，可以發(fā)現(xiàn)一種思路，不妨把上述結(jié)果推廣一下：37考慮這樣一個(gè)值：k’=max{bn}-L1，1<=n<L1,(b0=0,不考慮)L1是最短的木棍，故k’>0.⑴k’不屬于任何Si集合,否則與k’是某個(gè)S中最小元。即k’不能被小木棍拼出。⑵對(duì)任意L>k’,設(shè)LSp，L+L1>max{bn}>=bp故L>bp-L1而Lbp(modp)所以L>=bp，所以L一定能夠被拼出由以上兩點(diǎn)可知，k’一定是不能被拼出的木棍長(zhǎng)度中的最大值那么k’+1就是我們要求的答案！考慮這樣一個(gè)值：k’=max{bn}-L1，1<=n<38還剩下最后一步：求b0,b1,b2…bl1-1,也就是每個(gè)集合中的最小元事實(shí)上，每一個(gè)能被拼出來(lái)的木棍長(zhǎng)度x，都是從0開始，用已有的小木棍拼出來(lái)的。那么就可以把集合的編號(hào)看做頂點(diǎn)，小木棍的長(zhǎng)度看邊的長(zhǎng)度，建立一個(gè)圖。對(duì)于每個(gè)點(diǎn)i(集合i)，都連出n條邊，長(zhǎng)度為L(zhǎng)1,L2…Ln。對(duì)于長(zhǎng)度為L(zhǎng)k的邊，連向編號(hào)為(i+Lk)modL1的頂點(diǎn)。對(duì)于從頂點(diǎn)i到j(luò)的一條長(zhǎng)度為L(zhǎng)的路徑，表示集合i中的一個(gè)數(shù)加上L后得到的數(shù)屬于集合j。對(duì)于任意一個(gè)能拼出來(lái)的數(shù)x(設(shè)xmodL1=p),根據(jù)上面的建圖規(guī)則，x一定是點(diǎn)0到p的一條路徑的長(zhǎng)度。反過來(lái)，0到p的所有路徑長(zhǎng)度都屬于Sp。所以，可以得出結(jié)論：Sp中的最小元其實(shí)就是頂點(diǎn)0到頂點(diǎn)p的最短路徑長(zhǎng)度。有了這個(gè)結(jié)論，我們就可以很容易的求出序列{bn}了至此，這個(gè)問題也就被完美的解決還剩下最后一步：求b0,b1,b2…bl1-1,也就是每個(gè)集39數(shù)學(xué)建模——模型的選擇、關(guān)系的簡(jiǎn)化很多問題都是通過建立圖論模型解決的圖論中常見的模型有序列、樹、各種圖如何有效選擇數(shù)學(xué)模型，簡(jiǎn)化原問題中元素之間的關(guān)系是數(shù)學(xué)建模的關(guān)鍵數(shù)學(xué)建?！Ｐ偷倪x擇、關(guān)系的簡(jiǎn)化很多問題都是通過建立圖論模40題目坐船問題（改編自湖南省信息學(xué)省隊(duì)選拔賽試題）北大有n個(gè)學(xué)生去公園劃船：一只船最多坐2個(gè)人；出于娛樂目的，大家決定同船的2個(gè)人要么同姓要么同名；每個(gè)人都必須上船，且不能有腳踏多只船的情況問最少需要幾只船。題目坐船問題（改編自湖南省信息學(xué)省隊(duì)選拔賽試題）41例子6個(gè)同學(xué)：姚金宇，李金宇，姚峰宏，陳峰宏姚金宇姚峰宏陳峰宏李金宇姚金宇李金宇陳峰宏姚峰宏例子6個(gè)同學(xué)：姚金宇，李金宇，姚峰宏，陳峰宏姚金宇姚峰宏42例子4個(gè)同學(xué)：陳峰宏，囧峰宏，羅睿辭，廖葉子羅睿辭同學(xué)想和廖葉子同學(xué)坐同一船是不行的，因?yàn)樗麄儾煌膊煌贞惙搴陣宸搴炅_睿辭廖葉子陳峰宏囧峰宏羅睿辭廖葉子例子4個(gè)同學(xué)：陳峰宏，囧峰宏，羅睿辭，廖葉子陳峰宏囧峰宏43將每一同學(xué)視為一元素，元素之間的關(guān)系為同名或者同姓構(gòu)圖是很自然的思路：2名同學(xué)同名或者同姓就連一條邊一條邊就代表了一種坐船的搭配方式用最少的邊覆蓋圖中的點(diǎn)——一般圖的最小邊覆蓋問題一般圖最大匹配問題，算法復(fù)雜，實(shí)現(xiàn)麻煩。建模姚金宇李金宇姚峰宏陳峰宏陳峰宏囧峰宏羅睿辭廖葉子將每一同學(xué)視為一元素，元素之間的關(guān)系為同名或者同姓建模姚金宇44建模圖是本題信息最充分、最自然的模型，但其中數(shù)據(jù)關(guān)系存在很多冗余，沒有充分利用原題的條件單獨(dú)看同名、同姓這2種關(guān)系，它們都是等價(jià)關(guān)系，具有傳遞性那么換一種模型構(gòu)造如何？把圖轉(zhuǎn)換成樹來(lái)考慮建模圖是本題信息最充分、最自然的模型，但其中數(shù)據(jù)關(guān)系存在很多45建模對(duì)于原圖中的每一個(gè)連通分量，一定可以轉(zhuǎn)換成一棵二叉樹樹中一個(gè)結(jié)點(diǎn)的左孩子跟其同姓；一個(gè)結(jié)點(diǎn)的右孩子跟其同名。證明用反證法羅睿辭羅貫中羅納爾多廖睿辭羅睿辭羅貫中羅納爾多廖睿辭建模對(duì)于原圖中的每一個(gè)連通分量，一定可以轉(zhuǎn)換成一棵二叉樹羅睿46問題的解決含有n個(gè)點(diǎn)的連通分量，至少需要(n+1)div2只船使用貪心法，一定可以構(gòu)造出一個(gè)只需(n+1)div2只船的解羅睿辭羅貫中羅納爾多廖睿辭羅納爾多是羅貫中的獨(dú)生子，去掉他們2個(gè)，樹依然連通羅睿辭廖睿辭廖睿辭依然是羅睿辭的獨(dú)生子，將它們分成一組羅貫中羅納爾多羅睿辭廖睿辭得到了一個(gè)最優(yōu)解問題的解決含有n個(gè)點(diǎn)的連通分量，至少需要(n+1)div47貪心構(gòu)造1、若葉子結(jié)點(diǎn)是父親的獨(dú)生子，則刪去它們2個(gè)，樹依然保持性質(zhì)2、若父親結(jié)點(diǎn)有2個(gè)孩子重復(fù)以上步驟直至樹為空或者只剩一個(gè)結(jié)點(diǎn)為止貪心構(gòu)造1、若葉子結(jié)點(diǎn)是父親的獨(dú)生子，則刪去它們2個(gè)，樹依然48貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云49貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云50貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云51陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例52貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云53貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云54小結(jié)通過無(wú)向圖到二叉樹的轉(zhuǎn)化，將一個(gè)復(fù)雜的匹配問題用簡(jiǎn)單貪心解決了建模是一個(gè)去粗取精的過程，要盡可能利用對(duì)我們有利的信息，而忽略那些與我們目標(biāo)無(wú)關(guān)的信息LCA與RMQ問題之間相互轉(zhuǎn)化，就是樹形模型與序列模型相互輔助的經(jīng)典例子希望本例會(huì)對(duì)同學(xué)們今后的解題有所幫助！小結(jié)通過無(wú)向圖到二叉樹的轉(zhuǎn)化，將一個(gè)復(fù)雜的匹配問題用簡(jiǎn)單貪心55

數(shù)學(xué)建?？雌饋?lái)，總會(huì)讓人覺得是一種很抽象的概念如果把概念簡(jiǎn)單一點(diǎn)，再通俗一點(diǎn)，大概就是把一些實(shí)際中碰到的問題抽象化，化簡(jiǎn)成類似的數(shù)學(xué)問題，然后就可以用我們已經(jīng)知道的方法和工具來(lái)求解但是其實(shí)數(shù)學(xué)建模還有很多更深刻的含義和價(jià)值，不過已經(jīng)超出我可以講述的很清楚的范圍了其它數(shù)學(xué)模型舉例數(shù)學(xué)建?？雌饋?lái)，總會(huì)讓人覺得是一種很抽象的概念如果把概念簡(jiǎn)56

而且，其實(shí)計(jì)算機(jī)實(shí)現(xiàn)的問題建模不見得就一定局限于圖論或者其他離散數(shù)學(xué)問題的這些方面還有很多方面都是可以利用數(shù)學(xué)建模思想和方法的而有些時(shí)候，其實(shí)都是我們不經(jīng)意間已經(jīng)在數(shù)學(xué)建模了，只是自己沒有在意而已。比如說數(shù)論中有關(guān)于素?cái)?shù)篩選和測(cè)試，因式分解算法，一些特殊的進(jìn)位制問題，快速冪取模等問題其實(shí)都可以用數(shù)學(xué)建模的方式來(lái)求解。而且，其實(shí)計(jì)算機(jī)實(shí)現(xiàn)的問題建模不見得就一定局限于圖論或者其57

下面我要討論的是關(guān)于組合計(jì)數(shù)問題的一些討論。組合數(shù)學(xué)的問題隨處可見，他的歷史淵源扎根于古老的數(shù)學(xué)娛樂和游戲之中，而在當(dāng)今社會(huì)中同樣發(fā)揮著重要的作用。簡(jiǎn)單的說，組合數(shù)學(xué)研究一個(gè)集合的物體進(jìn)行滿足一些規(guī)則的排列。具體的說來(lái)，組合數(shù)學(xué)往往研究的是這些排列的存在性，計(jì)數(shù)和分類。有時(shí)候還需要構(gòu)造出滿足條件的一個(gè)或者多個(gè)最優(yōu)的排列。排列組合，容斥原理等都是這一方面的理論。其中很多時(shí)候都會(huì)廣泛的運(yùn)用到遞推和生成函數(shù)，這也是建立數(shù)學(xué)模型并用計(jì)算機(jī)求解的優(yōu)勢(shì)所在之一。下面我要討論的是關(guān)于組合計(jì)數(shù)問題的一些討論。組合數(shù)學(xué)的問題58E1E2E3棋盤多項(xiàng)式E1E2E3棋59問題簡(jiǎn)述一個(gè)國(guó)際象棋棋盤，若兩個(gè)主教互相不攻擊，則當(dāng)且僅當(dāng)他們不處于同一條斜線上。我們可以討論在一個(gè)n×n的棋盤上放k個(gè)互相不攻擊的主教有多少種方法？例如，當(dāng)n=8，k=6時(shí)，即在8×8的棋盤上放6個(gè)主教有5599888種方法問題簡(jiǎn)述一個(gè)國(guó)際象棋棋盤，若兩個(gè)主教互相不攻擊，則當(dāng)且僅當(dāng)他60布棋方案數(shù)Rk(C)設(shè)C是一個(gè)棋盤，Rk(C)表示把k個(gè)相同的棋子布到C中，且任意兩個(gè)棋子不能處于同一行或者同一列的方案數(shù)（把斜線換成行和列），并規(guī)定對(duì)于任意的棋盤C有R0(C)=1。棋盤多項(xiàng)式設(shè)C是棋盤，則R(C)=∑Rk(C)×xk叫做他的棋盤多項(xiàng)式布棋方案數(shù)Rk(C)設(shè)C是一個(gè)棋盤，Rk(C)表示把k個(gè)相同61可以證明步棋方案數(shù)Rk(C)具有下面的性質(zhì):1)對(duì)于任意的棋盤C和正整數(shù)k，如果k大于C中方格的總數(shù)，則Rk(C)=0；2)R1(C)等于C中的方格數(shù)3)設(shè)C1和C2是2個(gè)棋盤，如果C1經(jīng)過旋轉(zhuǎn)或者翻轉(zhuǎn)變成了C2,則Rk(C1)=Rk(C2)4)設(shè)Ci是從棋盤C中去掉指定的方格所在的行和列以后剩下的棋盤，C1是從棋盤C中去掉指定的方格以后剩下的棋盤，則有Rk(C)=Rk-1(Ci)+Rk(C1)（k>=1）5)設(shè)棋盤C由兩個(gè)子棋盤C1和C2組成，如果C1和C2的步棋方案是互相獨(dú)立的，則有Rk(C)=∑Ri(C1)*Rk-i(C2)可以證明步棋方案數(shù)Rk(C)1)對(duì)于任意的棋盤C和正整數(shù)k62顯然，在上述定義中當(dāng)k大于棋盤的格子數(shù)時(shí)Rk(C)=0，所以R(C)一般只有有限項(xiàng)。例如對(duì)于R(AT)=R0(AT)+R1(AT)×x+R2(AT)×x2=1+2x+x2At顯然，在上述定義中當(dāng)k大于棋盤的格子數(shù)時(shí)Rk(C)=0，所以63根據(jù)Rk(C)的性質(zhì)不難得到R(C)的性質(zhì)R(C)=xR(Ci)+R(C1)R(C)=R(C1)*R(C2)此后我們就用這兩條性質(zhì)計(jì)算棋盤多項(xiàng)式根據(jù)Rk(C)的性質(zhì)不難得到R(C)的性質(zhì)R(C)=xR(64另外，我們回到剛才的問題我們可以注意到白格主教和黑格主教是不會(huì)互相攻擊的所以問題可以化簡(jiǎn)為白格放i(i<=k)個(gè)棋子和黑格放k-i個(gè)棋子分別處理而且處理方法是一樣的。為了直觀，我們把白格從棋盤中抽出小方格和棋盤都順時(shí)針旋轉(zhuǎn)45度，再壓縮，黑格同樣最后都可以化建成左圖情況我們希望知道的，就是在這樣的一個(gè)棋盤上放置i(ork-i)各兩兩不同行不同列的象有多少種放法另外，我們回到剛才的問題65由于行列關(guān)系是相對(duì)的，所以行列順序不重要，所以把寬度小的行放在寬度大的行之上，將圖轉(zhuǎn)換成這樣的情況。然后，我們就可以繼續(xù)編寫算法來(lái)把這種有序的圖形遞歸化簡(jiǎn)，然后利用棋盤多項(xiàng)式的規(guī)則化簡(jiǎn)最后我們可以從第x的k次方項(xiàng)的系數(shù)得知放置k個(gè)互不攻擊的象的方法數(shù)有多少了由于行列關(guān)系是相對(duì)的，所以行列順序不重要，所以把寬度小的行放66數(shù)學(xué)建模雷濤羅睿辭王堯汪瑜婧數(shù)學(xué)建模雷濤羅睿辭王堯汪瑜婧67數(shù)學(xué)建模的定義目前還沒有統(tǒng)一的定義數(shù)學(xué)模型是為一種特殊目的而建立的一個(gè)抽象的、簡(jiǎn)化的結(jié)構(gòu)。描述現(xiàn)實(shí)世界的一部分特征表現(xiàn)事物之間的一部分客觀聯(lián)系數(shù)學(xué)建模的定義目前還沒有統(tǒng)一的定義68數(shù)學(xué)模型的分類微分方程模型差分方程模型層次分析模型線性規(guī)劃模型動(dòng)態(tài)規(guī)劃模型圖論模型其它模型數(shù)學(xué)模型的分類微分方程模型69主要內(nèi)容建模的方法和步驟——汪瑜婧圖論模型的建立——羅睿辭圖論模型的選擇和關(guān)系的簡(jiǎn)化 ——雷濤其它數(shù)學(xué)模型舉例——王堯主要內(nèi)容建模的方法和步驟——汪瑜婧70建模的方法和步驟模型準(zhǔn)備模型假設(shè)模型的建立模型求解與分析模型檢驗(yàn)?zāi)Ｐ蛻?yīng)用建模的方法和步驟模型準(zhǔn)備71問題的提出2007CUMCMB題乘公交，看奧運(yùn)給定若干條公交線路，以及在每條公交線路中任意相鄰的兩站之間所花費(fèi)的時(shí)間。并且給定乘客在任意站點(diǎn)換乘的耗時(shí)要求給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法，求出最佳的公交線路.問題的提出2007CUMCMB題乘公交，看奧運(yùn)72模型的假設(shè)對(duì)”最優(yōu)”的理解有三個(gè)具有代表性的指標(biāo)：時(shí)間最短花費(fèi)最少最方便（換乘次數(shù)最少）不同的人群對(duì)最優(yōu)的理解不同,需要根據(jù)實(shí)際定義.可以根據(jù)需要定義代價(jià)函數(shù),三個(gè)指標(biāo)的權(quán)重不同,代價(jià)值也不同。以時(shí)間最短為例模型的假設(shè)對(duì)”最優(yōu)”的理解有三個(gè)具有代表性的指標(biāo)：73模型的建立G=(V,E)每個(gè)車站：G的頂點(diǎn)每條公交線路相鄰兩點(diǎn)的連線：G的邊邊的權(quán)重：耗費(fèi)時(shí)間點(diǎn)的權(quán)重：換乘時(shí)間并不是一個(gè)簡(jiǎn)單圖，兩點(diǎn)間可能有多條邊5937acb(8)模型的建立G=(V,E)5937acb(8)74考慮a經(jīng)過b到c的最短路徑由于有換乘的情況，只記錄任意兩點(diǎn)間的最短路徑是不夠的。并非一個(gè)標(biāo)準(zhǔn)的圖論模型與經(jīng)典最短路徑問題比較567acb(8)Min(a,b)=5Min(b,c)=3Min(a,c)=5+6=113與經(jīng)典最短路徑問題比較567acb(8)Min(a,b75轉(zhuǎn)化成標(biāo)準(zhǔn)的圖論模型每條公交線路抽象為一層層與層之間相連的頂點(diǎn)均代表同一個(gè)車站它們之間的邊(虛線)的權(quán)值為換乘花費(fèi)的時(shí)間

調(diào)用M*M次Dijkstra算法才能得到最優(yōu)解M為公交線路的總數(shù)轉(zhuǎn)化成標(biāo)準(zhǔn)的圖論模型每條公交線路抽象為一層76回顧上圖導(dǎo)致無(wú)法使用標(biāo)準(zhǔn)算法原因:Min(a,b)和Min(b,c)之間需要計(jì)算附加耗時(shí)不用換車的線路成為最佳路徑改進(jìn)的想法:一次性地處理不用換車的情況567acMin(a,b)=5Min(b,c)=3Min(a,c)=5+6=113b(8)回顧上圖567acMin(a,b)=53b(8)77模型的求解標(biāo)準(zhǔn)算法:每次選擇一個(gè)新頂點(diǎn)進(jìn)行擴(kuò)展所有頂點(diǎn)擴(kuò)展完畢即為最優(yōu)解修改后的算法每次對(duì)一個(gè)頂點(diǎn)所能選擇的所有公交線路擴(kuò)展所有不用換乘就能到達(dá)的頂點(diǎn)均在一次中處理所有頂點(diǎn)擴(kuò)展完畢即為最優(yōu)解.模型的求解標(biāo)準(zhǔn)算法:78算法描述一次將擴(kuò)展出多個(gè)頂點(diǎn),用最小值堆保存初始:起點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)S入堆；并賦予標(biāo)志信息Time(S)=0取堆頂,對(duì)此定點(diǎn),逐一枚舉所有不用換乘就能到達(dá)的頂點(diǎn),更新堆中對(duì)應(yīng)點(diǎn)的標(biāo)志信息.不斷重復(fù)取堆頂?shù)倪^程,直到取出的頂點(diǎn)為最終目標(biāo)TTime(T)即為所求算法描述一次將擴(kuò)展出多個(gè)頂點(diǎn),用最小值堆保存79舉例說明算法步驟3245132abcdefg1298159206119225考慮頂點(diǎn)b到頂點(diǎn)g的路徑舉例說明算法步驟3245132abcdefg1298159280問題重述加入步行的因素,即任意兩個(gè)車站之間人都可能通過步行到達(dá),并給出步行的時(shí)間代價(jià).問題重述加入步行的因素,即任意兩個(gè)車站之間人都可能通過步行到81由于每?jī)牲c(diǎn)之間均有步行路徑,每次擴(kuò)展都將涉及到所有頂點(diǎn),復(fù)雜度增加不少改進(jìn)的辦法

預(yù)處理找到兩個(gè)相鄰頂點(diǎn)之間路徑的最小值,如果它加上兩個(gè)頂點(diǎn)的權(quán)值之后后,仍然小于一些其它的路徑,就可以將其它路徑刪除.這樣至少 可以刪除不少步行路徑考慮實(shí)際情況,可設(shè)定步行時(shí)間的上限.567ac加入步行的路徑并給定權(quán)值20由于每?jī)牲c(diǎn)之間均有步行路徑,每次擴(kuò)展都將涉及到所有頂點(diǎn),復(fù)雜82算法的總結(jié)關(guān)鍵在于如何解決換乘的耗時(shí)擴(kuò)展節(jié)點(diǎn)的策略與經(jīng)典算法不同算法實(shí)際用到了分支界限法的思想類似于回溯法，但是求解的目標(biāo)不同。目標(biāo)：找到使目標(biāo)函數(shù)取極值的解。算法的總結(jié)關(guān)鍵在于如何解決換乘的耗時(shí)83分支界限法思想以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹從一個(gè)點(diǎn)開始，每次以一定的策略擴(kuò)展一些結(jié)點(diǎn)。每一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有子結(jié)點(diǎn)，并從活節(jié)點(diǎn)中移除。在產(chǎn)生的子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)被舍棄，其余的加入活結(jié)點(diǎn)表中。分支界限法思想以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜84選擇擴(kuò)展的節(jié)點(diǎn)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)可能有不同的方式隊(duì)列式分支限界法：先入先出的原則優(yōu)先隊(duì)列式分支限界法：選擇優(yōu)先級(jí)最高的節(jié)點(diǎn)進(jìn)行擴(kuò)展最大效益問題：最大值堆最小耗費(fèi)問題：最小值堆選擇擴(kuò)展的節(jié)點(diǎn)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)可能有不同的方式85一個(gè)簡(jiǎn)單的例子印刷電路板將布線區(qū)域劃分為n×m個(gè)方格陣列精確的電路板布線問題要求確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。布線時(shí)電路只能沿直線或直角布線。為避免線路相交，已布線方格做上封閉標(biāo)記，其他線路布線不允許穿過封閉區(qū)域。一個(gè)簡(jiǎn)單的例子印刷電路板將布線區(qū)域劃分為n×m個(gè)方格陣列86abab8711a11b11a11b882211a12212b22211a12212b28932211a12212b2332211a12212b239032211a12212b23432211a12212b2349132211a12212b234532211a12212b23459232211a12212b23456632211a12212b2345669332211a12212b2345676732211a12212b234567679432211a12212b2348567867832211a12212b2348567867895建模步驟的總結(jié)模型的準(zhǔn)備提出問題，搜集數(shù)據(jù)。模型的假設(shè)根據(jù)實(shí)際情況，提出合理的假設(shè)簡(jiǎn)化問題。模型的建立根據(jù)所作的假設(shè)分析對(duì)象的因果關(guān)系，利用對(duì)象的內(nèi)在規(guī)律和適當(dāng)?shù)臄?shù)學(xué)工具，構(gòu)造各個(gè)量間的等式關(guān)系或其它數(shù)學(xué)結(jié)構(gòu)。建模步驟的總結(jié)模型的準(zhǔn)備96建模步驟的總結(jié)模型的分析與求解已建立的模型是否有標(biāo)準(zhǔn)解法轉(zhuǎn)化成標(biāo)準(zhǔn)模型對(duì)已有的標(biāo)準(zhǔn)解法修改，以適應(yīng)模型的求解模型的檢驗(yàn)靈敏性，魯棒性模型的應(yīng)用建模步驟的總結(jié)模型的分析與求解97圖論模型的引入 引例 現(xiàn)有6個(gè)人，任意兩人之間或者相互認(rèn)識(shí)，或者相互不認(rèn)識(shí)，證明這6個(gè)人中，或者有3個(gè)人彼此都認(rèn)識(shí)，或者有3個(gè)人彼此不認(rèn)識(shí)圖論模型的引入 引例98思路一只有6個(gè)人，人數(shù)非常少，可以枚舉任意兩人之間的關(guān)系，然后判斷每一種情況是否符合題意。如果所有情況都滿足，則命題成立。雖然只有6個(gè)人，但是這樣做的時(shí)間復(fù)雜度可不低，枚舉次數(shù)為215

只能借助計(jì)算機(jī)了。。。有沒有人可以直接證明的辦法呢？思路一只有6個(gè)人，人數(shù)非常少，可以枚舉任意兩人之間的關(guān)系，然99思路二有了圖論這個(gè)強(qiáng)大的工具我們還是像往常一樣，以人為頂點(diǎn)，關(guān)系為邊，建圖但是為了以后的直觀，這里圖的建立有一點(diǎn)小小的不同：如果兩個(gè)人之間相互認(rèn)識(shí)，則在這兩個(gè)人(頂點(diǎn))間連一條紅色邊，如果兩個(gè)人不認(rèn)識(shí)，則在這兩個(gè)人(頂點(diǎn))間連一條藍(lán)色邊(下面會(huì)看到這樣做的好處)那么這樣我們就得到了一個(gè)由紅邊和藍(lán)邊組成的6階完全圖我們實(shí)際上要證明的就是這個(gè)圖中或者存在一個(gè)紅三角形(認(rèn)識(shí))，或者存在一個(gè)藍(lán)三角形(不認(rèn)識(shí))思路二有了圖論這個(gè)強(qiáng)大的工具100任取一個(gè)頂點(diǎn)v0，由它連出5條邊到其它的頂點(diǎn)，這五條邊只有紅色和藍(lán)色兩種根據(jù)抽屜原理，肯定有一種顏色的邊有3條或3條以上,不妨設(shè)為紅色viv0vjvk如果vi,vj,vk之間的邊都是藍(lán)邊，則圖中存在一個(gè)藍(lán)三角形如果至少有1條為紅邊，那么它總會(huì)與v0發(fā)出的兩條紅邊組成一個(gè)紅三角形。這樣就證明了這個(gè)命題任取一個(gè)頂點(diǎn)v0，由它連出5條邊到其它的頂點(diǎn)，這五條邊只有紅101現(xiàn)有n根長(zhǎng)度不同的小木棍，每根木棍數(shù)量無(wú)限，取出一些小木棍可以拼出一根長(zhǎng)度為這些小木棍長(zhǎng)度之和的木棍?，F(xiàn)在要求最小的整數(shù)k，使得長(zhǎng)度大于等于k的木棍都能夠被給出的n根小木棍拼出。例如，現(xiàn)在有3根小木棍，長(zhǎng)度分別3,5,7它們可以拼出長(zhǎng)度為3,5,6,7,8,9,10,11,12,13……的木棍，看上去5就是答案，怎么證明呢？可以考慮把能夠拼出來(lái)的木棍長(zhǎng)度x根據(jù)模3的結(jié)果分成3類(0,1,2)對(duì)于xmod3=0,3能夠拼出來(lái)，那么6,9,12……等等模3為0的數(shù)都可以被拼出來(lái)對(duì)于xmod3=1，7能被拼出來(lái)，那么7,10,13……等等都能被拼出來(lái)對(duì)于xmod3=2，5能被拼出來(lái)，那么8,11,14……等等都能被拼出來(lái)也就是說，5確實(shí)是我們要求的答案這個(gè)題看上去似乎毫無(wú)頭緒，那就先看看簡(jiǎn)單的情況吧！現(xiàn)有n根長(zhǎng)度不同的小木棍，每根木棍數(shù)量無(wú)限，取出一些小木棍可102根據(jù)上面的證明，可以發(fā)現(xiàn)一種思路，不妨把上述結(jié)果推廣一下：設(shè)n根木棍的長(zhǎng)度為L(zhǎng)1,L2,…,Ln,不妨設(shè)L1為所有木棍中最短的現(xiàn)在把能夠拼出的木棍長(zhǎng)度根據(jù)模L1的結(jié)果分為L(zhǎng)1類(0,1…L1-1),若某一類中的數(shù)模L1的結(jié)果為i,則它們組成的集合為Si顯然，如果存在一個(gè)集合Si為空，則問題無(wú)解現(xiàn)在考慮所有集合都不為空的情況：設(shè)每個(gè)集合的最小元為b0,b1…bl1-1(集合不為空，肯定存在最小元)那么如何去求題目要求的k呢？根據(jù)上面的證明，可以發(fā)現(xiàn)一種思路，不妨把上述結(jié)果推廣一下：103考慮這樣一個(gè)值：k’=max{bn}-L1，1<=n<L1,(b0=0,不考慮)L1是最短的木棍，故k’>0.⑴k’不屬于任何Si集合,否則與k’是某個(gè)S中最小元。即k’不能被小木棍拼出。⑵對(duì)任意L>k’,設(shè)LSp，L+L1>max{bn}>=bp故L>bp-L1而Lbp(modp)所以L>=bp，所以L一定能夠被拼出由以上兩點(diǎn)可知，k’一定是不能被拼出的木棍長(zhǎng)度中的最大值那么k’+1就是我們要求的答案！考慮這樣一個(gè)值：k’=max{bn}-L1，1<=n<104還剩下最后一步：求b0,b1,b2…bl1-1,也就是每個(gè)集合中的最小元事實(shí)上，每一個(gè)能被拼出來(lái)的木棍長(zhǎng)度x，都是從0開始，用已有的小木棍拼出來(lái)的。那么就可以把集合的編號(hào)看做頂點(diǎn)，小木棍的長(zhǎng)度看邊的長(zhǎng)度，建立一個(gè)圖。對(duì)于每個(gè)點(diǎn)i(集合i)，都連出n條邊，長(zhǎng)度為L(zhǎng)1,L2…Ln。對(duì)于長(zhǎng)度為L(zhǎng)k的邊，連向編號(hào)為(i+Lk)modL1的頂點(diǎn)。對(duì)于從頂點(diǎn)i到j(luò)的一條長(zhǎng)度為L(zhǎng)的路徑，表示集合i中的一個(gè)數(shù)加上L后得到的數(shù)屬于集合j。對(duì)于任意一個(gè)能拼出來(lái)的數(shù)x(設(shè)xmodL1=p),根據(jù)上面的建圖規(guī)則，x一定是點(diǎn)0到p的一條路徑的長(zhǎng)度。反過來(lái)，0到p的所有路徑長(zhǎng)度都屬于Sp。所以，可以得出結(jié)論：Sp中的最小元其實(shí)就是頂點(diǎn)0到頂點(diǎn)p的最短路徑長(zhǎng)度。有了這個(gè)結(jié)論，我們就可以很容易的求出序列{bn}了至此，這個(gè)問題也就被完美的解決還剩下最后一步：求b0,b1,b2…bl1-1,也就是每個(gè)集105數(shù)學(xué)建?！Ｐ偷倪x擇、關(guān)系的簡(jiǎn)化很多問題都是通過建立圖論模型解決的圖論中常見的模型有序列、樹、各種圖如何有效選擇數(shù)學(xué)模型，簡(jiǎn)化原問題中元素之間的關(guān)系是數(shù)學(xué)建模的關(guān)鍵數(shù)學(xué)建模——模型的選擇、關(guān)系的簡(jiǎn)化很多問題都是通過建立圖論模106題目坐船問題（改編自湖南省信息學(xué)省隊(duì)選拔賽試題）北大有n個(gè)學(xué)生去公園劃船：一只船最多坐2個(gè)人；出于娛樂目的，大家決定同船的2個(gè)人要么同姓要么同名；每個(gè)人都必須上船，且不能有腳踏多只船的情況問最少需要幾只船。題目坐船問題（改編自湖南省信息學(xué)省隊(duì)選拔賽試題）107例子6個(gè)同學(xué)：姚金宇，李金宇，姚峰宏，陳峰宏姚金宇姚峰宏陳峰宏李金宇姚金宇李金宇陳峰宏姚峰宏例子6個(gè)同學(xué)：姚金宇，李金宇，姚峰宏，陳峰宏姚金宇姚峰宏108例子4個(gè)同學(xué)：陳峰宏，囧峰宏，羅睿辭，廖葉子羅睿辭同學(xué)想和廖葉子同學(xué)坐同一船是不行的，因?yàn)樗麄儾煌膊煌贞惙搴陣宸搴炅_睿辭廖葉子陳峰宏囧峰宏羅睿辭廖葉子例子4個(gè)同學(xué)：陳峰宏，囧峰宏，羅睿辭，廖葉子陳峰宏囧峰宏109將每一同學(xué)視為一元素，元素之間的關(guān)系為同名或者同姓構(gòu)圖是很自然的思路：2名同學(xué)同名或者同姓就連一條邊一條邊就代表了一種坐船的搭配方式用最少的邊覆蓋圖中的點(diǎn)——一般圖的最小邊覆蓋問題一般圖最大匹配問題，算法復(fù)雜，實(shí)現(xiàn)麻煩。建模姚金宇李金宇姚峰宏陳峰宏陳峰宏囧峰宏羅睿辭廖葉子將每一同學(xué)視為一元素，元素之間的關(guān)系為同名或者同姓建模姚金宇110建模圖是本題信息最充分、最自然的模型，但其中數(shù)據(jù)關(guān)系存在很多冗余，沒有充分利用原題的條件單獨(dú)看同名、同姓這2種關(guān)系，它們都是等價(jià)關(guān)系，具有傳遞性那么換一種模型構(gòu)造如何？把圖轉(zhuǎn)換成樹來(lái)考慮建模圖是本題信息最充分、最自然的模型，但其中數(shù)據(jù)關(guān)系存在很多111建模對(duì)于原圖中的每一個(gè)連通分量，一定可以轉(zhuǎn)換成一棵二叉樹樹中一個(gè)結(jié)點(diǎn)的左孩子跟其同姓；一個(gè)結(jié)點(diǎn)的右孩子跟其同名。證明用反證法羅睿辭羅貫中羅納爾多廖睿辭羅睿辭羅貫中羅納爾多廖睿辭建模對(duì)于原圖中的每一個(gè)連通分量，一定可以轉(zhuǎn)換成一棵二叉樹羅睿112問題的解決含有n個(gè)點(diǎn)的連通分量，至少需要(n+1)div2只船使用貪心法，一定可以構(gòu)造出一個(gè)只需(n+1)div2只船的解羅睿辭羅貫中羅納爾多廖睿辭羅納爾多是羅貫中的獨(dú)生子，去掉他們2個(gè)，樹依然連通羅睿辭廖睿辭廖睿辭依然是羅睿辭的獨(dú)生子，將它們分成一組羅貫中羅納爾多羅睿辭廖睿辭得到了一個(gè)最優(yōu)解問題的解決含有n個(gè)點(diǎn)的連通分量，至少需要(n+1)div113貪心構(gòu)造1、若葉子結(jié)點(diǎn)是父親的獨(dú)生子，則刪去它們2個(gè)，樹依然保持性質(zhì)2、若父親結(jié)點(diǎn)有2個(gè)孩子重復(fù)以上步驟直至樹為空或者只剩一個(gè)結(jié)點(diǎn)為止貪心構(gòu)造1、若葉子結(jié)點(diǎn)是父親的獨(dú)生子，則刪去它們2個(gè)，樹依然114貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云115貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云116貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云117陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例118貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云119貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云120小結(jié)通過無(wú)向圖到二叉樹的轉(zhuǎn)化，將一個(gè)復(fù)雜的匹配問題用簡(jiǎn)單貪心解決了建模是一個(gè)去粗取精的過程，要盡可能利用對(duì)我們有利的信息，而忽略那些與我們目標(biāo)無(wú)關(guān)的信息LCA與RMQ問題之間相互轉(zhuǎn)化，就是樹形模型與序列模型相互輔助的經(jīng)典例子希望本例會(huì)對(duì)同學(xué)們今后的解題有所幫助！小結(jié)通過無(wú)向圖到二叉樹的轉(zhuǎn)化，將一個(gè)復(fù)雜的匹配問題用簡(jiǎn)單貪心121

數(shù)學(xué)建?？雌饋?lái)，總會(huì)讓人覺得是一種很抽象的概念如果把概念簡(jiǎn)單一點(diǎn)，再通俗一點(diǎn)，大概就是把一些實(shí)際中碰到的問題抽象化，化簡(jiǎn)成類似的數(shù)學(xué)問題，然后就可以用我們已經(jīng)知道的方法和工具來(lái)求解但是其實(shí)數(shù)學(xué)建模還有很多更深刻的含義和價(jià)值，不過已經(jīng)超出我可以講述的很清楚的范圍了其它數(shù)學(xué)模型舉例數(shù)學(xué)建?？雌饋?lái)，總會(huì)讓人覺得是一種很抽象的概念如果把概念簡(jiǎn)122

而且，其實(shí)計(jì)算機(jī)實(shí)現(xiàn)的問題建模不見得就一定局限于圖論或者其他離散數(shù)學(xué)問題的這些方面還有很多方面都是可以利用數(shù)學(xué)建模思想和方法的而有些時(shí)候，其實(shí)都是我們不經(jīng)意間已經(jīng)在數(shù)學(xué)建模了，