관계(Relations)

• 정의
  • 이진관계
  • 하나의 집합에 대한 관계
  • 반사 관계
  • 대칭, 반대칭 관계
    • 주의1. 관계에 있어 대칭과 반대칭은 반대 의미가 아니다
    • 주의2. 반대칭(antisymmetric)과 비대칭(asymmetric)은 다르다
    • 대칭과 반대칭 예제
  • 전이적 관계
  • 관계 결합
• 관계의 폐쇄(closure)
• 참고문헌

정의

이진관계

• binary relation

Let A and B be sets. A binary relation from A to B is a subset of A \(\times\) B.

• A 에서 B로의 이진관계는 \(A \times B\)의 부분집합이다.
• A 에서 B로의 이진관계는 순서쌍의 집합 R 이다.
  • (A의 원소, B의 원소)는 집합 R의 원소.
  • \(( a, b ) ∈ R\)를 \(a \ R \ b\) 로도 표기한다.
  • \(( a, b ) \notin R\)는 \(a \cancel{R} \ b\) 로도 표기한다.
• 이진관계는 두 집합의 원소들 사이의 관계를 표현한다.
  • n 개 집합의 원소들 사이의 관계는 n항 관계(n-ary relations)라 한다.

하나의 집합에 대한 관계

• Relations on a Set

A relation on a set A is a relation from A to A.

• "집합 A에 대한 관계"는 A에서 A로의 관계를 말한다.
• 집합 A에 대한 관계는 \(A \times A\)의 부분집합이다.

반사 관계

• reflexive relation

A relation R on a set A is called reflexive if \((a, a) ∈ R\) for every element \(a ∈ A\).

• 집합 A의 모든 원소 a 에 대해 \((a, a) ∈ R\) 인 관계.

반사적 관계를 행렬로 표현하면 다음과 같은 모양을 갖는다.

한편 비반사적 관계(irreflexive relation)는 \((a, a) ∉ R\) 이고, 다음과 같은 모양을 갖는다.

다음은 반사적 관계도 아니고 비반사적 관계도 아닌 경우이다. (각 원소의 자기 자신과의 관계에 0과 1이 섞여 있다)

예제를 보자.

집합 \(A = \{ 1,2,3,4 \}\) 에 대한 관계 \(R_1 ~ R_6\) 중에서 반사적 관계에 해당되는 것들을 찾아보자.

• \(R_3, R_5\): \((1, 1), (2, 2), (3, 3), (4, 4)\)가 모두 있으므로 반사적 관계이다.

한편 방향성 그래프로 그리면 반사 관계를 쉽게 이해할 수 있다.

반사적 관계는 다음과 같이 각 원소가 자신에게 돌아간다.

대칭, 반대칭 관계

• symmetric, antisymmetric

A relation R on a set A is called symmetric if \((b,a) ∈ R\) whenever \((a,b) ∈ R\), for all \(a,b ∈ A\).
A relation R on a set A such that for all \(a, b ∈ A\), if \((a, b) ∈ R\) and \((b, a) ∈ R\), then \(a = b\) is called antisymmetric.

• 집합 A에 대한 관계 R이 있다고 하자.
• 집합 A의 원소 a, b에 대해,
  • \((a, b) ∈ R\) 일 때, \((b, a) ∈ R\)인 관계를 대칭(symmetric) 관계라 한다.
  • \((a, b) ∈ R\) 일 때, \((b, a) ∈ R\) 이고, \(a = b\) 인 관계를 반대칭(antisymmetric) 관계라 한다.

행렬로 나타내면 쉽게 이해할 수 있다.

• 대칭관계: \(M_r = [m_{ij}]\)에서 \(m_{ij} = m_{ji}\) 이면 대칭관계.
• 반대칭관계: \(M_r = [m_{ij}]\)에서 \(i \ne j\) 일 때, \(m_{ij} = 0\) 또는 \(m_{ji} = 0\) 이면 반대칭 관계.

방향성 그래프로 대칭 관계를 그려보면 양쪽 방향을 가리키는 화살표로 이해할 수 있다.

만약 화살표가 한쪽 방향만 가리킨다면 대칭 관계가 아니다.

주의1. 관계에 있어 대칭과 반대칭은 반대 의미가 아니다

\(R=\{(1,1),(2,2),(3,3),(4,4)\}\) 같은 경우는 대칭이면서 반대칭이다.

주의2. 반대칭(antisymmetric)과 비대칭(asymmetric)은 다르다

• 대칭의 반대는 반대칭이 아니라 비대칭이다.
• 비대칭은 \(∀a, b ∈ a R b \Rightarrow ¬ (b R a)\).

