4430
правок
Полностью динамический алгоритм достижимости с единственным источником: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамический алгоритм достижимости с единственным источником (посмотреть исходный код)
Версия от 11:43, 16 февраля 2018
, 16 февраля 2018→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Полностью динамическое транзитивное замыкание с единстве…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Пусть дан граф, имеющий n вершин и m ребер. Задача поиска транзитивного замыкания (или задача достижимости) заключается в построении булевой матрицы M размера n x n, такой, что M[x, y] = 1 в том и только том случае, если существует ориентированный путь в графе из вершины x в вершину y. Полностью динамическую версию этой задачи можно определить следующим образом. | Пусть дан граф, имеющий n вершин и m ребер. Задача поиска [[Транзитивное_замыкание_орграфа|транзитивного замыкания]] (или задача [[Достижимость|достижимости]]) заключается в построении булевой матрицы M размера n x n, такой, что M[x, y] = 1 в том и только том случае, если существует ориентированный путь в графе из вершины x в вершину y. Полностью динамическую версию этой задачи можно определить следующим образом. | ||