优美树验证项目

优美树验证项目
优美树验证项目 logo
优美树验证项目的运行界面
开发者	fwjmath
版本历史	2008年11月22日
运算平台	Windows
项目平台	独立平台
程序情况	x86 SSE2 CPU计算程序 程序大小<1MB
任务情况	每个任务包里面包含了约60亿棵树，平均需要15天的计算时间，任务限期3个月。
项目状态	运行中/关闭申请
项目类别	数学类
优化程序	无
计算特点	CPU密集： 支持0分享率： 支持GPU计算：
官方网址	优美树验证项目
	[{{{rss}}} 通过 RSS 获取项目新闻]

优美树验证项目（Graceful Tree Verification Project，简称GTV）是由 fwjmath 个人建立的数学类分布式计算项目.本项目旨在通过志愿分布式计算的方式对优美树猜想进行验证。优美树猜想是图论中一个重要但悬而未决的猜想，它猜想所有的树都是优美的。通过这个项目的计算，我们可以对优美树猜想进行验证，试图寻找反例，同时获得优美树的一些统计性质，帮助数学家更好的研究优美树猜想。

参与方法

该项目采取电子邮件的方式传递工作包，具体流程如下：

• 1. 下载客户端并解压缩

• 2. 以“GTV Block Request”为题发一封电子邮件到 [email protected]，内附你希望在网站上显示的用户名。如果有其它要求的话也可附上。

• 3. 主持者会回复一封带有附件的邮件。将附件中的“data.txt”下载到客户端所在的目录，运行 GTVGUI.exe，然后点击“Start”按钮即可开始计算。

• 4. 在计算过程中，如果需要停止计算，点击“Stop”按钮即可。计算程序每隔几分钟会自动存盘，所以无须担心计算进度丢失太多。

• 5. 计算完毕后，客户端会自动弹出提示，此时请将客户端所在目录下的“Result.zip”作为附件回复到[email protected]，并说明你是否希望继续进行计算。

• 6. 回到第三步，如此周而复始下去，直到你希望退出这个项目。这时请给 [email protected] 发送一封邮件说明原因.

项目数学背景

一棵有31个顶点的树

优美树的定义

如图所示，这是一棵有31个顶点的树，如果您数一数的话会发现这些顶点旁边被标记了从0到30的数字，没有两个不同的顶点标记了相同的数字，而每个数字都在这棵树上出现了。这叫一个标号。

如果我们看边上标记的数字的话，您会发现它们恰好是这条边的两个顶点的标记数字的差。这种边上的标记就叫由顶点标号诱导出来的一个边的标号。

这棵树一共有30条边。如果我们仔细数一数边上的数字的话，会发现从1到30的数字都碰巧出现了，满足这种条件的标号就叫做一个优美标号（graceful labelling）。

一般地说，一棵拥有n个顶点的树有n-1条边，如果存在一个对顶点进行从0到n-1的不重不漏的标号，它所诱导出来的边的标号恰好不重不漏为1到n-1的话，我们就把这个顶点的标号称为一个优美标号。

如果一棵树能拥有至少一个优美标号的话，我们就说这棵树是优美的。根据这个定义的话，图中的树是优美的。

这个优美性的定义只对于树有效，但也可以拓展到一般的图上。

优美标号的概念最早是由 Rosa 在1967年提出的，当时他把它称作“β-valuation”，而优美标号（graceful labelling）这个名字是在1972年由 Golomb 提出的。

优美树猜想

所谓优美树猜想，其实就是如下命题：

优美树猜想（Ringel-Kötzig 猜想）：所有树都是优美的。

顶点数目	树木数
1	1
2	1
3	1
4	2
5	3
6	6
7	11
8	23
9	47
10	106
11	235
12	551
13	1,301
14	3,159
15	7,741
16	19,320
17	48,629
18	123,867
19	317,955
20	823,065
21	2,144,505
22	5,623,756
23	14,828,074
24	39,299,897
25	104,636,890
26	279,793,450
27	751,065,460
28	2,023,443,032
29	5,469,566,585
30	14,830,871,802
31	40,330,829,030
32	109,972,410,221
33	300,628,862,480
34	823,779,631,721

