[자료구조] Equivalence Relation

출처: https://privatedevelopnote.tistory.com/81 [개인노트]

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

이번 시간에는 Equivalence Relation(동치관계) 에 대하여 배웠다. 이산수학에 나오는 내용으로 그레프 이론과 연계되는 것 같다. 우선 relation에 대하여 알아본 후, Equivalence Relation에 대하여 알아보자.

 

Relation

우선 relation이란 다음과 같다.

이를 좀더 해석해보면 Relation이란 한 집합 위에서 정의되는 관계를 말한다. 처음들어서는 명확하지 않다.

 

좀더 구체적으로 우리에게 A라는 집합이 주어졌다고 가정해보자. 여기서 relation은 AxA의 subset(부분집합)을 의미한다.

|A| = n 이라면, relation으로 가능한 모든 원소의 수는 |AxA| = n^2 이 된다.

 

그럼 |A| = n 일때 모든 가능한 서로다른 Relation의 수는 몇개일까? 답부터 말하면 다음과 같다.

$\combi{2}^{\combi{n}^2}$​

이는 총 원소의 수가 n*2인데 각 원소마다 포함되거나 or 포함안되거나 둘중 하나니 당연한 결과이다.

 

이번에는 예시를 통해 위의 내용들을 다시 이해하여 보자.

만약 A = {1, 2, 3, 4} 라는 집합 A가 주어졌다고 생각해보자. 이때 총 가능한 부분집합은 다음과 같을것 이다.

(1, 1), (1, 2), (1, 3) ... (4, 3), (4, 4)

 

위의 총 가능한 부분집합 중에서 Relation R을 만족하는 부분집합이 다음과 같다고 해보자.

R = {(1, 3), (3, 4), (1, 1), (2, 2)}

 

relation R을 보면 1과 3은 R이라는 Relation이 성립한다는 것 이며, 줄어서 1R3 이라고 한다.

 

좀더 극명한 예시를 확인해 보자.

Relation < 이 자연수 N위에서 정의된다고 해보자. < = {(1, 2), (1, 3), ..., (2, 3), (2, 4) ...} 이 있다.

2 <4 의 의미는 (2, 4) ∈ <과 같다. (3, 1)같은 경우 <에 속하지 않기 때문에 (3, 1) <이라 할수 없다.

 

Equivalence Relation (동치관계)

동치 관계는 다음 3가지(Reflexive, Symmetric, Transitive)를 모두 만족하는 관계를 말한다.

 

• Reflexive : 자기 자신과 성립하는, (1, 1), (2, 2) ... 과 같다. 줄여서 aRa 이다.
• Symmetric : (a, b)가 성립하면 (b, a)또한 성립한다. 줄여서 aRb implies bRa 이다.
• Transitive : (a, b)가 성립하고 (b, c)가 성립한다면, (a, c) 또한 성립한다.

좀더 직관적인 의미로 동치관계란 어떤 성질이 같은것을 말한다. 가령 "사람의 키" 라는 성질이 있다고 해보자.

• Reflexive : 자기 자신은 자신과 키가 같다.
• Symmetric : 내가 A랑 키가 같다면 A또한 나와 키가 같다.
• Transitive : 내가 A랑 키가 같고 A가 B와 키가 같다면, 나는 B와 키가 같다.

 

그럼 위와 같이 Abstraction(추상화) 해서 사용하는 이유는 무엇일까? 이는 구체적인 사례가 아니라 특징(위에서 3가지 특징)만 뽑아서 생각하면 단순 "사람의 키" 를 넘어서, 머리색, 같은학교 출신 등등 범용적인 범위에 적용이 가능해 진다.

 

Induced Partition

▶ 위와 같은 동치관계가 주어지면 자연스럽게 따라서 나오는 partition이 있다. 이를 induces partition이라 부른다.

여기서 partition이란 부분집합으로 나누는 것을 의미하며 다음 조건이 성립한다.

 

A 는 A1, A2, ... Ak 과 같이 부분집합으로 나눌 수 있다.

1) A1 ∪ A2 ∪ ... ∪ Ak = A ( 모든 부분집합을 합하면 원래의 A이다 )

2) Ai ∩ Aj = 공집합 ( 각 부분집합의 교집합은 없다 )

 

▶ induced partion의 정의 : subsets Ai where if and only if a ∈ Ai and b ∈ Ai then aRb

이를 한글로 생각해보면, a와 b가 같은 집합에 속하면 aRb가 성립한다. 그 역 또한 마찬가지 이다.

 

다음 그림은 A라는 집합을 partition한 것 이다. A가 A1, A2, A3라는 subset들로 나뉘어 졌다.

하지만 만약 A2라는 부분집합을 다음과 같이 잡았다면 partition이 성립할까?

3과 7은 간선으로 연결되 있다. 이 말은 Relation이 성립한다는 말 이며 3R7 이라는 것 이다.

3R7이면 3과 7은 같은 집합에 있어야 partition이 성립하는데 3과 7은 같은 집합안에 있지가 않다.

따라서 A2가 partition 되려면 4와 7까지 포함해야한다.

 

▶ How to find Induced Partition?

partition을 찾기 위해서는 DFS 방식을 이용하면 된다. 위의 그레프에서 생각해 보자.

 

시작은 1번 vertex에서 시작하자. 1번에 방문 표시를 한 후, 인접한 3번을 방문한적이 있는지 확인한다. 아직 가보지 않았다.

3번으로 전진한 후 방문표시한다. 이제 3번 에 인접한 vertex들은 점검한다. 1, 7, 9가 있으며 1은 이미 방문했으니 9와 7중 한곳을 방문한다. 이런식으로 모든 vertex를 반문한다.

 

따라서 결과적으로 Equivalence Class가 총 3개가 나온다.

{1, 3, 9, 4, 7}, {2, 6}, {5, 10, 8} 이다.

 

▶ One Assumption

모든 input을 전부 다 고려하면 성능이 하락한다. 따라서 유추할수 있는 정보들은 제공하지 않는다. (답이 달라지지 않는한)

 

예를 들어보자.

• Reflexive : (1, 1)은 동치 관계에 의해서 당연히 성립해야 한다. 따라서 (1,1) 쌍은 생략한다.
• Symmetric : (1, 3), (3, 1) 같은 경우 (1, 3)이 관계를 형성하면 당연하게 (3, 1)도 관계가 형성된다. 따라서 둘중 하나는 생략한다.
• Transitive : (1, 3), (3, 7) 이 있으면 (1, 7)도 성립하지만 생략한다.

 

구현 방식

2가지 방식이 있다.

1) 인접행렬

2) 인접리스트

 

이에 관한 자세한 사항은 이미 다 알고있는 내용으로 블로그에 따로 정리하지 않겠다.