Definition of Equivalence Relation
First, Definition for Relation
집합 A 의 관계 : 집합R
1R3 : (1,3) 이 R에 포함된다는 것으로 표현한다.
그렇다면 동치 관계는 어떤 것일까?
아래 그림에서 볼 수 있듯이 R,S,T 세 조건이 모두 성립하면 동치 관계이다.
위 설명을 처음에는 이해하지 못했지만,
작년 이산수학에 나왔던 집합에서의 "동치 관계"를 의미하는 것을 알 수 있었다.
Relflexive :반사
Symmetric :대칭
Transitive :전이
Induced Partition and How to find it
이렇게 동치관계를 이용하면, 각 원소를 연결하여 partition이 생길 수 밖에 없게된다.
Induced Partition을 어떻게 찾을까?
원소의 개수 : 10
관계의 개수 : 7
이 두 값을 주면 된다. 그런데 여기서 문제가 있다.
관계의 개수가 7보다 더 많기 때문이다. 관계 R의 집합을 표현했을 때, (1,7) 은 R에 포함된다.
하지만 필요가 없다. 유추가 가능하기 때문이다.
여기서 하나의 가정이 들어간다.
One Assumption : Input is given in Minimal Form (No deducible pairs are given)
예시: (1,1),(2,2),(1,7),(7,1) are not given
'2023 1학기 > 자료구조' 카테고리의 다른 글
| [자료구조/c언어] Using Dfs to print Equivalence Relation (0) | 2023.04.04 |
|---|---|
| [자료구조/c언어] naive 알고리즘, DFA 알고리즘 (0) | 2023.04.04 |
| [자료구조/c언어] 시간복잡도 (0) | 2023.04.02 |
| [자료구조/c언어] 명제와 수학적 귀납법을 재귀함수를 통해서 이해 (0) | 2023.04.02 |
| [자료구조/c언어]1. 메모리와 CPU (0) | 2023.04.02 |
