[이산 수학] 관계의 폐포

관계의 폐포

• 학번을 입력하면 학생의 이름을 비롯한 학생의 기타 정보를 검색할 수 있는 시스템이 있다고 하자. 
  • 하지만, 이 시스템은 등록된 전체 학생 중 재학생만 검색할 수 있다.
  • 이 시스템에서 휴학생의 정보도 검색할 수 있으려면 휴학생의 학번과 정보도 추가해야할 것이다.
• 이처럼 자료 집합에 필요한 원소를 추가하여 특정 조건을 만족하도록 만드는 것을 관계의 폐포라고 한다.

 

관계의 폐포(Closure)

집합 `A` 에 대한 관계를 `R` 이라 하고 관계 `R` 이 가져야 하는 성질을 `P` 라고 할 때, 관계 `R` 을 포함하면서 성질 `P` 를 갖는  가장 작은 집합 `A` 에 대한 관계 `S`

• 성질 `P` 를 갖지 않는 관계 `R` 이 성질 `P`를 갖도록 순서쌍을 추가할 때는 반드시 필요한 최소한의 순서쌍만 추가한다.
• 예) 집합 `A` 에 대한 관계 `R` 이 반사 관계가 아닐 때, 관계 `R` 의 반사 폐포 `S` 를 구하려면 반사 관계이기 위해 반드시 필요한 순서쌍 $(a, a) \; (a ∈ A)$ 만 추가한다.
  • 즉, 관계 `R` 이 없으면서 반사 관계를 만드는 데도 전혀 상관이 없는 순서쌍은 절대 추가하지 않는다.
• 관계에 대한 성질에는 반사, 비반사, 대칭, 반대칭, 추이가 있으며, 이 중에서 폐포를 만들 수 있는 성질은 반사, 대칭, 추이이다.

 

반사 폐포(Reflexive Closure)

집합 `A` 에 대한 관계 `R` 을 포함하면서 반사 관계를 갖는 가장 작은 관계 `S`
$$S = R ∪ \{(a, a) \; | \; a ∈ A \}$$

• 반사 폐포는 반사 관계가 아닌 집합 `A` 에 대한 관계 `R` 에 반사 관계를 만족하는 데 필요한 순서쌍 원소 `(a, a)` 를 추가하여 만든 새로운 관계 `S` 를 말한다.

 

예 : 집합 $A = \{ 1, 2, 3 \}$ 에 대한 다음과 같은 관계 `R` 이 있을 경우

$$R = \{ (1, 1), (1, 3), (2, 1), (3, 2) \}$$

• 관계 `R` 은 $(2, 2) \not \in R, \; (3, 3) \not \in R$ 이므로 반사 관계가 아니다.
• 그러므로 `(2, 2), (3, 3)` 을 추가한다면 관계 `R` 은 반사 관계가 될 것이다.
• 관계 `R` 에 순서쌍 `(2, 2), (3, 3)` 을 추가한 새로운 관계 `S` 는 다음과 같다.

$$ \eqalign{ S &= R \cup \{(2, 2), (3, 3)\} \\ &= \{(1, 1), (1, 3), (2, 1), (3, 2)\} \cup \{(2, 2), (3, 3)\} \\ &= \{(1, 1), (1, 3), (2, 1), (2, 2), (3, 2), (3, 3) \}}$$

• 이렇게 구한 관계 `S` 는 관계 `R` 의 반사 폐포이다.

 

관계 행렬 및 방향 그래프의 표현

• 반사 폐포를 구하거나 표현하기 위해 관계 행렬이나 방향 그래프를 활용할 수 있다.
• 반사 관계가 아닌 관계 `R` 에 대한 관계 행렬의 경우 주대각 원소 중 1이 아닌 원소가 존재하고, 방향 그래프의 경우 루프가 없는 원소가 존재할 수 있다.

관계 `R`
$$\quad \quad \quad \quad \begin{matrix} 1 & 2 & 3 \end{matrix} \\ M_{R} = \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$$

 

• 관계`R` 이 반사 관계가 되도록 관계 행렬의 주대각 원소를 모두 1로 만들고, 방향 그래프의 모든 원소가 루프를 갖도록 나타나면 반사 폐포 `S` 가 된다.

관계 `R` 의 반사 폐포 `S`
$$\quad \quad \quad \quad \begin{matrix} 1 & 2 & 3 \end{matrix} \\ M_{R} = \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}$$

 

