您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (8): 63-72.doi: 10.6040/j.issn.1671-9352.0.2021.513

•   • 上一篇    下一篇

几类联图的L(2, 1)-边染色算法研究

朱利娜(),李敬文*(),孙帅   

  1. 兰州交通大学电子与信息工程学院，甘肃 兰州 730070
  • 收稿日期:2021-08-17 出版日期:2023-08-20 发布日期:2023-07-28
  • 通讯作者: 李敬文 E-mail:3072039233@qq.com;lijingwen28@163.com
  • 作者简介:朱利娜(1996—), 女, 硕士研究生, 研究方向为图论算法及其应用. E-mail: 3072039233@qq.com
  • 基金资助:
    甘肃省科技计划项目(21ZD8RA008)

L(2, 1)- edge coloring algorithm for several kinds of composite graphs

Lina ZHU(),Jingwen LI*(),Shuai SUN   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Received:2021-08-17 Online:2023-08-20 Published:2023-07-28
  • Contact: Jingwen LI E-mail:3072039233@qq.com;lijingwen28@163.com

RichHTML

3

PDF (PC)

119

摘要：

本文针对随机图设计了一种L(2, 1)-边染色算法，实验结果证明，该算法能够解决有限点内随机图的L(2, 1)-边染色问题。通过分析实验结果发现了5类联图的染色特性，定义Fn↑Sm、Cn↑Cm、Fn(2)、C3(n)↑Sm和Cn(m)分别来刻画这5类联图，并给出了相关定理及证明。

关键词: L(2, 1)-边染色, 色数, 联图, 算法

Abstract:

An L(2, 1)- edge coloring algorithm is designed to solve the L(2, 1)- edge coloring for random graphs. By analyzing the experimental results, the coloring properties of five classes of join graphs are found, and Fn↑Sm、Cn↑Cm、Fn(2)、C3(n)↑Sm and Cn(m) are used to describe these graphs. The related theorems and proofs are given as well.

Key words: L(2, 1)- edge coloring, chromatic number, composite graphs, algorithm

中图分类号: 

  • O157.5

图1

图G↑H示例图"

图2

Cn(m)示例图"

表1

11个点以内随机图的L(2, 1)-边染色统计"

染色跨度 点数
3 4 5 6 7 8 9 10
Δ+1 0 2 3 2 2 2 5 4
Δ+2 1 2 7 17 32 63 122 290
Δ+3 0 1 7 30 98 289 872 2 740
Δ+4 0 1 2 28 146 649 2 916 12 664
Δ+5 0 0 2 15 136 1 037 6 431 39 338
Δ+6 0 0 0 9 140 1 350 12 252 99 986
Δ+7 0 0 0 6 111 1 553 18 727 207 699
Δ+8 0 0 0 3 90 1 659 25 206 368 272
Δ+9 0 0 0 1 51 1 456 29 834 578 938
Δ+10 0 0 0 1 30 1 106 32 771 824 978
Δ+11 0 0 0 0 7 797 31 555 1 059 707
Δ+12 0 0 0 0 6 506 28 313 1 218 095
Δ+13 0 0 0 0 2 327 22 872 1 278 529
Δ+14 0 0 0 0 0 156 17 606 1 244 017
Δ+15 0 0 0 0 1 83 12 084 1 146 528
Δ+16 0 0 0 0 12 48 8 128 997 517
Δ+17 0 0 0 0 0 18 5 090 830 287
Δ+18 0 0 0 0 0 9 3 037 687 759
Δ+19 0 0 0 0 0 5 1 709 570 315
Δ+20 0 0 0 0 0 2 915 426 317
Δ+21 0 0 0 0 0 1 375 259 821
Δ+22 0 0 0 0 0 15 154 149 071
Δ+23 0 0 0 0 0 0 65 95 342
Δ+24 0 0 0 0 0 0 24 55 577
Δ+25 0 0 0 0 0 0 8 28 543
Δ+26 0 0 0 0 0 0 5 15 130
Δ+27 0 0 0 0 0 0 2 5 514
Δ+28 0 0 0 0 0 0 1 1 416
Δ+29 0 0 0 0 0 0 1 515
Δ+30 0 0 0 0 0 0 0 179
Δ+31 0 0 0 0 0 0 0 75
Δ+32 0 0 0 0 0 0 0 27
Δ+33 0 0 0 0 0 0 0 9
Δ+34 0 0 0 0 0 0 0 5
Δ+35 0 0 0 0 0 0 0 2
Δ+36 0 0 0 0 0 0 0 1
Δ+37 0 0 0 0 0 0 0 1
图总数 1 6 21 112 853 11 117 261 080 12 205 208

图3

Fn↑Sm染色举例"

图4

Cn↑Cm染色举例"

图5

Fn(2)染色举例"

图6

C3(4)↑S5染色举例"

图7

Cn(m)(3≤n≤6)染色举例"

