离散数学实验四.doc

《离散数学实验四.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告（2014/2015学年第一学期）课程名称离散数学实验名称图的随机生成及欧拉（回）路的确定实验时间2014年12月12日指导单位南京邮电大学指导教师罗卫兰学生姓名沈一州班级学号B学院(系)计算机软件学院专业NIIT（软嵌）实验报告实验名称图的随机生成及欧拉（回）路的确定指导教师罗卫兰实验类型验证型实验学时4实验时间12.12一、实验目的和要求内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。二、

2、实验环境(实验设备)硬件：CPU：3.0Ghz内存：1.00GB软件：操作系统：WindowsXPSP3编程软件：VisualC++6.0一、实验原理及内容总体思想：这次题目要求是根据随机生成的图求欧拉（回）路，先要随机生成一个邻接矩阵，然后判定是否是欧拉回路只要根据奇数度结点的个数。再用一个递归函数找出欧拉路。核心代码：1、根据结点数生成邻接矩阵：for(i=0;ij)//边没有方向性a[i][j]=a[j][i];else{//随机赋

3、值，0代表没有边，1代表有边a[i][j]=rand()%2;}}cout<<"";//输出该邻接矩阵for(i=0;i

4、d++;//若为奇数，则总数+1}if(odd==0)cout<<"该图没有奇数度结点，具有欧拉回路，是欧拉图。"<

5、1){if(flag1==-1)flag1=i+1;elseflag2=i+1;}}4、求欧拉(回)路：voidfind(intfound,inttime){inti,j,flag;for(i=0;i

6、首先是输入结点数：然后随机打印出邻接矩阵：根据性质判断并求出欧拉图：再试3次：实验报告五、实验小结这次题目要求是根据随机生成的图求欧拉（回）路，首先难点是如何随机生成一个图，这要考虑到3个细节：第1个是同一个结点之间没有边，第2个就是这是无向图，一旦一个结点有了一条边，对应的另一个结点也要有一条边，第3个是要考虑到孤立结点。在此基础上生成了邻接矩阵，欧拉图判断就好弄多了，只要判断奇数度结点的个数。然后再用递归函数找到一条可行路即可。通过这次实验，加深了我对图的相关知识的理解，也提高了我动手编程的能力。五、指导教师评语成绩批阅人日期