关于图的两类标号问题的研究毕业论文.doc
约44页DOC格式手机打开展开
关于图的两类标号问题的研究毕业论文,摘 要图的标号问题起始于1966年a.rosa的著名的优美树猜想。一个图的顶点标号是图的顶点集到整数集的映射,而边标号则是图的边集到整数集的映射。根据对映射的不同要求,产生了各种类型的图的标号问题。本文对图skolem优美标号和调和标号两类问题进行研究,分别解决了这两类标号中的一些问题和猜想,取得了较好的结果。优美标号...
内容介绍
此文档由会员 白痴学东西 发布
摘 要
图的标号问题起始于1966年A.Rosa的著名的优美树猜想。一个图的顶点标号是图的顶点集到整数集的映射,而边标号则是图的边集到整数集的映射。根据对映射的不同要求,产生了各种类型的图的标号问题。本文对图Skolem优美标号和调和标号两类问题进行研究,分别解决了这两类标号中的一些问题和猜想,取得了较好的结果。
优美标号在射电天文学及计算机网络理论中有着广泛的应用。Skolem优美标号是优美标号的一个衍变。k-星图是由五个任意大小的星图组成的非连通图。对k-星图优美性,Kishore猜想当且仅当有一个星是偶星 时,k-星图是Skolem优美的。Choudum和Kishore等人证明了这个猜想 时成立。本文对任意的k-星图的Skolem优美性进行研究,针对k-星图和Skolem优美标号的特点,设计了相应的分支限界搜索策略。
调和标号是为解决纠错码的问题而由优美标号衍变而来的。徐士达证明了当且仅当 时,三角蛇图是调和图。本文证明了所有的双三角蛇图都是调和图。Deb和Limye提出猜想:所有的多贝壳图都是调和图,并证明了对平衡2贝壳图和平衡3贝壳图Deb猜想成立。杨元生等人证明了对平衡4贝壳图Deb猜想成立。本文证明了对平衡5贝壳图Deb猜想也成立。
关键词 Skolem优美标号 调和标号
Abstract
Graph labeling traces its origin to the famous conjecture that all trees are graceful presented by A.Rosa in 1996. Vertex labelling is a mapping from the vertex set to integer set. On the other hand, edge labeling maps edge set into integer set. According to the different requirements for the mapping, many variations of graph labelings have been evolved. In this paper, combining the computer constructure prove with mathematical prove, two classes of graph labelings: skolem graceful labeling and harmonious labeling are researched, some problems and conjectures have been solved redpectively.
Graceful labelings serves as useful models for a broad range of applications such as astronomy and communication networks. The Skolem graceful labelings have been invented analogues of graceful graphs by modifying the permissible vertex labels. The k-stars graph is a disjoint union of k stars with random size.
Hamonious labelings arise in the study of additive bases problems stemming from errorcorrecting codes. Xu Proved the triangular snake graph is harmonious if and only if .We prove all double triangular snake graphs are hamonious. Deb and Limy’s conjecture that all multiple shells are harmonious and have shown that the conjecture is true for the balanced double shells and balanced triple shells,Xu,Xi, and Qiao Proved the conjecture is true for balanced quadruple shells.
Key Words skolem graceful labeling harmonious labeling
目 录
摘 要 Ⅰ
Abstract Ⅱ
第1章 绪 论 1
1.1 图论的基本概念及相关知识 1
1.2 标号问题的研究现状 3
1.2.1 优美标号 3
1.2.2 调和标号 4
1.3 本文工作 6
第2章 图的优美标号 8
2.1优美标号的相关概念及发展概况 8
2.1.1 优美图的相关概念 8
2.1.2 优美图的发展概况 9
2.2 图的Skolem优美标号 12
2.2.1 k-星图的Skolem优美标号 12
2.3 小 结 19
第3章 图的调和标号 20
3.1 调和标号的相关概念及发展概况 20
3.1.1 调和图的相关概念 20
3.1.2 调和图的发展概况 21
3.2 双三角蛇图的调和标号 22
3.3 平衡5贝壳图的调和标号 26
3.4 小 结 32
结 论 33
致 谢 34
参 考 文 献 35
附录1 37
附录2 42
图的标号问题起始于1966年A.Rosa的著名的优美树猜想。一个图的顶点标号是图的顶点集到整数集的映射,而边标号则是图的边集到整数集的映射。根据对映射的不同要求,产生了各种类型的图的标号问题。本文对图Skolem优美标号和调和标号两类问题进行研究,分别解决了这两类标号中的一些问题和猜想,取得了较好的结果。
优美标号在射电天文学及计算机网络理论中有着广泛的应用。Skolem优美标号是优美标号的一个衍变。k-星图是由五个任意大小的星图组成的非连通图。对k-星图优美性,Kishore猜想当且仅当有一个星是偶星 时,k-星图是Skolem优美的。Choudum和Kishore等人证明了这个猜想 时成立。本文对任意的k-星图的Skolem优美性进行研究,针对k-星图和Skolem优美标号的特点,设计了相应的分支限界搜索策略。
调和标号是为解决纠错码的问题而由优美标号衍变而来的。徐士达证明了当且仅当 时,三角蛇图是调和图。本文证明了所有的双三角蛇图都是调和图。Deb和Limye提出猜想:所有的多贝壳图都是调和图,并证明了对平衡2贝壳图和平衡3贝壳图Deb猜想成立。杨元生等人证明了对平衡4贝壳图Deb猜想成立。本文证明了对平衡5贝壳图Deb猜想也成立。
关键词 Skolem优美标号 调和标号
Abstract
Graph labeling traces its origin to the famous conjecture that all trees are graceful presented by A.Rosa in 1996. Vertex labelling is a mapping from the vertex set to integer set. On the other hand, edge labeling maps edge set into integer set. According to the different requirements for the mapping, many variations of graph labelings have been evolved. In this paper, combining the computer constructure prove with mathematical prove, two classes of graph labelings: skolem graceful labeling and harmonious labeling are researched, some problems and conjectures have been solved redpectively.
Graceful labelings serves as useful models for a broad range of applications such as astronomy and communication networks. The Skolem graceful labelings have been invented analogues of graceful graphs by modifying the permissible vertex labels. The k-stars graph is a disjoint union of k stars with random size.
Hamonious labelings arise in the study of additive bases problems stemming from errorcorrecting codes. Xu Proved the triangular snake graph is harmonious if and only if .We prove all double triangular snake graphs are hamonious. Deb and Limy’s conjecture that all multiple shells are harmonious and have shown that the conjecture is true for the balanced double shells and balanced triple shells,Xu,Xi, and Qiao Proved the conjecture is true for balanced quadruple shells.
Key Words skolem graceful labeling harmonious labeling
目 录
摘 要 Ⅰ
Abstract Ⅱ
第1章 绪 论 1
1.1 图论的基本概念及相关知识 1
1.2 标号问题的研究现状 3
1.2.1 优美标号 3
1.2.2 调和标号 4
1.3 本文工作 6
第2章 图的优美标号 8
2.1优美标号的相关概念及发展概况 8
2.1.1 优美图的相关概念 8
2.1.2 优美图的发展概况 9
2.2 图的Skolem优美标号 12
2.2.1 k-星图的Skolem优美标号 12
2.3 小 结 19
第3章 图的调和标号 20
3.1 调和标号的相关概念及发展概况 20
3.1.1 调和图的相关概念 20
3.1.2 调和图的发展概况 21
3.2 双三角蛇图的调和标号 22
3.3 平衡5贝壳图的调和标号 26
3.4 小 结 32
结 论 33
致 谢 34
参 考 文 献 35
附录1 37
附录2 42