中国分布式计算论坛

标题: 调和树项目介绍 [打印本页]

作者: refla 时间: 2011-8-5 18:28
标题: 调和树项目介绍
原文：http://www.rechenkraft.net/wiki/index.php?title=Harmonious_Trees/en

In 1980, Graham and Sloane first introduced the notion of harmonious labelling on general graphs. It is a labelling scheme related to additive base. Basically, for a graph with e edges, a harmonious labelling is a labelling such that every node receives a different label that makes the sum modulo e of adjacent nodes runs from 0 through e - 1. This is not a trivial labeling, in the sense that not all graphs have a harmonious labelling. If a graph has a harmonious labelling, we say that it is harmonious.

Graham and Sloane proposed the following conjecture: Every tree is harmonious. Equivalently speaking, they conjectured that for every tree with n nodes, we can label them from 0 to n - 1 without repetition, such that the sum modulo (n - 1) of two adjacent nodes runs from 0 through n - 2.

According to Gallian's dynamic survey on graph labelling, there are few results on harmonious trees. Graham and Sloane proved that caterpillars are harmonious. Aldred and McKay used a computer program to verify that all trees with at most 26 nodes are harmonious. Recently, Fang proposed a new algorithm and pushed the verification to trees with at most 31 nodes. A distributed version of this algorithm is used in this subproject.

In this subproject, we aim to verify if trees with limited size are all harmonious. If they are all harmonious, it will confirm our faith in this conjecture. Otherwise, if a counter-example is found, it will immediately disprove the conjecture, therefore disprove a lasting open problem in graph theory.

作者: refla 时间: 2011-8-5 18:29
预备知识1：模运算

以我们熟悉的十进制运算为例，它的个位数有 0 ～ 9 个数字，当第十个计数对象出现时，就向十位数进 1，得到 10。因此，这种计数方法称为“进制”，十进制就是逢十进一的意思。

模运算是一种循环运算。“模”可以理解为计数的上限。比如，如果模取 10，则它的个位数也有 0 ～ 9 共计 10 个数字，当第十个计数对象出现时，它不是进位，而是从 0 开始计数。
日常生活中，最典型的例子就是挂在墙上的钟。钟的盘面被等分成 12 个刻度，13 点的时候，时针指向哪里呢？对了，是 1 而不是 13 ！

最常用的模运算是“取模”，它实际上就是“取余数”。比如，假设被除数是 121，除数是 10，则取余数的结果就是 1，记为 121 % 10 = 1 或者 121 mod 10 = 1。

有关模运算的更多知识，请参见http://baike.baidu.com/view/2385246.htm

作者: refla 时间: 2011-8-5 18:33
预备知识2：调和标号

调和标号的定义：
对于一张有 e 条边的图，图中的每一结点都有一个不同的编号，然后把相邻结点的编号加起来再取模e后，作为边的标号。如果标号恰好是从 0 到 e-1，则称这是一个调和标号。

显然，由定义不难得出以下算式：
假设结点 u 与结点 v 邻接（u 跟 v 之间至少有一条线相连），且结点 u 的编号是 x，结点 v 的编号是 y，则标号 l = (x + y) % e

比如，下图中的顶点（就是最上面的那个圈圈）编号为 1，与它邻接的左下角顶点编号为 4，则连接这两个顶点的边的标号 l = ( 1 + 4 ) % 5 = 0。

作者: refla 时间: 2011-8-5 18:38
In 1980, Graham and Sloane first introduced the notion of harmonious labelling on general graphs. It is a labelling scheme related to additive base. Basically, for a graph with e edges, a harmonious labelling is a labelling such that every node receives a different label that makes the sum modulo e of adjacent nodes runs from 0 through e - 1. This is not a trivial labeling, in the sense that not all graphs have a harmonious labelling. If a graph has a harmonious labelling, we say that it is harmonious.

1980年，格雷厄姆(Graham)和斯隆(Sloane)首次提出了图论中的“调和标号(harmonious labelling)”这一概念。调和标号是一种与附加前提有关的编号策略(scheme)。对于一张有 e 条边的图，图中的每一结点都有一个不同的编号，然后把相邻结点的编号加起来再取模e后，作为边的标号。如果标号恰好是从 0 到 e-1，则称这是一个调和标号。虽然这不是一个繁琐的标号（策略），但并非每张图都能生成一个调和标号。如果一张图有一个调和标号，就称图是调和的。

