[이산수학] 관계

관계에 대해 정의하고 성질에 고찰하며 여러 분야에 사용 방법을 익힐 수 있다

관계와 이항 관계

관계

객체들 간의 연관성을 표현하는 구조

이항 관계 (binary relation)

두 집합 A, B에 대하여, A로부터 B로의 이항 관계 R은 두 집합의 곱집합의 부분 집합

(a,b) ∈ R 과 aRb는 동치

2개의 집합 사이의 관계를 이항 관계

2개 그 이상의 원소에 대한 관계는 n-ary 관계라고 함

#1 관계 R의 원소인 순서쌍

첫 번째 원소의 집합을 정의역, Dom(R)로 표시

두 번째 원소의 집합을 치역, Ran(R)로 표시

Dom(R) = {a | (a,b) ∈ R} ⊆ A

Ran(R) = {b | (a,b) ∈ R} ⊆ B

#2 xRy ≠ yRx

정의역은 순서쌍의 첫 번째 원소로 이루어진 집합이고 치역은 두 번째 원소로 이루어진 집합이므로 해당 교환법칙은 성립하지 않는다

#3 카타시안 곱 ( 곱집합 )

A와 B가 집합일 때, 순서쌍의 첫 번째 요소는 집합 A의 원소이고 두 번째 요소는 집합 B의 원소로 구성된 모든 순서쌍의 집합을 A와 B의 카타시안 곱 또는 곱집합이라 함

A×B로 표현

#4 역관계

집합 A에서 집합 B로의 관계 R에 대한 역관계는 ****집합 B에서 집합 A로의 관계를 나타내며, 순서쌍 내의 순서를 바꾸면 그 순서쌍은 관계 R에 속함

관계의 표현

집합 사이의 관계를 표현하는 방법

#1 서술식 방법

집합 A = {1,2,3} 에서 원소 a,b가 a≥b인 관계 R 와 같이 표현

#2 나열식 방법

서술식에 따라 관계를 순서쌍들의 집합으로 표현

화살식 도표, 좌표 도표, 방향 그래프, 관계 행렬 등이 있음

(1) 화살식 도표

• a가 집합 A의 원소이고 b가 집합 B의 원소
• (a, b) ∈ R일 경우 집합 A에 있는 원소 a에서 집합 B에 있는 원소 b로 화살표를 그려 관계를 표현

(2) 좌표 도표

• 집합 A의 원소를 x축 위의 점으로 표시 → 집합 B의 원소를 y축 위의 점
• a∈A와 b∈B가 관계가 있으면 a를 가르키는 x축 좌표와 b를 가르키는 y축 좌표가 만나는 곳에 점으로 표시

(3) 방향 그래프

• 관계 R이 두 집합 A와 B 사이의 관계가 아니고 하나의 집합 A에 대한 관계라고 하면
• 집합 A의 각 원소를 그래프의 정범으로 표시
• (a,b) ∈ R일 경우 a에서 b로의 롸살표가 있는 연결선으로 표현

(4) 관계 행렬

• 불 행렬 : 행렬 안에 있는 모든 원소들이 0 또는 1로 표시되는 행렬
• 관계 행렬의 행에는 집합 A의 원소, 열에는 집합 B의 원소를 표시
• 행렬의 각 요소의 값은 a∈A와 b∈B의 관계가 있으면 1, 없으면 0으로 표현

합성 관계

주어진 두 관계로부터 새로운 관계를 이끌어내는 것

세 집합 A, B, C에서 R1을 집합 A에서 집합 B로의 관꼐라고 하고 R2를 집합 B에서 집합 C로의 관계라 하면 집합 A에서 집합 C로 합성 관계 R1R2는 다음과 같이 정의

R1R2={(a,c) | a∈A, c∈C, (a,b)∈R1, (b,c)∈R2}

합성 관계에서 관계 R1과 R2는 연관성이 있어야함 → R1의 치역이 R2의 정의역이 될 경우

관계의 성질

#1 반사 관계 (Reflexive Relation)

관계 R에 대한 방향 그래프를 그렸을 때 그래프의 모든 정점에서 자기 자신을 가리키는 화살표가 있어야 성립

• 비반사 관계 : 자기 자신을 가리키는 원소쌍이 존재하지 않아야함

#2 대칭 관계 (Symmetric Relation)

R이 대칭 관계일 때 R의 원소 중 (a,b) 가 존재하면 (b,a) 또한 반드시 존재한다

#3 반대칭 관계 (Anti-symmetric Relation)

대칭 관계와 반대의 개념으로 R이 반대칭 관게일 때 x와 y가 같지 않고 (x,y)가 존재하면 (y,x)는 존재하지 않는다

#4 추이 관계 (Transitive Relation)

집합 A에 있는 원소 x,y,z에 대하여 관계 R이 (x,y)이고 (y,z)이면 (x,z)인 관계를 만족할 때 해당 관계를 추이 관계라고 한다

동치 관계와 분할

관계 R에서 반사 관계, 대칭 관계, 추이 관계가 모두 성립할 때 이를 동치 관계라고 한다

동치 관계 R의 중요한 성질 : R이 서로 공통 부분이 없으면서 공집합이 아닌 클래스들로 S를 분할한다

#1 동치클래스 (동치류)

집합 A에 대한 동치 관계를 R이라고 할 때, A의 각 원소 x에 대하여 [x]를 R에 대한 x의 동치류, 동치 클래스라 하고

[x] = { y | (x,y) ∈ R } 로 정의한다

이때 집합 A의 동치류의 모임을 A의 몫집합이라고 한다

#2 분할의 조건

모든 분할 집합 {Ai}는 공집합이 아니다

S안에 있는 모든 원소는 임의의 Ai에 속한다

{Ai}의 집합은 서로 교차하지 않는다

부분 순서 관계

집합 A에 대한 관계 R이 반사 관계, 반대칭 관계, 추이 관계이면 관계 R을 부분 순서 관계라고 한다

해당 순서쌍 (A,R)을 부분 순서 집합이라고 한다

 

이러한 관계 표현과 관계를 통하여 그래프와 트리에 응용이 가능하며 여러 문제 풀이에 도움이 된다