-
- 加为好友
- 发送私信
- 在线聊天
|
| 发表于：2008-03-22 16: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
简介: 优美图是图论中极有趣的重要内容，有着较好的应用价值和广 阔 的研究前。作者以多年的科研经验，系统地总结了国内外优美图研究的重要成果，并提了新的研究问题和研究方向，为从事优美图研究的人员和图论爱好 者提供了量的前沿信息。全书共分七章，内容包括:图的基本知识，忧美图的 概 念、质和应用等。
____________________________________________________________________________________
树的邻接向量与优美树猜想的微机证明
周尚超
本文引入了树的邻接向量的概念，用微机证明阶数≤２０的树都是优美树．
【关键词】：图；树；向量；优美图；微型计算机
【基金】：江西省自然科学基金资助
【分类号】：O157.5
【DOI】：cnki:ISSN:10050523.0.1996-03-012
【正文快照】：
树的邻接向量与优美树猜想的微机证明周尚超（基础课部）摘要本文引入了树的邻接向量的概念，用微机证明阶数≤２０的树都是优美树．关键词图；树；向量；优美图；微型计算机分类号０１５７．５０引言本文所指的图Ｇ一（Ｖ，Ｅ）均为无向简单图．Ｖ－Ｖ（Ｇ）和Ｅ－Ｅ（Ｇ）分
____________________________________________________________________________________
置换与优美树谱
朱勇,王卫华,王展青
研究置换与优美树的关系，得到在ｎ阶标号优美树集与（ｎ－２）阶优美置换的一个子集之间存在着一一对应的结论。依据这一结论构造出ｎ阶优美树谱
【作者单位】：武汉汽车工业大学教务处
【关键词】：图；树；优美树；置换
【分类号】：O157.5
【DOI】：cnki:ISSN:1007-144X.0.1997-02-018
【正文快照】：
置换与优美树谱朱勇王卫华王展青（基础课部）摘要研究置换与优美树的关系，得到在ｎ阶标号优美树集与（ｎ－２）阶优美置换的一个子集之间存在着一一对应的结论。依据这一结论构造出ｎ阶优美树谱。
____________________________________________________________________________________
优美树的优美标号
姚兵;程辉
本文着重探讨了优美树的优美对偶标号函数、泛优美标号函数及可广义优美标号函数。得到“任何树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的优美图及其注记
唐保祥
利用计算机为辅助工具，分别给出了２类包含图Ｋ４的图Ｋ４＋Ｇｎ＋１和Ｋ４＋Ｋｎ，ｎ的优美标号，从而证明了图Ｋ４＋Ｇｎ＋１和Ｋ４＋Ｋｎ，ｎ是优美图，并由Ｋ４＋Ｋｎ，ｎ的优美性给出了边数为ｍ的极小优美图的顶点数ｆ（ｍ）的范图是｛（１＋８ｍ＋１）／２｝≤ｆ（ｍ）≤｛２（ｍ＋３－１）｝．
【作者单位】：天水师范学院 数学系 甘肃 天水 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)一卿(的!称为棱如的标
____________________________________________________________________________________
关于优美树研究方法的探讨
孟凡洪,常丹,王辉
归纳总结了优美树研究的几种常见方法，给出了基变换定理，对树的优美性的研究及Ｒｏｓａ猜想（每棵树都是优美的）的证明提供了一些有益的工具
____________________________________________________________________________________
关于优美图的计算机算法 马旭东
（国内的垃圾论文太多了，大都是为了评职称）
|
|
|
|
0
修改
删除
举报
引用
回复
| |
