圆染色在交通信号灯相位优化设计中的应用

通过引入图论中“最大独立集”、“圆染色”、“圆色数”的概念,将其运用于城市路口交通信号灯最优相位个数的最优相位设计上,并将交通信号灯最优相位归结为其交通流模型图的圆色数.在这篇文章中,根据实际生活中常见四、五交叉路口的各种交通状况,由车流的冲突关系给出交通流模型图并由圆染色的定义及一些已有的结论证明出这些图的圆色数.     

圆染色在交通信号灯相位优化设计中的应用

通过引入图论中“最大独立集”、“圆染色”、“圆色数”的概念，将其运用于城市路口交通信号灯最优相位个数的最优相位设计上，并将交通信号灯最优相位归结为其交通流模型图的圆色数．在这篇文章中，根据实际生活中常见四、五交叉路口的各种交通状况，由车流的冲突关系给出交通流模型图并由圆染色的定义及一些已有的结论证明出这些图的圆色数．     

两类齿轮图的分数色数

分数着色是在正常着色的基础上提出的,拓展了图着色的研究领域,便于更好的研究图的结构.主要研究了齿轮星图,齿轮风车图的分数色数,分数关联色数和分数全色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明.     

两类距离图的分式色数和点色数

分式色数和点色数是图的两个重要参数。本文在文献[1]的基础上给出了两类距离图G（Z,Dm,k,k 1)与G（Z,Dm,k,k 1,k 2）的分式色数和点色数。     

几类图色等价的充分必要条件

在微积分罗尔定理理论基础上,运用归纳法证明了两个多项式恒等的一个充分条件,进而利用色数、围长、补图的理想子图数给出了两类图n+s(s,n∈Z+)阶n-色图色等价的充分必要条件,这为构造色等价图提供了新方法,由此得到几类新的色等价的n+3阶n-色图.     

关于图的染色问题算法的新研究

图的染色问题(graph coloring problem,GCP)是图论中的一个经典难题,主要分为顶点染色、边染色、图的全染色,研究图的色数问题是重要的理论问题,研究图的染色算法则是实际应用问题,本文将几种已知的求图点色数的几种方法综合应用,利用已知定理,对顶点染色问题进一步探讨,得到一种求点色数的新算法.     

图的色数问题研究

为了确定任意无向简单图Ｇ从分析点色数的出发，采用了作点集Ｖ的最小划分的方法，得到了一个点色数算法科给出了证明，从而解决了无向简单图的点色数问题。     

路的Mycielski图上的对策着色和对策着色数

图G的对策色数Ⅱgχ*(G)是由图的点色数gχ(G)拓展而来的。本文对路的Myc ielsk i图进行了讨论,给出了它的对策色数Ⅱ,并给出了选手Alice相应获胜的对策。     

图的和运算与正规积运算的分数色数

首先给出图的分数色数、图的和运算和正规积运算的定义,然后研究图的和运算和正规积运算的分数色数,以及这些运算的分数色数之间的关系,进而得到图的和运算、正规积运算的分数色数上下界,从而完善图的四大运算分数色数与其因子的分数色数之间的关系。     

关于θ图的若干参数

设s,t,l至多有一个为1的正整数,长分别为s,t,l的不同三条路的端点重合后的图称为θ图.本文研究了θ图的覆盖数,独立数,色数,边色数和全色数.     

图的b-边染色数及b-边连续性研究

图染色及色数问题是图论中的一个重要内容,也是图论中的一个十分活跃的领域,同时有着深刻而丰富的理论结果和广泛的实际应用,其理论和方法在离散数学中占有重要地位.本文在图的b-染色数和b-连续概念的基础上提出图的b-边染色数及b-边连续的概念,给出了路图、圈图以及满n叉树图的b-边染色数,并且证明了这些图都是b-边连续的.     

The Incidence Coloring Number of Complete k-Partite Graph

The concept of the incidence chromatic number of a graph was introduced by Brualdi and Massey. Theyconjectured that every graph G can be incidence colored with △(G)+-2 colors. In this paper, the trueness of thisconjecture for complete k-partite graph was proved, and the incidence chromatic number of complete k-partitegraphs was calculated.     

图中点对偶的几个着色定理及算法

探讨了简单图Ｇ＝（Ｎ，Ｅ）中不邻接点的着色问题，给出连通的简单图中，点对偶在ｒ（Ｇ）＝ｋ）着色中为同色和异色的性质，色数的存在区间等，提出了求简单图色数的一种较有效的算法。     

基于缩边递推法的图色多项式求解算法设计与分析

给出了缩边递推法求解图的色多项式的有效算法,并用Java语言在计算机上实现：输入图的顶点数n及每一条边,即能在屏幕上输出该图图形及其色多项式;最后对算法实现的效率进行了分析,其时间复杂度为O（n2）。     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

几类积图的强边着色

图G的强边着色是指一个正常的边着色,同时对任意长为3的路上的边不能有相同的颜色.图G的强边色数是指在G的所有强边着色中所用色数的最小者.研究了几类积图的强边着色,并给出了相应图的精确的强边色数值.     

图的全谐调着色数

图的全谐调着色数表示为Th(G)是相邻的点与边着不同颜色 ,且任何两个不同的边上有不同的三元颜色组的最小着色数。本文给出了关于图的全谐调着色数的各种定理     

双外平面图的全染色

双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上。设G是一个双外平面图,V（G）,E（G）,F（G）分别为双外平面图G的点集,边集和面集。G的全色数XT（G）是使得V（G）UE（G）中的任意两个相邻或相关联的元素间均染不同颜色的最少颜色数。本文证明了对最大度为6的双外平面图,全色数是△（G）＋1,其中△（G）为G的最大度数。     

基于独立集划分的图着色算法

针对经典的图着色问题,在顶点集随机划分的基础上,设计了一种寻求集合个数最少的独立集划分遗传算法.运行算法获得的独立集个数即为图的色数.算法引入了模块化函数思想,采用了单向传递交叉算子.通过贪婪局部优化初始种群和杂交后代个体,使算法具有较好的收敛速度.对四个经典算例的仿真结果表明,本文提出的算法可获得问题的高质量解,是一种有潜力的算法.     

不含四圈，三圈不重点的平面图全染色的一个结论

设G是一个图，Δ(G)是G的最大度.本文对3 圈不重点的，且不含从4到k圈的平面图，得出的结论有：如果(Δ,k)分别是（6，4），（5，5），（4，11），则G的全染色数是Δ(G)+1.