입 달린 감자의 코딩 블로그

Transitive Relation 은 추이관계로 aRb이고 bRc이면 aRc를 만족하는 관계이다.

추이관계의 판별하는 방법에는 정의에 의한 판별도 있지만 프로그래밍하기 쉽게 다른 판별법을 알아보자

1  1  1

0  0  0

0  0  1

위의 행렬을 R이라고 두고 기수만큼 거듭제곱을 해준다.

R^3

1  1  1

0  0  0

0  0  1

로 R^3 ⊂= R 을 만족시킨다. 일반화 시키면 기수가 n 인 R 행렬에서 R^n ⊂= R 이면 추이관계이다.

위를 만족시키면 추이관계가 성립하게 된다.(흠... 설명이 부족해 보인다?)

위 과정을 코딩해보겠다.

#include <stdio.h>

void MatrixMul(int mul[][3],int arr1[][3],int arr2[][3]) {//행렬의 곱셈을 논리곱으로 표현
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				mul[i][j] |= arr1[i][k] & arr2[k][j];
			}
		}
	}

}

void TransitiveRelation(int arr[][3]) {//행렬의 논리곱을 활용하여 추이관계 표현
	int result[3][3] = { 0 };
	MatrixMul(result,arr,arr);
	MatrixMul(result, result, arr); //R^3의 표현
	int a = 0;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[i][j] == 1 || result[i][j] == arr[i][j]) //포함관계 이므로 R이 1이거나 R과 R^3 같다면 a를 추가하는 방식으로 구현해보았다.
				a++;
		}
	}

	if (a == 9)
		printf("추이관계!\n");
	else
		printf("추이관계 아님!\n");
}

int main() {
	int arr1[3][3] = { {1,1,1},{0,0,0},{0,0,1 } };
	int arr2[3][3] = { {0,1,0},{0,1,1},{1,0,0 } };

	TransitiveRelation(arr1);
	TransitiveRelation(arr2);
}

앞에서 반사, 대칭, 추이적 관계를 설명했다. 이를 토대로 부분순서관계에 대한 개념을 다음글에 설명하겠다.

Symmetric Relation 은 대칭관계로 집합 X 상의 임의의 두 원소 a, b에 대하여 정의된 이항관계 R이 대칭관계라 함은 aRb이면 bRa를 만족한다고 정의한다.

Antisymmetric Relation 은 반대칭관계로 집합 X 상의 임의의 두 원소 a, b에 대하여 정의된 이항관계 R이 반대칭관계라 함은 aRb이고 bRa이면 a=b 를 만족한다고 정의한다.

쉽게 예를 들어보자

1  1  1

1  1  1

1  1  1

위 행렬은 정의로나 시각적으로도 대각선을 기준으로 대칭임을 알 수 있다.

1  1  1

0  1  1

0  0  1

위 행렬은 aRb 이고 bRa 인 경우가 대각선에 존재하는데 그것은 즉  a=b를 만족하게 된다. 반대칭인 것이다.

1  0  1

1  0  1

1  0  1

위 행렬은 두 개의 정의를 모두 만족시키지 못하므로 둘 다 아닌 경우가 된다.

자 위 과정을 프로그래밍 해보자

void SymemetricRelation(int arr[][3]) {
	int a = 0;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[i][j] == arr[j][i])
				a++;
		}
	}

	if (a == 9)
		printf("대칭관계!\n");
	else if (a == 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] = { {1,1,1},{0,1,1},{0,0,1} };
	int arr3[3][3] = { {1,0,1},{1,0,1},{1,0,1} };

	SymemetricRelation(arr1);
	SymemetricRelation(arr2);
	SymemetricRelation(arr3);
}

간단하게 구현 가능하다.

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);
	
}

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