[이산수학]관계의 폐포(Closure)란? 반사폐포, 대칭폐포를 관계행렬, 방향그래프로 나타내기

이산수학_관계의 폐포(Closure)란? 반사폐포, 대칭폐포

 

 

폐포는 원래의 관계에 순서쌍 원소를 추가하여 특정 성실에 맞도록 만드는 것을 가리킵니다. 예를 들어 지역민만 대출할 수 있는 도서관이 있다고 합시다. 도서관 데이터베이스는 지역민 정보만 입력하고 검색할 수 있겠지요. 하지만 내년부터 다른 동네주민들도 책을 빌릴 수 있도록 시스템을 변경한다고 합니다. 이제는 다른 동네 주민들 정보도 입력하고 검색할 수 있도록 데이터를 추가해야겠네요. 이렇게 이전 관계에 다른 관계를 더하면서 새로운 성질을 가지게 되는 것을 페포라고 합니다. 

 

■ 폐포의 정의

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

 

페포를 만들기 위해서는 이전 관계가 가지고 있던 순서쌍에 원소를 추가하는 방법을 써야 합니다. 즉 이전 관계의 성질 또는 의미를 그대로 유지하면서 새로운 성질을 추가적으로 갖도록 만드는 것입니다. 

 

■ 반사폐포(Reflexive Closure)

반사페포는 이전 관계 R의 성질을 그대로 유지하면서 반사관계를 갖도록 관계 S를 만드는 것입니다. 그래서 관계 R이 집합 A에 포함되는 모든 원소에 대해 (a, a) 형태의 순서쌍을 관계 R에 추가하면 됩니다. 

 

S = R ∪ {(a,a)|a ∈ A}

 

예를 들어

집합 A = {1, 2, 4} 

집합 A에 대한 관계 R = {(1,1),(1,4),(2,1),(4,2)}

위의 두 요건을 이용해 반사페포 S를 구해봅시다.

 

관계 S는 관계 R의 원소들과 (1,1),(2,2),(4,4)도 가지고 있어야 합니다. 이미 관계 R은 (1, 1)를 포함하고 있으니 나머지를 추가해주면, S = {(1,1),(1,4),(2,1),(2,2),(4,2),(4,4)} 가 됩니다. 

 

그럼 이제 집합 A과 관계 R. 반사페포 S를 관계행렬과 방향그래프로 구해보겠습니다.

 

관계 R / 반사폐포 S

 

■ 대칭폐포(Sysmmetric Closure)

집합 A에 대해, 관계 R를 포함하면서 대칭관계를 갖는 관계 S

대칭페포 정의

대칭페포 역시 이전 관계 R의 성질은 그대로 가지면서 대칭관계까지 갖는 것이 대칭폐포 S가 됩니다. 대칭관계가 되기 위해서 (a, b)가 관계 R에 있을 때, (b, a)도 포함되어야 합니다. 

 

예를 들어

집합 A = {1, 2, 4} 

집합 A에 대한 관계 R = {(1,1),(1,4),(2,1),(4,2)}

위의 두 요건을 이용해 대칭페포 S를 구해봅시다.

 

관계 S는 관계 R의 원소들과 각 원소의 대칭인 (4,1),(1,2),(2,4)를 가지고 있어야 합니다. 그래서 대칭폐포 S = {(1,1), (1,2),(1,4),(2,1),(2,4),(4,1),(4,2)} 가 됩니다. 

 

그럼 이제 집합 A과 관계 R. 대칭페포 S를 관계행렬과 방향그래프로 구해보겠습니다.

 

관계 R / 대칭페포 S

 

 

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------