平面圖、對偶圖和色數(shù)的應用探究-畢業(yè)論文

1、<p><b>　　目 錄</b></p><p><b>　　1引言1</b></p><p>　　2相關(guān)概念和定理1</p><p>　　2.1 圖的相關(guān)概念1</p><p>　　2.2 平面圖的相關(guān)概念和定理2</p><p>　　2.3 對偶圖的

2、相關(guān)概念5</p><p>　　2.4 色數(shù)的相關(guān)概念和定理6</p><p>　　2.4.1 圖中頂點的著色6</p><p>　　2.4.2 邊著色6</p><p>　　2.4.3 面著色7</p><p>　　3平面圖、對偶圖和色數(shù)的應用7</p><p>　　3.1 平面圖

3、理論的應用7</p><p>　　3.2 對偶圖理論的應用9</p><p>　　3.3 色數(shù)理論的應用10</p><p>　　3.3.1 運用圖論知識解決高中數(shù)學染色問題10</p><p>　　3.3.2 染色理論在教務工作中的兩個應用12</p><p><b>　　4結(jié)束語15</

4、b></p><p><b>　　參考文獻16</b></p><p><b>　　致謝17</b></p><p>　　平面圖、對偶圖和色數(shù)的應用探究</p><p>　　xxx本xxx班 xxx</p><p>　　指導老師 xxx</p>

5、<p>　　摘 要：平面圖、對偶圖和色數(shù)理論不僅是圖論中的重要內(nèi)容,而且在實際生活中應用廣泛。本文首先闡述了平面圖、對偶圖和色數(shù)的相關(guān)概念和定理，然后分別探究了其實際應用。其中，景區(qū)空調(diào)管道的設計和3間房子3種設施問題是典型的平面圖模型，電力電子器件的對偶變換是對偶圖理論的應用，高中數(shù)學染色問題的圖論解法和教務工作中期末考試安排和排課表問題是平面圖的色數(shù)理論的應用。</p><p>　　關(guān)鍵詞：平

6、面圖，對偶圖，色數(shù)，應用探究。</p><p>　　The application of planar graph, dual graphs and chromatic number</p><p>　　Xxxxxxxxxxxxxxx </p><p>　　Class xxxx, Mathematics Department</p><p>

7、　　Tutor: xxxxxxxx</p><p>　　Abstract: plan, dual graphs and chromatic number theory is not only the important content in graph theory, and extensive application in real life. This paper firstly explains the

8、related concept plan, dual graphs and chromatic number and theorem, and then explores its practical application. Among them,the scenic design of air conditioning pipeline and 3 houses 3 facilities is a plane graph model,

9、 dual transformation of power electronic devices is the application ofthe dual graph coloring problem</p><p>　　Key words: plan, dual graph, chromatic number, application research.</p><p><b&g

10、t;　　1引言</b></p><p>　　圖論起源于著名的哥尼斯堡七橋問題，歐拉在1736年解決了這個問題，并于1753年發(fā)現(xiàn)了歐拉公式而成為拓撲圖論的奠基人。接著中斷了170多年。1930年，當波蘭數(shù)學家C.Kuratowski和美國數(shù)學家O.Frink & P.A.Smith發(fā)現(xiàn)了平面圖判定準則后，這方面的研究才開始復蘇。20世紀70年代，我國著名數(shù)學家吳文俊教授和劉彥佩教授創(chuàng)立了平面性

11、判定的“吳-劉”方法得到了國際數(shù)學界的認可。如今，平面問題的研究成果已經(jīng)在交通網(wǎng)絡和印刷線路的設計等方面得到應用。世界上著名的“四色猜想”曾困擾了數(shù)學家們將近100年，期間人們進行了各種嘗試，平面圖的對偶圖也曾用于解決著名的四色猜想問題，但都以失敗告終，最后數(shù)學家凱尼斯.阿佩爾和沃夫?qū)?哈肯借助計算機得以解決。平面圖的染色問題是與四色問題緊密相聯(lián)的。于是產(chǎn)生了著色問題即給定一個圖，如果要求把所有頂點涂上顏色，使得相鄰頂點具有不同的顏色，

