[이산수학] 관계(relation), 관계의 성질

1. relation(관계)

두 집합 setA 와 setB의 순서쌍의 부분집합이라고 볼 수 있다.

관계 예시: 
A → A, A = {1, 2, 3, 4}일때,
R = {(a, b)| a divides b} 일때 	- b를 나눌 수 있는 a라는 뜻

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

 

함수와 관계짓는다면, 함수가 관계의 부분집합이다.

(함수는 정의역당 하나의 공역만 매핑이 가능하지만, 관계는 multiple mapping 이므로)

 

 

2. relation properties(관계의 성질)

다음 성질들은 A → A 관계에서 일어나는 성질이다.

 

 

반사 관계 (reflexive)

모든 element에 대해 같은 원소끼리의 (예시: (a, a)) 관계가 성립할때

예시:
setA = {1, 2, 3}일때, (1,1), (2,2), (3,3)을 모두 포함하는 관계는 reflexive

matrix 표현시 =, ≥, ≤ 이 reflexive에 해당한다.

 

 

irreflexive(비반사 관계)

모든 element에 대해 같은 원소끼리의( 예시: (a, a)) 관계가 성립하지 않을때

예시: 
setA = {1, 2, 3}일때, (1,1), (2,2), (3,3) 모두 미포함하는 관계는 irreflexive

matrix표현시 <, > 이 irreflexive에 해당한다.

 

 

symmetry(대칭 관계)

모든 (a, b) 꼴 관계에 대해 (b, a)꼴도 존재할때

예시:
(1,3), (2,3) 관계가 있을때 이 관계가 symmetry가 될려면 (3,1), (3,2)도 포함해야 한다.

matrix표현시 =, is twin of()가 symmetry에 해당한다.

 

 

asymmetry(비대칭 관계)

모든 (a,b) 관계에 대해, 대칭인 (b, a) 관계는 존재하지 않을때, + 반사관계(a,a)꼴이 없을때

예시: 
(1,2), (1,3)이 존재하는 관계가 asymmetry가 될려면 (2,1), (3,1)이 존재하지 않아야 하며 
(1,1), (2,2), (3,3)도 존재하면 안 된다.

matrix표현시 <, >가 asymmetry에 해당한다.

 

 

antisymetry(반대칭관계)

a≠b면 (a,b)이 관계에 속하거나 (b,a)가 속해야 한다. (즉, a≠b인 경우 (a,b), (b,a)둘 중 하나만 존재) 

+(a=a), (b=b)관계가 둘 다 존재한다.

a=b일때는 관계는 신경쓰지 않는다.

예시1:
{(1,1), (2,2), (3,3)}은 antisymmetry다.
예시2:
(1,2)가 있는 관계가 antisymmetry가 될려면 (2,1)은 존재해선 안되고, (1,1), (2,2)가 존재해야 한다.

matrix 표현시 =, ≤, ≥가 antisymmetry에 해당한다. 

 

 

transitivity(전이 관계)

모든 관계에 대해 (a, b), (b,c) 관계가 있으면 (a,c) 관계도 존재해야 한다.

(1,2), (2,3) (3,4)가 있는 관계가 transitivity가 될려면:
(1,3), (2,4), (1,4)가 존재해야 한다.

 

 

3. 그래프로 나타낸 관계

reflexive: 모든 노드에 self loop가 있다

irreflexive: 모든 노드에 self loop가 없다

symmetry: 관계가 존재하는 노드들이 anti-parellel pair를 가진다

asymmetry: 관계가 존재하는 노드들이 anti-parellel pair를 안 가진다

antisymetry: 관계가 존재하는 노드들이 self loof를 가지고 anti-parellel pair를 안 가진다

transitivity: (a, b), (b, c)관계가 있으면 (a, c)관계도 존재한다