Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством).

Рефлексивное, симметричное и транзитивное отношение, заданное на множестве А, называется отношением эквивалентности на множестве А, т.е:

1.

2. х,у

3. ,y,z , х

Классом эквивалентности [х], порожденным элементом х А, называется подмножество множества А, состоящее из тех и только тех элементов у, которые состоят в отношении эквивалентности с х, т.е. [х]={y: x=y, y }. Множество классов эквивалентности А\R называется фактор-множеством множества А по эквивалентности R: A\R={[x]:x A}.

Свойство классов эквивалентности:

1. . В самом деле х => х [x]

2. Класс эквивалентности порождается любым своим элементом, т.е. х у => [x]=[y]

3. Различные классы эквивалентности друг с другом не пересекаются, т.е. х у, то [х] [у]=

Совокупность множеств А₁,А₂,…,А_n называется разбиением множества А, если выполняются два условия: А₁vA₂v…vA_n=A и = , i j, j=1..n.

Между разбиением множества и эквивалентностью, заданной на этом множестве существует связь, которая устанавливается следующими теоремами:

Теорема. Всякое отношение эквивалентности на множестве А определяет разбиение множества А, причем среди элементов разбиения нет пустых. Обратно, всякое разбиение на множестве А, не содержащее пустых элементов, определяет отношение эквивалентности на этом множестве.

Доказательство. Разбиение с непустыми элементами может быть построение по отношению к эквивалентности следующим образом:

1. Выбрать произвольный элемент а A

2. Построить класс эквивалентности [a]

3. A:=A\[a]; A:=A {[a]}

4. Если А непусто, перейти к шагу 1

5. Добавим класс Х в разбиение В:=В Х

6. Если U= , то разбиение построено, в противном случае переходим к шагу №2

12. Yandex.RTB R-A-252273-3
    Содержание

    • Множества. Элементы множеств. Интуитивный принцип объемности. Способы задания множества. Мощность множества.
    • Подмножества и их свойства.
    • Операции над множествами: объединение, пересечение, разность, дополнение. Диаграммы Эйлера-Венна.
    • Свойства операций над множествами (с доказательством).
    • Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.
    • Операции над бинарными отношениями: композиция отношений, степень отношения, обратное отношение, дополнение отношения, объединение, пересечение, разность отношений.
    • Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность.
    • Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.
    • Операции над бинарными отношениями, заданными в матричной форме.
    • Алгоритм определения матрицы транзитивного замыкания бинарного отношения.
    • Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством).
    • Отношение порядка. Строгий и нестрогий порядок. Частичный и полный порядок. Упорядоченные множества.
    • Соответствия. Образ и прообраз. Свойства соответствий: всюду определенные, инъективные, сюръективные, функциональные, взаимнооднозначные соответствия.
    • Функции и отображения. Виды отображений. Обратные соответствия и функции. Способы задания функций.
    • Алгебраические операции. Примеры операций. Арность операции. Способы задания.
    • Свойства бинарных алгебраических операций: коммутативность, ассоциативность, дистрибутивность, поглощение, идемпотентность. Нейтральный и симметричный элементы.
    • Комбинаторные правила суммы и произведения. Выборки (упорядоченные, неупорядоченные, с повторениями и без).
    • Операции над графами.
    • Способы представления графов и орграфов на эвм: матрица смежности, матрица инцидентности, список смежности, массив ребер (дуг).
    • Маршруты в графах. Виды маршрутов: замкнутые и незамкнутые. Цепь. Простая цепь. Цикл. Простой цикл. Длина маршрута. Расстояние между вершинами. Диаметр графа.
    • Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности.
    • Определение матрицы достижимости орграфа как матрицы рефлексивного и транзитивного замыкания отношения смежности.
    • Алгоритм выделения компонент связности (сильной связности)
    • Нагруженные орграфы Длина пути в нагруженном орграфе. Минимальные пути в нагруженных орграфах.
    • Нагруженные орграфы. Алгоритм Форда-Беллмана выделения минимального пути в нагруженном орграфе.

    Yandex.RTB R-A-252273-4