| 【中文题名】 | 复合图的L（2，1）-标号 |
| 【英文题名】 | L(2, 1)-Labelings of Composite Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-3-2 |
| 【中关键词】 | 频道分配问题,L（2,1）-标号,复合图,1）-标号数, |
| 【英关键词】 | channel assignment problem,L（2,1）-labeling,L（2,1）-labeling number,composite graph, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 图G的L(2，1)-标号是一个从点集V(G)到非负整数集上的函数f，满足条件：(1)|f(u)-f(v)|≥2，若uv∈E(G)；(2)|f(u)-f(v)|≥1，若d(u，v)=2。图G的L(2，1)-标号数定义为：λ(G)=min_fmax{f(v)：v∈V(G)}。图G的L(2，1)-标号来自于频道分配问题：不同的电台要使用无线电波发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的频道资源。
通常情况下每个电台不止有一个频道，本文讨论了在每个电台不止有一个频道时的频道分配问题，建立的模型为复合图G[H_(v1)，H_(v2)，…，H_(v_m)]的L(2，1)-标号。图G中的点v_i代表电台，图H_(v_i)代表电台v_i中的频道。文章的第一章主要介绍了图的L(2，1)-标号的定义和一些基本的定理。
在第二章中，我们先得到了复合图的一些基本性质，接着通过构造一个算法对复合图中的子图H_i进行标号，由此说明了如果子图H_i的点数都等于n且没有洞，即图H_i的... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-9 |
|
第一章 引言 |
9-14 |
|
1.1 L(2,1)-标号的定义和背景 |
9-12 |
|
1.2 本文的主要工作 |
12-14 |
|
第二章 复合图的定义和基本性质 |
14-18 |
|
2.1 复合图的定义 |
14-15 |
|
2.2 复合图的L(2,1)-标号 |
15-18 |
|
第三章 复合图的L(2,1)-标号 |
18-32 |
|
3.1 G为路时复合图G[H]的L(2,1)-标号 |
18-20 |
|
3.2 G为树的复合图G[H]的L(2,1)-标号 |
20-25 |
|
3.3 G为圈的复合图的L(2,1)-标号 |
25-32 |
|
参考文献 |
32-34 |
|
第五章 致谢 |
34 |
|
| 【DOI】 | LunWen.ID:2.2008.11753 |
