관계

◎ 관 계

관심대상의 모임인 집합에서 2개 이상의 원소들 간에는 수많은 관계가 있을 수 있다. 예를 들면 "동창관계", "친척관계", 등의 관계가 있을 수 있다.
이와 같은 관계는 전산학의 이론분야와 응용분야에서 널리 적용된다. 예를 들면 관계 는 자료구조에서 데이터들 간에 내재된 관계를 함축적으로 표현하기 위한 수학적 모델로 쓰이며, 프로그램의 구조나 계산이론(Computation theory) 또는 알고리즘의 분석 등에서도 응용된다.

1. 관계의 개요

·순서쌍(Ondered pair) ∼ 순서로 구분되는 대상의 쌍 (a,b).
·곱집합(Product set, Cartesian product) ∼ 공집합(empty)이 아닌
임의의 두 집합 A,B에 대하여

표시법. 곱집합 AxA는 A²으로 표시하고 AxAx…xA=Aⁿ으로 표기한다.

예제 1. 두 집합 A={a,b}, B={1,2,3}에 대하여

주의 :

요점 : 공집합이 아닌 임의의 두 유한집합 A,B에 대하여
, 여기서 은 집합 A의 원소개수

정의 : [관계(이항관계, relation or binary relation)]

특히 R이 A에서 A로의 관계 (즉, )일 때 R을 A에 관한 관계(relation on A)라고 한다.

예제 2. A={1,2,3} 에 대하여
① a=b인 관계가 성립하는 순서쌍 (a,b) 를 원소로 하는
A에 관한 관계

② a≤b인 순서쌍을 원소로 하는 A에 관한 관계

표시법 : 곱집합 AxB의 원소인 임의의 순서쌍 (x,y)에 대하여 이면 "x는 y에 대하여 R관계가 있다"라 고 하며 xRy로 표시한다.
이면 "x는 y에 대하여 R관계가 없다"라고 하며 xRy로 표기하기로 한다.
특히 관계 의 순서쌍 모임에서 의 첫 번째 원소의 집합을 R의 정의역이라 하고 Dom(R), 두 번째 원소의 집합을 R의 치역이라 하고 Ran(R)로 표시한다.

정의. [여관계 Complementary relation ], 또는 관계 R이 AxB의 부분집합에서을 여관계라 하며 로 표기

즉 =

기호표기 :

예제 3. R={(2,c),(1,d),(3,d),(2,a)}일 때
Dom(R)={1,2,3} 이고 Ran(R)={a,c,d}

정의. [역관계 inverse relation], R^-1
집합 A에서 B로의 관계 R에 대하여, B에서 A로의 관계를 역관계라 하고 R^-1 로 표기한다.
즉

요약 : 1.
2.
3.

예제 4.

정리. 관계 가 주어질 때

2. 관계의 표현

관계를 표현하는 방법
⑴ 관계의 성질을 서술하는 방법
"집합 A={1,2,3} 대하여 x=y인 관계 R 등
⑵ 관계 R에 속하는 순서쌍들을 집합에 열거하는 방법
"R={(1,1),(2,2),(3,3)}등
⑶ 관계를 구성하는 순서쌍의 원소간의 관계를 그래프로 표현하는 방법
ⅰ) 화살표 도표 (arrow diagram)
ⅱ) 좌표 도표 (coordinate diagram)
ⅲ) 관계행렬 (relation matrix)
ⅳ) 유항 그래프 (directed graph)

ⅰ) 화살표 도표 (arrow diagram)

예제 5. 집합 A={1,2,3,4}, B={1,4,6,8,9}에 대하여
관계 이 주어질 때 R을 화살표 도표로 표현하라

(풀이)

ⅱ) 좌표도표 (coordinate diagram) - 좌표도형(A, B가 유한집합일 때)
A에서 B로의 관계 R이 주어질 때 A 원소들을 어떤 수평축 상의 점들로 표시하고 B의 원소들은 어떤 수직 축 상의 점들로 표시할 때 A의 점들을 지나는 수직선들과 B의 점들을 지나는 수평선들과의 교차점에 대한 표현을 AxB의 자료도형

예제 6. A=B={1,3,5,7,9}일 때 를 집합적 관계로 표현하라.

