Слайд 2Основные понятия
Неориентированный граф
Компоненты связности
Компоненты реберной
двусвязности – вершины в одной компоненте, если
![Основные понятия Неориентированный граф Компоненты связности Компоненты реберной двусвязности – вершины в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-1.jpg)
существует два реберно непересекающихся пути между ними.
Мосты – ребра, при удалении которых увеличивается количество компонент связности.
Слайд 7Offline и Online
Offline задача
Все запросы к структуре данных известны заранее. Порядок
![Offline и Online Offline задача Все запросы к структуре данных известны заранее.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-6.jpg)
запросов также известен.
Online задача
Новый запрос становится известен только после того, как на предыдущий запрос дан ответ.
Слайд 8Постановка задачи связности
Неориентированный граф
Запрос изменения графа – добавить ребро или удалить ребро
Нужно
![Постановка задачи связности Неориентированный граф Запрос изменения графа – добавить ребро или](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-7.jpg)
после каждого запроса знать
количество компонент связности
Входные данные: изначально пустой граф и K запросов изменения графа
Выходные данные: K чисел – количество компонент связности после каждого из запросов
Слайд 9Постановка задачи двусвязности
Отличие от предыдущей задачи заключается в том, что теперь нас
![Постановка задачи двусвязности Отличие от предыдущей задачи заключается в том, что теперь](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-8.jpg)
интересует количество
компонент реберной двусвязности и количество мостов
Слайд 10Усложненная задача
Между запросами изменения графа нужно обрабатывать запросы вида «лежат ли вершины
![Усложненная задача Между запросами изменения графа нужно обрабатывать запросы вида «лежат ли](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-9.jpg)
A и B в одной компоненте связности», «лежат ли вершины A и B в одной компоненте реберной двусвязности, сколько между ними мостов»
Слайд 15Цели данной работы
Обзор существующих решений сформулированных задач.
Подробное описание известных мне offline решений
![Цели данной работы Обзор существующих решений сформулированных задач. Подробное описание известных мне](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-14.jpg)
обеих задач.
Разработка нового, более быстрого, offline решения.
Слайд 16Наивное решение
Для каждого из K моментов времени запустим процедуру поиска компонент связности
![Наивное решение Для каждого из K моментов времени запустим процедуру поиска компонент](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-15.jpg)
и реберной двусвязности.
Время работы такого
алгоритма = O(K2). Алгоритм использует O(K) дополнительной памяти.
Обе оценки в худшем случае достигаются.
Слайд 17Существующие решения
Задача о связности решена в 1992-м году Eppstein-ом за время O(N
![Существующие решения Задача о связности решена в 1992-м году Eppstein-ом за время](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-16.jpg)
* logN).
Задача о двусвязности решена Thorup-ом за время O(N * log3N * loglogN) в 2000-м году.
До сих пор это было лучшим достижением.
Слайд 18Основные идеи решения
Add + Delete = отрезок времени
Метод разделяй и властвуй
Можно разбить
![Основные идеи решения Add + Delete = отрезок времени Метод разделяй и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-17.jpg)
все моменты времени на две части. Рекурсивно обработать сперва первую половину, затем вторую.
Редукция и конденсация.
Если количество запросов = k, граф всегда можно уменьшить до размера O(k) вершин
Слайд 19Тестирование алгоритма
Реализованы 2 более медленных и простых решения.
Написаны различные генераторы
1. случайные процесс
![Тестирование алгоритма Реализованы 2 более медленных и простых решения. Написаны различные генераторы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-18.jpg)
(центрированный и нет)
2. волны (длинные, короткие)
3. клики
4. циклы
5. ….
Сравнение результатов работы решений в «бесконечном» цикле.
Подсчет времени работы (реального + счетчики внутри программы).
Слайд 20Результат работы
Алгоритм, решающий задачу про
двусвязность за время O(KlogK)
и использующий O(K) памяти.
На
![Результат работы Алгоритм, решающий задачу про двусвязность за время O(KlogK) и использующий](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-19.jpg)
Intel Pentium U5400 1.2 GHz за 1 секунду
обрабатывается более 2.105 запросов.
Подробное описание на русском языке offline решений задачи о связности
Слайд 21Сравнение решений задачи о связности
![Сравнение решений задачи о связности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-20.jpg)
Слайд 22Сравнение решений задачи о двусвязности
Задача о связности решена в 1992-м году Eppstein-ом
![Сравнение решений задачи о двусвязности Задача о связности решена в 1992-м году](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-21.jpg)
за время O(N * logN).
Мое решение работает за то же время.
В сравнении с решением Thorup-а, мое решение проще в реализации (у Thorup-а поддерживается MST во взвешенном меняющемся графе, а задача связности сводится к MST).
Слайд 23Результат 2
Эффективная реализации предложенного мной алгоритма для задачи о двусвязности.
ACM версия задачи
![Результат 2 Эффективная реализации предложенного мной алгоритма для задачи о двусвязности. ACM](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-22.jpg)
о двусвязности (набор тестов в формате, позволяющем автоматическую проверку решений)
Аналогичный алгоритм для
задачи о связности. Требуемые время и память те же – O(KlogK) и O(K)
Слайд 24Применение алгоритмов
Статистические запросы к динамически меняющимся графам.
Пример #1: есть граф пользователей социальной
![Применение алгоритмов Статистические запросы к динамически меняющимся графам. Пример #1: есть граф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/997785/slide-23.jpg)
сети, можно для фиксированной группы из K человек узнать “интересные моменты времени”, когда появлялась связность и двусвязность в данной группе.
Пример #2: Проверка надежности сетей за счет проверки того, что сеть постоянно двусвязна.