原理:
设X={1,2,3,......,n},关系R的关系矩阵是M=(mij)
判断等价关系
(1)R是自反的<=>m11=m22=......=mnn=1
(2) R是对称的<=><=>mij=mji
(3) R是传递的<=>tr(R)=R
求等价类
如果mij=1,即iRj,则
算法:
Step1 写出n元集合X上关系R的关系矩阵M=(mij)
Step2 for i=1 to n
如果mii=0,则停止,关系R不是自反的.
Step3 for i=1 to n
for j=1+i to n
如果mij != mji,则停止,关系R不是对称的
Step4 求传递闭包的关系矩阵A
如果A!=M,则停止,关系R不是传递的。
Step5 令B={}(空集,用于放置等价类元素)
Step6 令X= X-B(X 存放剩余元素)
Step7 如果X为空,则停止,否则令i是X中最小元素,B={}空集,B=B交{i}
Step8 for j=1 to n
如果mij=1,则B=B交{i}
Step9 按行输出B得到一个等价类,转到Step6
代码实现:
以X={1,2,3,4,5,6},R={(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,4),(2,3),(2,6),(3,2),(3,6),(4,1),(6,2),(6,3)}为例,给出代码
#include <stdio.h>
#include <stdlib.h>
int main()
{
int x[6]={1,2,3,4,5,6};
//写出关系矩阵
int Mr[6][6]={{1,0,0,1,0,0},{0,1,1,0,0,1},{0,1,1,0,0,1},{1,0,0,1,0,0},{0,0,0,0,1,0},{0,1,1,0,0,1}};
int n=6;
//判断关系是否自反
int flag=0;
for(int i=0;i<n;i++){
if(Mr[i][i]!=1){
printf("该关系不为等价关系");
flag++;
}
}
//判断关系是否对称
if(flag==0){
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(Mr[i][j]!=Mr[j][i]){
printf("该关系不为等价关系");
flag++;
}
}
}
}
//判断关系是否传递
if(flag==0){
//将关系矩阵储存到新的二维数组里
int B[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
B[i][j]=Mr[i][j];
}
}
//求传递闭包
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(Mr[i][j]==1){
if(Mr[i][k]==0&&Mr[j][k]==0){
Mr[i][k]=0;
}
else
Mr[i][k]=1;
}
}
}
}
//判断关系是否传递
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if( B[i][j]!=Mr[i][j]){
printf("该关系不为等价关系");
}
}
}
}
if(flag==0){
printf("该关系为等价关系\n");
printf("有如下等价类:\n");
// 求等价类
for(int i =0;i<n;i++){
int M[6]={0,0,0,0,0,0};
int x=0;
for(int j=0;j<n;j++){
if(Mr[i][j]==1){
M[x]=j+1;
x++;
}
}
printf("M[%d]={",i+1);
for(int k=0;k<=5;k++){
if(M[k]!=0){
printf("%d,",M[k]);
}
}
printf("}\n");
}
}
return 0;
}
最终得出以下结果