科研之友
微信
新浪微博
Facebook
分享链接
摘要
图的距离染色问题是频率分配问题的一种图模型，所谓的频率分配问题是指某一区域的不同电台要使用无线电波发送信号，为了避免干扰，位置较近的电台需要使用不同的频道，当电台距离特别近时，它们之间需要间隔至少2个信道。L (2,1)-边染色是指距离为1的两条边的色数差值大于等于2，距离大于1的两条边的色数不同。本文针对随机图设计了一种L (2,1)-边染色算法，实验结果表明，该算法能够解决有限点内随机图的L (2,1)-边染色问题。通过分析实验结果，发现了3类单圈图的染色特性，定义C3↑Pn↑Sm,Cn↓Sm和Cn↑Sm分别来刻画这三类单圈图，并给出相关定理及其证明。
- 单位