대칭과 반대칭 예제

다음 관계들에서 대칭과 반대칭 관계를 찾아보자.

• 대칭: \(R_2, R_3\)
• 반대칭: \(R_4,R_5,R_6\)

대칭 반대칭은 해당되는 곳에 1을 표시한 행렬로 그려보면 이해가 쉽다.

대칭은 \(M_r = [m_{ij}]\)에서 \(m_{ij} = m_{ji}\) 이다.

반대칭관계는 \(M_r = [m_{ij}]\)에서 \(i \ne j\) 일 때, \(m_{ij} = 0\) 또는 \(m_{ji} = 0\) 이다.

그러면 \(R_1\)은 왜 대칭도 반대칭도 아닌가?

• \((3,4) ∈ R\) 인데, \((4,3) ∉ R\) 이므로 대칭이 아니다.
• \((1,2) ∈ R\) 이고, \((2,1) ∈ R\) 이므로 반대칭이 아니다. 적어도 둘 중 하나는 0 이어야 한다.

전이적 관계

• transitive
• 추이적 관계라고도 한다.

A relation R on a set A is called transitive if whenever \((a,b) ∈ R\) and \((b,c) ∈ R\), then \((a,c) ∈ R\), for all \(a,b,c ∈ A\).

• 집합 A에 대한 관계 R이 모든 \(a,b,c ∈ A\) 에 대해…
  • \((a,b) ∈ R\) 이고 \((b,c) ∈ R\) 일 때, \((a,c) ∈ R\) 이면 전이적 관계라 한다.

전이적 관계를 행렬로 나타내면 \(M_r = [m_{ij}]\)에서 \(m_{ij} = 1, m_{jk} = 1\) 일 때, \(m_{ik} = 1\)인 행렬이다.

다음 관계들에서 전이적 관계를 찾아보자.

관계 \(R_4, R_5, R_6\)이 전이적이다.

• \((a,b) ∈ R\) 이고 \((b,c) ∈ R\) 인 관계는 모두 다음과 같다.
  • \((3,2), (2,1)\).
  • \((4,2), (2,1)\).
  • \((4,3), (3,1)\).
  • \((4,3), (3,2)\).

이 네 관계가 모두 전이적인지만 확인하면 된다.

• \((3,1)\): \((3,2), (2,1) ∈ R\) 이면서, \((3,1) ∈ R\)을 만족.
• \((4,1)\): \((4,2), (2,1) ∈ R\) 이면서, \((4,1) ∈ R\)을 만족.
• \((4,1)\): \((4,3), (3,1) ∈ R\) 이면서, \((4,1) ∈ R\)을 만족.
• \((4,2)\): \((4,3), (3,2) ∈ R\) 이면서, \((4,2) ∈ R\)을 만족.

그러므로 \(R_4\)는 전이적이다.

• \((a,b) ∈ R\) 이고 \((b,c) ∈ R\) 인 관계는 모두 다음과 같다.
  • \((1,2), (2,3)\).
  • \((1,2), (2,4)\).
  • \((1,3), (3,4)\).
  • \((2,3), (3,4)\).
  • 당연한 관계
    • \[(1,1), (1,1)\]
    • \((2,2), (2,2)\).
    • \((3,3), (3,3)\).
    • \((4,4), (4,4)\).

이 네 관계가 모두 전이적인지만 확인하면 된다.

• \((1,3)\): \((1,2), (2,3) ∈ R\) 이면서, \((1,3) ∈ R\)을 만족.
• \((1,4)\): \((1,2), (2,4) ∈ R\) 이면서, \((1,4) ∈ R\)을 만족.
• \((1,4)\): \((1,3), (3,4) ∈ R\) 이면서, \((2,3) ∈ R\)을 만족.
• \((2,4)\): \((2,3), (3,4) ∈ R\) 이면서, \((2,4) ∈ R\)을 만족.

그러므로 \(R_5\)는 전이적이다.

• \(R_6\)은 잘 모르겠는데, 책에서는 \(R_6\)이 전이적 관계라고 한다.
• 왜 그렇지? 전이 관계를 위반하는 것이 하나도 없는 것도 전이 관계로 보는 걸까?
  • 황병연 교수님의 이산수학 수업을 보고 알게 되었다(링크된 동영상의 3:00 ~ 3:15) - 관계가 몇 개 없어서 추이관계가 안 되는 게 없다면 추이관계다.

전이 관계가 아니라는 \(R_1, R_2, R_3\) 도 살펴보자.

• \(R_1\)의 경우 \((3,4), (4,1)\)은 있는데 \((3,1)\)이 없다.
  • 따라서 \(R_1\)은 전이적 관계가 아니다.
