共查询到20条相似文献,搜索用时 161 毫秒
1.
图G=(V,E)的一个正常着色就是将G的顶点划分为独立集,或称之为色类,记为П=|V1,V2,…VK|.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则”被称为是满色的.如果在一个正常着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为xf(G).另外,记f(G)为使图存在满着色的最大颜色数.在这篇文章中,我们研究了一些乘积图的满着色,得出一些关于正则图的满着色的结果. 相似文献
2.
刘峙山 《内蒙古师范大学学报(自然科学版)》1991,(4):24-25
H.P.Yap在[1]中提出这样一个问题,是否存在偶阶边着色8临界图,它除了有一个2度点和两个3度点外其余的都是8度点?作为本文定理推论的一个特殊情形给出了这个问题的否定性答案。 相似文献
3.
4.
5.
本文提出了图的区间着色模型,并对相容性图给出了区间着色的多项式算法,同时改进了求图的着色问题的算法。 相似文献
6.
7.
8.
10.
张卫标 《重庆工商大学学报(自然科学版)》2017,34(3):21-23
著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的. 相似文献
11.
12.
关于强边着色猜想的最优图问题 总被引:1,自引:1,他引:0
著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的. 相似文献
13.
14.
素距离图的着色与距离集的分类 总被引:2,自引:2,他引:2
刘儒英 《青海师范大学学报(自然科学版)》1993,(2)
设 P 表示全体素数的集合,D(?)P,令 Z(D)表示这样一个图:它的顶点集是全体整数的集合,两个顶点 x 和 y 之间有边连结当且仅当(?)x—y(?)D.文[1]证明了.对任意 D(?)P,Z(D)的色数至多是4,因而可按照 Z(D)的色数把 P 的所有子集 D 分为四类,本文给出了两组新的4类子集簇,并给出若干个 D 是3类子集的充分条件。 相似文献
15.
针对经典的图着色问题,依据传统图着色算法中逆序图着色的着色思想,结合蚁群算法的搜索机制,给出了逆序蚁群着色算法.根据着色进度和未着色点的相邻点度数随机动态逆序选择新的着色点,使得算法具有较强的搜索全局最优解的能力.利用计算机生产大量随机图作为测试实例,对比逆序着色算法和逆序蚁群算法,实验结果说明逆序蚁群着色算法提高了求解质量,加快了收敛速度,证明了其优良特性.同时算法效率的提高,也保证了该算法可适用于较大规模的着色问题求解.此外,还进行了一系列对比试验,得出了关键参数的合理取值范围. 相似文献
16.
许宝刚 《山东大学学报(自然科学版)》1996,31(4):384-387
图G的全色数xT(G)是使得VE9G)中相邻接或相关联的元素均着不同颜色的最少颜色数,证明了:如果v(G)=v(H),存在v∈V(G),V‘∈V(H)使得G^c-v和C-v’都含有完美对集且Δ(G)=Δ(H)并存在e∈E(G-v),e‘∈E(H-v’),使得G-e和H-e‘都是第一类图,或ΔG)〈(H)且存在e∈E(H-v’)使得H-e‘是第一类图,则xT(GVH)≤Δ(GVH)+2。 相似文献
17.
图顶点m着色的改进算法 总被引:1,自引:0,他引:1
对于解决图顶点着色问题,目前较常使用DFS算法,而由于该算法存在效率不高问题,故提出DFS改进算法,极大提高了该算法的效率,对于较难的图顶点着色问题,利用该改进算法更为有利。 相似文献
18.
设图G的点集V(G)=(v1,v2…,vn),Vi是点集(i=1,2,…,n),G的膨胀图FG的点集V(FG)=V1∪V2…∪Vn,且对x∈Vi,y∈Vj有xy∈E(FG),当且仅当i=j或vivj∈E(G).若对所有的i,满足|Vi|=t,则称其为G的一致膨胀图.证明了树的膨胀图的关联色数是最大度加1,K2,n的一致膨胀图的关联色数为最大度加2. 相似文献
19.
N((3, 3), 5) denotes the minimum N so that there exists a graph of N vertices which doesn't contain complete subgraph on 5 vertices and can't be (3, 3)-colored. It is shown that N ((3, 3), 5) = l5. 相似文献