Компоненты сильной связности и граф конденсации

Разделить ориентированный граф на максимальные группы взаимной достижимости и построить ациклический граф связей между ними.

Ваш пример

Дроби вводите как 1/3, десятичные числа — 0.5 или 0,5. Таблицы: числа через пробел, строки с новой строки. Формулы не выполняются.

Разбор примера

Компонент сильной связности: 2

Проверяемый расчёт
КомпонентаВершины
11, 2
23, 4
  1. Достижимость включает путь длины ноль.
  2. Взаимно достижимые вершины объединены в максимальные группы.
  3. Дуги внутри группы отброшены; оставшиеся дуги конденсации не создают цикл.
Прямые дуги конденсации
C1 → C2

Метод и условия расчёта

В ограниченном графе вычисляем транзитивную достижимость.

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

Теория к методу

Матрица смежности A хранит прямые дуги, матрица достижимости R — существование направленных путей. Начните с R=A∨I. На этапе k заменяйте клетку Rᵢⱼ значением Rᵢⱼ∨(Rᵢₖ∧Rₖⱼ). После всех этапов вершины одной компоненты определяются взаимными единицами Rᵢⱼ=Rⱼᵢ=1. Прямые дуги конденсации затем восстанавливают по исходной A, а не по всем единицам R.

В квадратной матрице A строка задаёт начало, столбец — конец дуги; единица Aᵢⱼ означает прямой переход i→j. Ноль сообщает отсутствие такой дуги, а не обязательно отсутствие любого пути. Для ручной таблицы достижимости добавьте единицы на диагональ: путь длины ноль существует из каждой вершины в себя. Исходную A сохраните отдельно, потому что она понадобится после замыкания.

Пример: Продолжите этот расчёт после k=2. Какие клетки добавит k=3, каковы итоговые строки R и группы взаимной достижимости?

Через вершину 3 добавляются 1→4 и 2→4. Новых обратных путей нет; k=4 ничего не меняет. Итоговые строки: «1 1 1 1»; «0 1 1 1»; «0 1 1 1»; «0 0 0 1». Вершины 2 и 3 имеют взаимные единицы; 1 не достижима обратно из них, а 4 не возвращается к ним. Получаются группы {1}, {2,3}, {4}.

Вопросы по теме

Одного пути между вершинами достаточно?

Нет. Нужны пути в обе стороны с учётом направлений дуг.

Компонента из одной вершины допустима?

Да. Путь длины ноль связывает вершину с собой; отдельной петли для этого не требуется.

Почему нельзя сразу вводить в калькулятор матрицу достижимости R?

Группы взаимной достижимости сохранятся, но инструмент восстанавливает прямые дуги конденсации по введённым единицам. Если вместо A подать R, путь может стать дополнительной прямой дугой результата.

Единица на диагонали означает, что в исходном графе была петля?

Нет. При построении R диагональ учитывает путь длины ноль. Исходная матрица A при этом не меняется, и реальная петля в ней по-прежнему определяется собственным значением клетки.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.