12、問最少需要幾種不同的顏色？這個問題叫做圖的點著色問題。如果對給定圖的全部邊都涂上顏色，使相鄰的邊有不同的顏色，問至少需要幾種顏色？這個問題叫做邊的著色問題，邊的著色問題可以轉(zhuǎn)化為點著色問題。由于生產(chǎn)管理、軍事</p><p><b>　　2相關(guān)概念和定理 </b></p><p><b>　　2.1圖的相關(guān)概念</b></p>&l

13、t;p>　　定義1 一個圖是一個三元組, 其中為有限非空結(jié)點集合, 稱為結(jié)點, 為有限的邊集合, 稱為邊, 是從邊集合到結(jié)點對集合上的函數(shù).  圖可簡記為:.</p><p>　　定義2 如果中邊對應V中的結(jié)點對是無序的, 稱是無向邊, 記, 稱,是的兩個端點. 如果與結(jié)點有序?qū)ο鄬? 稱是有向邊, 記, 稱為的始點, 為的終點. </p><p>　　定義3 每條

14、邊均為無向邊的圖稱為無向圖. 每條邊均為有向邊的圖稱為有向圖. 有些邊是無向邊, 有些邊是有向邊的圖稱為混合圖.</p><p>　　定義4 設, 為兩個圖(同時為無向圖或有向圖), 若且, 則稱為的子圖, 為的母圖, 記作. 若是 的子圖, 且或, 則稱為的真子圖. 若是的子圖, 且, 則稱為的生成子圖.</p><p>　　定義5 兩個圖和, 如果它們的結(jié)點間存在一一對應關(guān)系（雙射

15、）, 而且這種對應關(guān)系也反映在表示邊的結(jié)點對中(如果是有向邊則對應的結(jié)點對還保持相同的順序), 則稱這兩圖是同構(gòu)的, 記作. </p><p>　　特別申明, 本文所涉及到的圖均指無向圖.</p><p>　　2.2 平面圖的相關(guān)概念和定理</p><p>　　定義1 設圖是一個無向圖, 如果能夠把的所有結(jié)點和邊畫在平面上, 且使得任何兩條邊除了端點外沒有其他的交

16、點, 就稱是一個平面圖.</p><p>　　注意: 有些圖從表面上看有幾條邊是相交的, 但是改畫之后, 仍然是平面圖.</p><p><b>　　圖1</b></p><p><b>　　圖2</b></p><p><b>　　圖3</b></p><

17、p><b>　　圖4</b></p><p>　　定義2 設是一個連通平面圖, 由圖中的邊所包圍的區(qū)域, 在區(qū)域內(nèi)既不包含圖的結(jié)點, 也不包含圖的邊, 這樣的區(qū)域稱為的一個面, 包圍該面的諸邊所構(gòu)成的回路稱為這個面的邊界. 面的邊界的回路長度稱作該面的次數(shù), 記為.</p><p>　　定義3 路圖, 即每個點只與其相鄰的2個或1個點相連,首位不連的平面圖,

18、 如圖5. 個頂點,條邊的路圖用表示.</p><p><b>　　圖5</b></p><p>　　定義4 圈圖, 即首尾相連的路圖,如圖6. 個頂點,條邊的圈圖用表示.</p><p><b>　　圖6</b></p><p>　　定義5 輪圖, 即圈圖的中間還有一個點,該點與圈上每個點有一

19、條連線的平面圖, 如圖7. 個頂點,條邊的輪圖用表示.</p><p><b>　　圖7</b></p><p>　　定義6 完全圖, 即每兩個頂點之間都有一條邊相連的平面圖, 如圖8. 個頂點,條邊的完全圖用表示.</p><p><b>　　圖8</b></p><p>　　定義7 數(shù)圖,

20、即不包含圈的圖, 如圖9.</p><p><b>　　圖9</b></p><p>　　定理1 （歐拉定理）設有一個連通的平面圖, 共有個結(jié)點條邊和個面,則歐拉公式成立.</p><p>　　定理2 設是一個有個結(jié)點條邊的連通簡單平面圖, 若, 則.</p><p>　　推論 如果圖是連通的簡單平面圖, 若, 且