这个猜想蕴含了 Ringel 猜想：完全图 K(2n+1) 可以被分解为 2n+1 棵含有n条边的同构的树。

直到现在，人们对这个猜想还是无从下手，但它仍然吸引了不少的数学家。Kötzig 本人有一次就曾经说过证明这个猜想的努力是一种“疾病”。

但是人们通过各种各样的方法仍然得到了一些部分的结果。现在已经证明了一些特殊的树的优美性。

一个例子就是毛毛虫树。如果一棵树去掉所有只连出一条边的顶点，剩下的部分没有分支的话，这棵树就被称为毛毛虫树。容易设计出一个算法可以有效地找出毛毛虫树的一个优美标号。所以我们说毛毛虫树是优美的。

这样的理论上的结果还有很多，但都只针对一些非常特殊的树。目前为止得到最普遍的结论就是由 P.HrnČiar 和 A.Haviar 在2001年证明的，他们证明了所有直径等于5的树都是优美的。再加上之前的结果，我们可以知道所有直径小于等于5的树都是优美的。在这里，直径的定义就是树的任意两个顶点间的最大距离，也就是说在树上任意取两个顶点，从一个顶点沿着边走到另一个顶点至少经过的边的数目。

也有数学家试图利用计算机的强大计算能力来帮助验证优美树猜想。Aldred 和 McKay 在1998年用计算机验证了所有顶点数小于等于27的树都是优美的。他们所使用的算法是爬坡搜索和禁忌搜索的结合体。

而这个项目对他们的算法进行了重大的改进，以获得更好的速度，用于验证优美树猜想。

树的数目

为什么我们需要借助空闲计算机的计算能力来做这个计算呢？

右边是一个列表，左列代表树的顶点数，右列代表含有这个数目的顶点的不同的树的数目。

可以看出，树的数目是随着顶点的数目指数增长的，大约是 O(2.6687ⁿ) 。这种增长是非常快速的，所以我们需要大量的计算资源来推进优美树猜想的验证。这就是我们需要您的原因！

项目动态

• 2008/11/22 项目正式开始测试
• 2008/11/22 注册项目域名和空间，感谢 phchenjie！
• 2008/11/27 参加者 BiscuiT 返回了第一个结果，成功通过验证！
• 2008/12/10 所有测试用的工作包都已发放完毕！
• 2009/01/21 项目测试完毕，正式开始！经验证，所有含有32个顶点的树都是优美树。
• 2009/02/12 含有33个顶点的工作包已经发放完毕！开始发放含有34个顶点的工作包！
• 2009/03/07 由于技术原因，项目暂停新用户的注册以及新工作包的发放。不便之处，敬请原谅。
• 2009/04/27 所有含有33个顶点的工作包都已回收完成！经验证，所有含有33个顶点的树都是优美树。
• 2009/05/10 客户端升级，项目重新开始工作包的发放！
• 2009/06/05 含有34个顶点的工作包已经发放完毕！开始发放含有35个顶点的工作包！
• 2009/08/23 所有含有34个顶点的工作包都已回收完成！经验证，所有含有34个顶点的树都是优美树。

基准测试程序及使用方法

项目提供了能估算您计算机的CPU在参与优美树验证项目时速度的程序、估算一个包所需时间的方法与一些CPU的参考速度。（详细介绍）

知道您计算机CPU的相对速度后，很容易通过简单的计算得到完成一个计算包在您的计算机上大约所需的CPU时间。在项目计算状态页面顶部，我们标注了当前正在计算的包在Core 2 Duo T7200上所需的CPU时间。只需将这个时间除以您计算机CPU的相对速度即可得出一个计算包在您的计算机上大约所需的CPU时间。

• 各类CPU参考速度表

项目计算结果

目前已经完成的计算有：

• n=32：经验证所有含有32个顶点的树都是优美的（详细信息）。
• n=33：经验证所有含有33个顶点的树都是优美的（详细信息）。
• n=34：经验证所有含有34个顶点的树都是优美的（详细信息）。

相关链接

• 项目官方网站
• 项目数学背景