关于标号类论文范本,与本科生毕业文相关论文格式

本论文是一篇关于标号类论文格式,关于本科生毕业文相关本科论文范文。免费优秀的关于标号及参考文献及物流管理方面论文范文资料,适合标号论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

本科生毕业论文(或设计)

(申请学士学位)

论文题目图的顶点标号

作者姓名XXX

专业名称数学与应用数学

指导教师XX

2016年6月

学生:(签字)

学号:5060352041

论文答辩日期:2016年x月xx日

指导教师:(签字)

目录

摘 要1

Abstract1

1.绪论2

1.1背景和基本概念2

1.2已有相关结果4

2.哈密顿性和图的No-holeL(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

图的顶点标号

摘 要:给定一个无向图,的一个标号是指从其顶点集到非负整数集的一个映射,满足:

这里表示和之间的距离,即和之间最短路的长度.若一个标号中的所有标号都不超过整数,则称之为标号.图的标号数,记作,是使得图存在标号的最小整数.本文研究了一些图类的标号数,给出了该参数的一些上界.此外,本文还研究了标号的一种变形,图的标号问题.

关 键 词:频率设置问题,标号,标号,哈密顿图

VertexLabelingsonGraphs

Abstract:Foragivengraph,anlabelingisdefinedasafunction:suchthat:

wheredenotesthedistancebetweenand.Aisan-labelingsuchthatnolabelisgreaterthan.Thelabelingnumberof,denotedby,isthesmallestnumbersuchthathasa.Thelabelingnumbersofsomeclassesofgraphsareinvestigatedandsomeupperboundsaboutthisparameteraregiven.Moreover,asatransmogrification,thelabelingproblemarealsostudiedhere.

Keywords:Channelassignmentproblem,labeling,labeling,Hamiltoniangraph

1绪论

1736年是图论的元年,在这一年,Euler解决了一个当时困惑人们的着名问题——Knigsberg七桥问题,从而使他成为图论和拓扑学创始人.当时的数学界并没有对Euler解决七桥问题的意义有足够的认识,甚至仅仅视其为一个数学游戏而已.图论诞生后没有及时获得足够的发展,直到1936年,匈牙利数学家Knig出版《有限图与无限图理论》,这是图论的第一部专着,它总结了图论200年来的成果.从此,图论进入发展与突破的快车道.经过半个多世纪的发展,现已成为数学科学的一个独立的重要学科,它的分支很多,如图论,算法图论,极值图论,网络图论,代数图论,随机图论,拓扑图论,超图论等.不论那一支都是以图结构特征为研究的核心,因此对反映图的本质属性的参数的研究是十分活跃的研究方向.如图的着色数,控制数,覆盖数等.本文主要介绍图的一个重要参数——着色数.

1.1背景和基本概念

图的顶点标号问题也就是图的顶点着色问题,在图论中有着很重要的地位.在Hale[1]将它引入到频率设置问题上之后再次引起了大家浓厚的兴趣.作为频率设置问题的一个变形,Griggs和Yeh[2]提出了标号问题.即给定一些发射台,要求给它们设置适当的频率——非负整数,使得"邻近"的发射台必须占用不同的频率值而"非常邻近"的发射台必须占用有间隔的频率值,以减小相互干扰.反映到图上,用图的顶点表示发射台,距离为2的点视为"邻近",距离为1的点视为"非常邻近".于是,无向图的一个标号是指从其顶点到非负整数集的一个映射,满足:

象集合中的元素称为标号.若一个标号中的所有标号都不超过整数,则称之为标号.图的标号数,记作,是使得图存在标号的最小整数.特别地,若的某个标号中的标号是连续出现的,则称之为的一个No-hole标号.图的No-hole标号数,记作,是使得图存在No-hole标号的最小整数.我们的目标是确定各类图的和的值或上界.

除此之外,频率设置问题还有其他一些变形,如No-hole,No-hole,标号以及有向图的标号等.由于这些问题有非常重要的应用价值,从而吸引了国内外很多知名学者.如G.J.Chang,J.R.Griggs,R.K.Yeh,D.D.F.Liu,P.C.Fishburn,R.S.Roberts,D.Sakai,J.P.Gees,D.W.Mauro和M.Whittlesey等,他们在这方面做了大量的工作[1-22],有很多优美的结果和巧妙的研究方法.同时他们也提出了许多值得思考的问题,如J.R.Griggs和R.K.Yeh的猜想:对任何最大度的图,,这里表示的顶点的最大度.这个猜想被后来学者不断接近但至今仍未被解决或推翻.

1.2已有相关结果

在[2]中,J.R.Griggs和R.K.Yeh给出了阶路,圈,轮图的值,以及阶超方图,可着色图的值的上界.值和图的阶数有关,当然也和图的边数有关.于是他们还考虑了值和图的最大度的直接联系并得到以下结果和猜想:(1)对于的树,或,(2)对3连通图,,(3)对直径为2的图,,(4)对一般图,,(5)猜想对任何的图,.D.Sakai[19]证明了对弦图,,从而符合上述猜想.在[12]中,G.J.Chang和D.Kuo非常巧妙的证明了对一般图,.Král和krekovski[26]又稍做改进,证明了对任何的图有,.

由定义不难知道,若存在No-hole标号,则.为建立No-hole标号的存在性,J.P.Gees,D.W.Mauro以及M.Whittlesey[14]证明了当且仅当存在哈密顿路.P.C.Fishburn和F.S.Roberts[7]又证明了存在No-hole标号当且仅当,并且他们还给出了几类的图.

对频率设置问题的其他一些变形,如No-hole,No-hole,Circular标号等,其他文献也都研究了它们的性质,并且对一些图类给出了相应的着色数的值或界.

2哈密顿性和图的No-holeL(2,1)-标号

给定一个无向图,的一个标号是指从其顶点集到非负整数集的一个映射,满足:

这里表示和之间的距离,即和之间最短路的长度.若一个标号中的所有标号都不超过整数,则称之为.图的数,记作,是使得图存在labeling的最小整数.特别地,若的某个labeling中的标号是连续出现的,则称之为的一个No-hole.图的No-hole数,记作,是使得图存在No-holelabeling的最小整数.

自从labeling问题被提出,No-holelabeling作为它的一个变形也受到了广泛研究.由定义我们知道,若存在No-holelabeling则.

在这一章中,我们将注意力放在了不等式的另一侧.我们首先根

1 2 下一页

关于标号类论文范本,与本科生毕业文相关论文格式参考文献资料：

如何写一篇论文

写不出论文

议论文怎么写好

被骗

怎样写出高考满分作文

高考写人满分作文

写论文的技巧

博士论文好写吗

论文结尾怎么写

替写论文