Graham and Sloane proposed the following conjecture: Every tree is harmonious. Equivalently speaking, they conjectured that for every tree with n nodes, we can label them from 0 to n - 1 without repetition, such that the sum modulo (n - 1) of two adjacent nodes runs from 0 through n - 2.
格雷厄姆和斯隆提出一个猜想：每棵树都是和谐的。也就是说，对于有 n 个结点的树，一定可以从 0 到 n-1 无重复地标记各条边。

According to Gallian's dynamic survey on graph labelling, there are few results on harmonious trees. Graham and Sloane proved that caterpillars are harmonious. Aldred and McKay used a computer program to verify that all trees with at most 26 nodes are harmonious. Recently, Fang proposed a new algorithm and pushed the verification to trees with at most 31 nodes. A distributed version of this algorithm is used in this subproject.
加利安对图标号的动态研究(survey)过程中，有关调和树的成果寥寥可数。格雷厄姆和斯隆证明，毛毛虫(caterpillars，可能是一种树的形状)是和谐的。奥尔德雷德(Aldred)和麦凯(McKay)编程验证了 26 个结点以内的所有树（形）都是调和的。最近，方(Fang)提供了一个新算法，把验证的结点数提高到了 31 结点。我们这个子项目采用的，正是该算法的分布式版本。

In this subproject, we aim to verify if trees with limited size are all harmonious. If they are all harmonious, it will confirm our faith in this conjecture. Otherwise, if a counter-example is found, it will immediately disprove the conjecture, therefore disprove a lasting open problem in graph theory.
我们这个子项目的目标是，验证 n 个结点(size)以内的树都是调和的。如果证明结果为真（就是所有 n 个结点以内的树都是调和的），将会坚定(confirm)我们对这一猜想的信念。否则，哪怕只是找到一个反例，马上就能否定这一猜想，同时也就终结了图论当中一个悬而未决的问题了。

作者: refla 时间: 2011-8-5 18:58
有关这一程序的实现。。。

http://fwjmath.wordpress.com/2010/10/04/harmonious-labelling-algorithm/

作者: Youth 时间: 2011-8-5 21:26
翻译好就直接放维基上吧~~

作者: panzerkiller 时间: 2011-8-5 23:09
能多核并行吗？

作者: 前朝遗少 时间: 2011-8-6 06:40
需要捧一下臭脚吗？

作者: refla 时间: 2011-8-6 17:03
回复 8# 前朝遗少

这不是需不需要你的问题，而是你必须参加这个活动知道不？！

作为一个农民，一定要对树有感情。。。

况且，你还是个无证气象员嘛

作者: refla 时间: 2011-8-6 17:23
回复 7# panzerkiller

其实，分布式都是并行的。。。比如，我现在的 U 是双核的，就能同时算两个 WU。

作者: 前朝遗少 时间: 2011-8-6 21:23
回复 9# refla

俺还真是有证的

现在很多人在本科阶段就能考这个证

考完了会分析天气画符?

作者: feynord 时间: 2011-8-7 00:09
本帖最后由 feynord 于 2011-8-7 00:14 编辑

预备知识2：调和标号

调和标号的定义：
对于一张有 e 条边的图，图中的每一结点都有一个不同的编号，然后把相邻结点的编号加起来再取模e后，作为边的标号。如果标号恰好是从 0 到 e-1，则称这是一个调和标号。
refla 发表于 2011-8-5 18:33

我土，e是整数，任何一个整数取模e后一定是0到e-1阿？就是说每一个结点的赋值（编号）不一定是整数？

作者: refla 时间: 2011-8-7 21:25
回复 12# feynord

你说的没错，取模后一定是整数，但有些图的标号会重复，无法取得 0 ～ e-1 的无重复序列。比如下图

(, 下载次数: 907)

不管你怎么弄，都搞不出标号 0 来。因为，边数 e > 顶点数n+2。

作者: feynord 时间: 2011-8-8 12:41
回复 13# refla

明白了，原来是从0到e-1的数列的意思。。。

欢迎光临中国分布式计算论坛 (https://www.equn.com/forum/)