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

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

 

간단하게 구현 가능하다.