대칭 폐포(Symmetric Closure)

집합 `A` 에 대한 관계 `R` 을 포함하면서 대칭 관계를 갖는 가장 작은 관계 `S`
$$S = R ∪ \{(b, a) ∈ A \times A \; | \; (a, b) \in R \} = R \cup R^{-1}$$

• 대칭 폐포는 대칭 관계가 아닌 집합 `A` 에 대한 관계 `R` 에 대칭 관계를 만족하는 데 필요한 순서쌍 원소를 추가하여 만든 새로운 관계 `S` 를 의미한다.

 

예 : 집합 $A = \{ 1, 2, 3 \}$ 에 대한 다음과 같은 관계 `R` 이 있을 경우

$$R = \{ (1, 1), (1, 3), (2, 1), (3, 2) \}$$

• 관계 `R` 은 다음과 같은 이유로 대칭 관계가 아니다.

$(1, 1) \in R$ 일 때 `1 = 1` 이고 $(1, 1) \in R$ $(1, 3) \in R$ 일 때 `1 ≠ 3` 이고 $(3, 1) \not \in R$ $(2, 1) \in R$ 일 때 `2 ≠ 1` 이고 $(1, 2) \not \in R$ $(3, 2) \in R$ 일 때 `3 ≠ 2` 이고 $(2, 3) \not \in R$

• 그러므로 관계 `R` 이 대칭 관계이려면 `(1, 1), (2, 3), (3, 1)` 을 추가해야 한다.

$$\eqalign{S &= R \cup \{(1, 2), (2, 3), (3, 1)\} \\ &= \{(1, 1), (1, 3), (2, 1), (3, 2) \} \cup \{(1, 2), (2, 3), (3, 1) \} \\ &= \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) \} \\ &= \{(1, 1), (1, 3), (2, 1), (3, 2) \} \cup \{(1, 1), (1, 2), (2, 3), (3, 1) \} \\ &= R \cup R^{-1}}$$

• 이렇게 구한 관계 `S` 는 관계 `R` 의 대칭 폐포가 된다.
• 위에서 알 수 있듯이 대칭 폐포는 관계 `R` 의 역관계 $R^{-1}$ 와 관계 `R` 의 합집합으로 구할 수도 있다.

 

관계 행렬 및 방향 그래프의 표현

• 대칭 폐포를 구하거나 표현하기 위해 관계 행렬이나 방향 그래프를 활용할 수 있다.
• 대칭 관계가 아닌 관계 `R` 에 대한 관계 행렬의 경우 주대각 원소를 기준으로 마주보는 원소가 다르고, 방향 그래프의 경우 단방향 화살표로만 표현된다.

관계 `R`
$$\quad \quad \quad \quad \begin{matrix} 1 & 2 & 3 \end{matrix} \\ M_{R} = \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$$

 

• 관계 `R` 을 대칭 관계로 만들기 위해 관계 행렬에서 주대각 원소를 기준으로 마주보는 원소가 서로 다른 경우에 해당 원소를 모두 1로 나타내면 대칭 폐포 `S` 가 된다. 
• 또한 방향 그래프의 경우, 단방향 화살표를 모두 양방향 화살표로 바꿔 그리면 대칭 폐포 `S` 가 된다.

관계 `R` 의 반사 폐포 `S`
$$\quad \quad \quad \quad \begin{matrix} 1 & 2 & 3 \end{matrix} \\ M_{R} = \begin{matrix} 1 \\ 2 \\ 3 \end{matrix} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}$$

 

추이 폐포(Transitive Closure)

집합 `A` 에 대한 관계 `R` 을 포함하면서 추이 관계를 갖는 가장 작은 관계 `S`
$$S = R ∪ \{(a, c) ∈ A \times A \; | \; (a, b) \in R \; \land \; (b, c) \in R \} $$

• 추이 폐포는 추이 관계가 아닌 집합 `A` 에 대한 관계 `R` 에 추이 관계를 만족하는 데 필요한 순서쌍 원소를 추가하여 만든 새로운 관계 `S` 를 의미한다.

 

예 : 집합 $A = \{ 1, 2, 3 \}$ 에 대한 다음과 같은 관계 `R` 이 있을 경우

$$R = \{ (1, 1), (1, 3), (2, 1), (3, 2) \}$$

• 관계 `R` 이 추이 관계인지 판별해보자.

