在无向完全图中寻找边不重复的汉密尔顿回路【直接打印】在无向完全图中寻找边不重复的汉密尔顿回路【直接打印】
北京交通大学 计算机与信息技术学院 2005-06-07
在无向完全图中寻找边不重复的汉密尔顿回路
摘要:汉密尔顿回路以它可以遍历所有结点的特征,常常被用来解决邮路,架建网络等问题。在带限制条件的路径选择等应用上,常常需要在无向完全图中找出多个边不重复的汉密尔顿回路。结合实际情况,对每个汉密尔顿图进行分析,可以方便的解决最佳路径问题。
关键词:图论;无向完全图;边不重复的汉密尔顿回路
英文翻译:(略)
正文:
图论是近年来发展迅速而又应用广泛的一门新兴学科,它...
在无向完全图中寻找边不重复的汉密尔顿回路【直接打印】
北京交通大学 计算机与信息技术学院 2005-06-07
在无向完全图中寻找边不重复的汉密尔顿回路
摘要:汉密尔顿回路以它可以遍历所有结点的特征,常常被用来解决邮路,架建网络等问
。在带限制条件的路径选择等应用上,常常需要在无向完全图中找出多个边不重复的汉密尔顿回路。结合实际情况,对每个汉密尔顿图进行分析,可以方便的解决最佳路径问题。
关键词:图论;无向完全图;边不重复的汉密尔顿回路
英文翻译:(略)
正文:
图论是近年来发展迅速而又应用广泛的一门新兴学科,它以结点代
事物,连线代表关系可以描述现实世界中的许多状态。随着近十几年来电子计算机的发展,图论算法也充分得到利用,它在计算机科学,电路网络,信息论,控制论,数值分类学甚至于社会科学的一些方面都可称为得力的工具。而图论最早的起源是一些数学游戏中的难题研究,如七桥问题,迷宫问题,匿门博弈问题,以及四色猜想,汉密尔顿(环游世界)数学难题。
针对在无向完全图中寻找边不重复的汉密尔顿回路,为便于理解程序的算法,现在引入一个背景问题:N个人参加一个会议,在会议期间,每天都要在一只圆桌上共进晚餐,如果要求每次晚餐就座时,每个人相邻就座者都不相同,问这样的晚餐最多能进行多少次,如果给定N的值,问该如何排列,问题分析如下:N个人在圆桌上共进晚餐,可以看作在一个圆周上排列N个结点,两人相邻而坐,就可看作两点之间有边相连,因此任意一人与其他人相邻就坐的所有情况,就是N个结点的无向完全图,在KN中任意一个汉密尔顿回路,就表示一次晚餐的就座方式。对KN中任意两个汉密尔顿回路只要没有公共边,这就表示两次晚餐的就座中,每个人相邻就座者都不相同。于是晚餐最多能进行的次数就是KN中无公共边的汉密尔顿回路的个数。由完全图的性质可知,KN中共有[N(N-1)/2]条边,每个汉密尔顿回路有N条边,因此,边不重复的汉密尔顿回路最多有[(N-1)/2]条。
一(相关名词解释:
1.简单图:不含有平行边和环的图叫做简单图。
2.完全图:简单图G,
中,若每一对结点间都有边相连,则称该图为完全图。(有N个结点的无向完全图记作KN)例:下图为有五个结点的无向完全图:
3.汉密尔顿回路:给定图G,若G中存在一条回路,经过图中的每个结点恰好一次,这条回路称作汉密尔顿回路。例:在下图中存在一条汉密尔顿回路:
1
北京交通大学 计算机与信息技术学院 2005-06-07
二.构造算法:
1.基本思想:结合实例,对于N个人每次用餐的坐法,只由他们之间的相邻关系决定,排成圆形时,只与排列顺序有关。因此对各种坐法,可认为一人的座位不变,于是可将其设作1号,并不妨将其放于圆心,其余N-1人可放在圆周上。于是边不重复的汉密尔顿回路,可由圆周上不同编号的旋转而得到。
当N为奇数的情况,可做出图1所示:
5
3
N,2
, , N
4 N,1
6 N,,
图1
显然,(1,2,3,4,„„,,-2,N-1,N,1)是KN中的一条汉密尔顿回路。现将圆周上的点的编号依次顺时针旋转[360/(N-1)],[2*360/(N-1)],„„,[(N-3)/2]*[360/(N-1)],它们分别对应边不相重的汉密尔顿回路:
(1,4,2,6,3,8,„„,N-1,N-4,N,N-2,1)
(1,6,4,8,2,10,„„,N,N-6,N-2,N-4,1)
„„„„„„„„„„„
(1,N-1,N-3,N,N-5,N-2,„„,7,2,5,3,1)
当N为偶数的情况,可做出图2所示:
2
北京交通大学 计算机与信息技术学院 2005-06-07
,
3
,,,
, ,
4
, ,,,
, ,,,
图2
即对N,1为奇数的情况,在结点3,结点5的边上添加结点4。
显然,(1,2,3,4,„„,,-2,N-1,N,1)是KN中的一条汉密尔顿回路。现将圆周上的点的编号依次顺时针旋
转[360/(N-2)],[2*360/(N-2)],„„,[(N-4)/2]*[360/(N-2)],它们分别对应边不相重的汉密尔顿回路: (1,5,2,4,7,3,„„,N-1,N-4,N,N-2,1)
(1,7,5,4,9,2,„„,N,N-6,N-2,N-4,1)
„„„„„„„„„„„
(1,N-1,N-3,4,N,N-5,„„,8,2,6,3,1)
由上可知,无论N是奇数还是偶数,N个人共坐圆桌相邻两人都不相同的就座方式最多有[(N-1)/2]种。且可知,
当N?4时,只有一种就座方式。
2.算法描述:(用C++语言实现)
由1可推知,在N为奇数或是偶数,且满足条件的情况下,均遵循一定的规律。如果用数组来存储结点
编号,数组的下标表示每次就座的顺序,则由以下算法可实现具体满足条件的就座方式,即可达到在无向完全图寻
找边不重复的汉密尔顿回路的目的。
#include
class queue{ //定义一个整型队列类
int q[51]; //用数组q来存放队列中的各个元素
int sloc,rloc; //sloc表示队列尾,rloc表示队列头
public:
queue(); //声明构造函数
void qput(int i); //往队列中增加元素并排序的函数
void qout();
}a; //声明对象a
3
北京交通大学 计算机与信息技术学院 2005-06-07
queue::queue()
{
sloc=1;
rloc=0; //给队列中的两个私有变量赋初值
}
void queue::qput(int i)
{
for(int j=1;j<=i;j++){
q[sloc]=j;
sloc++; //按顺序向队列增加元素
if(sloc==51){ //若sloc为51,表示队列已满,提示增加队列长度
cout<<"please enlarge queue~~\n";
return;
}
}
a.qout();
cout<=1;m--){
q[2*m+3]=q[2*m+1];} //下标为奇数的结点顺时针旋转[360/(N-1)]
q[3]=temp0; //将q[2]的值赋给q[3]
q[i-1]=temp1; //将q[i]的值赋给q[i-1]
a.qout(); //顺序输出
cout<6时:
for(int k=i/2;k>=4;k--){
q[2*k]=q[2*k-2];} //下标为偶数的结点顺时针旋转[360/(N-2)]
q[6]=temp0; //将q[3]的值赋给q[6]
}
a.qout(); //输出排序后的次序
cout<>n; //接受用户输入的结点个数
cout<<"-------------------------------------\n";
a.qput(n); //调用排序函数并输出结果
cout<<"-------------------------------------\n";
cout<<"注:只有最后一行排序出现相邻结点的重复\n";
cout<<"\n";
cout<<"所以边不重复的汉密尔顿回路个数为:"<<(n-1)/2<<"\n"; //给出符合要求的汉密尔顿回路个数
cout<<"******************************************\n";
return 1;
}
3.正确性证明:在上面的程序算法中,通过类queue的对象a调用赋值及排序函数qput,并通过改变qput的
参数n改变要排序的元素个数,如N,13,程序运行后的结果为:
****************************************** ** 边不重复的汉密尔顿回路 **
**-------------------------**
** 程序提示: **
1.使用之前,请将图中结点从1开始连续编号.
2.接点个数上限为50.
3.接点个数上限可在源程序中修改.
**-------------------------**
**输入图中接点个数n(050,
则提示“please enlarge queue!!”
此时只需扩展数组q[]的长度即可。
4.开发文档:(见附页)
8
北京交通大学 计算机与信息技术学院 2005-06-07 5.结束语:
本文对在无向完全图中寻找边不重复的汉密尔顿回路给出了相关算法并通过引入背景实例使算法更容易
理解,在学习的过程中,将理论知识与生活中的实例相结合往往使问题更容易解决。
参考文献:
1.左孝凌等《离散数学?理论?分析?题解》,上海科学技术文献出版社,2004.4
2. 王燕 《面向对象的理论与C++实践》,清华大学出版社,2004.7
9
本文档为【在无向完全图中寻找边不重复的汉密尔顿回路【直接打印】】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。