(풀이)
R={ (1,1),(1,3),(1,5),(1,7),
(3,1),(3,5),(5,1),(5,3),(7,1) }

ⅲ) 관계행렬 (Relation matrix)

집합 에 대하여 R을 A에서 B로의 관계라 할 때

인 mxn 행렬 M_R을 R 관계행렬이라 한다.

예제 7. A={1,3,5,7,9},B={2,4,6,8}일 때 관계 을 M_R로 표현하라

(풀이)

ⅳ) 유향 그래프 (directed graph)

집합 A는 유한 집합이고 R은 A에 대한 관계일 때 집합 A의 원소들을 그래프의 정점(vertex)으로 표시하고, 각 원소와 대응되는 정점은 등으로 표시되며 R이면 정점 에서 정점 까지의 방향을 잦는 연결선(edge)로 묶는다. 이와 같은 관계 R을 그림으로 표시한 결과를 유향그래프(directed graph) 또는 디그래프(digraph)라 한다.

예제 8. 집합 A={a,b,c,d,e}가 주어질 때 그것의 관계
R={(a,b),(b,b),(b,d),(c,e),(d,b),(b,e)}이 주어졌다면 이 때 관계를 유향 그래프로 표시하여라.

(풀이)

예제 9. 유향그래프에서의 관계 R ?

정의. R은 집합 A에 대한 관계일 때, R의 유향그래프에서
① 의 내차수(in-degree) ∼ a를 끝점으로 하는 간선의 수
즉, 인 b의 개수
② 의 외차수(out-degree) ∼ a를 시점으로 하는 간선의 수
즉, 인 b의 개수

예제 10. A={a,b,c,d}, R은 A에 대한 관계이고
일 때 모든 정점에 대한 내차수와 외차수를 구하라.

(풀이)

예제 11. 집합A={1,4,5}일 때 아래 유향그래프의 관계행렬 M_R과 관계 R ?

(풀이)

3. 합성관계 (Composation selation)

집합 A,B,C에 대하여 R은 A에서B로, S는 B에서 C로의 관계라 할 때 R·S(R과 S의 합성관계)는 A에서 C로의 관계로서 다음과 같다.

예제 12. A={2,3,8,9}, B={4,6,18}, C={1,4,7,9}이고

일 때 R·S=? 또한 화살표 도표를 그려라 !

(풀이) R·S={(2,4),(2,7),(2,9),(2,9),(3,7),(3,9)}

예제 13. 집합 A={1,2}, B={3,4}, C={5,6}, 관계 일 때 R={(1,3),(1,4)}, S={(3,5),(4,5)}이다. AxC이 순서쌍 중에서 R·S에 속하는 것은?

풀이. R·S={(1,5)}

예제 14 A={a,b,c}, 관계 일 때

풀이

※ Boolean matrix (부울 행렬) ~ 모든 행렬 원소의 값이 0또는 1인 행렬
← 관계 및 그래프 이론에서 사용

① 부울 연산자 의 정의

② 을 mxn 부울 행렬일 때

③ A는 mxp인 부울 행렬, B는 pxn인 부울 행렬일 때, A와 B의 부울곱 (Boolean ploduct)

예제 15. 집합 A,B,C 가 다음과 같은 부울 행렬일 때

아래의 연산을 계산하면 다음과 같다.

참고. 예제 14에서

예제 15. 예제 12를 관계행렬을 사용하여 R·S를 구하라.

(풀이)

예제 16. 관계 R={(1,1),(3,1),(2,3),(4,2)}일 때

정리 2. 집합 A,B,C,D에 대하여이면 임을 보여라.

(증명)

예제 17. R={(1,2),(3,4),(2,2)}, S={(4,2),(2,5),(3,1),(1,3)}일 때

①

②

정리 3. 집합 A,B,C에 대해서 이면

(증명)

정리 4. 집합 에 대하여 관계 라 할 때 관계행렬 와 는 각각 의 크기를 가지며 은 nxm크기를 가진다. 또한 이다

(증명)

요점. 관계 R이 집합 A에 대한 관계라면 임의의 n에 대하여

4. 관계의 성질

집합 A에 관한 관계 R은 특정 성질에 따라 기본적으로 다음과 같이 나누어진다.

