南京邮电大学离散数学实验二（二元关系的性质判定）

1

（1）全局变量：

#define MAX 100  
bool flag_ref, flag_irr, flag_sym, flag_dis, flag_tra;  //判断自反性、反自反性、对称性、反对称性、传递性的 flag  
int arr[MAX][MAX];  
int n;

（2）函数调用关系

int main()
{  
   initial();          //相关初始化，从键盘获取信息。  
    Reflexive();        //自反性  
    Irreflexive();      //反自反性  
    Symmetrical();      //对称性  
    Dissymmetrical();   //范对称性  
    Transitive();       //传递性  
    print();            //打印结果  
    return 0; 
} 

2、核心代码

（1）代码

//自反性  
void Reflexive() {  
    for (int i = 0; i < n; i++) {  
        //如果存在对角线为0，则为假。 
        if (arr[i][i] == 0) {   
            flag_ref = 0;  
        }  
    }  
}  

//反自反性  
void Irreflexive() {  
    for (int i = 0; i < n; i++) {
    	//如果存在对角线为1，则为假。     
        if (arr[i][i] == 1) {   
            flag_irr = 0;  
        }  
    }  
}  

//对称性  
void Symmetrical() {  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
       		//如果存在arr[i][j] != arr[j][i]，则为假。  
			if (arr[i][j] != arr[j][i]) {   
				flag_sym = 0;  
			}  
		}  
	}  
} 

//反对称性  
void Dissymmetrical() {  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) { 
 		//如果存在arr[i][j] = arr[j][i]，则为假。   
            if (arr[i][j] == arr[j][i]) {  
                flag_dis = 0;  
            }  
       }  
    }  
}  
	  
	  
//传递性  
void Transitive() {  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            for (int k = 0; k < n; k++) {  
				//如果存在arr[i][j] = 1 且 arr[j][k] = 1，找不到arr[i][k] = 1，则为假。  
                if (arr[i][j] && arr[j][k] && !arr[i][k]) {   
                    flag_tra = 0;  
                }  
            }  
       }  
    }  
}  

（2）时间复杂度为O（n2）和O（n3）

3、测试数据及结果结论

（1）测试1

请输入元素个数  
	1  
请输入集合各元素  
	1  
集合A = {1}  
请输入关系矩阵  
	1  
  
具有以下关系  
	自反性  
	对称性  
	传递性 

测试2

请输入元素个数  
	3  
请输入集合各元素  
	1 4 5  
集合A = {1,4,5}  
请输入关系矩阵  
	1 0 1  
	0 0 0  
	1 0 0  
	  
具有以下关系  
	对称性 

测试3

请输入元素个数  
	2  
请输入集合各元素  
	1 3  
集合A = {1,3}  
请输入关系矩阵  
	1 0  
	0 1  
	  
具有以下关系  
	自反性  
	对称性  
	传递性  

全部代码

#include <iostream>
using namespace std;

#define MAX 100
bool flag_ref, flag_irr, flag_sym, flag_dis, flag_tra;  //判断自反性、反自反性、对称性、反对称性、传递性的 flag
int arr[MAX][MAX];
int n;

void initial(){
	int a[MAX];
	flag_ref = flag_irr = flag_sym = flag_dis = flag_tra = 1;
	cout << "请输入元素个数" << endl;
	cin >> n;
	cout << "请输入集合各元素" << endl;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	cout << "集合A = {";
	for (int i = 0; i < n - 1; ++i) {
		cout << a[i] << ",";
	}
	cout << a[n - 1] << "}" << endl;
	cout << "请输入关系矩阵" << endl;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> arr[i][j];
		}
	}
	cout << endl;
}

//自反性
void Reflexive() {
	for(int i = 0; i < n; i++){
		if(arr[i][i] == 0){
			flag_ref = 0;
		}
	}
}


//反自反性
void Irreflexive() {
	for(int i = 0; i < n; i++){
		if(arr[i][i] == 1){
			flag_irr = 0;
		}
	}
}


//对称性
void Symmetrical() {
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(arr[i][j] != arr[j][i]){
			flag_sym = 0;
			}
		}
	}
}


//反对称性
void Dissymmetrical() {
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(arr[i][j] == arr[j][i]){
			flag_dis = 0;
			}			
		}
	}
}


//传递性
void Transitive() {
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				if(arr[i][j] && arr[j][k] && !arr[i][k]) {
					flag_tra = 0;
				}	
			}
		}
	}
}

void print(){
	cout << "具有以下关系" << endl;
	if (flag_ref) {
		cout << "自反性" << endl;
	}
	if (flag_irr) {
		cout << "反自反性" << endl;
	}
	if (flag_sym) {
		cout << "对称性" << endl;
	}
	if (flag_dis) {
		cout << "反对称性" << endl;
	}
	if (flag_tra) {
		cout << "传递性" << endl;
	}
	cout << endl;
}

int main() {
	initial();
	Reflexive();
	Irreflexive();
	Symmetrical();
	Dissymmetrical();
	Transitive();
	print();
	return 0;
}