Компоненты сильной связности и граф конденсации
Разделить ориентированный граф на максимальные группы взаимной достижимости и построить ациклический граф связей между ними.
Ваш пример
Разбор примера
Компонент сильной связности: 2
| Компонента | Вершины |
|---|---|
| 1 | 1, 2 |
| 2 | 3, 4 |
- Достижимость включает путь длины ноль.
- Взаимно достижимые вершины объединены в максимальные группы.
- Дуги внутри группы отброшены; оставшиеся дуги конденсации не создают цикл.
- Прямые дуги конденсации
- 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. По ссылкам можно сверить определения и условия модели.