英特尔线程挑战赛3月题目 - 优美图问题的背景介绍

zm0011 2008-03-22 04:06:10


图论中关于“优美图”的研究课题是本世纪60年代提出来的,它一出现就引起了图论研究者们的极大兴趣,取得了不少成果,但至今仍未完全解决。J·A·Bondy 将它作为50个难题的第15个难题收列于“Graph Theory WithApplications”(有中译本)一书末。

优美图的研究是从1963年G.Ringel的一个猜想引起的,G.Ringel猜想:设T是一个给定的n个顶点,n-1条边的树,那么由K2n-1可以分解出2n-1个树同构于T。

G.Ringel猜想至今没有被证明或否定。它的证明与优美树猜想有关,A.Rosa指出了这一点。1966年,A.Rosa猜想:所有的树都是优美的!这就是著名的优美树猜想。这个猜想至今没有被完全证明或否定,不过有几类树已经被证明是优美的。1972年S.W.Golomb明确给出了优美图的定义。近几年来,国内外获得了不少研究成果,并在编码理论,x射线晶体学,雷达、通讯网络,射电天文学中得到了初步应用。由于优美图总是对简单图而言的,所以这里提到的图均指简单图。


【优美图的定义】:
对于一个图 G = (V, E) ,如果对每一个v ∈V,存在一个非负数θ(v)(称为顶点v的标号)使满足:

(1) ∨ u,v ∈V 如果u≠v,则θ(u)≠θ(v);
(2) max{θ(v) | v ∈V} = |E|;
(3) ∨ e1,e2 ∈E,如果e1≠e2,则θ'(e1)≠θ'(e2),其中θ'(e) = |θ(u)-θ(v)|,e = uv 。

则称G为优美图(graceful graph)。称θ为G的一个优美值,或称为优美标号(graceful labeling)。


上面是对优美图的精确的数学定义,也是判定一个优美图的三个充要条件。对这个定义的通俗易读的解释,就是英特尔线程挑战赛3月题目的描述性文字。

关于优美图的论文在互联网上不计其数,百度GOOGLE一搜一大堆。

这里罗列一些,仅供大家参考。
____________________________________________________________________________________

唯一的一本专门论述优美图的中文出版书:

书名: 《优美图》
作者: 马克杰编著
出版社: 北京大学出版社
出版日期: 1991-10-01
出版地:北京
ISBN: 9787301015438
价格: 4.50
简介: 优美图是图论中极有趣的重要内容,有着较好的应用价值和广 阔 的研究前。作者以多年的科研经验,系统地总结了国内外优美图研究的重要成果,并提了新的研究问题和研究方向,为从事优美图研究的人员和图论爱好 者提供了量的前沿信息。全书共分七章,内容包括:图的基本知识,忧美图的 概 念、质和应用等。

____________________________________________________________________________________

树的邻接向量与优美树猜想的微机证明
周尚超
  本文引入了树的邻接向量的概念,用微机证明阶数≤20的树都是优美树.
【关键词】:图;树;向量;优美图;微型计算机
【基金】:江西省自然科学基金资助
【分类号】:O157.5
【DOI】:cnki:ISSN:10050523.0.1996-03-012
【正文快照】:
  树的邻接向量与优美树猜想的微机证明周尚超(基础课部)摘要本文引入了树的邻接向量的概念,用微机证明阶数≤20的树都是优美树.关键词图;树;向量;优美图;微型计算机分类号0157.50引言本文所指的图G一(V,E)均为无向简单图.V-V(G)和E-E(G)分

____________________________________________________________________________________

置换与优美树谱
朱勇,王卫华,王展青
  研究置换与优美树的关系,得到在n阶标号优美树集与(n-2)阶优美置换的一个子集之间存在着一一对应的结论。依据这一结论构造出n阶优美树谱
【作者单位】:武汉汽车工业大学教务处
【关键词】:图;树;优美树;置换
【分类号】:O157.5
【DOI】:cnki:ISSN:1007-144X.0.1997-02-018
【正文快照】:
  置换与优美树谱朱勇王卫华王展青(基础课部)摘要研究置换与优美树的关系,得到在n阶标号优美树集与(n-2)阶优美置换的一个子集之间存在着一一对应的结论。依据这一结论构造出n阶优美树谱。


____________________________________________________________________________________

优美树的优美标号
姚兵;程辉
  本文着重探讨了优美树的优美对偶标号函数、泛优美标号函数及可广义优美标号函数。得到“任何树T皆含有优美子树H,并且D(T)=D(H)、△(T)=△(H)”的结论。给出了几种构造优美树的方法。