• \(R_2\)의 경우 \((2,1), (1,2)\)는 있는데 \((2,2)\)가 없다.
  • 따라서 \(R_2\)는 전이적 관계가 아니다.
• \(R_3\)의 경우 \((4,1), (1,2)\)는 있는데 \((4,2)\)가 없다.
  • 따라서 \(R_3\)는 전이적 관계가 아니다.

관계 결합

• combining relations

Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs \((a, c)\), where \(a ∈ A\), \(c ∈ C\), and for which there exists an element \(b ∈ B\) such that \((a, b) ∈ R\) and \((b, c) ∈ S\). We denote the composite of R and S by \(S \circ R\).

• R을 집합 A에서 집합 B로의 관계라 하자.
• S를 집합 B에서 집합 C로의 관계라 하자.
• R과 S의 합성은 \((a, c)\)로 구성되는 관계이다.
  • \(a ∈ A, c ∈ C\)이고, \((a,b) ∈ R, (b,c) ∈ S\)인 원소 \(b ∈ B\)가 존재한다.
• R과 S의 합성을 \(R \circ S\)로 표기한다.

Let R be a relation on the set A. The powers \(R^n, n = 1,2,3,...\), are defined recursively by \(R^1 =R\) and \(R^{n+1} =R^n \circ R\).

• \(R^{n+1} = R^n \circ R\).

The relation R on a set A is transitive if and only if \(R^n ⊆ R\) for \(n = 1,2,3,...\).

• 집합 A에 대한 관계 R 이 전이적이라면, 자연수 n에 대하여 \(R^n ⊆ R\) 이다.

관계의 폐쇄(closure)

A path from a to b in the directed graph G is a sequence of edges \((x_0,x_1), (x_1,x_2), (x_2,x_3),...,(x_{n−1},x_n)\) in G, where n is a nonnegative integer, and \(x_0 = a\) and \(x_n = b\), that is, a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path. This path is denoted by \(x_0, x_1, x_2, ... , x_{n−1}, x_n\) and has length n. We view the empty set of edges as a path of length zero from a to a. A path of length \(n ≥ 1\) that begins and ends at the same vertex is called a circuit or cycle.

• 방향성 그래프 G 에서 "a 에서 b 로의 경로"는 G의 모서리들의 순서쌍의 시퀀스로 표현한다.
• 길이가 1 이상이고 한 정점에서 시작해서 시작한 정점에서 끝나는 경로를 회로(circuit) 또는 사이클(cycle)이라 부른다.

Let R be a relation on a set A. There is a path of length n, where n is a positive integer, from a to b if and only if \((a, b) ∈ R\)n.

• 길이가 n인 a 에서 b 로의 경로가 있다는 것과 \((a,b) ∈ R^n\)은 똑같은 표현이다.

Let R be a relation on a set A. The connectivity relation \(R^∗\) consists of the pairs \((a, b)\) such that there is a path of length at least one from a to b in R.

• \(R^n\)은 a 에서 b 로의 길이 n 의 경로가 있는 쌍 \((a, b)\)로 구성된다.
• 연결관계(connectivity relation) \(R^*\)
  • R의 원소들 중 길이가 적어도 1 이상인 a 에서 b 로의 경로 순서쌍\((a, b)\)로 구성된다.
  • \(R^*\)는 모든 집합 \(R^n\)의 합집합이다.

The transitive closure of a relation R equals the connectivity relation \(R^∗\).

• 관계 \(R^*\)의 전이폐쇄(transitive closure)는 연결관계 \(R^*\)과 같다.

Let \(M_R\) be the zero–one matrix of the relation R on a set with n elements. Then the zero–one matrix of the transitive closure \(R^∗\) is
\(M_{R^∗} = M_{R} ∨ M_{R}^{[2]} ∨ M_{R}^{[3]} ∨ ... ∨ M_{R}^{[n]}\)

예제를 풀어보자. 다음 관계 R의 전이폐쇄를 의미하는 0-1 행렬을 구하라.

이걸 풀기 위해 먼저 \(M_R^{[2]}\)를 구하자.

길이가 2인 a에서 b로 가는 경로가 존재하는가?

위의 표를 참고하면 다음과 같이 행렬을 그릴 수 있다.

이번엔 \(M_R^{[3]}\)을 구하자.

길이가 3인 a에서 b로 가는 경로가 존재하는가?

위의 표를 참고하면 다음과 같이 행렬을 그릴 수 있다.

잘 살펴보면 \(M_R^{[2]}\)과 \(M_R^{[3]}\)가 똑같으므로 계속 순환할 것임을 알 수 있다.

따라서

참고문헌

• Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등 저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일