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

《平面圖、對偶圖和色數(shù)的應(yīng)用探究-畢業(yè)論》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、目錄1引言12相關(guān)概念和定理12.1圖的相關(guān)概念12.2平面圖的相關(guān)概念和定理22.3對偶圖的相關(guān)概念52.4色數(shù)的相關(guān)概念和定理62.4.1圖中頂點的著色62.4.2邊著色62.4.3面著色73平面圖、對偶圖和色數(shù)的應(yīng)用73.1平面圖理論的應(yīng)用73.2對偶圖理論的應(yīng)用93.3色數(shù)理論的應(yīng)用103.3.1運用圖論知識解決高中數(shù)學(xué)染色問題103.3.2染色理論在教務(wù)工作中的兩個應(yīng)用124結(jié)束語15參考文獻16致謝17ii平面圖、對偶圖和色數(shù)的應(yīng)用探究xxx本xxx班xxx指導(dǎo)老師xxx摘要：平面圖、對偶圖和色數(shù)理論不僅是圖論中的重要內(nèi)容,而且在實際生活中應(yīng)用

2、廣泛。本文首先闡述了平面圖、對偶圖和色數(shù)的相關(guān)概念和定理，然后分別探究了其實際應(yīng)用。其中，景區(qū)空調(diào)管道的設(shè)計和3間房子3種設(shè)施問題是典型的平面圖模型，電力電子器件的對偶變換是對偶圖理論的應(yīng)用，高中數(shù)學(xué)染色問題的圖論解法和教務(wù)工作中期末考試安排和排課表問題是平面圖的色數(shù)理論的應(yīng)用。關(guān)鍵詞：平面圖，對偶圖，色數(shù)，應(yīng)用探究。Theapplicationofplanargraph,dualgraphsandchromaticnumberXxxxxxxxxxxxxxxClassxxxx,MathematicsDepartmentTutor:xxxxxxxxAbstr

3、act:plan,dualgraphsandchromaticnumbertheoryisnotonlytheimportantcontentingraphtheory,andextensiveapplicationinreallife.Thispaperfirstlyexplainstherelatedconceptplan,dualgraphsandchromaticnumberandtheorem,andthenexploresitspracticalapplication.Amongthem,thescenicdesignofairconditio

4、ningpipelineand3houses3facilitiesisaplanegraphmodel,dualtransformationofpowerelectronicdevicesistheapplicationofthedualgraphcoloringproblem,highschoolmathematicsgraphtheorymethodandthefinalexamscheduleadministrationworkandthetimetableproblemistheapplicationofchromaticnumberofplana

5、rgraphsoftheory.Keywords:plan,dualgraph,chromaticnumber,applicationresearch.ii1引言圖論起源于著名的哥尼斯堡七橋問題，歐拉在1736年解決了這個問題，并于1753年發(fā)現(xiàn)了歐拉公式而成為拓?fù)鋱D論的奠基人。接著中斷了170多年。1930年，當(dāng)波蘭數(shù)學(xué)家C.Kuratowski和美國數(shù)學(xué)家O.Frink&P.A.Smith發(fā)現(xiàn)了平面圖判定準(zhǔn)則后，這方面的研究才開始復(fù)蘇。20世紀(jì)70年代，我國著名數(shù)學(xué)家吳文俊教授和劉彥佩教授創(chuàng)立了平面性判定的“吳-劉”方法得到了國際數(shù)學(xué)界的認(rèn)可。如今，平

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

7、化為點著色問題。由于生產(chǎn)管理、軍事、交通運輸?shù)确矫嫣岢龃罅繉嶋H問題的需要，圖的染色理論及其應(yīng)用研究得到飛速發(fā)展。2相關(guān)概念和定理2.1圖的相關(guān)概念定義1一個圖是一個三元組,其中為有限非空結(jié)點集合,稱為結(jié)點,為有限的邊集合,稱為邊,是從邊集合到結(jié)點對集合上的函數(shù).?圖可簡記為:.定義2如果中邊對應(yīng)V中的結(jié)點對是無序的,稱是無向邊,記,稱,是的兩個端點.如果與結(jié)點有序?qū)ο鄬?yīng),稱是有向邊,記,稱為的始點,為的終點.定義3每條邊均為無向邊的圖稱為無向圖.每條邊均為有向邊的圖稱為有向圖.有些邊是無向邊,有些邊是有向邊的圖稱為混合圖.定義4設(shè),為兩個圖(同時為無向圖

8、或有向圖),若１６且,則稱為的子圖,為的母圖,記作.若是的子圖,且