所有含有30个顶点的树都是优美的! All trees with 30 nodes are graceful!

经过两个多月的计算,我,fwjmath,和我的笔记本宣布,经过计算,所有含有30个顶点的树可以分为两部分,一部分可以用一个确定性算法给出一个优美标号,而对于另一部分,我们可以显式地对每棵树给出一个优美标号。这也就是说,我们已经证明,所有含有30个顶点的树都是优美的。

After more than 2 months’ calculation, I, fwjmath, with my laptop, declare that all trees with 30 nodes can be divided into 2 classes, one in which every tree can be given a graceful labeling by a determinist algorithm, and for the others a graceful labeling can be given explicitly to every tree. In other words, we have proved that every tree with 30 nodes is graceful!

Après un calcul durant plus que 2 mois, Je, fwjmath, avec mon ordinateur, proclame que les arbres avec 30 noeuds peuvent être classés dans 2 catégories, l’une dont un algorithme déterministe donne à chaque arbre un marquage gracieux, l’autre dont un marquage gracieux est explicitement donné à chaque arbre. En conclusion, tout arbre possèdant 30 noeuds est gracieux.

 

关于优美图、优美树和优美标号的介绍,请参看这两个链接:

http://topic.csdn.net/u/20080322/16/c5441587-d534-4bfb-8033-87367c452985.html

http://en.wikipedia.org/wiki/Graceful_labeling

简单地说,假设有一颗树T拥有n个顶点,如果存在对顶点的一个由0至n-1的不重不漏的标号方法,使每条边由此诱导出来的标号(即为边的两个顶点标号的差的绝对值)为从1到n-1的不重不漏的n-1个数的话,那么我们称这个标号方案是一个优美标号,而这棵树也被称为优美的。注意,在这里关于优美性的论述只对于树有效。

图论中著名的Ringel-Kotzig猜想断言:所有的树都是优美的。这是一个尚未证明而意义重大的猜想。曾经有很多人尝试证明这个猜想,但都没有成功。而也有人对这个猜想进行数值上的验证。在此之前的记录是任意含有29个顶点的树都是优美的,这个结论是由Michael Horton在10台计算机上用了总计58天的CPU时间作出的。

 

About graceful labeling, please have a look at this:

http://en.wikipedia.org/wiki/Graceful_labeling

If you are interested and want to know about details, please contact me via:

fwjmath@gmail.com

 

在接下来的一段时间中,我会对我的算法进行进一步的优化和调整,然后继续冲击n=31!

After this, I’ll optimize and modify my program for the next aim of n=31!

Ensuite, je vais optimizer et modifier mon algorithme pour le but suivant, n=31!

Advertisements

2 thoughts on “所有含有30个顶点的树都是优美的! All trees with 30 nodes are graceful!

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s