下载此文档

第五组图的传递闭包(一笔画问题).doc


文档分类:IT计算机 | 页数:约14页 举报非法文档有奖
1/14
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/14 下载此文档
文档列表 文档介绍
实训十一笔画问题和图的传递闭包任务分配成员1张藤成绩 综合分数 成员2金洲成绩        一、设计目的1)掌握一笔画问题和图的传递闭包;2)进一步掌握图的传递闭包的基本思想和算法设计方法;二、)一笔画问题简介[问题描述]编程对给定的一个图,判断能否一笔画出,若能请输出一笔画的先后顺序,否则输出“NoSolution!”。[输入格式]输入文件共n+1行,第1行为图的顶点数n,接下来的n行(每行n个数据)为图的邻接矩阵,G[i,j]=1表示顶点i和顶点j有边相连,G[i,j]=0表示顶点i和顶点j无边相连。[输出格式]若能一笔画出,则输出一笔画出的顶点先后顺序,否则输出“NoSolution!”。[样例输入]6010011101101010100011011100101110110[样例输出]5--->1--->2--->3--->4--->2--->6--->4--->5--->6--->12)算法分析1、建立邻接矩阵,link[i,j]:=1或0;2、求每个顶点的度数,存入degree[i];3、统计奇点的个数,存入odt;4、若无奇点,则可从任意一结点出发开始一笔画,一般start:=1;5、若有2个奇点,则从其中一个奇点i出发开始一笔画,start:=i;6、若奇点个数超过2个,则不能一笔画出。如何画呢?即如何打印序列呢?细化第4、5步:;(偶点)出发,打印出来,且degree[i]-1;,且degree[j]-1;:=sum-2; 判断“sum=0”,成立就结束,。3)问题分析由数学知识可知:当一个图的顶点全是偶点或仅有两个奇点时才能一笔画出,而且此图必须是连通图。下面再给出几个概念:1、欧拉路:在无孤立结点的图G中,若存在一条路,经过图中每条边一次且仅一次,则称此路为欧拉路。如图5_15(左)中存在一条从顶点1到顶点6的欧拉路。本题其实就是判断一个图是否存在欧拉路,如果有还要输出顶点序列。2、欧拉回路:在无孤立结点的图G中,若存在一条路,经过图中每条边一次且仅一次,且回到原来位置,则称此路为欧拉回路。如图 5_15(右)中任意两个顶点之间都存在欧拉回路。因此,本章开头提出的柯尼斯堡七桥问题实际上就是讨论图的欧拉回路问题。图5_153、欧拉图:存在欧拉回路的图,称为欧拉图,图5_15(右)所示的图就是一个欧拉图。4、定理1:存在欧拉路的条件:图是连通的,且存在0个或2个奇点。5、定理2:存在欧拉回路的条件:图是连通的,且存在0个奇点。6、哈密尔顿图:在无孤立结点的连通图中,若存在一条路,经过图中每个结点一次且仅一次,则称此图为哈密尔顿图。7、哈密尔顿环:是一条沿着图的n条边环行的路径,它访问每一个结点一次且仅一次,并且返回到它的开始位置。。用自然语言、伪程序设计语言或流程图等形式针对一笔画问题的求解(抽象地)描述递推过程……[6];//储存矩阵intstart,now;//定义七点,[6];intr,sum,odt,start,now;sum=0;odt=0;start=1;for(i=1;i<=n;i++){arr[i]=0;for(j=1;j<=n;j++)arr[i]=arr[i]+[i][j];sum=sum+arr[i];if(odd(arr[i])){odt=odt+1;start=i;}}if(odt>2){printf("'nosolution\n");}else{now=start;printf("%d",start);do{r=0;do{r=r+1;}while(!(([now][r]>0)&&((arr[r]>1)||((arr[r]==1)&&(sum==2)))));[now][r]=0;[r][now]=0;sum=sum-2;arr[now]=arr[now]-1;arr[r]=arr[r]-1;now=r;printf("--->%d",r);}while(sum!=0);printf("\n");}三、、测试模块、测试数据实例(文字数据、图或表等形式)……、。。

第五组图的传递闭包(一笔画问题) 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数14
  • 收藏数0 收藏
  • 顶次数0
  • 上传人文库旗舰店
  • 文件大小152 KB
  • 时间2019-12-11