本科生毕业论文.doc

本 科 生 毕 业 论 文 （申请学士学位） 论文题目 作者姓名 所学专业名称 指导教师 年 月 日  学 生： （签字） 学 号： 答 辩 日 期： 年 月 日 指 导 教 师 ： （签字） 目 录 摘要 1 Abstract 1 1. 绪论 2 1.1 背景和基本概念 2 1.2 已有相关结果 4 2. 哈密顿性和图的No-hole L(2,1)-标号 5 2.1 补图的哈密顿性 6 2.2 的图 7 3. 图的L(3,2,1)-标号 15 3.1 路和圈的L(3,2,1)-标号数 15 3.2 树的L(3,2,1)-标号数 20 3.3 一般图的L(3,2,1)-标号数 21 参考文献 23 致谢 24  图的顶点标号 摘要：给定一个无向图，的一个标号是指从其顶点集到非负整数集的一个映射，满足： 这里表示和之间的距离，即和之间最短路的长度。若一个标号中的所有标号都不超过整数，则称之为标号。图的标号数，记作，是使得图存在标号的最小整数。本文研究了一些图类的标号数，给出了该参数的一些上界。此外，本文还研究了标号的一种变形，图的标号问题。 关键词：频率设置问题；标号；标号；哈密顿图 Vertex Labelings on Graphs Abstract: For a given graph , an labeling is defined as a function : such that: where denotes the distance between and . A is an －labeling such that no label is greater than . The labeling number of , denoted by , is the smallest number such that has a . Thelabeling numbers of some classes of graphs are investigated and some upper bounds about this parameter are given. Moreover, as a transmogrification, thelabeling problem are also studied here. Key words: Channel assignment problem;labeling;labeling; Hamiltonian graph 1 绪 论 1736年是图论的元年，在这一年，Euler解决了一个当时困惑人们的著名问题——K?nigsberg七桥问题，从而使他成为图论和拓扑学创始人。当时的数学界并没有对Euler解决七桥问题的意义有足够的认识，甚至仅仅视其为一个数学游戏而已。图论诞生后没有及时获得足够的发展，直到1936年，匈牙利数学家K?nig出版《有限图与无限图理论》，这是图论的第一部专著，它总结了图论200年来的成果。从此，图论进入发展与突破的快车道。经过半个多世纪的发展，现已成为数学科学的一个独立的重要学科，它的分支很多，如图论，算法图论，极值图论，网络图论，代数图论，随机图论，拓扑图论，超图论等。不论那一支都是以图结构特征为研究的核心，因此对反映图的本质属性的参数的研究是十分活跃的研究方向。如图的着色数、控制数、覆盖数等。本文主要介绍图的一个重要参数——着色数。 1.1 背景和基本概念 图的顶点标号问题也就是图的顶点着色问题，在图论中有着很重要的地位。在Hale[1]将它引入到频率设置问题上之后再次引起了大家浓厚的兴趣。作为频率设置问题的一个变形，Griggs和Yeh[2]提出了标号问题。即给定一些发射台，要求给它们设置适当的频率——非负整数，使得“邻近”的发射台必须占用不同的频率值而“非常邻近”的发射台必须占用有间隔的频率值，以减小相互干扰。反映到图上，用图的顶点表示发射台，距离为2的点视为“邻近”，距离为1的点视为“非常邻近”。于是，无向图的一个标号是指从其顶点到非负整数集的一个映射，满足： 象集合中