21、每個區(qū)域至少由四條邊圍成, 則有.</p><p>　　2.3對偶圖的相關(guān)概念</p><p>　　定義1 給定平面圖, 它具有面,,,, 若有圖 滿足下列條件:</p><p>　　(a) 對于圖的任何一個面, 內(nèi)部有且僅有一個結(jié)點;</p><p>　　(b) 對于圖的面和的公共邊界, 有且僅有一條邊, 使得, 且 與相交;</p&

22、gt;<p>　　(c) 當且僅當只是一個面的邊界時, 存在一個環(huán)與相交, 則稱是的對偶圖.</p><p>　　定義2 若圖的對偶圖同構(gòu)于, 則稱是自對偶圖.</p><p>　　定理1 設是連通平面圖的對偶圖, , , 和 , , 分別為和的頂點數(shù)、邊數(shù)和面數(shù), 則 (1) ; (2) ; (3) ; (4) 設的頂點位于的面中, 則.</p>

23、<p>　　定理 2 設是具有個連通分支的平面圖的對偶圖, 則(1) ;(2) ;(3);(4) 設位于的面中, 則, 其中, , , , , 同前.</p><p>　　2.4色數(shù)的相關(guān)概念和定理</p><p>　　2.4.1圖中頂點的著色</p><p>　　定義1 圖的一種著色, 即對無環(huán)圖的每個頂點涂上一種顏色, 使相鄰頂點涂不同的顏色.&

24、lt;/p><p>　　定義2 對進行著色（是可著色的）, 即能用種顏色給的頂點著色.</p><p>　　定義3 的色數(shù), 即是可著色的, 但不是可著色的.</p><p>　　定理1 當且僅當為零圖.</p><p><b>　　定理2 . </b></p><p>　　定理3 設中至少

25、含有一條邊, 則當且僅當為二部圖.</p><p>　　定理4 對于任意無向圖, 均有?. </p><p>　　定理5 圈圖著色定理: 用(為正整數(shù)) 種顏色給圈圖的頂點著色, 方法數(shù)為:, 其中, .</p><p>　　定理6 輪圖著色定理

26、: 用(為正整數(shù))種顏色給輪圖的頂點著色, 方法數(shù)為:,其中,,.</p><p>　　推論1 圈圖上一個指定的頂點染指定的顏色, 方法數(shù)為,.</p><p>　　推論2 圈圖上兩個指定相鄰的頂點染指定的不同的顏色, 方法數(shù)為, .</p><p><b>　　2.4.2邊著色</b></p><p>　　定義1

27、 對圖邊的一種著色, 即對圖的每條邊涂上一種顏色, 使相鄰的邊涂不同的顏色.</p><p>　　定義2 是邊可著色的, 即能用種顏色給的邊著色.</p><p>　　定義3 的邊色數(shù), 即是邊可著色的, 但不是邊可著色的, 也就是說最少用種顏色給的邊著色.</p><p>　　定理1 為簡單平面圖, 則??.</p><p>　　定理

28、2 若是二部圖, 則?. </p><p><b>　　2.4.3面著色</b></p><p>　　定義1 是面可著色的, 即能用種顏色給的面著色, 就稱對的面進行了著色.</p><p>　　定義2 的面色數(shù), 即是面可著色的, 但不是面可著色的, 也就是說最少用種顏色給的面著色.</p><p>　　定理

29、1 圖是面可著色的當且僅當它的對偶圖是點可著色的.</p><p>　　定理2 任何平面圖都是可著色的. </p><p>　　3平面圖、對偶圖和色數(shù)的應用</p><p>　　3.1平面圖理論的應用</p><p>　　例1 (空調(diào)管道的設計) 某娛樂中心有6個景點, 位置分布如下圖.</p><p><

30、b>　　圖10</b></p><p>　　經(jīng)考察知, 與、與、與間人流較少, 其它景點之間人流量大, 必須投資鋪設空調(diào)管道, 但要求空調(diào)管道間不能交叉. 如何設計?</p><p>　　如果把每個景點分別模型為一個點, 景點間連線, 當且僅當兩景點間要鋪設空調(diào)管道. 那么, 上面問題直接對應的圖為:</p><p><b>　　圖11&

