관계

관계

• Relation
• 객체들 간의 연관성을 표현하는 구조
• 수학이나 공학 분야 뿐만 아니라 다른 여러 분야에서도 기본적이고 중요한 개념
• 수학·컴퓨터 등 여러 공학 분야에서의 객체들도 이와 같이 여러 가지 관계를 가짐

이항관계

• Binary Relation, ₓRᵧ
• 집합 A, B가 있을 때 집합 A에서 집합 B로 가는 관계, A × B의 부분집합

정의역 & 공역 & 치역

• 정의역(domain): 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 첫 번째 원소가 포함되어 있는 집합 A
• 공역(codomain): 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 두 번째 원소가 포함되어 있는 집합 B
• 치역(range): 집합 A에서 집합 B로 가는 관계 R에 속한 순서쌍의 두 번째 원소들을 모아놓은 집합, 공역의 부분집합

n항관계

• n-ary Relation
• 관계가 이루어지는 집합이 셋 이상일 때
• 집합 A₁, A₂, ... , Aₙ이 있을 때 A₁ × A₂ × ... × Aₙ의 부분집합

역관계

• Inverse Relation, R⁻¹
• 집합 A에서 집합 B로 가는 관계 R이 있을 때, R에 대한 역관계
• R⁻¹ = {(b, a) | (a, b) ∈ R}
• 관계 R에서의 정의역이 역관계 R⁻¹에서는 공변역이 되고, 관계 R에서의 공변역이 역관계 R⁻¹에서의 정의역
• 집합 B에서 집합 A로의 관계를 나타내며, 순서쌍 내의 순서를 다시 바꾸면 그 순서쌍은 관계 R에 속하게 됨
• 관계가 존재해야 역관계가 존재

---

관계의 표현

• 화살표 선도(Arrow Diagram): 집합 A에서 집합 B로 가는 관계 R이 있을 때, 두 집합 원소 사이의 관계를 화살표로 나타내는 방법
• 좌표 도표(Coordinate Diagram): 집합 A에서 집합 B로 가는 관계 R이 있을 때, 집합 A의 원소(정의역)들을 x축에, 집합 B의 원소(공역)들을 y축에 표시하여 관계 R을 좌표에 나타내는 방법
• 관계 행렬(Relation Matrix): 집합 A에서 집합 B로 가는 관계 R에 대한 n × m 행렬
  • 정의역을 행으로 나열하고 공역을 열로 나열하여 관계의 순서쌍에 해당하면 1, 아니면 0으로 표시
• 방향그래프(Directed Graph): 하나의 집합 A에서 집합 A로 가는 관계 R을 꼭짓점과 화살표를 이용해 나타낸 그래프
  • 루프: 원소에서 시작하여 그 원소로 끝나는 화살표가 그려짐

---

관계의 성질

반사관계

• Reflexive Relation
• 집합 A에 대한 관계 R이 있을 때, 모든 a ∈ A에 대해 (a, a) ∈ R인 관계
• 반사관계에 대한 관계행렬은 대각원소들이 모두 1로 표기되어 있음
• 방향그래프로 나타내면 모든 원소에 대해 루프가 존재

비반사관계

• Irreflexive Relation
• 집합 A에 대한 관계 R이 있을 때, 모든 a ∈ A에 대해 (a, a) ∉ R인 관계
• 비반사관계에 대한 관계행렬은 대각원소들이 모두 0으로 표기되어 있음
• 방향그래프로 나타내면 모든 원소에 대해 루프가 존재하지 않음

대칭관계

• Symmetric Relation
• 집합 A에 대한 관계 R이 있을 때, 어떤 (a, b) ∈ A에 대해 (a, b) ∈ R이면 (b, a) ∈ R인 관계
• 대칭관계에 대한 관계행렬은 대각원소들을 기준으로 마주보는 원소들이 많음
• 방향그래프로 나타냈을 때는 두 개의 원소 사이에 반드시 양방향 화살표가 존재

반대칭관계

• Antisymmetric Relation
• 집합 A에 대한 관계 R이 있을 때, 어떤 (a, b) ∈ A에 대해 (a, b) ∈ R이고 (b, a) ∈ R이면 a = b인 관계

---

합성관계

• Composition Relation, S ৹ R
• 두 개 이상의 관계를 합성하여 새로운 관계를 생성
• 이미 존재하고 있는 관계 R₁과 R₂로부터 새로운 관계 R₁·R₂를 만들어냄
• 합성관계에서 관계 R₁과 R₂는 연관성이 있어야 함
  • R₁의 치역이 R₂의 정의역이 될 경우에만 R₁·R₂를 만들 수 있음

합성관계의 거듭제곱 Rⁿ

• 집합 A에서 B로 가는 관계 R은 m × n 크기의 관계행렬 Mᵣ로 작성
• 집합 B에서 C로 가는 관계 S는 n × s 크기의 관계행렬 Mₛ로 작성
• 관계 S ৹ R은 이 두 관계행렬 Mᵣ과 Mₛ의 부울곱으로 구함

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

• 기수(Cardinality)가 n인 집합 A에 대한 관계 R이 추이관계인 필요충분조건은 모든 양의 정수 n에 대하여 Rⁿ ⊆ R 이다.

기본가정	n = 1일 때, R¹ ⊆ R로 성립
귀납가정	n = k일 때, Rᵏ ⊆ R로 가정
귀납증명	n = k+1일때, Rᵏ⁺¹ ⊆ R임을 증명 (x,y) ∈ Rᵏ⁺¹이면, Rᵏ⁺¹ = Rᵏ ৹ R이기 때문에 (x,y) ∈ Rᵏ ৹ R 그러므로 (x,y) ∈ R이고 (z,y) ∈ Rᵏ인 z가 존재 귀납가정에서 Rᵏ ⊆ R이므로 (z,y) 결국 (z,y) ∈ R이고,  (x,y) ∈ R이므로 (x,y) ∈ R 따라서 Rᵏ⁺¹ ⊆ R이 성립
∴ 모든 양의 정수 n에 대하여 Rⁿ ⊆ R

---

폐포

• Closure
• 원래의 관계에 순서쌍 원소를 추가하여 특정 성질에 맞게 만든 것
• 집합 A에 대한 관계를 R이라고 하고, 관계가 가질 수 있는 성질을 P라고 할 때, 집합 A에 대한 관계 S가 관계 R을 포함하면서 성질 P를 갖는다면 S를 R에 대한 P의 폐포라고 함

반사폐포

• Reflexive Closure
• 집합 A에 대해 관계 R을 포함하면서 반사관계를 갖는 관계 S
• S = R ∪ {(a, a) | a ∈ A}

추이폐포

• Transitive Closure
• 집합 A에 대해 관계 R을 포함하면서 추이관계를 갖는 관계 S
• S = R ∪ {(a, c) ∈ A × A | (a, b) ∈ R ∧ (b, c) ∈ R}

---

동치관계

• 반사관계, 대칭관계, 추이관계가 모두 성립하는 관계

부분순서관계

• 집합 A에 대한 관계 R이 반사관계, 반대칭관계, 추이관계가 모두 성립하는 관계