Операции над графами.

1. Одноместные (унарные):

а) удаление ребра, при этом множество вершин сохраняется

б) добавление ребра

в) добавление вершины, которую можно связать с некоторыми ребрами

г) удаление вершины совместно с инцидентными ей ребрами

д) стягивание ребра – удаление пары смежных вершин и добавление новой вершины, смежной с теми вершинами, которые были смежны хотя бы с одной из удаленных вершин.

е) дополнение графа – дополнением графа Г является граф Г ', который дополняет исходный граф до полного.

2. Бинарные

а) объединением G₁(V_1,X₁) и G₂(V_2,X₂) является G₁∪ G₂(V₁∪ V₂; X₁∪ X₂)

б) пересечение G₁(V_1,X₁) и G₂(V_2,X₂) является G₁∩ G₂(V₁∩ V₂; X₁∩ X₂)

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

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

    Yandex.RTB R-A-252273-4