____________________________________________________________________________________

优美树求解的表上作业法
朱明奎
  本文提出一种求解优美树的表上作业法,并编制了求解程序.结出了N≤14的有关结果.

____________________________________________________________________________________

图2 C4忌U P 优美性的一些结果
宋庆华,段滋明
(中国矿业大学理学院,江苏徐州 221008)
摘要:对两个圈与路的不交并图2C4tUP 的优美性进行研究,构造性地给出了n一2五+2,4五,4五+ 2,4五+4时2C4。
UP 的优美标号,证明了它们的优美性.
关键词 优美性;圈;路;图;标号
中闰分类号:O157.5 文献标识码:A 文章编号:1007—6573(2003)03—0018—05
O 引言
图论中一个比较有趣的问题是所谓的图标号问题.优美标号是图标号问题中首先提出的一类,到目
前为止,已有数十种标号定义,如协调标号、边幻标号、序列标号等.图标号理论在编码理论、同步机码、
X射线结晶学、雷达脉冲码、天文学、导弹控制码、通讯网络、循环设计理论等领域内有着广泛的应用.
对图优美性的研究已经取得了很多成果[1 ].自1975年Kotzig首先考虑了两个图之并,即不连通
图的优美性以来,人们在这方面做了大量的研究,主要有路与路之并、路与圈之并、圈与圈之并、星与星
之并等的优美性问题.下面首先介绍优美图的定义.
____________________________________________________________________________________

一类包含优美树的优美图
唐保祥
  设T_m是m个顶点的优美树,G_n是n个顶点的空留,证明了联图G_nVT_m是优美图.

____________________________________________________________________________________

2类包含K_4的优美图及其注记
唐保祥
  利用计算机为辅助工具,分别给出了2类包含图K4的图K4+Gn+1和K4+Kn,n的优美标号,从而证明了图K4+Gn+1和K4+Kn,n是优美图,并由K4+Kn,n的优美性给出了边数为m的极小优美图的顶点数f(m)的范图是{(1+8m+1)/2}≤f(m)≤{2(m+3-1)}.
【作者单位】:天水师范学院 数学系 甘肃 天水  741001

____________________________________________________________________________________

关于优美图Bodendiek猜想的一种推广
陈志增
  <正> Bodendiek猜想一个圈加一条弦是优美图。已由[1][2]和[3]给出证明。本文以矩阵为工具,证明了该猜想的一种推广:连结两个顶点的三条独立路所成简单图,在一定条件下是优美的。
【DOI】:cnki:ISSN:1001-8735.0.1987-01-000
【正文快照】:
  Bodendiek猜想一个圈加一条弦是优美图。己由〔1〕L名〕和〔3〕给出证明。阵为工具,证明了该猜想的一种推广:连结两个顶点的三条独立路所成简单图,件一I.’是优美的。本文以矩在一定条如预备知识 首先罗列出有关概念。

____________________________________________________________________________________

