4430
правок
Компромиссы при решении динамических графовых задач: различия между версиями
Материал из WEGA
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 10:59, 28 декабря 2018
, 28 декабря 2018нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 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. | ||