(1) 반사관계(Reflexive relation)와 비 반사관계(Irreflexive relation)

정의. 집합 A에 관한 관계 R이 주어질 때 임의의 원소 에 대하여

정의. 집합 A에 관한 항등관계(Identity relation)은 I_A로 표시하고 다음과 같이 정의한다.

예제 19. ① I_A는 반사관계이다.
② 라 하면 R은 비 반사관계이다.
③ 집합 A={1,2,3}와 관계 R={(1,1),{2,3)}이 주어지면 R은 반사관계도 비 반사관계도 아니다.

정리 5. 집합 A에 관한 관계 R이 주어지면
⑴ R은 반사관계
⑵ R은 비 반사관계

예제 20.

예제 21.

예제 22.
반사, 비 반사도 아닌 관계행렬

예제 23. 집합 A={1,2,3,4}이고 관계 R이 다음과 간이 주어질 때 반사, 비 반사관계를 구별하여라.

: 반사, 비 반사도 아님
: 반사
: 반사아님
: 비 반사관계
: 반사관계
: 반사관계

(2) 대칭관계(Symmetric relation)와 비 대칭관계(Asymmetric relation)

정의. 집합 A에 관한 관계 R이 주어질 때 임의의 원소 에 대하여
·에 대하여 일 때 R을 대칭관계
·에 대하여 일 때 R을 비 대칭관계
·이고 일 때 a=b인 관계R을 반 대칭관계(anti - symmetric relation)이라 한다.

요점. 집합 A에 대한 관계 R을 관계행렬 로 표현했을 때 대칭관계는 이면 이면 이다. 따라서 관계 R이 대칭이면

정의. 라 표시했을 때 .

· 비대칭관계는 이면 이고 모든 i에 대하여
즉, M_R의 모든 대각원소는 0이다.
· 반 대칭관계는 일 때 이거나 이다.

예제 24.

예제 25. A=Z일 때 관계 은 어떤 관계인가?

(풀이) ① 이면 이므로 비대칭관계
② 이면 또는 이므로 반 대칭관계

(3) 추이관계(Transitive relation)

정의. 집합 A에 대한 관계 R이 주어질 때 임의의 인 관계 R을 추이관계라 한다.

참고. 논리행렬 이 주어질 때 일 때 인 논리행렬 즉, 일 때 R은 추이관계이다.

예제 26.

예제 27. 예제 25의 R은 추이관계이다.

5. 동치관계와 분할(Equivalence relation and Partition)

정의. 집합 A의 관계 R의 동치관계와 합은 R이 반사,대칭,추어관계를 만족하는 관계 R을 말한다.

예제 28. 집합 A={1,2,3,4}에 대하여 R={(1,1),(1,2),(2,1),(2,2),(3,4),(4,3),(3,3),(4,4)}일 때 R은 동치관계 이다.

(풀이)

예제 29. A=Z 일 때 는 동치관계가 아니다.
에 대하여 그러나 따라서 R은 대칭관계가 아니다.

예제 30. A=Z이고 은 동치관계이다.

(풀이) ① 반사관계 :
② 대칭관계 :

③ 추이관계 :

정의. 집합 A에 대하여 R이 동치관계일 때 에 대하여 R에 대한 a의 동치류(equivalence class) [a]은 로 정의한다.

참고. 동치류

예제 31. 예제 28의 R에 대한 동치류

정리 6. 이 에 관한 동치관계일 때 다음의 성질이 만족한다.

(증명)

정의. 집합에 A대한 동치관계 R이 주어질 때 집합 A의 모든 원소들의 동치류의 모임을 A의 몫집합(Quotient set)라 하고 A/R로 표시한다.

예제 32. 예제 31에서

정의 [분할(Partition)]
공집합이 아닌 집합 A에 대하여 공집합이 아닌 이 주어질 때 이 A의 분할이라 하는 것은 다음의 조건을 만족하여야 한다.

또한 분할 내에 있는 부분집합 을 블록(block)라 한다.

예제 33. Z에서 A₁과 A₂를 각각 홀수와 짝수의 집합이라 하면 는 Z의 분할이다.

정리 7. 집합 A의 동치관계 R이 주어질 때 A의 몫집합 A/R의 분할이다.

(증명)

