Операции над бинарными отношениями, заданными в матричной форме.

Рассмотрим два конечных множества А={а₁,а_2,…,а_m}, B={b₁,b₂,…,b_n} и бинарное отношение

Р с А . Определим матрицу [P]=(p_ij) размера m n, бинарного отношения Р по следующему правилу: p_ij=1, если (a_i,b_j) P. : p_ij=0, если (a_i,b_j) P.

Заметим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения.

Для матричной формы задания:

1. Объединение отношений. v .

2. Пересечение отношений. .

3. Обратное отношение. Транспонирование: C_ij=a_ij.

4. Композиция отношений. С_ij= .

5. Дополнение. C_ij=a_ij.

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

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

    Yandex.RTB R-A-252273-4