$(1, 1) \in R$ 이고 $(1, 1) \in R$ 일 때 $(1, 1) \in R$ $(1, 1) \in R$ 이고 $(1, 3) \in R$ 일 때 $(1, 3) \in R$ $(1, 3) \in R$ 이고 $(3, 2) \in R$ 일 때 $(1, 2) \not \in R$ $(2, 1) \in R$ 이고 $(1, 1) \in R$ 일 때 $(2, 1) \in R$ $(2, 1) \in R$ 이고 $(1, 3) \in R$ 일 때 $(2, 3) \not \in R$ $(3, 2) \in R$ 이고 $(2, 1) \in R$ 일 때 $(3, 1) \not \in R$

• 관계 `R` 이 추이 관계이려면 $(1, 2), (2, 3), (3, 1)$ 을 추가해야 한다.

$$\eqalign{S &= R \cup \{(1, 2), (2, 3), (3, 1)\} \\ &= \{(1, 1), (1, 3), (2, 1), (3, 2) \} \cup \{(1, 2), (2, 3), (3, 1) \} \\ &= \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) \} }$$

• 그런데 이렇게 1차적으로 필요한 원소를 추가했다고 해서 관계 `S` 가 반드시 추이 폐포인 것은 아니라는 점을 주의해야 한다.
• 즉, 관계 `S` 는 추이 폐포일 수도 있고 아닐 수도 있으므로, 다음과 같이 1차적으로 구한 관계 `S` 가 추이 관계인지 판별해야 한다.

$(1, 1) \in S$ 이고 $(1, 1) \in S$ 일 때 $(1, 1) \in S$ $(1, 1) \in S$ 이고 $(1, 2) \in S$ 일 때 $(1, 2) \in S$ $(1, 1) \in S$ 이고 $(1, 3) \in S$ 일 때 $(1, 3) \in S$ $(1, 2) \in S$ 이고 $(2, 1) \in S$ 일 때 $(1, 1) \in S$ $(1, 2) \in S$ 이고 $(2, 3) \in S$ 일 때 $(1, 3) \in S$ $(1, 3) \in S$ 이고 $(3, 1) \in S$ 일 때 $(1, 1) \in S$ $(1, 3) \in S$ 이고 $(3, 2) \in S$ 일 때 $(1, 2) \in S$ $(2, 1) \in S$ 이고 $(1, 1) \in S$ 일 때 $(2, 1) \in S$ $(2, 1) \in S$ 이고 $(1, 2) \in S$ 일 때 $(2, 2) \not \in S$ $(2, 1) \in S$ 이고 $(1, 3) \in S$ 일 때 $(2, 3) \in S$ $(2, 3) \in S$ 이고 $(3, 1) \in S$ 일 때 $(2, 1) \in S$ $(2, 3) \in S$ 이고 $(3, 2) \in S$ 일 때 $(2, 2) \not \in S$ $(3, 1) \in S$ 이고 $(1, 1) \in S$ 일 때 $(3, 1) \in S$ $(3, 1) \in S$ 이고 $(1, 2) \in S$ 일 때 $(3, 2) \in S$ $(3, 1) \in S$ 이고 $(1, 3) \in S$ 일 때 $(3, 3) \not \in S$ $(3, 2) \in S$ 이고 $(2, 1) \in S$ 일 때 $(3, 1) \in S$ $(3, 2) \in S$ 이고 $(2, 3) \in S$ 일 때 $(3, 3) \not \in S$

• 앞의 과정을 통해 1차적으로 구한 관계 `S` 는 추이 관계가 아님을 알 수 있다.
• 그러므로 관계 `S` 가 추이 관계가 되어 관계 `R` 의 추이 폐포이려면 순서쌍 `(2, 2), (3, 3)` 을 추가해야 한다.

