資源描述：
《平面圖、對(duì)偶圖和色數(shù)的應(yīng)用探究-畢業(yè)論》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、目錄1引言12相關(guān)概念和定理12.1圖的相關(guān)概念12.2平面圖的相關(guān)概念和定理22.3對(duì)偶圖的相關(guān)概念52.4色數(shù)的相關(guān)概念和定理62.4.1圖中頂點(diǎn)的著色62.4.2邊著色62.4.3面著色73平面圖、對(duì)偶圖和色數(shù)的應(yīng)用73.1平面圖理論的應(yīng)用73.2對(duì)偶圖理論的應(yīng)用93.3色數(shù)理論的應(yīng)用103.3.1運(yùn)用圖論知識(shí)解決高中數(shù)學(xué)染色問(wèn)題103.3.2染色理論在教務(wù)工作中的兩個(gè)應(yīng)用124結(jié)束語(yǔ)15參考文獻(xiàn)16致謝17ii平面圖、對(duì)偶圖和色數(shù)的應(yīng)用探究xxx本xxx班xxx指導(dǎo)老師xxx摘要：平面圖、對(duì)偶圖和色數(shù)理論不僅是圖論中的重要內(nèi)容,而且在實(shí)際生活中應(yīng)用
2、廣泛。本文首先闡述了平面圖、對(duì)偶圖和色數(shù)的相關(guān)概念和定理，然后分別探究了其實(shí)際應(yīng)用。其中，景區(qū)空調(diào)管道的設(shè)計(jì)和3間房子3種設(shè)施問(wèn)題是典型的平面圖模型，電力電子器件的對(duì)偶變換是對(duì)偶圖理論的應(yīng)用，高中數(shù)學(xué)染色問(wèn)題的圖論解法和教務(wù)工作中期末考試安排和排課表問(wèn)題是平面圖的色數(shù)理論的應(yīng)用。關(guān)鍵詞：平面圖，對(duì)偶圖，色數(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引言圖論起源于著名的哥尼斯堡七橋問(wèn)題，歐拉在1736年解決了這個(gè)問(wèn)題，并于1753年發(fā)現(xiàn)了歐拉公式而成為拓?fù)鋱D論的奠基人。接著中斷了170多年。1930年，當(dāng)波蘭數(shù)學(xué)家C.Kuratowski和美國(guó)數(shù)學(xué)家O.Frink&P.A.Smith發(fā)現(xiàn)了平面圖判定準(zhǔn)則后，這方面的研究才開(kāi)始復(fù)蘇。20世紀(jì)70年代，我國(guó)著名數(shù)學(xué)家吳文俊教授和劉彥佩教授創(chuàng)立了平面性判定的“吳-劉”方法得到了國(guó)際數(shù)學(xué)界的認(rèn)可。如今，平
6、面問(wèn)題的研究成果已經(jīng)在交通網(wǎng)絡(luò)和印刷線路的設(shè)計(jì)等方面得到應(yīng)用。世界上著名的“四色猜想”曾困擾了數(shù)學(xué)家們將近100年，期間人們進(jìn)行了各種嘗試，平面圖的對(duì)偶圖也曾用于解決著名的四色猜想問(wèn)題，但都以失敗告終，最后數(shù)學(xué)家凱尼斯.阿佩爾和沃夫?qū)?哈肯借助計(jì)算機(jī)得以解決。平面圖的染色問(wèn)題是與四色問(wèn)題緊密相聯(lián)的。于是產(chǎn)生了著色問(wèn)題即給定一個(gè)圖，如果要求把所有頂點(diǎn)涂上顏色，使得相鄰頂點(diǎn)具有不同的顏色，問(wèn)最少需要幾種不同的顏色？這個(gè)問(wèn)題叫做圖的點(diǎn)著色問(wèn)題。如果對(duì)給定圖的全部邊都涂上顏色，使相鄰的邊有不同的顏色，問(wèn)至少需要幾種顏色？這個(gè)問(wèn)題叫做邊的著色問(wèn)題，邊的著色問(wèn)題可以轉(zhuǎn)
7、化為點(diǎn)著色問(wèn)題。由于生產(chǎn)管理、軍事、交通運(yùn)輸?shù)确矫嫣岢龃罅繉?shí)際問(wèn)題的需要，圖的染色理論及其應(yīng)用研究得到飛速發(fā)展。2相關(guān)概念和定理2.1圖的相關(guān)概念定義1一個(gè)圖是一個(gè)三元組,其中為有限非空結(jié)點(diǎn)集合,稱為結(jié)點(diǎn),為有限的邊集合,稱為邊,是從邊集合到結(jié)點(diǎn)對(duì)集合上的函數(shù).?圖可簡(jiǎn)記為:.定義2如果中邊對(duì)應(yīng)V中的結(jié)點(diǎn)對(duì)是無(wú)序的,稱是無(wú)向邊,記,稱,是的兩個(gè)端點(diǎn).如果與結(jié)點(diǎn)有序?qū)ο鄬?duì)應(yīng),稱是有向邊,記,稱為的始點(diǎn),為的終點(diǎn).定義3每條邊均為無(wú)向邊的圖稱為無(wú)向圖.每條邊均為有向邊的圖稱為有向圖.有些邊是無(wú)向邊,有些邊是有向邊的圖稱為混合圖.定義4設(shè),為兩個(gè)圖(同時(shí)為無(wú)向圖
8、或有向圖),若１６且,則稱為的子圖,為的母圖,記作.若是的子圖,且