1 HALE W K . Frequency assignment: theory and applications[J]. Proceedings of the IEEE, 1980, 68, 1497- 1514.
doi: 10.1109/PROC.1980.11899
2 GRIGGS J R , YEH R K . Labelling graphs with a condition at distance 2[J]. SIAM Journal on Discrete Mathematics, 1992, 5 (4): 586- 595.
doi: 10.1137/0405048
3 陈琴. 图的L(2, 1)-边标号[D]. 南京: 东南大学, 2006.
CHEN Qin. L(2, 1)-Edge-labeling of graphs[D]. Nanjing: Southeast University, 2006.
4 ASLAN S . A comparative study between artificial bee colony (ABC) algorithm and its variants on big data optimization[J]. Memetic Computing, 2020, 12 (2): 129- 150.
doi: 10.1007/s12293-020-00298-2
5 CHEN Q , LIN W S . L(j, k)-labelings and L(j, k)-edge-labelings of graphs[J]. ARS Combinatoria -Waterloo Then Winnipeg-, 2012, 106, 161- 172.
6 孙帅, 李敬文, 袁清厚. 随机图的L(2, 1)-标号混合人工蜂群算法[J]. 武汉大学学报(理学版), 2021, 67 (2): 158- 164.
SUN Shuai , LI Jingwen , YUAN Qinghou . A hybrid artificial bee colony algorithm for L(2, 1)-labelling of random graph[J]. Journal of Wuhan University (Natural Science Edition), 2021, 67 (2): 158- 164.
[1] 卢健伟,任济洲,关杰. 广义SIMON类轮函数的密码学性质研究[J]. 《山东大学学报(理学版)》, 2023, 58(9): 51-58.
[2] 房明磊,丁德凤,王敏,盛雨婷. 一种求解非线性方程组的改进Shamanskii-like Levenberg-Marquardt算法[J]. 《山东大学学报(理学版)》, 2023, 58(8): 118-126.
[3] 刘海燕,拓守恒. 求解全局优化问题的一个新的填充函数算法[J]. 《山东大学学报(理学版)》, 2023, 58(7): 80-87.
[4] 徐华畅,许倩,赵钰琳,梁峰宁,徐凯,朱红. 基于改进EfficientNetV2的脑胶质瘤IDH1突变状态预测方法[J]. 《山东大学学报(理学版)》, 2023, 58(7): 60-66.
[5] 张金珂,张建刚. 基于改进粒子群优化算法的信号检测及故障诊断[J]. 《山东大学学报(理学版)》, 2023, 58(5): 63-75.
[6] 任师贤,安静. 球域上传输特征值问题的一种有效的谱逼近[J]. 《山东大学学报(理学版)》, 2023, 58(4): 8-15.
[7] 陈晶晶,杨延涛. 解变分不等式与不动点问题的一种修正的惯性投影算法[J]. 《山东大学学报(理学版)》, 2023, 58(3): 64-76.
[8] 兰琳钰,李敬文,张树成,张丽景,申化玉. 图的点可约全标号算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(11): 135-146.
[9] 仲诚诚,周恒,张梓童,张春雷. LAC-UNet:基于胶囊表达局部-整体特征关系的语义分割模型[J]. 《山东大学学报(理学版)》, 2023, 58(11): 116-126.
[10] 陈淑珍,李守伟,史开泉. 证据推理与检索数据网络安全获取[J]. 《山东大学学报(理学版)》, 2023, 58(1): 1-9.
[11] 梁云,门昌骞,王文剑. 基于模型决策树的AdaBoost算法[J]. 《山东大学学报(理学版)》, 2023, 58(1): 67-75.
[12] 李守伟,史开泉. 逆分离模糊集合((-overA)F,(-overA)(-overF))与模糊信息安全获取[J]. 《山东大学学报(理学版)》, 2022, 57(9): 1-14.
[13] 郭精军,汪育兵,白亚楠. 混合分形Heston-CIR模型下的美式期权定价及模拟[J]. 《山东大学学报(理学版)》, 2022, 57(9): 46-54.
[14] 刘云,宋凯,陈路遥,朱鹏俊. 均衡评估算法对基于区块链的无线传感网节点信任管理优化[J]. 《山东大学学报(理学版)》, 2022, 57(7): 73-84.
[15] 赵亚迪,陈祥恩. m个长为14的圈的不交并的点可区别Ⅰ-全染色[J]. 《山东大学学报(理学版)》, 2022, 57(6): 54-60.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .
[2] 田学刚, 王少英. 算子方程AXB=C的解[J]. J4, 2010, 45(6): 74 -80 .
[3] 霍玉洪,季全宝. 一类生物细胞系统钙离子振荡行为的同步研究[J]. J4, 2010, 45(6): 105 -110 .
[4] 唐风琴1,白建明2. 一类带有广义负上限相依索赔额的风险过程大偏差[J]. J4, 2013, 48(1): 100 -106 .
[5] 程智1,2,孙翠芳2,王宁1,杜先能1. 关于Zn的拉回及其性质[J]. J4, 2013, 48(2): 15 -19 .
[6] 汤晓宏1，胡文效2*，魏彦锋2，蒋锡龙2，张晶莹2，. 葡萄酒野生酿酒酵母的筛选及其生物特性的研究[J]. 山东大学学报（理学版）, 2014, 49(03): 12 -17 .
[7] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[8] 杨永伟1,2,贺鹏飞2,李毅君2,3. BL-代数的严格滤子[J]. 山东大学学报（理学版）, 2014, 49(03): 63 -67 .
[9] 李敏1,2,李歧强1. 不确定奇异时滞系统的观测器型滑模控制器[J]. 山东大学学报（理学版）, 2014, 49(03): 37 -42 .
[10] 何海伦， 陈秀兰*. 变性剂和缓冲系统对适冷蛋白酶MCP-01和中温蛋白酶BP-01构象影响的圆二色光谱分析何海伦， 陈秀兰*[J]. 山东大学学报（理学版）, 2013, 48(1): 23 -29 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发