图论期末论文——顶点着色

附件1《图论》课程专题论文论文题目：基于顶点着色理论的期末考试时间安排问题专业：数学与应用数学班级：2012级数学与应用数学班组长：张正中年月日论文编号姓名张正中马晓晨余铁方李斌唐毓春杨昌天马福贵学号P121713337P121713347P121713348P121713357P121713338P121713354P121713342成绩论文评价指标与鉴定意见论文题目基于点着色理论的期末考试时间安排问题完成人张正中、马晓晨、李斌、唐毓春、余铁方、杨昌天、马福贵专业及班级2012级数学与应用数学班指标论文评价（对表格中的各栏，用“√”表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86—100分）B（70—85分）C（60—69分）D（0—59分）鉴定意见评阅人签名：成绩评阅人职称专业附件2分工情况论文题目基于点着色理论的期末考试时间安排问题专业年级2012级数学与应用数学班组长张正中电话[phone]QQ号1098758179完成人分工情况完成度（%）张正中摘要、论文整合15马晓晨顶点着色在期末考试时间安排中的应用15李斌数据收集、整合14余铁方顶点着色应用的实际意义14杨昌天考试时间安排问题的发展现状14唐毓春顶点着色理论及其算法的发展现状14马福贵顶点着色理论及其算法的发展现状14摘要随着Internet的发展和我国高校校园网的普及,采用计算机网络进行考试安排的需求非常迫切,而考试冲突问题又是考试安排的核心,使用顶点着色算法设计一个高效的考试安排系统,解决考试冲突问题,使考务工作适应信息化的需求,实现管理的科学化、自动化,最大程度为教师和同学们提供方便是本论文研究的重点本文应用图论的原理将数学与计算机科学学院2014级考试安排问题转化为对图的顶点着色问题。提出用求图的极大独立集的方法求解图的点色数，并用布尔方法计算图的极大独立集,有效的避免了相同班级的不同考试科目在同一时间进行考试的问题关键词顶点着色问题考试安排布尔算法ABSTRACTWiththedevelopmentofInternetandthepopularizationofcampusnetworkinCollegesanduniversitiesinChina.Itisurgenttousecomputernetworktocarryoutthetestarrangementandtheexaminationconflictproblemisthecoreoftheexaminationarrangement.Usingvertexcoloringalgorithmtodesignanefficientexaminationarrangementsystem,solvetheconflictproblemofexaminationexaminationwork,tomeettheneedsofinformationization,therealizationofscientificmanagementandautomation,thegreatestdegreeforteachersandstudentstofacilitatetheresearchfocusofthispaper.Inthispaper,theprincipleofgraphtheoryisappliedtotheproblemof2014levelsofthecomputersciencecollege.Itisproposedtosolvetheproblemofthesameclassofdifferenttestsubjectsinthesametimebyusingthemaximalindependentsetofthegraph.Keyword:VertexcoloringproblemExaminationarrangementBoorAlgorithm目录摘要.........................................................................................................4关键字.....................................................................................................4ABSTRACT............................................................................................5Keyword:.................................................................................................5引言.......................................................................................................7着色问题知识背景.................................................................................8顶点着色应用.........................................................................................9顶点着色预备知识.................................................................................91.无向图概念......................................................................................92.简单图概念......................................................................................93.完全图概念......................................................................................9顶点着色相关定义...............................................................................10顶点着色算法分析...............................................................................10实例.....................................................................................................11结果分析...............................................................................................19结束语...................................................................................................19引言图的着色问题是组合优化问题，无论理论上还是应用上都具有良好的相关应用背景。先从1736年的“七桥问题”引开，得出图再展开它的领域。图的顶点数、对图的顶点着色以及边数着色都是直的研究的问题，它不仅仅是数学问题，还涉及到很广泛的应用。各个领域的科学家也因此对图的研究有很大兴趣，主要是对它的研究在别的领域上可以使某些问题在使用相关领域法的情况下变得更简单明了。随着计算机水平的迅速提升，使得今天对图的研究有较强劲的推动。目前，许多数学家层出不穷的想法，图的研究领域有较多的有趣实用结果，很多相关领域也因此而享以福泽。因考虑到某些问题中时间的最优安排和涉及相关结点不存在矛盾且不冲突，本小组借前人的研究经验来对其一小分支加以研究——图的顶点着色问题，从而可以折射到研究考试时间冲突问题，主要解决要在怎样的情况下不存在考试时间冲突却使时间考试最少。这课题也可以应用于别的领域探索，如：员工分配相应工作与工作的时间问题、电路系统问题、排课问题、存储问题等。解决的重点是使各个条件达到最优，从而使图的顶点着色得到更广泛的推广与应用。着色问题知识背景顶点着色，较为流行的一种渲染方法，比平面着色更先进一些，它为3D物体的每个顶点提供了一组单独的色调值，并对各顶点的颜色进行平滑、融合处理，为多边形着上渐变色。它所渲染出的物体具有相当丰富的颜色和平滑的变色效果，不过其着色速度比平面着色要慢得多。着色问题(RoadColoringProblem)是图论中最著名的猜想之一。通俗的说，这个猜想认为，可以绘制一张万能地图，指导人们到达某一目的地，不管他们原来在什么位置。这个猜想最近被以色列数学家艾夫拉汉·特雷特曼(AvrahamTrahtman)在2007年9月证明特雷特曼在数学上的这一成果极为令人瞩目，英国《独立报》为此事专门发表了一篇题为身无分文的移民成了数学超级明星的文章，给予了高度的评价。以色列人也为特雷特曼取得的成就感到无比的骄傲。特拉维夫电视台中断了正常的节目播放，以第一时间发布了这一重大消息，连中东其他国家的主流媒体也作了大篇幅的相关报道。得知特雷特曼解决这一难题的消息后，多年从事路线着色问题研究的加拿大数学家乔尔·弗里德曼说，路线着色问题的解决令数学共同体非常兴奋。读过特雷特曼论文的中国数学家和语言学家周海中教授认为，特雷特曼的数学知识非常渊博，解题方法十分巧妙，这一谜题得到破解，无疑是数学史上的一个华彩乐章。顶点着色应用顶点着色问题是一个很重要的问题。例如某委员会会议日程安排可以使用着色问题来解决会议冲突的安排。同样的，在为某大学安排考试时间时需要将有学生同时选修的的两门课程安排在不同时间，把课程看做图中的顶点，学生同时选修的两门课程有边相连，考试时间段的总数等于图着色的色数顶点着色预备知识1.无向图概念：任意一条边都代表u连v以及v连u。无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。2.简单图概念：在无向图中，如果关联一对顶点的无向边多于一条，则称这些边为平行边，平行边的条数称为重数。自环是两端连接着同一端点的边，既不含平行边也不含自环的图称为简单图。3.完全图概念：若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n−1)/2条边，以Kn表示。它是(k−1)-正则图。所有完全图都是它本身的团顶点着色相关定义定义1.1用n种颜色对图G的顶点进行着色,且没有相异的邻接顶点着色相同,则称为G的一个n-顶点着色(n-vertexcolouring),简称n-着色.定义1.2使图G为n-着色的最小数值称为G的色数(chromaticnumber),记作x(G).如果x(G)=n,则G为n-色的(n-colouring).顶点着色应用。顶点着色算法分析有若干学生同时选修N门课程，同一个学生每场只能参加一门考试，则在最短时间内，需要安排多少场次?即同一学生选修的不同课程不能在一个时间段考试，没有相同学生的课程可以安排在一个时间段考试总结为:在给定一个无向图G=(V,E)，|V|=n,,,ijvvE当且仅当有一个同学选了课程i和课程j，考试安排方案