共查询到20条相似文献,搜索用时 93 毫秒
1.
用k种颜色给一个图的顶点正常着色,即使相邻的顶点不同色,若各色类的基数至多差一,则称该图是可均匀k-着色的.基于均匀着色的理论本文得到了毛虫树可均匀k-着色的一个充分条件. 相似文献
2.
称图G是可均匀k-着色的,如果可以用k种颜色给G的顶点着色,使得相邻的顶点不同色且各色类的基数至多差1.可得到毛虫树的一个性质和计算毛虫树的均匀色数的一个精确计算公式. 相似文献
3.
尹杰杰 《海南大学学报(自然科学版)》2014,(1):35+38-38
对于具有n个顶点的简单连通图G,首先证明求解G的k-星着色等价于一个多元多项式方程组在{1,2,…,k}上的求解问题,其次使用Grbner基给出求解该多元多项式方程组的方法,从而得到求G的星色数的一个可行途径,最后通过实例验证了此代数计算方法的有效性. 相似文献
4.
李雪峰 《安徽大学学报(自然科学版)》2009,33(4)
如果用k种颜色对图G的顶点进行着色,使相邻顶点具有不同的颜色,那么称此种着色为G的一个正常k-着色(简称k-着色).图G的色数χ(G)是指使G可正常着色的最少颜色数,其中具有相同颜色的顶点集称为一个色类.如果对G的所有χ(G)-着色产生的色类是相同的,那么称G是唯一χ(G)-着色的.论文给出了一些唯一3-着色图. 相似文献
5.
6.
即是k-覆盖又是k-消去的图称为k-对等图.本文研究了有约束条件的r-正则图和k-对等图之间的关系,给出了有约束条件的r-正则图是k-对等图的关于顶点数和边连通度的充分条件. 相似文献
7.
王俊梅 《太原师范学院学报(自然科学版)》2012,(4):4-6
设G是简单图,用颜色1,2,3,…对G进行正常边着色,若每一个顶点上表现的颜色都能构成一个连续的整数集合,则称这个边着色是连续的.图G的亏度def(G)等于粘在G上使它可连续边着色的悬挂边的最小数目.文章研究了四类圈树的亏度. 相似文献
8.
设G是简单图,用颜色1,2,3,…,对G的正常边着色,如果每一个顶点上表现的颜色都构成一个连续的整数集合,那么就称这个边着色是连续的,图G的亏度def(G)是粘在G上使它可连续边着色的悬挂边的最小数目,对几类图的亏度进行了研究。 相似文献
9.
图的着色算法是一种典型的NP-完全问题。在系统地讨论了图的正常顶点着色,边着色以及全着色的有关理论的基础上,提出了基于分组遗传算法和启发式搜索的图的正常k-点着色,正常k-边着色以及正常k-全着色的新型混合算法,提出了评价算法性能的标准。实验仿真结果表明,新型混合算法可以获得问题高质量的解,即对图进行着色所使用的颜色数接近图的色数。 相似文献
10.
提出了中国建筑师问题,阐明了求解中国建筑师问题的基本思路。介绍了25个顶点、69个边、45个面的对偶图的顶点4着色的全过程。将对偶图分解成含2棵可以2着色的对偶树的森林,在以r、b两色为对偶树得到的顶点实施2着色,以y、g两色为对偶树得到的顶点实施2着色,从而实施对偶图顶点的4着色。阐述了对偶图的4着色关键是将对偶图分解出森林,提出了3个森林的分解方法,讨论了H路径的个数、森林的个数、对偶图的A区和B区划分方案、对偶图的顶点4着色方案数。解决了对偶图顶点的4着色问题,利用对偶图顶点4着色方法使Kempe四色猜想"证明"中的漏洞得到了弥补。将此种方法用于12面体、20面体、22面体、32面体的对偶图的4色问题,并取得了成功。 相似文献
11.
利用反证法构造具体的染色方法, 讨论完全二部图的顶点被多重集可区别的IE-全染色及一般全染色, 给出最优染色方案, 并确定相应染色的色数. 相似文献
12.
13.
杨鹏辉 《海南大学学报(自然科学版)》2011,29(1):8-10,19
图G(超图H)的全着色是指同时给图中的顶点和边进行着色,使相关联或相邻的元素间着不同的颜色,而使用的最少的颜色数就称为全色数,记为xT(G)(xT(H)).超图的全着色又可以分成弱全着色和强全着色2种情况.本文主要讨论超图中轮形图W(v)的全着色性质,并得到具体的强全色数和弱全色数,xWT(W(v))=△+1,xST(... 相似文献
14.
15.
图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同.论文确定了k4-minor-free图的邻点可区别全色数. 相似文献
16.
图的邻点可区别全染色,相对于图的正常全染色有更强的要求,因为它要求相邻顶点具有不同的颜色集合.本文刻画了两类特殊的完全多部图、广义圈和广义Mycielski图的邻点可区别全色数. 相似文献
17.
18.
首先, 利用色集合事先分配法, 反证探讨完全三部图K3,5,p(p≥5)的点可区别一般全色数, 给出当p较小时的特殊性证明以及当p逐渐增大时的规律性证明; 其次, 利用构造染色法对完全三部图K3,5,p进行染色, 给出染色方案. 染色的成功验证了反证法所证明色数的正确性, 从而解决了完全三部图K3,5,p的点可区别一般全染色问题. 相似文献
19.
邢婷文 《新疆师范大学学报(自然科学版)》2014,(1):72-77,80
图的染色问题具有广泛的实际应用背景,其与计算机网络结构、银行安全密码、电信通讯站点的频率分配以及人力资源配置等问题均有重要的联系。作为图的正常染色的自然推广,学者们提出了图的强染色(即2-距离染色)乃至 m -距离(m为正整数)染色的概念。文章在此基础上,定义了有向图的 m -距离染色,并研究了无向图和有向图的 m -距离染色问题,运用图论的相关技巧及标号排序等方法获得了圈、树、路、星图、有向圈、有向树的 m -距离色数,及一般无向图和有向图其 m -距离色数的上、下界。 相似文献
20.
首先, 利用色集合事先分配法, 反证探讨完全三部图K3,5,p(p≥5)的点可区别一般全色数, 给出当p较小时的特殊性证明以及当p逐渐增大时的规律性证明; 其次, 利用构造染色法对完全三部图K3,5,p进行染色, 给出染色方案. 染色的成功验证了反证法所证明色数的正确性, 从而解决了完全三部图K3,5,p的点可区别一般全染色问题. 相似文献