Соответствия. Образ и прообраз. Свойства соответствий: всюду определенные, инъективные, сюръективные, функциональные, взаимнооднозначные соответствия.
Соответствием между множествами А и В называется подмножество . G – соответствие между А и В. Область определения соответствия: DG={x: (x,y) }. Область значений соответствия: ЕG={y: (x,y) G}.
Образом элемента а во множество В называется множество таких b B, (a,b) G. Образом множества С с А называется множество образов всех элементов С.
Прообразом элемента b B во множестве А, называется множество таких элементов а, что (а,b) G. Прообразом множества D c B называется множество прообразов всех элементов, принадлежащих D.
образ элемента а
а
В
А
b
образы
прообразы
Если G c A B, то говорят, что множеству А соответствует множество В. G:A B. Пара множеств А и В определяет тип соответствия.
Свойства соответствий:
G называется всюду определенным в том и только в том случае, когда DG=A
G называется сюръективным в том и только в том случае, когда ЕG=В
G называется функциональным (однозначным) в том и только в том случае, когда
y1=y2
: (x,y1) G
(x,y2) G
Каждому прообразу соответствует единственный образ
4. G называется инъективным в том и только том случае, когда
х1=х2
1,х2 А, у В: (x1,y) G
(x2,y) G
G называется биективным (взаимнооднозначным), если оно всюду определено, сюръективно,
функционально и инъективно.
Yandex.RTB R-A-252273-3- Множества. Элементы множеств. Интуитивный принцип объемности. Способы задания множества. Мощность множества.
- Подмножества и их свойства.
- Операции над множествами: объединение, пересечение, разность, дополнение. Диаграммы Эйлера-Венна.
- Свойства операций над множествами (с доказательством).
- Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.
- Операции над бинарными отношениями: композиция отношений, степень отношения, обратное отношение, дополнение отношения, объединение, пересечение, разность отношений.
- Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность.
- Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.
- Операции над бинарными отношениями, заданными в матричной форме.
- Алгоритм определения матрицы транзитивного замыкания бинарного отношения.
- Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством).
- Отношение порядка. Строгий и нестрогий порядок. Частичный и полный порядок. Упорядоченные множества.
- Соответствия. Образ и прообраз. Свойства соответствий: всюду определенные, инъективные, сюръективные, функциональные, взаимнооднозначные соответствия.
- Функции и отображения. Виды отображений. Обратные соответствия и функции. Способы задания функций.
- Алгебраические операции. Примеры операций. Арность операции. Способы задания.
- Свойства бинарных алгебраических операций: коммутативность, ассоциативность, дистрибутивность, поглощение, идемпотентность. Нейтральный и симметричный элементы.
- Комбинаторные правила суммы и произведения. Выборки (упорядоченные, неупорядоченные, с повторениями и без).
- Операции над графами.
- Способы представления графов и орграфов на эвм: матрица смежности, матрица инцидентности, список смежности, массив ребер (дуг).
- Маршруты в графах. Виды маршрутов: замкнутые и незамкнутые. Цепь. Простая цепь. Цикл. Простой цикл. Длина маршрута. Расстояние между вершинами. Диаметр графа.
- Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности.
- Определение матрицы достижимости орграфа как матрицы рефлексивного и транзитивного замыкания отношения смежности.
- Алгоритм выделения компонент связности (сильной связности)
- Нагруженные орграфы Длина пути в нагруженном орграфе. Минимальные пути в нагруженных орграфах.
- Нагруженные орграфы. Алгоритм Форда-Беллмана выделения минимального пути в нагруженном орграфе.