이산구조기초-관계3

합성관계

합성관계(Composition Relation)의 정의

두 개 이상의 관계를 합성하여 새로운 관계를 생성

집합 A에서 집합 B로의 관계 R과 집합 B에서 집합 C로의 관계 S가 있을 때, 관계 R에 대해서 공변역이면서 관계 S에 대해서는 정의역인 집합 B가 있기 때문에 관계 R과 S는 합성 가능

집합 A에서 집합 B로 가는 관계 R (R:A→B)과 집합 C에서 집합 B로 가는 관계 S(S:C→B)의 경우는 관계 R의 공변역(집합 B)과 관계 S의 정의역(집합C)이 같지 않으므로 합성관계가 성립될 수 없다.

합성관계는 교환법칙이 성립하지 않음

합성관계의 거듭제곱

집합 A={a1,a2,…,am}에서 집합 B={b1,b2,…,bn}으로 가는 관계 R은 m×n 크기의 관계행렬 Mr로 작성
집합 B에서 집합 C={c1,c2,…,cs}로 가는 관계 S는 n×s 크기의 관계행렬 Ms로 작성
관계 S∘R은 이 두 관계행렬 Mr과 Ms의 부울곱으로 구함

합성관계의 거듭제곱: R^n

추이관계와 거듭제곱의 관계

관계의 폐포

폐포의 정의

폐포(Closure): 원래의 관계에 순서쌍 원소를 추가하여 특정 성질에 맞게 만든 것

반사폐포(Reflexive Closure)


추이폐포(Transitive Closure)


연결관계(Connectivity Closure: R^*)