Алгоритм выделения компонент связности (сильной связности)

1. Полагаем р:=1 и S­₁:=S(p).

2. Включаем во множество вершин V_p очередной компонент сильной связности вершины соответствующей единицам первой строки матрицы S(p). В качестве матрицы смежности очередной компонентой сильной связности G(p) берем подматрицу A(G), составленную из элементов, находящихся на пересечении строк и столбцов соответствующей вершинам, принадлежащим из V_p.

3. Вычеркиваем из S(p) строки и столбцы соответствующем вершинам принадлежащим V_p. Если в результате вычеркивания ничего не осталось, то р – число компонент сильной связности, а A(G₁),…, A(G_p) есть матрицы смежности этих компонент, в противном случае обозначаем оставшуюся после вычеркивания матрицу через S(p), p:=p+1 и переходим к шагу №2.

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

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

    Yandex.RTB R-A-252273-4