-
题名完全图的准强边着色图的计数
被引量:1
- 1
-
-
作者
连广昌
戴绍虞
-
机构
金陵科技学院公共基础课教学部
-
出处
《金陵科技学院学报》
2007年第2期5-8,共4页
-
文摘
使用准强边着色矩阵讨论了完全图的准强边着色图的计数。
-
关键词
完全图
准强边着色图
准强边着色矩阵
计数
-
Keywords
complete graph
quasi-strong edge colourings graphs
quasi-strong edge colourings ma- trix
computation.
-
分类号
O157.5
[理学—基础数学]
-
-
题名准强边着色图的分类
被引量:3
- 2
-
-
作者
连广昌
-
机构
金陵科技学院
-
出处
《金陵科技学院学报》
2006年第4期1-6,11,共7页
-
文摘
如果图G已有一个合理边着色,使得图G中所有相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色。具有准强边着色的图称为准强边着色图,并对准强边着色图给出一个分类。
-
关键词
准强边着色
准强边色数
准强边着色图
分类
-
Keywords
quasi-strong edge colourings
quasi-strong edge chromatic number
quasi-strong edge colouring graph
classification
-
分类号
O157.5
[理学—基础数学]
-
-
题名边着色图上最大弱适当树问题近似算法
- 3
-
-
作者
金世豪
陈光亭
陈永
张安
-
机构
杭州电子科技大学理学院
台州学院电子与信息工程学院
-
出处
《杭州电子科技大学学报(自然科学版)》
2021年第4期88-91,102,共5页
-
基金
国家自然科学基金资助项目(11971139,11771114)。
-
文摘
边着色图上最大弱适当树问题是针对给定的边着色的简单无向图,寻找1个弱适当树,使得这颗树包含顶点的个数尽可能多,这一问题是NP-hard。利用弱适当树及边着色图的性质,通过限制着色边的颜色数为2,从算法理论的角度来考虑该问题,设计了最坏情况界为2的多项式时间近似算法,并给出近似算法的紧例及其分析。
-
关键词
边着色图
近似算法
最坏情况界
树
-
Keywords
edge-colored graph
approximation algorithm
worst case ratio
tree
-
分类号
O221.7
[理学—运筹学与控制论]
-
-
题名边着色完全图中的单色圈和单色树
- 4
-
-
作者
程书婷
吴宝音都仍
-
机构
新疆大学数学与系统科学学院
-
出处
《新疆大学学报(自然科学版)(中英文)》
CAS
2022年第1期16-18,41,共4页
-
基金
supported by National Natural Science Foundation of People’s Republic of China(12061073).
-
文摘
令f(r,n)是使得任意r-边着色完全图K_(n)包含一个长度至少为k的单色圈的最大正整数k.2009年,Faudree,Lesniak和Schiermeyer提出猜想:任意(r+1)-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中r≥2.同时他们还证明了f(2,n)≥[2n/3]且界是紧的,其中n≥6.2011年,Fujita证明了当n=2r时猜想不成立,同时还证明了任意r-边着色完全图K_(n)包含一个长度至少为n/r的单色圈,其中1≤r≤n.本文中我们证明了存在(r+1)-边着色完全图K_(n)包含一个长度小于n/r的单色圈,其中n=tr+1,r≥2且n-1/r为正偶数.令c表示K_(n)的某种k-边着色.在边着色c的完全图K_(n)中,令moc(K_(n),c)表示单色树的最大阶数且moc(n,k)=min{moc(K_(n),c):c是K_(n)的某种k-边着色}.我们还证明了当n≡0,1(mod 4)时,moc(n,3)=[n/2];当n≡2,3(mod 4)时,moc(n,3)=[n+1/2],其中n≥3.
-
关键词
周长
边着色完全图
单色圈
单色树
-
Keywords
circumference
edge-colored complete graphs
monochromatic cycles
monochromatic trees
-
分类号
O157
[理学—基础数学]
-
-
题名次模函数近似算法求最小颜色生成树(英文)
被引量:1
- 5
-
-
作者
李学良
涂建华
-
机构
南开大学组合数学中心
-
出处
《新疆大学学报(自然科学版)》
CAS
2008年第4期391-394,共4页
-
基金
Supported by NSFC
Supported by PCSIRT
Supported by the "973" programm
-
文摘
给定图G并对其进行边着色,G的最小颜色生成树(MCST)问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论(贪婪算法的思想)给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.
-
关键词
边着色图
最小颜色生成树(MCST)
最大颜色匹配(MCM)
次模函数
近似算法
-
Keywords
Edge-colored graph
minimum color spanning tree
maximum color matching
submodular potential function
approximation algorithm
-
分类号
O157.5
[理学—基础数学]
-
-
题名关于n-方体的2-虹连通(英文)
- 6
-
-
作者
朱尧兴
-
机构
南京铁道职业技术学院苏州校区
-
出处
《苏州大学学报(自然科学版)》
CAS
2011年第4期14-17,共4页
-
基金
supported by Nanjing Institute of Railway Technology(Y201145)
-
文摘
边着色图中的一条路称为虹当它的边着色各不相同.如果一个图的任意两点间存在k条内部不交的虹,则称该图为k-虹连通图.记rCk(G)为使图G为k-虹连通图的最小色数.本文考察了一类特殊图n-方体,在k=2时,有rC2(Qn)=max{4,n},n≥2.
-
关键词
边着色图
虹
k-虹连通
n-方体
-
Keywords
edge-colored graph
rainbow path
rainbow k-connectivity
n-cube
-
分类号
O157.5
[理学—基础数学]
-