共查询到20条相似文献,搜索用时 663 毫秒
1.
一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法:三角排序。利用该排序的结果证明了当n≡4(mod8)和C4n-1/2+2〈m≤C4n/2+2时,梯图Lm■Pm×P2的点可区别全色数为n。 相似文献
2.
一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法——三角排序,利用该排序的结果证明了当n=7(mod8)且Cn-1^4/2+2〈m≤Cn ^4/2+2时,梯图Lm≌Pm×P2的点可区别全色数为n。 相似文献
3.
图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。 相似文献
4.
5.
田京京 《计算机工程与应用》2012,48(25)
根据路和星、圈的多重Mycielski图的结构性质,用穷染递推的方法,讨论了图Mn(Cm)和Mn(Pm),以及Mn(Sm)的邻点可区别I-全染色,得到了图Mn(Sm)和Mn(Pm)的邻点可区别I-全色数等于它们的最大度,图Mn(Cm)的邻点可区别I-全色数在m=4,5时等于它的最大度加1,其余情况等于它的最大度,即分别给出图Mn(Sm)和Mn(Cm)、Mn(Pm)一种染色方案. 相似文献
6.
田京京 《计算机工程与应用》2012,(25):39-41,60
根据路和星、圈的多重Mycielski图的结构性质,用穷染递推的方法,讨论了图Mn(Cm)和Mn(Pm),以及Mn(Sm)的邻点可区别I-全染色,得到了图Mn(Sm)和Mn(Pm)的邻点可区别I-全色数等于它们的最大度,图Mn(Cm)的邻点可区别I-全色数在m=4,5时等于它的最大度加1,其余情况等于它的最大度,即分别给出图Mn(Sm)和Mn(Cm)、Mn(Pm)一种染色方案。 相似文献
7.
《计算机应用与软件》2013,(3)
设f是简单图G的一个正常k-全染色,若G中任意两点所关联的点及其关联边的颜色所构成的集合互不相同,则称f为G的K-点可区别强全染色,k中的最小值为G的点可区别强全色数。针对完全图的点可区别强全染色的特点,提出一种新算法。该算法把需要填充的颜色分为两部分:超色数和正常色数,在分别得到其染色数量和染色次数的前提下先对超色数进行染色以增强算法的收敛性。实验结果表明,该算法能有效地解决完全图的点可区别强全染色问题。 相似文献
8.
邻点可区别[VI]-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类(点或边)的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别[VI]-均匀全色数。提出了一种针对随机图的邻点可区别[VI]-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别[VI]-均匀全色数。 相似文献
9.
设f是图G的一个正常的k-全染色,若G中任意两点的色集不同,则称f为G的k-点可区别全染色,简记为k-VDTC of G,,并称最小的k为G的点可区别全色数。该文针对完全图的点可区别全染色的特点提出了分类顺次着色算法,该算法首先按照一定的规则对元素进行分类然后对元素进行顺次着色,同时给出关联锁表,根据关联锁表判断是否得到问题的解。实验结果表明:该算法有效地解决了完全图的点可区别全染色问题。 相似文献
10.
图的邻点可区别均匀V-全染色(AVDEVTC)是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数(AVDEVTCN)。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1000个顶点以内的图的AVDEVTCN。 相似文献
11.
12.
13.
14.
文章主要刻画了循环图C2n(1,2n/3)的k-偶匹配可扩性,得出对任意的n(n>3),C2n(1,2n/3)是2-偶匹配可扩性的. 相似文献
15.
联图G+H表示将G中每个点与H中的每个点连边得到的图。在Klesc M.给出联图W3+Cn的交叉数的基础上,应用反证法和排除法得到了联图W4+Cn的交叉数为Z(5,n) + n +|n/2|+ 4(n≥3)),并在Zarankiewicz猜想成立的前提下,根据证明,提出对Wm+Cn的交叉数的一个猜想:cr(Wm+Cn)=Z(m+1,n)+|m/2||m-1/2||n/2|+|m/2|+|n/2|+2,n≥3。其中Z(m,n)=|m/2||m-1/2||n/2||n-1/2|,m,n为非负整数。 相似文献
16.
改进的赫夫曼树(Huffman Tree)和赫夫曼编码(Huffman Code)构造算法 总被引:1,自引:0,他引:1
通过将待排序的数据应用快速排序算法进行排序处理,使得赫夫曼算法(Huffman Algorithm)65时间复杂度从O(n^2)降低为O(n*log2n)。当用于构造赫夫曼树(Huffman Tree)的结点比较多时,可较大的提高程序的运行时间。 相似文献
17.
18.
第五节圆弧 在汉语编程环境下,确定了两点的位置即可画出一条线段或一个矩形,甚至一个椭圆.但要画一条圆弧,除了要确定边界矩形左上角顶点A和右下角顶点B的坐标外,还要定义好圆弧的起始点C及终止点D的坐标(如图2-9)。 相似文献
19.