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

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

 

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