2011-5-30-宋平平.docVIP

毕 业 设 计 (论 文) 题 目： 星的广义Mycielski图的连续着色 07级班 星的广义Mycielski图连续边着色图论是一个它在自然科学、社会科学等领域均有很多应用图论以图为研究对象，图形中用点表示对象，两点之间连线表示两个对象之间的关系，任意包含了某种二元关系的系统都可以用图来模拟。图的染色问题一直是图论研究的焦点，它具有深远的理论意义和广泛的应用价值，为一些实际问题的解决提供了科学的理论依据。对简单图的边进行着色，如果相邻边所着颜色不同，则称此边着色为正常边着色. 对简单图，用颜色对其边进行正常着色，如果每个顶点所关联的边的着色构成一个连续整数集合，则称此正常边着色为连续的. 图的亏度是粘在上使它可连续边着色的悬挂边的最小数目. 本文主要研究星的广义Mycielski图，并得到如下结果.对正整数， ，其中为整数，且为偶数. 图；星；亏度；连续边着色；广义Mycielski图Mycielski graphs of stars 【Abstract】Graph theory is a branch of mathematicsmany applications in the natural sciences, social sciences and so on. The object of study in it is graph, where the vertices represent the objects and edges represent the relationships among the objects. Any system that contains a binary relationship can be simulated with the graph. The coloring of graphs is one of the very important problems in graph theory, is valuable in both theory and application, and provides the theoretical guides on doing some practical problems. Coloring a simple graph , if each pair of adjacent edges have different colors, then the coloring is called proper. For a simple graph and a proper edge-coloring of with colors , if the colors of edges adjacent to a common vertex form a consecutive set of integers, then the coloring is called consecutive. The deficiency of is the minimum number of pendant edges whose attachment makes consecutively colorable. In this paper, we study the generalized Mycielski graphs of stars , where, and get the following results: 字For any positive integer , where and is even. 朗读 显示对应的拉丁字符的拼音 【】generalized Mycielski graph 目 录 1 图的着色 1 2 图的基本概念 1 3 图的连续边着色 2 4 和 4 5 主要结果 5 6 结论 10 参考文献 11 致谢 14 1 图的着色 图论是数学领域中发展最快的分支之一，是组合数学的一个分支，以图为研究对象，图形中用点表示对象，两点之间的连线表示对象之间某种特定的关系.关于图论的文字记载最早出现在欧拉1736年的论述中，他所考虑的原始问题有很强的实际背景，它起源于著名的可尼斯堡七桥问题，这是图论发展的萌芽时期最具代表性的问题. 19世纪中叶，图论进入第二个发展阶段，这个时期图论问题大量出现，诸如由“环游世界”游戏发展起来的哈密顿问题，关于地图染色的四色问题以及与之相关联的图的可平面性问题等，由于染色问题反映了广泛而深刻的实际背景，它的研究带动了整个图论的发展. 直到1936年柯尼希发表了图论的第一本专著《有限与无限图理论》，这时图论才成为一门学科，以后图论进入第三个发展阶段