31、lt;/b></p><p>　　于是, 問題轉(zhuǎn)化為, 能否把上圖畫在平面上, 使得邊不會相互交叉?</p><p>　　通過嘗試, 可以把上圖畫為:</p><p><b>　　圖12</b></p><p>　　于是, 鋪設方案為:</p><p><b>　　圖13</

32、b></p><p>　　例2（3間房子和3種設施問題）要求把3種公用設施(煤氣、水和電)分別用煤氣管道、水管和電線連接到3間房子里, 要求任何一根線或管道不與另外的線或管道相交, 能否辦到?</p><p>　　經(jīng)分析知,上面問題可以模型為如下偶圖:</p><p><b>　　圖14</b></p><p>　

33、　問題轉(zhuǎn)化為, 能否把上面偶圖畫在平面上, 使得邊與邊之間不會交叉?</p><p>　　該圖有6個結(jié)點, 9條邊, 此時926-4=8, 根據(jù)2.2定理2的推論知, 此圖不是平面圖, 即任何一根線或管道不與另外的線或管道相交是不可能的.</p><p>　　3.2對偶圖理論的應用</p><p>　　電力電子電路中包括很多電力電子器件, 在對電路進行對偶變換時,

34、需要將各種器件變成相應的對偶器件. 對于線性器件, 具有對偶關(guān)系的器件包括: 電阻元件與電導元件, 電容元件與電感元件, 電壓源與電流源等. 電力電子器件主要是非線性的開關(guān)器件, 非線性電力電子器件的對偶定義為: 非線性器件的對偶,就是在其理想靜態(tài)開關(guān)特性曲線上, 電壓軸與電流軸互換; 在動態(tài)特性方面, 可控開通與可控關(guān)斷呈對偶關(guān)系, 可控開通與不可控開通也呈對偶關(guān)系; 同理, 不可控開通與不可控關(guān)斷, 以及可控關(guān)斷與不可控關(guān)斷都是對偶

35、的.</p><p>　　根據(jù)定義, 表1 列出了幾種常見開關(guān)器件的對偶器件.</p><p>　　表1 常見開關(guān)器件的對偶</p><p>　　3.3色數(shù)理論的應用</p><p>　　3.3.1運用圖論知識解決高中數(shù)學染色問題</p><p>　　例1 ( 2007 天津高考題) 如圖15, 用6 種不同的顏色給四

36、個格子染色, 每個格子涂一種顏色, 要求最多使用3 種顏色且相鄰的兩個格子顏色不同, 則不同的染色方法共有_種.</p><p><b>　　圖15</b></p><p>　　常規(guī)解法: 分2 種染色與3 種染色討論, 共390 種.</p><p>　　圖論解法: 此題可以轉(zhuǎn)化為路圖的3 染色與2 染色問題, 的染色方法數(shù)為. 所以, 例

37、1 的解答為: .</p><p>　　例2 ( 2008 全國卷高考題) 如圖16, 一環(huán)形花壇分成, , , 四塊,現(xiàn)有4 種不同的花供選種, 要求在每塊里種1 種花, 且相鄰的2 塊種不同的花,則不同的種法總數(shù)為_.</p><p><b>　　圖16</b></p><p><b>　　常規(guī)解法: .</b>&l

38、t;/p><p>　　圖論解法: 此題可以先假設中間也有一種花, 問題即轉(zhuǎn)化為輪圖的的5染色問題, 最后再除以中間的5種不同染色方案即可. 所以, 例2的解答就為:</p><p><b>　　.</b></p><p>　　例3 ( 2003 廣東高考題) 如圖17, 一個地區(qū)分為5個行政區(qū)域, 現(xiàn)給地圖著色, 要求相鄰區(qū)域不得使用同一顏色. 現(xiàn)

39、有4種顏色可供選擇, 則不同的著色方法共有_種.</p><p><b>　　圖17</b></p><p>　　常規(guī)解法: 分2、4 同花與2、4 不同花兩種情況討論或是枚舉法, 共72 種.</p><p>　　圖論解法: 此題可以直接轉(zhuǎn)化為輪圖的的4染色問題, 解法為:.</p><p>　　由于點的著色與面的著色

