浅谈图论中着色问题的应用.pdf.pdf

维普资讯
浅谈图论中着色问题的应用�
重庆工商大学数学与统计学院袁怡�
图论��������������是数学的—个分支。它以图为研究�使用最少时�
对象。给定—个图,如果要求把所有顶点涂上颜色,使得相邻�间段的考试安排�
顶点具有不同的颜色,问最少需要几种不同的颜色�这个问题�等价于�的使用�
叫做图的点着色问题。由于着色问题反映了广泛而深刻的实际�����种颜色的�
背景,它的研究带动了整个图论的发展。如今图着色的理论被�着色, 由于结点�
广泛利用于解决安排会议或考试的日程以避免冲突和安排化学����、���、���和���相互邻接,所以����≥�。�的一种�
品的存储以避免互相反应等具体问题上。下面举例加以说明。��着***如图�所示。由此表明������,即最少需要�个时�
�例��期末考试的安排��������大学的�学院有�名教授。�间段。如果仅仅需要每位教授监考自己的课程,那么完整的考�
这学期他们每人开设�门课程,课程表�试安排如表�所示。�
如表�所示。�袭�
教援�所授罐耩�时熙段�舞斌秘秘�鼗鸯教撬�
在安排考试的时候,已经确定学院�抽或��������������《煎�����、���,�����血�《����蚰懈�《��强��媾《��≈∞�幽�竭����嚣�
��������黪����》�越畦���噬����
的每门课程都将有考试,且同一课程的����������������
��蘸�����、�����国《��妨�。�������矗蹦���,∞�莲���》�濑�����
����:�������.����
不同部分将同时考试,每位教员必须监���������,������������
考自己的课程。学校有充足的教室空����������.������黄���������、���������》�濑�����
�����������������������妨,��§鼢�船�矗�《������
间,且每人都希望能尽早结束,这样他�
��������������������缫�����、����鹚《���鼢����》���妊�����越潮�燃《���
们就能尽情投入到暑假中去。那么,整��������������������
个考试最少需要多少时间��王�������������,���、����以上就是两个图着色理论的实际应用,类似的例子还有很�
�解�: 以结点代表课程, 以课程编�多,限于篇幅就不在多加举例。但综上可知着色理论正在我们�
号作为结点标记,构造课程图;如果某两门课程是由同一名�的日常生活中发挥着巨大的作用,它是我们生活中的一个好帮�
教员开设的,则将相应结点之间连一条边。如图�所示�手、好工具。�
身体健康、心理健康、社会适应等五个方面来表述具体目�建设性的,而不是居高临下。在教学过程中应充分发挥师生�
标���。未来的体育教学内容,将从以运动技术为中心向以�双方在教学过程中的主动性和创造性,在教学中努力体现体�
体育方法、体育动机、体育活动、体育经验为中心转移。但�育的实践性、综合性,重视学生情感、态度、价值观的正确�
这并不意味着对运动技术教学的否定,不过,具体的教学内�导向,