Содержание
- 2. Основные понятия Неориентированный граф Компоненты связности Компоненты реберной двусвязности – вершины в одной компоненте, если существует
- 7. Offline и Online Offline задача Все запросы к структуре данных известны заранее. Порядок запросов также известен.
- 8. Постановка задачи связности Неориентированный граф Запрос изменения графа – добавить ребро или удалить ребро Нужно после
- 9. Постановка задачи двусвязности Отличие от предыдущей задачи заключается в том, что теперь нас интересует количество компонент
- 10. Усложненная задача Между запросами изменения графа нужно обрабатывать запросы вида «лежат ли вершины A и B
- 15. Цели данной работы Обзор существующих решений сформулированных задач. Подробное описание известных мне offline решений обеих задач.
- 16. Наивное решение Для каждого из K моментов времени запустим процедуру поиска компонент связности и реберной двусвязности.
- 17. Существующие решения Задача о связности решена в 1992-м году Eppstein-ом за время O(N * logN). Задача
- 18. Основные идеи решения Add + Delete = отрезок времени Метод разделяй и властвуй Можно разбить все
- 19. Тестирование алгоритма Реализованы 2 более медленных и простых решения. Написаны различные генераторы 1. случайные процесс (центрированный
- 20. Результат работы Алгоритм, решающий задачу про двусвязность за время O(KlogK) и использующий O(K) памяти. На Intel
- 21. Сравнение решений задачи о связности
- 22. Сравнение решений задачи о двусвязности Задача о связности решена в 1992-м году Eppstein-ом за время O(N
- 23. Результат 2 Эффективная реализации предложенного мной алгоритма для задачи о двусвязности. ACM версия задачи о двусвязности
- 24. Применение алгоритмов Статистические запросы к динамически меняющимся графам. Пример #1: есть граф пользователей социальной сети, можно
- 26. Скачать презентацию