优美图的若干问题研究
优美图是图论中的一个极其有趣且重要的研究课题,有着较好的应用价值和广阔的研究前景。由于其本身研究的多样性特点,也使得研究者们纷纷沉醉于其中。本篇论文主要研究了几类特殊图的优美性,讨论了广义仙人掌及其γ—冠图和几类偶图及偶图并图的优美性。 本文的主要内容及研究成果如下: 在第一章中,主要介绍了图和优美图的基本概念及其应用,阐述了优美图的历史与现状,概述了本文的主要研究成果。 在第二章中,主要研究了两类广义仙人掌ω_(m_1,m_2,…,m_n)和ω_(m_1,m_2,…,m_n,m_(n+1))的优美性,分别给出了ω_(m_1,m_2,…,m_n)和ω_(m_1,m_2,…,m_n,m_(n+1))(其中m_1,M_2,…,m_n≡0(mod4),m_(n+1)≡3(mod4))的新优美标号,并证明了在这种新标号下ω_(m_1,m_2,…,m_n)和ω_(m_1,m_2,…,m_n,m_(n+1))是优美图,且ω_(m_1,m_2,…,m_n)为交错图;所得结论不同于付明彦、李春香等人的研究结果。 在第三章中,分别研究了图ω_(m,n)在m,n≡0(mod...

____________________________________________________________________________________

优美图中几个问题的研究

优美图在X-射线晶体学,雷达、通讯网络、编码及射电天文学有重要的应用价值,因而优美图的研究仍然是图论中活跃的课题之一。另外,解决优美图需要一些特别的技巧和灵活多样的方法,因此为图论其他分支的研究提供了一些建设性的和有价值的方法。同时作为一类实际问题的抽象,有实际应用价值和理论基础研究价值。本文正是研究优美图中的几个问题。 在Rosa给出了一个欧拉图的特殊图类C_n是优美图的必要和充分条件之后,冯成进在1983年给出了回路C_m和C_n恰有一个公共点所组成的图ω_(m,n)是优美图的充要条件。本文在第三章首先证明了:将n个C_(m_i)依次串起来,使两两之间恰有一个公共点的图ω_(m_1,m_2,…,m_n)(m_1≡0(mod4),i=1,2,…,n)是优美的。之后,在此基础上做了进一步推广,证明了ω_(m_1,m_2,…,m_n,m_(n+1))(m_i≡0(mod4),m_(n+1)≡3(mod4),i=1,2,…,n)(ω_(m_1,m_2,…,m_n,m_(n+1))是在原图ω_(m_1,m_2,…,m_n)之上又串了一个回路C_(n+1)(n+1≡3(mod4)))也是优美的。

____________________________________________________________________________________


优美图的扩充
徐保根
  本文主要介绍几种优美图的扩充方法,并以此来判断某些图的优美性。
【关键词】:优美图;扩充;优美值
【分类号】:O157.5
【DOI】:cnki:ISSN:10050523.0.1994-03-008
【正文快照】:
  优美图的扩充徐保根(基础课部)摘要本文主要介绍几种优美图的扩充方法,并以此来判断某些图的优美性。

____________________________________________________________________________________


优美图Bodendiek猜想的证明
陈志增
  <正> Bodendiek猜想一个圈加一条弦是优美图。已由[1]和[2]给出证明。本文以矩阵为工具,给出该猜想的另一种证明,并证明了该猜想的一种推广。
【DOI】:cnki:ISSN:1001-8735.0.1986-03-000
【正文快照】:
  Bodendiek猜想一个圈加一条弦是优美图。已由〔1]和〔幻给出证明。本文以矩阵为工具,给出该猜想的另一种证明,并证明了该猜想的一种推广。 且1双备知识 假如对于简单图‘(犷,E),V成犷,赋予一个非负整数甲(的,则称图G是标定的,甲(的称为顶点v的标号,}甲(u)一卿(的!称为棱如的标

____________________________________________________________________________________

关于优美树研究方法的探讨
孟凡洪,常丹,王辉
  归纳总结了优美树研究的几种常见方法,给出了基变换定理,对树的优美性的研究及Rosa猜想(每棵树都是优美的)的证明提供了一些有益的工具

____________________________________________________________________________________
关于优美图的计算机算法 马旭东

(国内的垃圾论文太多了,大都是为了评职称)



...全文
740 5 打赏 收藏 转发到动态 举报
写回复
用AI写文章
5 条回复
切换为时间正序
请发表友善的回复…
发表回复
zm0011 2008-03-25
  • 打赏
  • 举报
回复
重新上传了程序文件:

http://d.download.csdn.net/down/394716/zm0011
茶禅如水 2008-03-24
  • 打赏
  • 举报
回复
找到这么多资料!
相当佩服你,
祝你取得好成绩。
zm0011 2008-03-24
  • 打赏
  • 举报
回复
θ(v)应该是非负整数,这是个前提条件。

有人把paley17的计算时间缩短到300多秒,我的程序没这么快。也许再多一天的时间能找到一个更好的算法。

我把从INTEL论坛上收集的测试数据和自己的程序打包上传在:http://download.csdn.net/source/393521

有兴趣的同学可自己试试。

祝各位取得好成绩。
zhangvy 2008-03-23
  • 打赏
  • 举报
回复
阁下的解释更为精确,尤其是提到
max{θ(v) ¦ v ∈V} = ¦E ¦
这一点在英特尔线程挑战赛3月题目的描述中并未提到。

另外,θ(v)应该是非负整数吧。

感谢您提供的参考资料!对这个问题我思考了很长时间还是没有找到比较好的算法!
可能是我对这个问题的了解太少了,很希望找一本比较好的参考资料看一下!
dsdsdds 2008-03-23
  • 打赏
  • 举报
回复
好多书啊... 真是有很多人在研究啊。

谢谢楼上啊,呵呵

566

社区成员

发帖
与我相关
我的任务
社区描述
英特尔® 边缘计算,聚焦于边缘计算、AI、IoT等领域,为开发者提供丰富的开发资源、创新技术、解决方案与行业活动。
社区管理员
  • 英特尔技术社区
  • shere_lin
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