“优美树验证项目”的版本间差异
(新页面: <big>'''优美树验证项目(Graceful Tree Verification Project)'''</big><br>验证优美树猜想<br> =='''项目简介'''== 优美树验证项目(简称GTV)是由 fwjmath 个...) |
小 |
||
第1行: | 第1行: | ||
− | + | {{Infobox Project | |
− | == | + | | name =优美树验证项目 |
− | + | | logo =[[Image:GTVbanner.png|230px]] | |
− | + | | screenshot =[[Image:GTV_screenshot.jpg|230px]] | |
− | + | | caption =优美树验证项目的运行界面 | |
− | ==''' | + | | developer =[http://www.equn.com/forum/space-username-fwjmath.html fwjmath] |
− | 该项目采取电子邮件的方式传递工作包,具体流程如下: | + | | released =2008年11月22日 |
− | 1. 下载客户端并解压缩 | + | | operating system =Windows |
− | 2. 以“GTV Block | + | | platform =独立平台 |
− | 3. 主持者会回复一封带有附件的邮件。将附件中的“data. | + | | program size =<1MB |
− | 4. 在计算过程中,如果需要停止计算,点击“Stop”按钮即可。计算程序每隔几分钟会自动存盘,所以无须担心计算进度丢失太多。 | + | | work unit info =每个任务包里面包含了约60亿棵树,平均需要15天的计算时间,任务限期3个月。 |
− | 5. 计算完毕后,客户端会自动弹出提示,此时请将客户端所在目录下的“Result.zip”作为附件回复到projectgtv@gmail.com,并说明你是否希望继续进行计算。 | + | | status =运行中/开发申请 |
− | 6. | + | | genre =数学类 |
+ | | optimization =无 | ||
+ | | website =http://www.projectgtv.cn/index.html | ||
+ | }} | ||
+ | [[优美树验证项目]](Graceful Tree Verification Project,简称GTV)是由 fwjmath 个人建立的数学类分布式计算项目.本项目旨在通过志愿分布式计算的方式对优美树猜想进行验证。优美树猜想是图论中一个重要但悬而未决的猜想,它猜想所有的树都是优美的。通过这个项目的计算,我们可以对优美树猜想进行验证,试图寻找反例,同时获得优美树的一些统计性质,帮助数学家更好的研究优美树猜想。 | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | =='''参与方法'''== | ||
+ | |||
+ | 该项目采取电子邮件的方式传递工作包,具体流程如下: | ||
+ | |||
+ | *1. 下载客户端并解压缩 | ||
+ | |||
+ | *2. 以“GTV Block Request”为题发一封电子邮件到 projectgtv@gmail.com,内附你希望在网站上显示的用户名。如果有其它要求的话也可附上。 | ||
+ | |||
+ | *3. 主持者会回复一封带有附件的邮件。将附件中的“data.txt”下载到客户端所在的目录,运行 GTVGUI.exe,然后点击“Start”按钮即可开始计算。 | ||
+ | |||
+ | *4. 在计算过程中,如果需要停止计算,点击“Stop”按钮即可。计算程序每隔几分钟会自动存盘,所以无须担心计算进度丢失太多。 | ||
+ | |||
+ | *5. 计算完毕后,客户端会自动弹出提示,此时请将客户端所在目录下的“Result.zip”作为附件回复到projectgtv@gmail.com,并说明你是否希望继续进行计算。 | ||
+ | |||
+ | *6. 回到第三步,如此周而复始下去,直到你希望退出这个项目。这时请给 projectgtv@gmail.com 发送一封邮件说明原因. | ||
+ | |||
+ | |||
+ | =='''项目数学背景'''== | ||
+ | |||
+ | [[Image:GTV_T31_1.jpg|220px|right|thumb|一棵有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猜想):所有树都是优美的。 | ||
+ | |||
+ | 这个猜想蕴含了Ringel猜想:完全图K(2n+1)可以被分解为2n+1棵含有n条边的同构的树。 | ||
+ | |||
+ | 直到现在,人们对这个猜想还是无从下手,但它仍然吸引了不少的数学家。Kötzig本人有一次就曾经说过证明这个猜想的努力是一种“疾病”。 | ||
+ | |||
+ | 但是人们通过各种各样的方法仍然得到了一些部分的结果。现在已经证明了一些特殊的树的优美性。 | ||
+ | |||
+ | 一个例子就是毛毛虫树。如果一棵树去掉所有只连出一条边的顶点,剩下的部分没有分支的话,这棵树就被称为毛毛虫树。容易设计出一个算法可以有效地找出毛毛虫树的一个优美标号。所以我们说毛毛虫树是优美的。 | ||
+ | |||
+ | 这样的理论上的结果还有很多,但都只针对一些非常特殊的树。目前为止得到最普遍的结论就是由P.HrnČiar和A.Haviar在2001年证明的,他们证明了所有直径等于5的树都是优美的[1]。再加上之前的结果,我们可以知道所有直径小于等于5的树都是优美的。在这里,直径的定义就是树的任意两个顶点间的最大距离,也就是说在树上任意取两个顶点,从一个顶点沿着边走到另一个顶点至少经过的边的数目。 | ||
+ | |||
+ | 也有数学家试图利用计算机的强大计算能力来帮助验证优美树猜想。Aldred和McKay在1998年用计算机验证了所有顶点数小于等于27的树都是优美的[2]。他们所使用的算法是爬坡搜索和禁忌搜索的结合体。 | ||
+ | |||
+ | 而这个项目对他们的算法进行了重大的改进,以获得更好的速度,用于验证优美树猜想。 | ||
+ | |||
+ | ===树的数目=== | ||
+ | |||
+ | 为什么我们需要借助空闲计算机的计算能力来做这个计算呢? | ||
+ | |||
+ | 以下是一个列表,左列代表树的顶点数,右列代表含有这个数目的顶点的不同的树的数目。 | ||
+ | |||
+ | {|border=1 align=right style="width: autoem; font-size: 100%; text-align: left; background: #f9f9f9; border: 1px #999999 solid; border-collapse: collapse;" cellpadding="2" cellspacing="0" | ||
+ | !顶点数目 | ||
+ | !树木数 | ||
+ | |- | ||
+ | |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 | ||
+ | |- | ||
+ | |} | ||
+ | |||
+ | |||
+ | |||
+ | |||
=='''相关链接'''== | =='''相关链接'''== | ||
− | [http://www.projectgtv.cn/ 项目官方网站] | + | *[http://www.projectgtv.cn/ 项目官方网站] |
− | [http://www.projectgtv.cn/math_cn.html 项目数学背景] | + | *[http://www.projectgtv.cn/math_cn.html 项目数学背景] |
2009年6月8日 (一) 13:44的版本
优美树验证项目 | |
---|---|
优美树验证项目 logo | |
优美树验证项目的运行界面 | |
开发者 | fwjmath |
版本历史 | 2008年11月22日 |
运算平台 | Windows |
项目平台 | 独立平台 |
程序情况 | |
任务情况 | 每个任务包里面包含了约60亿棵树,平均需要15天的计算时间,任务限期3个月。 |
项目状态 | 运行中/开发申请 |
项目类别 | 数学类 |
优化程序 | 无 |
计算特点 | CPU密集: |
官方网址 | 优美树验证项目 |
[{{{rss}}} 通过 RSS 获取项目新闻] |
优美树验证项目(Graceful Tree Verification Project,简称GTV)是由 fwjmath 个人建立的数学类分布式计算项目.本项目旨在通过志愿分布式计算的方式对优美树猜想进行验证。优美树猜想是图论中一个重要但悬而未决的猜想,它猜想所有的树都是优美的。通过这个项目的计算,我们可以对优美树猜想进行验证,试图寻找反例,同时获得优美树的一些统计性质,帮助数学家更好的研究优美树猜想。
参与方法
该项目采取电子邮件的方式传递工作包,具体流程如下:
- 1. 下载客户端并解压缩
- 2. 以“GTV Block Request”为题发一封电子邮件到 projectgtv@gmail.com,内附你希望在网站上显示的用户名。如果有其它要求的话也可附上。
- 3. 主持者会回复一封带有附件的邮件。将附件中的“data.txt”下载到客户端所在的目录,运行 GTVGUI.exe,然后点击“Start”按钮即可开始计算。
- 4. 在计算过程中,如果需要停止计算,点击“Stop”按钮即可。计算程序每隔几分钟会自动存盘,所以无须担心计算进度丢失太多。
- 5. 计算完毕后,客户端会自动弹出提示,此时请将客户端所在目录下的“Result.zip”作为附件回复到projectgtv@gmail.com,并说明你是否希望继续进行计算。
- 6. 回到第三步,如此周而复始下去,直到你希望退出这个项目。这时请给 projectgtv@gmail.com 发送一封邮件说明原因.
项目数学背景
优美树的定义
如图所示,这是一棵有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猜想):所有树都是优美的。
这个猜想蕴含了Ringel猜想:完全图K(2n+1)可以被分解为2n+1棵含有n条边的同构的树。
直到现在,人们对这个猜想还是无从下手,但它仍然吸引了不少的数学家。Kötzig本人有一次就曾经说过证明这个猜想的努力是一种“疾病”。
但是人们通过各种各样的方法仍然得到了一些部分的结果。现在已经证明了一些特殊的树的优美性。
一个例子就是毛毛虫树。如果一棵树去掉所有只连出一条边的顶点,剩下的部分没有分支的话,这棵树就被称为毛毛虫树。容易设计出一个算法可以有效地找出毛毛虫树的一个优美标号。所以我们说毛毛虫树是优美的。
这样的理论上的结果还有很多,但都只针对一些非常特殊的树。目前为止得到最普遍的结论就是由P.HrnČiar和A.Haviar在2001年证明的,他们证明了所有直径等于5的树都是优美的[1]。再加上之前的结果,我们可以知道所有直径小于等于5的树都是优美的。在这里,直径的定义就是树的任意两个顶点间的最大距离,也就是说在树上任意取两个顶点,从一个顶点沿着边走到另一个顶点至少经过的边的数目。
也有数学家试图利用计算机的强大计算能力来帮助验证优美树猜想。Aldred和McKay在1998年用计算机验证了所有顶点数小于等于27的树都是优美的[2]。他们所使用的算法是爬坡搜索和禁忌搜索的结合体。
而这个项目对他们的算法进行了重大的改进,以获得更好的速度,用于验证优美树猜想。
树的数目
为什么我们需要借助空闲计算机的计算能力来做这个计算呢?
以下是一个列表,左列代表树的顶点数,右列代表含有这个数目的顶点的不同的树的数目。
顶点数目 | 树木数 |
---|---|
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 |