[이산수학] 반사관계 알고리즘

Reflexive Relation 은 반사관계로 관계 R이 정의된 집합의 모든 원소 a에 대해서 aRa가 성립하는 경우에 대해 R을 반사관계라고 정의한다. 

Irreflexive Relation는 비반사관계로 모든 원소가 반사관계를 만족하지 않는 이항관계로 정의한다.

간단하게 설명하자면

 

1  1  1

1  1  1

1  1  1

 

위와 같은 행렬에서 대각선에 있는 모든 행렬이 1이기 때문에 반사관계로 볼 수 있고

 

0  1  1

1  0  1

1  1  0

 

위와 같은 행렬에서는 대각선에 있는 모든 행렬이 0이기 때문에 비반사관계라고 볼 수 있다.

 

0  1  1

1  1  1

1  1  0

 

위와 같은 경우에는 반사, 비반사관계 둘 다 만족하지 않는다.

위와 같은 과정을 프로그래밍 해보겠다.

 

 

#include <stdio.h>

void ReflexiveRelation(int arr[][3]) { //크기가 3인 정사각행렬로 가정
	int a = 0;
	int b = 0;
	int c = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j && arr[i][j] == 1)
				a++;
			else if (i == j && arr[i][j] == 0)
				b++;
		}
	}
	if(a== 3)
		printf("반사관계!\n");
	else if(b==3)
		printf("비반사관계!\n");
	else
		printf("둘 다 아님!\n");

}

int main() {
	int arr1[3][3] = { {1,1,1},{1,1,1},{1,1,1} }; //반사관계
	int arr2[3][3] = { {0,1,1},{1,0,1},{1,1,0} }; //비반사관계
	int arr3[3][3] = { {0,1,1},{1,1,1},{1,1,0} }; //둘 다 아닌 경우

	ReflexiveRelation(arr1);
	ReflexiveRelation(arr2);
	ReflexiveRelation(arr3);
	
}

 

정의를 토대로 간단하게 프로그래밍 가능하다.