图的区间边着色的收缩图方法

发布时间：2018-05-29 22:14

  本文选题：区间边着色 + 收缩图　； 参考：《新疆大学》2017年硕士论文

【摘要】：图论作为数学的一个分支,近年来得到了较快发展和广泛应用,已广泛应用于运筹学,控制论,信息论和计算机科学等各个领域.一般说来,图的着色问题最早起源于著名的”四色问题”.由于图的着色问题反映了广泛而深刻的实际背景,它的研究带动了整个图论的发展.如今图着色理论被广泛应用于化学品的贮藏,考试日程和安排会议等许多实际问题上.图G的一个用了颜色1,2,...,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作N.对图G∈N,使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G).本文中,我们给出了图的区间着色的收缩图方法.利用此方法我们对双圈图G∈N,证明了w(G)=?(G)或?(G)+1,并且完全确定了w(G)=?(G)及w(G)=?(G)+1的双圈图类.全文共分为三章.第一章首先介绍了图着色的研究背景及相关应用,以及图的区间边着色的刻画问题;其次介绍了基本概念及术语;最后列出了图的区间边着色研究的一些已有结果.第二章给出了收缩图方法.第三章主要利用前面的方法给出了双圈图区间边着色的下界.第三章分为三个小节.第一节中给出了双圈图G∈β∞的区间边着色的下界w(G);第二节中给出了双圈图G∈βθ的区间边着色的下界w(G);第三节中给出了双圈图G∈β的区间着色的下界w(G).
[Abstract]:As a branch of mathematics, graph theory has been rapidly developed and widely used in recent years. It has been widely used in the fields of operational research, cybernetics, information theory and computer science. Generally speaking, the coloring problem of graphs originated from the famous four-color problem. Because the coloring problem of graphs reflects a wide and profound practical background, its research has driven the development of the whole graph theory. Graph coloring theory is widely used in many practical problems such as chemical storage, examination schedule and meeting scheduling. One of the edges of the graph G is called interval t- coloring, if all the t colors are used. And the colors on the edges of the same vertex associated with G are different and these colors form a continuous integer interval. G is called interval colored if there is an interval t-coloring for a positive integer t G. The set of all interval-coloring graphs is denoted as N. For a graph G 鈭，

本文编号：1952645