现代科技综述知识文库：优美图、鲍丹狄克猜想

1、现代科技综述系列优美图、鲍丹狄克猜想科技是人类区别于动物的重要文明之一，是人类对自然规律研究和利用的学科。本文提供对科技基本概念“优美图、鲍丹狄克猜想”的解读，以供大家了解。优美图、鲍丹狄克猜想一个点集V以及V中某些点对连线(边)的集合E，就构成一个图(graph)。现实世界任何一个离散事物集合以及这集合中两元素间的一种关系，都可用图作数学模型。最早的图论论文是欧拉(Euler)1736年写成的关于哥尼斯堡(Knigsberg)七桥问题。20世纪60年代以来，随着近代科技特别是计算机的应用，使图论在理论上迅速发展，并在自然科学、社会科学和近代科技的许多方面，都有广泛、重要的应用。对于简单图G(

2、V，E)，若每一个顶点vV，存在一个标号(v)0，1，2，E；不同顶点的标号不同；uvE，(u)(v)称为边uv的标数，且不同边的标数不同，则称G为优美图(graceful graph)。由于优美图在编码理论、x射线晶体学、雷达、通讯网络和无线电天文学等方面有实际应用，并且大多数图不是优美图，从而论证图的优美性，便成为比较活跃的课题。邦迪(Bondy)和默蒂(Murty)1976年提出50个未解决的图论难题，优美图问题是其中第15个。至今未解决的重要问题是如何判别一个图是否是优美图。解决此问题是非常难的，部分原因是由于目前缺乏较系统有力的研究工具；并且优美图的子图未必还是优美图，也给优美图的论

3、证带来障碍。所以当前国内外学者只囿于寻求某些特殊图类的优美标号。树是优美图的猜想，现已得到众多结果，但离完全解决还相差甚远。鲍丹狄克(Bodendiek)猜想一个圈加一条弦是优美图(连接圈上不相邻两点的边称为弦)，于1977年提出，它的几个特殊情形也同时得证。这个猜想也是很难的。经过近4年的努力，才由德劳姆(Delome)等于1980年给出证明。随后冯成进于1983年、陈志增于1986年也分别独立地给出证明。一般证法大多是找规律直接标号，再证明是优美标号。陈志增一改直接标号方法，引进GL矩阵，通过GL阵的运算，证得该猜想。由于GL阵方法在一定范围内较为有力，故随即用GL阵于19861991年证

4、得13odendiek猜想的一种推广：连接两个顶点的3条独立路所成简单图是优美的(其中有3种特殊情形的结论略有变通)，并证得其它一些优美图类。与此同时，柯赫(Koh)等于1982年证得该猜想的另一种推广：从圈上一点任意引2(或3)条相邻的弦，构成优美图；并且在圈Cn=v1v2v3vnv1中，引所有可能使iP的弦v1vi(3pn1)，所成的图记为Cn(P)，又证得Cn(3)是优美图。此后马旭东于1988年证得当p0，3(mod4)，Cn(p)是优美图；同时他又进一步推广，证得从Cn(3)的v1向Vi连接ki条与Cn没有公共内点的长为2的路(整数ki1，i=2，3，n)，且所有路相互独立，也构成优

5、美图；他还证得另一种特殊多弦圈的优美性。今后若干年内，下列几个图类是否优美图，可能会被关注：(1)连接两个顶点的多条独立路所成简单图。(2)一般的有一个公共顶点的多条弦的圈。(3)一般多弦圈。(4)多圈共弦图，等等。鉴于当前尚缺乏系统有力的理论工具，看来只能从这些图类的特殊情形，逐步证起，并且一般说是很困难的。【参考文献】： 1 Bondy J A, Murty U S R. GraphTheory with Applica-tions. Macmillan,1976 2 Bodendiek R, et al. Elemente der Mathematik,1977,32:49 3 Delome C, et al. Journal of Graph Theory ,1980,4:409 4 Koh K M, et al.Bull Malaysian Math. Soc, 1982,5(2):49 63 5 冯成进科学通报，1983，13 6 陈志增内蒙古师大学报，1986，319 7 Ma XudongJ Math Res & Exposition，1988，2215 9 Che