위키득계정 ↗
과학

추이적 폐포

추이적 폐포과학
영문명
Transitive closure
표기 예
R⁺
포함 범위
양의 유한 단계로 이어지는 관계
주의
자기 쌍을 무조건 추가하지 않음
추이적 폐포는 이항 관계를 포함하는 가장 작은 추이 관계이다. 기존 관계를 유한 번 이어서 도달할 수 있는 모든 순서쌍을 추가하며 보통 R⁺로 나타낸다.

여러 단계의 연결

R={(1,2),(2,3),(3,4)}라면 (1,3), (2,4), (1,4)가 필요하다. 두 단계뿐 아니라 세 단계를 통해 이어지는 쌍도 포함해야 전체 관계가 추이적이 된다.

원래 쌍을 보존한다

폐포를 만들 때 기존 관계의 쌍은 지우지 않는다. R을 포함하는 추이 관계가 반드시 가져야 하는 연결만 더해 가장 작은 결과를 만든다.

순환하면 자기 쌍이 생긴다

R={(1,2),(2,1)}에서는 두 단계를 거쳐 1에서 1로, 2에서 2로 돌아온다. 따라서 추이적 폐포에 (1,1)과 (2,2)가 들어간다. 반면 순환 경로가 없으면 자기 쌍이 반드시 생기는 것은 아니다.

반사 추이적 폐포와 비교

길이 0인 경로까지 허용해 모든 자기 쌍을 포함하면 반사 추이적 폐포를 얻으며 흔히 R*로 나타낸다. R⁺와 R*의 차이는 0단계 연결을 포함하는지에 있다.

관련 문서

추이 관계 / 관계의 합성 / 이항 관계 / 반사적 폐포 / 반사 관계 / 순서쌍 / 유향 그래프