离散数学 欧拉图实验

《离散数学 欧拉图实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、欧拉图判定和应用【实验内容】判断一个图是不是，如果是，求出所有欧拉路【实验原理和方法】（1）用关系矩阵R=表示图。（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。C语言算法：flag=1;for(i=1;i<=n&&flag;i++){sum=0;for(j=1;j<=n;j++)if(r[i][j])sum++;if(sum%2==0)flag=0;}如果flag该无向图是欧拉图（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。C语言算法：flag=1;for(i=1;i<=n&&flag;i++){sum1=0;sum2=0;for(j=1;j<=n;j++

2、)if(r[i][j])sum1++;for(j=1;j<=n;j++)if(r[j][i])sum2++;if(sum1%2==0

3、

4、sum2%2==0)flag=0;}如果flag该有向图是欧拉图（4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。C语言算法：intcount=0,cur=0,r[N][N];//r[N][N]为图的邻接矩阵，cur为当前结点编号，count为欧拉路的数量。intsequence[M];//sequence保留访问点的序列，M为图的边数输入图信息;voidtry1(intk)//k表示边的序号{inti,pre=cur;/

5、/j保留前一个点的位置,pre为前一结点的编号for(i=0;i

6、方法】（1）用一维数组f[N]存贮通信符号的使用频率，用求最优二叉树的方法求得每个通信符号的前缀码。（2）用链表保存最优二叉树，输出前缀码时可用树的遍历方法。#include#include#defineN13structtree{floatnum;structtree*Lnode;structtree*Rnode;}*fp[N];//保存结点chars[2*N];//放前缀码voidinite_node(floatf[],intn)//生成叶子结点{inti;structtree*pt;for(i=0;i

7、)malloc(sizeof(structtree));//生成叶子结点pt->num=f[i];pt->Lnode=NULL;pt->Rnode=NULL;fp[i]=pt;}}voidsort(structtree*array[],intn)//将第N-n个点插入到已排好序的序列中。{inti;structtree*temp;for(i=N-n;inum>array[i+1]->num){temp=array[i+1];array[i+1]=array[i];array[i]=temp;}}structtree*construct_tree(

8、floatf[],intn)//建立树{inti;structtree*pt;for(i=1;inum=fp[i-1]->num+fp[i]->num;pt->Lnode=fp[i-1];pt->Rnode=fp[i];fp[i]=pt;//w1+w2sort(fp,N-i);}returnfp[N-1];}voidpreorder(structtree*p,intk,charc){intj;if(p!=NULL){if(c=='l')s[k]='0';elses

9、[k]='1';if(p->Lnode==NULL){//P指向叶子printf("%.2f:",p->num);for(j=0;j<=k;j++)printf("%c",s[j]);putchar('');}preorder(p->Lnode,k+1,'l');preorder(p->Rnode,k+1,'r');}}voidmain(){floatf[N]={2,3,5,7,11,13,17,19,23,29,3