40、是等價的, 所以我們將例1至例3中的問題轉(zhuǎn)化為圖中的圖的染色問題, 這為我們解決問題帶來了方便. 特別是遇到一些需要煩瑣的枚舉或是分多種類型進行思考的問題, 圖論方法也可以作為檢驗常規(guī)方法是否做對的一個有效工具. 由此可見, 利用圖論知識解決高考中的染色問題會帶來很大的方便, 運用圖論知識解決高中數(shù)學中的染色問題也是十分可行的.</p><p>　　3.3.2染色理論在教務工作中的兩個應用</p>

41、<p>　　例1 學院某學期開設高等數(shù)學、線性代數(shù)、概率統(tǒng)計、計算機基礎4門公共課和數(shù)學分析、高等代數(shù)、常微分方程數(shù)值解、數(shù)據(jù)庫原理及應用計算機網(wǎng)絡8門專業(yè)課, 這12門課程都將進行期末考試, 其中8名教師開課情況如表2所示:</p><p><b>　　表2：開課表</b></p><p>　　同名課程必須同時考試, 要求每位教師必須監(jiān)考自己所任課程, 且

42、每天只監(jiān)考一門科目. 假設考試教室相對充足, 且每人都希望盡早結(jié)束考試投入假期生活.問該學期的期末考試最少要幾天才能完成?</p><p>　　解 設公共課高等數(shù)學、線性代數(shù)、概率統(tǒng)計、計算機基礎的課程編號分別為，，，; 專業(yè)課數(shù)學分析、高等代數(shù)、常微分方程、復變函數(shù)、數(shù)學模型、微分方程數(shù)值解、數(shù)據(jù)庫原理及應用、計算機網(wǎng)絡的課程編號分別為1, 2, 3, 4, 5, 6, 7, 8.</p><

43、;p>　　以結(jié)點代表課程, 以課程編號作為結(jié)點標記, 構(gòu)造課程圖: 如果某兩門課程是由同一名教師開設的, 則將相應結(jié)點之間連一條邊, 得到一個圖, 使用最短的時間考試等價于對使用種顏色的染色. 對圖進行正常的頂點染色,滿足相鄰的兩點染不同的顏色, 則同色的頂點可以安排在同一天進行考試.這樣, 每位教師就不會出現(xiàn)監(jiān)考沖突的現(xiàn)象.</p><p>　　算法思想: 從頂點度數(shù)最小的頂點開始染色, 找到不與其相鄰的

44、頂點并選擇其中一個頂點進行染色, 再找與這兩個頂點都不相鄰的頂點集合, 并對其中一個頂點染色, 直到找不到為止. 再找未染色的度數(shù)小的頂點, 重復進行以上過程,直到所有頂點都已染色為止, 程序結(jié)束.</p><p>　　按照以上算法對圖染色, 于是本題的一種染色方案為點4、、5、7染紅色; 點1、、、8染綠色; 點2、3、6、染藍色. 如圖18所示:</p><p><b>　　

45、圖18：課程圖</b></p><p>　　由以上的染色結(jié)果得到=3, 即學院這學期的期末考試三天就可以完成.具體安排可以為: 第一天考高等數(shù)學、復變函數(shù)、數(shù)學模型、數(shù)據(jù)庫原理及應用; 第二天考線性代數(shù)、概率統(tǒng)計、數(shù)學分析、計算機網(wǎng)絡; 第三天考計算機基礎、高等代數(shù)、常微分方程、微分方程數(shù)值解.</p><p>　　例2 五名教師, , , , 給八個班級, , , , , ,

46、 , 授課, 教學要求可參照關(guān)聯(lián)矩陣: =, 其中中元素表示教師有班級的課程數(shù), 問: 一天至少要安排幾節(jié)課才能完成教學要求, 并排出相應的課表.</p><p>　　解 分別以=, , , , ,=, , , , , , , 為頂點構(gòu)造二布圖=,, =1時, 在和間連一條邊, 得到圖,一天安排最少的課程數(shù)實際上就是對使用種顏色的邊染色, 由2.4.2的定理2可得=Δ=5.</p><p>

