资源描述：
《平面图、对偶图和色数的应用探究-毕业论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、目录1引言12相关概念和定理12.1图的相关概念12.2平面图的相关概念和定理22.3对偶图的相关概念52.4色数的相关概念和定理62.4.1图中顶点的着色62.4.2边着色62.4.3面着色73平面图、对偶图和色数的应用73.1平面图理论的应用73.2对偶图理论的应用93.3色数理论的应用103.3.1运用图论知识解决高中数学染色问题103.3.2染色理论在教务工作中的两个应用124结束语15参考文献16致谢17ii平面图、对偶图和色数的应用探究xxx本xxx班xxx指导老师xxx摘要：平面图、对偶图和色数理论不仅是图论中的重要内容,而且在实际生活中应用
2、广泛。本文首先阐述了平面图、对偶图和色数的相关概念和定理，然后分别探究了其实际应用。其中，景区空调管道的设计和3间房子3种设施问题是典型的平面图模型，电力电子器件的对偶变换是对偶图理论的应用，高中数学染色问题的图论解法和教务工作中期末考试安排和排课表问题是平面图的色数理论的应用。关键词：平面图，对偶图，色数，应用探究。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年发现了欧拉公式而成为拓扑图论的奠基人。接着中断了170多年。1930年，当波兰数学家C.Kuratowski和美国数学家O.Frink&P.A.Smith发现了平面图判定准则后，这方面的研究才开始复苏。20世纪70年代，我国著名数学家吴文俊教授和刘彦佩教授创立了平面性判定的“吴-刘”方法得到了国际数学界的认可。如今，平
6、面问题的研究成果已经在交通网络和印刷线路的设计等方面得到应用。世界上著名的“四色猜想”曾困扰了数学家们将近100年，期间人们进行了各种尝试，平面图的对偶图也曾用于解决著名的四色猜想问题，但都以失败告终，最后数学家凯尼斯.阿佩尔和沃夫冈.哈肯借助计算机得以解决。平面图的染色问题是与四色问题紧密相联的。于是产生了着色问题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色？这个问题叫做图的点着色问题。如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色？这个问题叫做边的着色问题，边的着色问题可以转
7、化为点着色问题。由于生产管理、军事、交通运输等方面提出大量实际问题的需要，图的染色理论及其应用研究得到飞速发展。2相关概念和定理2.1图的相关概念定义1一个图是一个三元组,其中为有限非空结点集合,称为结点,为有限的边集合,称为边,是从边集合到结点对集合上的函数. 图可简记为:.定义2如果中边对应V中的结点对是无序的,称是无向边,记,称,是的两个端点.如果与结点有序对相对应,称是有向边,记,称为的始点,为的终点.定义3每条边均为无向边的图称为无向图.每条边均为有向边的图称为有向图.有些边是无向边,有些边是有向边的图称为混合图.定义4设,为两个图(同时为无向图
8、或有向图),若１６且,则称为的子图,为的母图,记作.若是的子图,且
