《离散数学实验四》由会员分享，可在线阅读，更多相关《离散数学实验四（6页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告（2014 / 2015 学年 第 一 学期）课程名称离散数学实验名称图的随机生成及欧拉（回）路的确定实验时间2014年12月12日指导单位南京邮电大学指导教师罗卫兰学生姓名沈一州班级学号B12040920学院(系)计算机软件学院专 业NIIT（软嵌）实 验 报 告实验名称图的随机生成及欧拉（回）路的确定指导教师罗卫兰实验类型验证型实验学时4实验时间12.12一、 实验目的和要求内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧
2、拉路。二、 实验环境(实验设备)硬件： CPU：3.0Ghz 内存：1.00GB软件：操作系统：Windows XP SP3编程软件：Visual C+ 6.0三、 实验原理及内容总体思想：这次题目要求是根据随机生成的图求欧拉（回）路，先要随机生成一个邻接矩阵，然后判定是否是欧拉回路只要根据奇数度结点的个数。再用一个递归函数找出欧拉路。核心代码：1、根据结点数生成邻接矩阵：for(i=0;in;i+)for(j=0;jj) /边没有方向性aij=aji;else /随机赋值，0代表没有边，1代表有边aij=rand()%2;cout ; /输出该邻接矩阵for(i=0;in;i+)cout i
3、+1;coutendl;for(i=0;in;i+)couti+1;for(j=0;jn;j+)cout aij;coutendl;2、根据奇数度结点数判定是否含有欧拉(回)路：odd=0;for(i=0;in;i+)count=0;for(j=0;jn;j+)count+=aij; /统计每个结点的度数if(count%2=1)odd+; /若为奇数，则总数+1if(odd=0)cout该图没有奇数度结点，具有欧拉回路，是欧拉图。endl;else if(odd=2)cout该图有两个奇数度结点，具有欧拉路，是半欧拉图。endl;elsecout该图奇数度结点的个数为odd，所以不具有欧拉路
4、。endl;3、半欧拉图中找出奇数度结点标号：flag1=flag2=-1; /分别代表两个奇数度结点的标号for(i=0;in;i+)count=0;for(j=0;jn;j+)count+=aij;if(count%2=1)if(flag1=-1)flag1=i+1;elseflag2=i+1;4、求欧拉(回)路：void find(int found,int time)int i,j,flag;for(i=0;in;i+)if(afoundi=1)flag=0;for(j=0;jtime;j+) /表示是否已经存在if(bj=i)flag=1;break;if(!flag)btime=i
5、;time+;if(timeexist) /如果还没走完find(i,time); /递归elsereturn;四、运行结果：首先是输入结点数：然后随机打印出邻接矩阵：根据性质判断并求出欧拉图：再试3次：实 验 报 告五、实验小结这次题目要求是根据随机生成的图求欧拉（回）路，首先难点是如何随机生成一个图，这要考虑到3个细节：第1个是同一个结点之间没有边，第2个就是这是无向图，一旦一个结点有了一条边，对应的另一个结点也要有一条边，第3个是要考虑到孤立结点。在此基础上生成了邻接矩阵，欧拉图判断就好弄多了，只要判断奇数度结点的个数。然后再用递归函数找到一条可行路即可。通过这次实验，加深了我对图的相关知识的理解，也提高了我动手编程的能力。五、指导教师评语 成 绩批阅人日 期- 5 -
