文章摘要
优雅图猜想
The conjecture of Elegant graph
投稿时间:2018-01-02  修订日期:2018-03-02
DOI:
中文关键词: 优雅标号  优雅图  非优雅图  优雅空间  优雅图猜想
英文关键词: elegant labeling  elegant graphs  non elegant graphs  elegant spaces  elegant graphs conjectures
基金项目:国家自然科学基金,国家自然科学基金项目(面上项目,重点项目,重大项目)
作者单位E-mail
赵科 兰州交通大学 794292116@qq.com 
李敬文 兰州交通大学 lijingwen28@163.com 
摘要点击次数: 160
全文下载次数: 
中文摘要:
      Chang,Hsu,and Rogers在1981年提出了优雅标号的概念。对于给定的图G(p,q),如果存在一个单射f:V(G)→[0,1,2,…q],使得边标号集合f(E(G) )={f(uv)=(f(u )+f(v ))mod(q+1)|uv∈E(G) }=[1,…q],则称图G为优雅图(Elegant graph),f为图G的一个优雅标号。图的标号广泛应用于计算机科学、网络、有机化学、机器学习等多个领域。本文采用剪枝与预判函数相结合的方式,设计了递归回溯算法,对9个点内的所有简单连通图进行优雅性验证,得到所有优雅图和非优雅图的数量,结果表明,绝大多数的图是优雅的。根据实验结果,文中给出优雅树的一个定理,优雅图的二个定理和三个猜想。
英文摘要:
      Chang, Hsu, and Rogers proposed the concept of elegant labeling in 1981. For a given (p, q) - graph G, if there exists an injective functionf:V(G)→[0,1,2,…q],such that the set of edge labelsf(E(G) )={f(uv)=(f(u)+f(v) )mod(q+1)|uv∈E(G) }=[1…q],The graph G is called an elegant graph, and f is an elegant label of graph G. The label is widely used in computer science, networking, organic chemistry, machine learning and other fields. In this paper, a combination of pruning and predictive function is used to design a recursive backtracking algorithm, The elegantness of all the simple connected graphs in 9 points was verified, and the numbers of all the elegant and non-elegant graphs were obtained. The result showed that most of the graphs were elegant. According to the experimental results, an elegant tree theorem, two elegant graph theorems and three elegant graph conjectures are given.
View Fulltext   查看/发表评论  下载PDF阅读器
关闭