|
圖論模型的建立與轉(zhuǎn)化
（作者未知） 2011/5/9
關(guān)鍵字：圖論模型、建立、轉(zhuǎn)化
摘要
本文主要寫(xiě)圖論模型的建立與轉(zhuǎn)化，共分四部分：
第一部分引言說(shuō)明了圖論建模在整個(gè)信息學(xué)競(jìng)賽中的地位，以及圖論模型與其它數(shù)學(xué)模型的異同，并指出很有研究總結(jié)圖論建模的思想、方法及技巧的必要。
第二部分提出了圖論模型建立中的兩個(gè)要點(diǎn)：對(duì)原型中的要素進(jìn)行適當(dāng)?shù)娜∩岷瓦x擇合適的理論體系，并分別舉例加以詳細(xì)分析，然后從中總結(jié)出了圖論建模的總的原則：準(zhǔn)確、清晰、簡(jiǎn)明。
第三部分主要討論了在圖論模型的轉(zhuǎn)化中，應(yīng)用得較為廣泛的兩種方法：拆分轉(zhuǎn)化和補(bǔ)集轉(zhuǎn)化，并著重分析了前者。文中把前者分為三類(lèi)：點(diǎn)邊、點(diǎn)點(diǎn)、邊邊，其中詳細(xì)分析了第二類(lèi)。
第四部分總結(jié)了全文，并指出了進(jìn)一步研究圖論模型的必要性。
目錄
一． 引言…………………………………………………………… 2
二． 圖論模型的建立……………………………………………… 2
I. 要素的取舍 …………………………………………………… 2
II. 選擇合適的理論體系 ………………………………………… 4
三． 圖論模型的轉(zhuǎn)化……………………………………………… 7
I. 拆分轉(zhuǎn)化………………………………………………………… 7
II. 補(bǔ)集轉(zhuǎn)化……………………………………………………… 10
四． 結(jié)語(yǔ)…………………………………………………………… 11
正文
一. 引言
信息學(xué)競(jìng)賽以解題為主，整個(gè)解題過(guò)程中一個(gè)重要的步驟就是數(shù)學(xué)建模，本文要討論的就是數(shù)學(xué)建模的一個(gè)分支——圖論建模。
圖論建模是指對(duì)一些客觀事物進(jìn)行抽象、化簡(jiǎn)，并用圖 來(lái)描述事物特征及內(nèi)在聯(lián)系的過(guò)程。
建立圖論模型的目的和建立其它的數(shù)學(xué)模型一樣，都是為了簡(jiǎn)化問(wèn)題，突出要點(diǎn)，以便更深入地研究問(wèn)題的本質(zhì)；它的求解目標(biāo)可以是最優(yōu)化問(wèn)題，也可以是存在性或是構(gòu)造性問(wèn)題；并且，和幾何模型、運(yùn)籌學(xué)模型一樣，在建立圖論模型的過(guò)程中，也需要用到集合、映射、函數(shù)等基本的數(shù)學(xué)概念和工具；
但圖論模型和其它模型在它們的研究方法上又有著很大的不同，例如我們可以運(yùn)用典型的圖論算法來(lái)對(duì)圖論模型進(jìn)行求解，或是根據(jù)圖論的基本理論來(lái)分析圖論模型的性質(zhì)，這些特殊的算法和理論都是其它模型所不具備的，而且在其它模型中，能用類(lèi)似于圖這種直觀的結(jié)構(gòu)來(lái)描述的也很少。
我們學(xué)習(xí)圖論，一般都是通過(guò)書(shū)籍，但書(shū)上介紹的往往只限于圖論模型的基本要素、一些圖論的相關(guān)理論和經(jīng)典算法等，至于如何建立圖論模型、如何運(yùn)用這些理論和算法、如何研究圖論問(wèn)題，都只有靠自己來(lái)理解、來(lái)領(lǐng)會(huì)，并通過(guò)實(shí)踐來(lái)驗(yàn)證這些理解，通過(guò)摸索總結(jié)來(lái)提高自己的能力。
在建立圖論模型的過(guò)程中，我們常常會(huì)遇到一些困難，例如難以建立點(diǎn)、邊、權(quán)關(guān)系，或是原型中的一些重要因素?zé)o法納入現(xiàn)有模型，或是現(xiàn)有模型雖能表示原型，卻無(wú)法求解等等。為了克服這些困難，就需要用到某些獨(dú)特的思想、方法和技巧，本文要寫(xiě)的正是我在學(xué)習(xí)、實(shí)踐中得出的這方面的一點(diǎn)認(rèn)識(shí)。
二. 圖論模型的建立
在建立模型之前，我們首先要對(duì)研究對(duì)象進(jìn)行全面的調(diào)查，將原型理想化、簡(jiǎn)單化（對(duì)于競(jìng)賽題而言，這一步大部分已經(jīng)由出題人完成了）；然后對(duì)原型進(jìn)行初步的分析，分清其中的各個(gè)要素及求解目標(biāo)，理出它們之間的聯(lián)系；下一步就是用恰當(dāng)?shù)哪Ｐ蛠?lái)描述這些要素及聯(lián)系。
.......
附件下載：點(diǎn)擊查閱全文
|