정리 8. A의 분할 가 주어져있다. 이 때 A에 관한 동치관계 R을 정의할 수 있고, R에 대응하는 동치류들은 A의 분할의 블록들이다. 여기서 불럭은 분할의 원소 이다.

(증명)

예제 34. A={1,2,3,4,5,6,7,8}이며 A의 분할 ={(1),(2),(3),(4),(5),(6),(7),(8)}일 때 A에 관한 동치관계 R=

(풀이)

6. 관계의 폐쇄

정의. [폐쇄, closure]
관계 R을 포함하고, 어떤 성질 P를 포함하는 가장 작은 관계 R₁을 R의 폐쇄(closure)라 한다.

정의. [반사석 폐쇄(reflexive closure)]
한 집합 A에 관한 관계 R이 주어질 때 R이 반사관계가 아니면라 정의하면 은 반사적 페쇄이다.

예제 35. A={1,2,3,4}관계 F={(1,2),(2,1),(2,2),(3,2)}일 때 A에 대한 반사적 폐쇄

정리 9. [대칭적 폐쇄(Symmetric closure)]
R은 A에 대한 관계이고 R이 대칭관계가 아니면 은 대칭적 폐쇄이다.

예제 36.

정의. [경로 Path]
한 집합 A에 대한 관계 R이 주어질 때 시점 a에서 종점 b까지 길이가 n인 경로(path of length n)라 하는 것은 이 존재하고 유한수열 을 나타낸다.
특히 a=b일 때의 경로를 순회(cyle)이라 한다.

표기 : 유한수열 으로 표시하기로 한다.

예제 37.
① <1,2,1,6,5>는 (1,2),(2,1),(1,6),(6,5)이므로 길이4인 경로

② <1,2,3,4,5>는 (1,2),(2,3),(3,4),(4,5)가 없으므로 경로가 없다.
③ <5,4,2,1,6,5>는 (5,4),(4,2),(2,1),(1,6),(6,5)이므로 길이는 5인 순회이다.

참고. 집합 A에 관계 R이 주어질 때, 에 대하여, 일 때, 은 시점 a에서부터 종점 b까지 길이 n인 경로가 있음을 의미한다.

정의. [연결관계(Connectivity relation)와 도달관계(reachability relation)]

R의 연결관계 :

R의 도달관계 :

참고.

예제 38. A={1,2,3,4}, 관계R={(1,2),(2,3),(3,4),(2,1)} 일 때

정의. [추이적 폐쇄 Transitive closure]

를 R의 추이적 폐쇄라고 한다.

참고: R에서 추이적으로 얻을 수 있는 모든 순서쌍들은 에 속하므로
는 추이적 폐쇄이다.

예제 39. A={1,2,3,4}이고 R={(1,2),(2,3),(3,4),(2,1)}이고 일 때 R의 추이적 폐쇄 를 구하라.

(풀이)
방법 1 : 유향그래프에 의한 방법

방법 2 : 관계행렬에 의한 방법

정리 10. A는 집합이고 . R가 집합 A에 관한 관계일 때 이다. 즉, 을 구하는데 이상으로 R의 부울 곱을 할 필요가 있다.

* Wanshall의 추의적 폐쇄 *

정리 11. [Wanshall 알고리즘]
Step 1. 의 1을 로 모두 옮겨 쓴다.
Step 2. 성분1인 의 k열의 위치와 성분1인 의 k행의 위치 을 나열
Step 3. 의 의 위치에 1을 쓴다.
에서 을 구하는 알고리즘을 Wanshall의 알고리즘이라 한다
여기서이다.

예제 40. 위의 예제에서

k=1일 때 의 1이 있는 위치를 의 같은 위치에 1을 넣는다.
의 1열의 위치 (=2행)
1행의 위치 (=2열) 이므로 (,)위치에 1삽입.

k=2일 때 의 1이 있는 위치를 의 같은 위치에 1을 넣고 의 2열의 위치 (=1행, =2행)
2행의 위치 (=1열, =2열, =3열)이므로

k=3일 때 마찬가지로 의 3열의 위치 (=1행, =2행) 3행의 위치 (=4열)

k=4일 때 위와 마찬가지로 의 4열 위치 (1, 2 ; 3행), 4행 위치 (없음)