图的L（d，1）-标号的边跨度

论文题目: 图的L（d，1）-标号的边跨度

论文类型: 硕士论文

论文专业: 运筹学与控制论

作者: 冯桂珍

导师: 宋增民

关键词: 频道分配问题,标号,标号着色数,边跨度,弦图,单位区间图,正三角形网格,正四边形网格,正六边形网格

文献来源: 东南大学

发表年度: 2005

论文摘要: 图G的标号着色L（2，1）-labeling是一个从顶点集V（G）到非负整数集的函数f，满足条件：（1）|f（u）-f（v）|≥2，若uv∈E（G）；（2）|f（u）-f（v）|≥1，若d（u，v）=2．将所有正常L（2，1）-标号的集合记作￡（2，1），图G的标号着色数定义为：λ（G）=min max{f（v）∶v∈V（G）}，即使图G所有正常的L（2，1）-标号的最大标号达到最小值。我们可以将这个概念推广到一般的情形L（d，1）-标号和L（s，t）-标号，相应的标号着色数分别记为λd（G）和λ（s，t）（G）。图的标号着色问题来自所谓的频道分配模型：不同的电台要使用无线频道发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的频道资源。本文主要研究该标号的另外一个参数，即边跨度，记做β（G）=min max{|f（u）-f（v）||uv∈v（G）}，其中f∈￡（2，1），即在所有的正常L（2，1）-标号中，使得相邻顶点的标号之差最大值达到最小值。同样我们可以求出L（d，1）-标号下的边跨度βd（G）和L（s，t）-标号下的边跨度β（s，t）（G）。对于部分图类，我们还给出了标号着色数限制下的边跨度，分别记作β（G，λ）和βd（G，λd）。在第二，三，四，五章中，我们分别讨论了Cn、T、Kn1，n2，…，nk、正三角形网格、正四边形网格、正六边形网格、轮Wn、路的强积图和弦图的边跨度。对于正六边形网格、轮、路的强积图和弦图，还给出了它们在标号着色数限制下的边跨度。

论文目录:

摘要

Abstract

第一章引言

1.1 标号着色的背景及定义

1.2 图的L(d，1)-labeling

1.3 图标号着色的跨度和边跨度

1.4 图论的基本符号与概念

第二章关于边跨度的基本结论

2.1 关于圈的边跨度

2.2 关于树和k部完全图的边跨度

第三章正则网格图的边跨度

3.1 正则网格的定义及基本结论

3.2 正三角形网格的边跨度

3.3 正四边形网格的边跨度

3.4 正六边形网格的边跨度

第四章轮W_n的边跨度

4.1 轮的定义以及基本结论

4.2 关于轮L(2，1)-标号的边跨度

4.3 关于轮L(d，1)-标号的边跨度

第五章路的强积图与弦图的边跨度

5.1 关于路的强积图L(2，1)-标号的边跨度

5.2 弦图的L(d，1)-标号以及相应的边跨度

致谢

参考文献

发布时间: 2007-06-11

参考文献

[1].图的L（2，1）-边标号[D]. 陈琴.东南大学2006
[2].复合图的L（2，1）-标号[D]. 时姝静.东南大学2006
[3].星与圈结合图奇优美标号的研究[D]. 张雪.哈尔滨工程大学2017
[4].几类图的（a，d）—H—和标号[D]. 朱东旭.河北师范大学2016
[5].关于某些图的超边幻和标号及其算法[D]. 何芳.安徽大学2014
[6].树的奇优美标号问题研究[D]. 刘施梁.华东师范大学2014
[7].图的非正常L（p，q）-标号和非正常L（p，1）-全标号的研究[D]. 孙丽娇.山东师范大学2013
[8].图的（d，1）-全标号及游戏着色[D]. 张焕.天津师范大学2011
[9].图的（d，1）-全标号问题[D]. 黄静.浙江师范大学2009
[10].图的L（2，1）-标号及其算法[D]. 叶林.浙江师范大学2009

图的L（d，1）-标号的边跨度

猜你喜欢