离散数学欧拉图实验

【实验内容】 判断一个图是不是，如果是，求出所有欧拉路 【实验原理和方法】

（1）用关系矩阵R=(rij)nn表示图。

（2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。

C语言算法： flag=1;

for(i=1;i<=n && flag;i++) { }

如果 flag 该无向图是欧拉图

（3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。

C语言算法： flag=1;

for(i=1;i<=n && flag;i++) { }

如果 flag 该有向图是欧拉图

sum1=0; sum2=0;

for(j=1;j<=n;j++)

if(r[i][j]) sum1++; sum=0;

for(j=1;j<=n;j++)

if(r[i][j]) sum++;

if(sum%2==0) flag=0;

for(j=1;j<=n;j++)

if(r[j][i]) sum2++;

if(sum1%2==0 || sum2%2==0) flag=0;

（4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。 C语言算法：

int count=0,cur=0,r[N][N]; f: \

}

preorder(p->Lnode,k+1,'l');

for(j=0;j<=k;j++)

printf(\"%c\

putchar('\\n');

} }

preorder(p->Rnode,k+1,'r');

void main(){

float f[N]={2,3,5,7,11,13,17,19,23,29,31,37,41}; struct tree *head;

inite_node(f,N); //初始化结点

head=construct_tree(f,N);//生成最优树 s[0]=0;

preorder(head,0,'l');//遍历树 }