优美树标号的一种算法:混泥土标号与强度算法
时间：2019-01-21 03:29:05 来源：雅意学习网 本文已影响 人 
摘 要:设计了优美树标号的一种算法,并写出了相应的程序,给出了顶点个数为12的树的优美标号。 关键词:优美树标号;算法;程序 中图分类号:F224--39 文献标识码:B 文章编号:1009--9166(2010)002(C)-0061-01
一、基本概念
图的标号问题:作为图论中极有趣的重要内容,有着较好的应用价值和广阔的研究前景。它的研究始于1963年G.Ringel提出如下的猜想:设T是一个给定的有n个顶点,n-1条边的树,那么由凡n-1可分解成2n-1个树同构于T。
优美树猜想:1966年A.Rosa提出了著名的优美树猜想:所有的树都是优美的。A.Rosa还给出了更一般的结论:如果G是一个有q条边的优美图,那么由凡叶1可分解出2q+1个图同构于G。优美树猜想的发展:优美标号的概念最早是由Rosa在1967年提出的,当时他把它称作“β――valuation”,而优美标号(graceful labelling)这个名字是在1972年由Golomb提出的。优美树的猜想蕴涵了Ringel猜想:完全图K(2n+1)可以被分解为2n+1棵含有n条边的同构的树。直到现在,人们对这个猜想还是无从下手,但它仍然吸引了不少的数学家。人们通过各种各样的方法仍然得到了一些部分的结果。现在已经证明了一些特殊的树的优美性。一个例子就是毛毛虫树。如果一棵树去掉所有只连出一条边的顶点,剩下的部分没有分支的话,这棵树就被称为毛毛虫树。容易设计出一个算法可以有效地找出毛毛虫树的一个优美标号。所以我们说毛毛虫树是优美的。这样的理论上的结果还有很多,但都只针对一些非常特殊的树。目前为止得到最普遍的结论就是由P.HrnČiar和A.Haviar在2001年证明的,他们证明了所有直径等于5的树都是优美的。再加上之前的结果,我们可以知道所有直径小于等于5的树都是优美的。在这里,直径的定义就是树的任意两个顶点间的最大距离,也就是说在树上任意取两个顶点,从一个顶点沿着边走到另一个顶点至少经过的边的数目。也有数学家试图利用计算机的强大计算能力来帮助验证优美树猜想。Aldred 和McKay在1998年用计算机验证了所有顶点数小于等于27的树都是优美的。他们所使用的算法是爬坡搜索和禁忌搜索的结合体。而这个项目对他们的算法进行了重大的改进,以获得更好的速度,用于验证优美树猜想。本文就给出了应用计算机计算优美标号的方法。
几类被证明是优美的树:(1)所有的道路都是优美的。(2)所有的毛毛虫都是优美的。(3)1979年,J.c.Bermord提出猜想因:所有的龙虾树都是优美的.有几类龙虾树已经证明是优美的。(4)Bermond和sotteau在1976年、Poljak和sura在1982年均证明了对称树是优美的。(5)A.M.Pastel和H.Raynaudlso、Aban和Bhat一Nayak[sl]证明所有的橄榄树都是优美的。(6)其他已知是优美的树:最多有4个端点的树即直径多为5的树队;最多有27个顶点的树图。
二、算法描述
任意取给定整数n,有集合V={0、1、2、3……n-1},取集合P={1、2、3、……n-1。(1)构造有序对(Ak,Bk)k=1,2,3……n-1,使Bk-Ak=k;(2)第一步,有序对为(0,1)(0,2)(0,3)……(0,n-1);(3)第二步,第一个有序对不变寻找差值为2的有序对,排在第二个位置,要求满足(1),依次类推到n-1个位置,直到找出所有符合条件的有序对;(4)第三步,改变第一个有序对,使其中两个元素差值为1,将这个有序对放到第一个位置,其余各项与(2)中一致;(5)第四步,再次执行第二步,找出所有符合条件的有序对。
依次类推到直到找出所有符合条件的有序对。
三、算法程序
在C语言中执行此程序:
// math2.cpp : Defines the entry point for the console application.
#include
#include
#define SIZE 12
const int X[4]={-1,0,-1,0};
const int Y[4]={0,1,0,-1};
int numtime=0;
struct Point
{
int x;
int y;
};
int map[20][20]={0};
Point point[20];
void dfs(int x,int y,int pos);
ofstream fout("output.txt");
void main()
{
point[0].x=12;
point[0].y=1;
int x,y;
for( x=1;x=SIZE )
{
numtime++;
point[SIZE].x=x;
point[SIZE].y=y;
for(int i=0;i
