离散数学实验指导书及其答案(2)

for(i=0;i

if(a[i]) { }

printf(\for(j=0;j

if(r[i][j] && a[j]!=0) { }

printf(\打印和第i个元素有关系的所有元素*/ a[j]=0;

a[i]=i+1;/*i代表第i个元素*/ for(i=0;i

printf(\

实验五 关系闭包运算

【实验目的】掌握求关系闭包的方法。

【实验内容】编程求一个关系的闭包，要求传递闭包用warshall方法。 【实验原理和方法】

设N元关元系用r[N][N]表示，c[N][N]表示各个闭包，函数initc(r)表示将c[N][N]

初始化为r[N][N]。

（1）自反闭包：r(R)?R?IA。

C语言算法： 将关系矩阵的对角线上所有元素设为1。

initc(r);

/*将关系矩阵的对角线上所有元素设为1*/ for(i=0;i

c[i][i]=1;（2）对称闭包：s(R)?R?R?

C语言算法： 在关系矩阵的基础上，若rij?1,令rji?1。

initc(r); for(i=0;i

for(j=0;j

if(c[i][j]) c[j][i]=1;/*将关系矩阵的对角线上所有元素设为1*/

2n（3）传递闭包：t(R)?R?R???R，或用warshall方法。

方法1：t(R)?R?R???R，下面求得的关系矩阵T=(bij)n?n就是t(R)。

int b[N][N];

initc(r);/*用c装好r*/

for(m=1;m

for(i=0;i

for(j=0;j

b[i][j]=0; for(k=0;k

b[i][j]+=c[i][k]*r[k][j]; if(b[i][j]) b[i][j]=1;

2ninitc(b);/*把r的m次方b赋给c保存*/

方法2：warshall方法

initc(r);/*用c装好r*/ for(i=0;i

if(c[j][i])

for(k=0;k

c[j][k]=c[j][k]+c[i][k]; if(c[j][k]) c[j][k]=1;

for(j=0;j

实验六 欧拉图判定和应用

【实验目的】掌握判断欧拉图的方法。

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

（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 该有向图是欧拉图

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

欧拉路。

C语言算法：

int count=0,cur=0,r[N][N]; // r[N][N]为图的邻接矩阵，cur为当前结点编号，count为欧拉路的数量。

int sequence[M];// sequence保留访问点的序列，M为图的边数 输入图信息;

sum1=0; sum2=0;

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

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

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

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

if(r[i][j]) sum++; if(sum%2==0) flag=0;

void try1(int k) //k表示边的序号 { }

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

if (r[cur][i]) //当前第cur点到第i点连通

{ }

r[cur][i]=0;cur=sequence[k]=i; if (k

//删除当前点与第i点的边，记下第k次到达点i，把第i个点设为当前点

//上面条件不满足，说明当前点的出度为0，回溯，试下一位置