Отношение эквивалентности на множестве
Отношение — это подмножество декартова произведения множества на другое множество. Отношение содержит упорядоченные пары элементов множества, на котором оно определено.
Что такое отношение эквивалентности?
Отношение R на множестве A называется отношением эквивалентности, если оно
- Рефлексивное отношение : (a, a) ∈ R ∀ a ∈ A, т. е. aRa для всех a ∈ A.
- Симметрическое отношение : ∀ a, b ∈ A, (a, b) ∈ R (b, a) ∈ R.
- Транзитивное отношение : ∀ a, b, c ∈ A, если (a, b) ∈ R и (b, c) ∈ R, то (a, c) ∈ R.
где R — подмножество (A x A), т. е. декартово произведение множества A на себя.
Пример: рассмотрим множество A = {a, b}
R = {(a, a), (a, b), (b, a)} не является эквивалентностью, так как для (b, b) кортеж отсутствует, но
R = {(a, a), (a, b), (b, a), (b, b)} — отношение эквивалентности.
Свойства отношения эквивалентности
- Пустое отношение на непустом множестве никогда не является эквивалентностью.
- Универсальное отношение над любым множеством всегда эквивалентно.
Как проверить отношение эквивалентности?
Процесс идентификации/проверки эквивалентности любого заданного отношения:
- Проверьте, является ли отношение рефлексивным.
- Проверьте, является ли отношение симметричным.
- Проверьте, является ли отношение транзитивным.
Следуйте приведенной ниже иллюстрации для лучшего понимания
Пример: рассмотрим множество R = {(1, 1), (1, 3), (2, 2), (3, 3), (3, 1), (3, 2), (3, 4), ( 4, 4), (4, 3)}
Пары (1, 1), (2, 2), (3, 3), (4, 4) существуют:
⇒ Это удовлетворяет рефлексивному условию.
Условие симметрии также выполняется.
Для пар (1, 3) и (3, 4):
⇒ Соотношение (1, 4) не существует
⇒ Это не удовлетворяет условию транзитивности.
Таким образом, отношение не является транзитивным.
Следовательно, это не эквивалентность.
Примечание: (1, 4) и (4, 1) будут вставлены в R, чтобы сделать его отношением эквивалентности.
Временная сложность: O(N * K * log N), где N — количество кортежей в отношении, а K — максимальное количество кортежей (a, b), для которых a одинаково.
Вспомогательное пространство: O(N)