관계(2)[이산수학]

저번 포스팅에 이어서, 이번에는 합성관계, 합성관계의 거듭제곱, 추이관계와 거듭제곱의 관계, 폐포, 연결관계와 추이관계에 대해서 알아볼 것이다.
1.합성관계(composition Relation)

이걸 그림으로 표현하면

이렇게 된다. 뒤에 있는 관계가 먼저이기 때문에 관계행렬로 표현할 시 관계R이먼저 오게 된다.

2.합성관계의 거듭제곱

관계행렬로 나타내었을 때, R의 2승은 자기자신을 부울곱 해주면 된다.

거듭제곱과 추이관계에는 관계가 있는데 그 관계는

이것이다. 말로 하면 어려우니까 예제를 들어보자면

이렇게 할 수 있다. 이걸 또 증명해보자. 우선 관계R이 추이관계인지 알아봐야겠다.

그 후 추이관계와 거듭제곱의 관계를 이용해서 풀어보면

이렇게 된다.

3.폐포(Closure)
집합 A에 대한 관계를 R이라 하고, 관계가 가질 수 있는 성질을 P라고 할때, 집합 A에 대한 관계 S가 관계 R을 포함하면서 성질 P를 갖는다면
S를 R에 대한 P의 폐포 라고 한다.

예시를 보자면

관계 S가 관계 R을 포함하면서 반사관계의 성질을 갖는다. 따라서
S는 R에 대한 반사 폐포이다. 폐포는 그냥 그 성질로 바꿔주는 것이다.
폐포에는 반사폐포,대칭폐포,추이폐포가 있다.
반사폐포와 대칭폐포는 그냥 관계R을 반사관계,대칭관계로 바꿔주면 된다.
추이폐포도 추이관계로 만들어주면 되지만 그 전에 연결관계에 대해서 알아보겠다.

4.연결관계(Connectivity Closure)

이것도 예시를 들어보자.

원소의 개수가 2인 집합 A에 대한 관계 R이 있다.
그렇다면 연결관계는 R^1 + R^2 이다. (이해가 되실런지요,,,)
아무튼 이렇게 원소의 개수만큼 제곱을 해줘서 더해주면 그것이 연결관계이다.
그럼 이 연결관계와 추이관계는 어떤 연관이 있을까?

5.연결관계와 추이관계

바로 연결관계는 관계R의 추이 폐포이다!

한번 예제를 풀어보자.

이러한 예제가 있다. 집합 A의 원소의 개수는 4이므로
4제곱까지 한걸 다 합하면 그것이 추이폐포이다.

문제를 풀어보자면

이렇게 풀 수 있다. 짜잔~~
연결관계가 추이폐포이니까 추이폐포 R은
R = {(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)} 이다!

이상입니다.

저 혼자 공부하는것이므로, 만약 틀린것이 있다면 댓글로 지적해주시면 감사하겠습니다!