实验四 二元关系及其性质
【实验目的】掌握二元关系在计算机上的表示方法，并掌握如果判定关系的性质。 【实验内容】 编程判断一个二元关系是否为等价关系，如果是，求其商集。 等价关系：集合A上的二元关系R同时具有自反性、对称性和传递性，则称R是A上的
等价关系。
【实验原理和方法】
（1）A上的二元关系用一个n×n关系矩阵R=(rij)n?n表示，定义一个n×n数组r[n][n]表示n×n矩阵关系。
（2）若R对角线上的元素都是1，则R具有自反性。
C语言算法：
int i,flag=1;
for(i=0;i if(r[i][i]!=1) flag=0; 如果flag=1， 则R是自反关系 （3）若R是对称矩阵，则R具有对称性。对称矩阵的判断方法是： ?rij?R,有?rji?R。 C语言算法： int i,j,flag=1; for(i=0;i for(j=i+1;j if(r[i][j] &&r[j][i]!=1) flag=0; 如果flag=1， 则R是对称关系 （4）关系的传递性判断方法：对任意i，j，k，若rij?1且rjk?1有rik?1。 C语言算法： int i,j,k,flag=1; for(j=0;j for(k=0;k if(r[i][j] &&r[j][k] && r[i][k]!=1) flag=0; for(i=0;i 如果flag=1， 则R是传递关系 （5）求商集的方法：商集是由等价类组成的集合。已知R是等价关系，下面的算法是把等价类分行打印出来。 C语言算法： int i,j,flag=1; int a[N]; 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*/ （3）传递闭包：t(R)?R?R2???Rn，或用warshall方法。 方法1：t(R)?R?R2???Rn，下面求得的关系矩阵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; initc(b);/*把r的m次方b赋给c保存*/ 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 方法2：warshall方法 实验六 欧拉图判定和应用 【实验目的】掌握判断欧拉图的方法。 【实验内容】 判断一个图是不是，如果是，求出所有欧拉路 【实验原理和方法】 （1）用关系矩阵R=(rij)n?n表示图。 （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;