47、;　　算法思想: 從圖的任一條邊染色, 然后找到一條不與其相鄰的邊進行染色, 再找與兩條邊都不相鄰的一條邊進行染色, 直到?jīng)]有可以染色的邊為止; 再找一條沒有染色的邊重復上述過程, 直到所有邊都已染色為止, 程序結(jié)束.</p><p>　　按照以上的算法對圖進行邊染色, 本題的一種染色方案為, , , 染紅色; , , , , 染黑色; , , , , 染綠色; , , , , 染藍色; , , , 染黃色. 如

48、圖19所示:</p><p><b>　　圖19：教學圖</b></p><p>　　于是一天至少安排5節(jié)課, 按照以上染色情況可排出相應的課表. 如:紅色的第一節(jié)上, 黑色的第二節(jié)上, 綠色的第三節(jié)上, 藍色的第四節(jié)上, 黃色的第五節(jié)上, 見表3:</p><p><b>　　表3: 課表安排</b></p>

49、<p><b>　　4結(jié)束語</b></p><p>　　通過收集、查閱大量的資料，本文總結(jié)歸納了平面圖、對偶圖和色數(shù)的相關(guān)概念和定理，在此基礎上分別探究了它們在實際生活中的應用。平面圖、對偶圖和色數(shù)的應用很多，本文只是簡單介紹了它們的幾個典型應用，我們主要是體會其思想和方法。</p><p><b>　　參考文獻</b></

50、p><p>　　[1] J.A.邦迪U.S.R.圖論及其應用[M].北京: 科學出版社,1984. </p><p>　　[2] 徐俊明.圖論及其應用[M]. 北京:中國科學技術(shù)大學出版社,2010.</p><p>　　[3] 史天治.平面圖與對偶原理[J].長春師范學院學報,2006,10:38-40.</p><p>　　[4] 王紹文.圖

51、的染色問題綜述[J].北京機械工業(yè)學院學報,1995,02:59-65.</p><p>　　[5] 胡作玄,王獻芬.從平面布線到瓦格納猜想[J].科學世界,2006,12:80-87.</p><p>　　[6] 馮紀先.圖論中圖的點數(shù)、區(qū)數(shù)和邊數(shù)[J].高等數(shù)學研究,2007,04:26-30.</p><p>　　[7] 陳博.染色理論在教務工作中的兩個應用[

52、J].陰山學刊.2011,25(4):34-37.</p><p>　　[8] 燕子宗,張寶琪.圖論及其應用[J].重慶科技學院學報(自然科學 版),2007,02:121-123.</p><p>　　[9] 張良震.網(wǎng)絡圖論在集成電路設計中的應用[J].安徽大學學報(自然科學版),1981,02:115-123.</p><p>　　[10] 伍小杰.對偶原理在

53、電力電子電路中的應用[J].中國礦業(yè)大學電氣電子教學學報,2007,29(5):33-37.</p><p>　　[11] 劉一真.運用圖論知識解決高中數(shù)學染色問題[J]. 華南師范大學數(shù)學學習與研究學報,2013,19:121-122.</p><p><b>　　致謝</b></p><p>　　時光如梭，短暫而有意義的四年大學生活即將結(jié)束

54、，此時看著畢業(yè)設計擺在面前，我感慨萬千。它不僅承載了我四年來的學習收獲，更讓我學會了如何求學、如何進行科學研究甚至如何做人?；叵肫鹚哪甑膶W習生活，有太多的人給我以幫助與鼓勵，教導與交流。在此我將對我的恩師們，還有所有的同學們表示我的謝意！</p><p>　　首先，衷心感謝我的恩師副教授對我的悉心教誨和指導！在跟隨老師的這段時間里，我不僅跟老師學到了許多專業(yè)知識，同時也學習到了他嚴謹求實、一絲不茍的治學態(tài)度和踏踏

55、實實、孜孜不倦的工作精神，它將使我受益終生。在此我對老師的教育和培養(yǎng)表示衷心的感謝！</p><p>　　同時我還要感謝學校領導和數(shù)學系的師生對我日常生活的關(guān)心和幫助，思想上的激勵和啟發(fā)，以及為我提供了良好的學習環(huán)境。</p><p>　　最后，我要感謝我的家人在這些年來給予我的大力支持，還要感謝在一起愉快的度過畢業(yè)論文小組的同學們，正是由于你們的幫助和支持，我才能克服一個一個的困難和疑惑