1294
правки
Компромиссы при решении динамических графовых задач: различия между версиями
Материал из WEGA
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 04:25, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий 1 участника) | |||
| Строка 8: | Строка 8: | ||
'''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке: | '''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке: | ||
insert(u, v): вставка | insert(u, v): вставка ребра (u, v) в граф; | ||
delete(u, v): удаление | delete(u, v): удаление ребра (u, v) из графа; | ||
query(..): ответ на запрос о выполнении свойства P графа. | query(..): ответ на запрос о выполнении свойства P графа. | ||
| Строка 26: | Строка 26: | ||
'''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | '''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | ||
insert(u, v): вставка | insert(u, v): вставка ребра (u, v) в граф; | ||
delete(u, v): удаление | delete(u, v): удаление ребра (u, v) из графа; | ||
query(x, y): возвращает ''true'', если существует ориентированный путь между вершинами x и y, и ''false'' в противном случае. | query(x, y): возвращает ''true'', если существует ориентированный путь между вершинами x и y, и ''false'' в противном случае. | ||
| Строка 35: | Строка 35: | ||
'''Определение 3 (Полностью динамическая задача нахождения кратчайших путей между всеми парами)'''. Задача заключается в поддержке взвешенного ориентированного графа и выполнении последовательности следующих операций в различном порядке: | '''Определение 3 (Полностью динамическая задача нахождения кратчайших путей между всеми парами)'''. Задача заключается в поддержке взвешенного ориентированного графа и выполнении последовательности следующих операций в различном порядке: | ||
insert(u, v, w): вставка | insert(u, v, w): вставка ребра (u, v) с весом w в граф; | ||
delete(u, v): удаление | delete(u, v): удаление ребра (u, v) из графа; | ||
query(x, y): возвращает расстояние между x и y в графе либо значение <math>+ \infty</math> в случае, если не существует ориентированного пути из x в y. | query(x, y): возвращает расстояние между x и y в графе либо значение <math>+ \infty</math> в случае, если не существует ориентированного пути из x в y. | ||
| Строка 152: | Строка 152: | ||
| Граф общего вида | | Граф общего вида | ||
| Детерминированный | | Детерминированный | ||
| O(m + n log n) аморт. | | <math>O(m + n \; log \; n)</math> аморт. | ||
| O(n) | | O(n) | ||
| Родитти, Цвик [11] | | Родитти, Цвик [11] | ||
| Строка 158: | Строка 158: | ||
Таблица 1. Полностью | Таблица 1. Полностью динамические алгоритмы транзитивного замыкания с неявным представлением решения | ||
== Применение == | == Применение == | ||
| Строка 167: | Строка 167: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остается нерешенным фундаментальный вопрос: можно ли решить задачу о нахождении кратчайших путей между всеми парами из определения 3 за время ниже квадратичного | Остается нерешенным фундаментальный вопрос: можно ли решить полностью динамическую задачу о нахождении кратчайших путей между всеми парами из определения 3 за время на операцию ниже квадратичного в случае графов с вещественными весами ребер. | ||
== См. также == | == См. также == | ||
* [[Алгоритм поиска кратчайших путей в разреженных графах]] | |||
* [[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | |||
* [[Декрементный алгоритм нахождения кратчайших путей между всеми парами]] | |||
* [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | |||
* [[Полностью динамический алгоритм транзитивного замыкания]] | |||
* [[Полностью динамический алгоритм достижимости с единственным источником]] | |||
== Литература == | == Литература == | ||
| Строка 209: | Строка 209: | ||
16. Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville (1990). pp. 230-242 | 16. Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville (1990). pp. 230-242 | ||
[[Категория: Совместное определение связанных терминов]] | |||
