共查询到20条相似文献,搜索用时 0 毫秒
1.
刘儒英 《内蒙古师范大学学报(自然科学版)》1990,(4):14-18
设G=(V,E)是一个简单图.称V 的一个划分{V_1,V_2,…,V_φ}是一个路着色,如果对任意的i∈{1,2,…,k},〈V_i〉的每个分支都是路.G 的路着色中所需的最少颜色数叫G 的路色数.本文给出了路色数的一个下界;并讨论了两个图的笛卡儿积的路色数,最后,还推广了文[1]的一个定理的结论. 相似文献
2.
3.
4.
大边数图的星约束色数 总被引:1,自引:0,他引:1
图的P-色数χ(G,P)是对G的顶点着色,使得每一色类的导出子图具有性质P的最小颜色数,该文研究χ(G,P),这里P是星的并这一性质,且把这种P-色数星约束色数,记为χ(G,St),该文给出一些大边数图的星约束色数。 相似文献
5.
徐丽琼 《福建师范大学学报(自然科学版)》2004,20(2):1-3
群色数χ1(G)是最小数m,使得对任意Abel群A,若|A|≥m,则G是A-可着色的.称G是群色临界的,若对于G的任一真子图H,有χ1(H)<χ1(G).研究了群色临界图的一些性质,给出某些群色临界图的刻划,证明了k群色临界图G的最小度为k-1,且若G是3群色临界图当且仅当G是圈. 相似文献
6.
图的着色算法是一种典型的NP-完全问题。在系统地讨论了图的正常顶点着色,边着色以及全着色的有关理论的基础上,提出了基于分组遗传算法和启发式搜索的图的正常k-点着色,正常k-边着色以及正常k-全着色的新型混合算法,提出了评价算法性能的标准。实验仿真结果表明,新型混合算法可以获得问题高质量的解,即对图进行着色所使用的颜色数接近图的色数。 相似文献
7.
任庆军 《陕西师范大学学报(自然科学版)》2002,30(2):123-124
研究了具有禁止路的条件色数,若把这一色数记作X(G,^7Pj),得出了大边数图G的X(G,^7Pj)值在不同情形下为[n/(j-1)]或[(n-1)/(j-1]。 相似文献
8.
9.
图顶点m着色的改进算法 总被引:1,自引:0,他引:1
对于解决图顶点着色问题,目前较常使用DFS算法,而由于该算法存在效率不高问题,故提出DFS改进算法,极大提高了该算法的效率,对于较难的图顶点着色问题,利用该改进算法更为有利。 相似文献
10.
吴举林 《青岛大学学报(自然科学版)》1990,3(1):1-6
图G=(V,E)中一个点V的领域是点V及其邻点导出的G的子图。领域复盖问题就是求一级量小个的领域,使其复盖子G的每一条边。本文证明了无三角形图上和分离图上的领域复盖问题是NP-完全问题。通过研究集族的强Helly性质,得到了领域复盖问题可转化为团复盖问题的条件一图的领域二分具有强Helly性质。文中给出了弦图的领域二分图具有强Helly性质的禁用子图形式的充分必要条件。 相似文献
11.
关于距离图着色问题的一点结果 总被引:3,自引:0,他引:3
整数距离图是这样一类图G(Z,D),其中V(G)=Z,两点u,v之间有一条边相连,当且仅当|u-v|∈D,这里D∈ N.本文确定了|D|≥4时某些距离图G(Z,D)的点色数χ(G),解决了|D|=3时某些距离图G(Z,D)的star extremal问题. 相似文献
12.
本文讨论调和图的边数以及调和转换的一些应用,本文提供了关于调和图边数的由顶点数表示的上界,并且给出一种可用于将调和图标号转变为序列标号的方法。 相似文献
13.
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. 相似文献
14.
15.
林育青 《安徽大学学报(自然科学版)》2007,31(6):13-15
Lovasz 在 1968 年提出了猜想[1]:若 G 不是完全图,并且x=m+n-1,这里 m≥2 以及n≥2,则存在 G 的不相交子图 G1和G2使得X(G1)=m 和 X(G2)=n.该文举例说明该猜想并不一定成立,同时给出使此猜想成立的一些充分性条件. 相似文献
16.
李雪峰 《安徽大学学报(自然科学版)》2009,33(4)
如果用k种颜色对图G的顶点进行着色,使相邻顶点具有不同的颜色,那么称此种着色为G的一个正常k-着色(简称k-着色).图G的色数χ(G)是指使G可正常着色的最少颜色数,其中具有相同颜色的顶点集称为一个色类.如果对G的所有χ(G)-着色产生的色类是相同的,那么称G是唯一χ(G)-着色的.论文给出了一些唯一3-着色图. 相似文献
17.
亓健 《中国石油大学学报(自然科学版)》1989,(5)
本文证明了P_∞-K-临界图的一些简单性质,并给出了某些图类的路色数。主要证明了:(1)若x(G,P_∞)=K,则G包含一个P_∞-l-临界子图,这里对所有的l≤K;(2)设G是P_∞-K-临界图,H是G的子图,且H∈P_∞。,则x(G—H,P_∞)=K-1;(3)设T为m阶树,C_n为偶圈,则x(T×C_n,P_∞)=2;(4)若C_n为奇圈,则对任意树T,有x(T×C_n,P_∞)≤3;(5)若m≠n,则x(K_m×K_n,P_∞)=max{[(m 1)/2],[(n 1)/2]}。 相似文献
18.
琼吉 《青海师范大学学报(自然科学版)》2011,27(1):5-8
本文围绕列表着色展开讨论,将列表着色方面的已有结论进行了整理和简要的证明及补充说明.本文对一些猜想的特殊情况进行了论证. 相似文献
19.
20.
Mycielski图的对策染色数 总被引:5,自引:1,他引:4
介绍了一种新的图着色--关于图G的对策色数Ⅱ和对策色数χ^*g(G)。确定了Mycielski图的对策色数Ⅱ,并给出了选手A获胜的对策。讨论了关于对策杂色Ⅱ的性质。 相似文献