$$\eqalign{S' &= R \cup \{(2, 2), (3, 3)\} \\ &= \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) \} }$$

 

연결 관계(Connectivity Relation : $R^{*}$)

집합 `A` 에 대한 관계 `R` 에 대하여,
$$R^{*} = \bigcup_{n=1}^{∞} R^{n} = R^{1} \cup R^{2} \cup R^{3} \cup \cdots = R^{\infty}$$
일반적으로 집합 `A` 의 기수가 `n` 일 때, 관계 `R` 의 연결 관계 $R^{*}$ 는 다음과 같이 구한다.
$$R^{*} = \bigcup_{k=1}^{n} R^{k} = R^{1} \cup R^{2} \cup \cdots \cup R^{n-1} \cup R^{n}$$

• 어떤 관계 `R` 의 추이 폐포 `S` 를 구할 때 필요한 순서쌍의 포함 여부를 확인하고 추가하는 작업을 여러 번 반복해야 하는 경우도 있어 추이 폐포를 구하는 과정이 쉽지 않을 수 있다.
• 추이 폐포를 구하기 위한 조금 더 간단한 방법으로 연결 관계를 이용할 수 있다.

 

연결 관계와 추이 폐포의 관계

관계 `R` 의 연결 관계 $R^{*}$ 는 관계 `R` 의 추이 폐포이다.

• 연결 관계 $R^{*}$ 가 관계 `R` 의 추이 폐포임을 증명하려면 다음 두 명제를 모두 증명해야 한다.

(i) 관계 `R` 의 연결 관계 $R^{*}$ 는 추이 관계이다. (ii) 관계 `R` 의 추이 폐포 `S` 가 있다면 $R^{*} ⊆ S$ 이다.

 

증명

(i) 관계 `R` 의 연결 관계 $R^{*}$ 는 추이 관계이다.

$(a, b) \in R^{*}, \; (b, c) \in R^{*}$ 라고 가정하면 자연수 `p, q` 에 대하여 $(a, b) \in R^{p}, \; (b, c) \in R^{q}$ 이다.

$(a, b) \in R^{p}$ 의 경우, 어떤 $x_{1}, x_{2}, \cdots, x_{p - 1}$ 에 대하여 다음을 만족한다.

$$(a, x_{1}) \in R, \; (x_{1}, x_{2}) \in R, \cdots, (x_{p-2}, x_{p-1}) \in R, \; (x_{p-1}, b) \in R$$

$(b, c) \in R^{q}$ 의 경우, 어떤 $y_{1}, y_{2}, \cdots, y_{q - 1}$ 에 대하여 다음을 만족한다.

$$(b, y_{1}) \in R, \; (y_{1}, y_{2}) \in R, \cdots, (y_{q-2}, y_{q-1}) \in R, \; (y_{q-1}, c) \in R$$

따라서 $(a, c) \in R^{p + q}$ 이고, $R^{*} = R \cup R^{p} \cup R^{q} \cup R^{p+q}$ 이므로 $(a, b) \in R^{*}, \; (b, c) \in R^{*}, \; (a, c) \in R^{*}$ 이다.

∴ 관계 `R` 의 연결 관계 $R^{*}$ 는 추이 관계이다.

 

 

(ii) 관계 `R` 의 추이 폐포 `S` 가 있다면 $R^{*} ⊆ S$ 이다.

관계 `R` 의 추이 폐포 `S` 가 있다면 $R^{*} ⊆ S$ 이다.

관계 `S` 는 관계 `R` 의 추이 폐포이므로 관계 `R` 에 관한 집합 `A` 의 기수가 `n` 일 때 $S^{n}$ 도 추이 관계이다.

따라서 $S^{n} ⊆ S$ 이므로 다음이 성립한다.

$$S^{*} = \bigcup_{n=1}^{\infty} S^{n} \quad \quad ∴ S^{*} ⊆ S$$

또한 관계 `S` 가 관계 `R` 의 추이 폐포이므로 관계 `S` 는 관계 `R` 을 포함한다.

따라서 $R^{*} ⊆ S^{*}$ 이다.

∴ $R^{*} ⊆ S^{*} ⊆ S$

따라서 연결 관계 $R^{*}$ 는 관계 `R` 의 추이 폐포이다.

 

예 : 집합 $A = \{ 1, 2, 3 \}$ 에 대한 다음과 같은 관계 `R` 이 있을 경우

$$R = \{ (1, 1), (1, 3), (2, 1), (3, 2) \}$$

• 관계 `R` 의 추이 폐포를 연결 관계를 이용하여 구해보자.
• 집합의 기수가 3($|A| = 3$)이므로 거듭 제곱을 세 번하여 연결 관계를 구한다.

$$M_{R} = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \\ R^{2} = R \circ R = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \odot \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{bmatrix} \\ R^{3} = R^{2} \circ R = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \odot \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix} \\ R^{*} = \bigcup_{n=1}^{3} R^{n} = R^{1} \cup R^{2} \cup R^{3} = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) \}$$ ∴ 관계 `R` 의 추이 폐포는 $S = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) \}$