4551
правка
Полностью динамическая проверка на планарность: различия между версиями
Материал из WEGA
Полностью динамическая проверка на планарность (посмотреть исходный код)
Версия от 19:47, 26 июля 2014
, 26 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку, не нарушает ли новое ребро планарность графа, возможно выполнить за амортизированное время O( | '''Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку, не нарушает ли новое ребро планарность графа, возможно выполнить за амортизированное время <math>O(n^{1/2}) \;</math> на один запрос или обновление.''' | ||
| Строка 19: | Строка 19: | ||
Теорема 2. Поддержку графа с произвольными вставками и удалениями ребер и выполнением запросов на проверку, является ли граф в текущий момент планарным и не нарушит ли новое ребро планарность, возможно выполнить за амортизированное время O( | '''Теорема 2. Поддержку графа с произвольными вставками и удалениями ребер и выполнением запросов на проверку, является ли граф в текущий момент планарным и не нарушит ли новое ребро планарность, возможно выполнить за амортизированное время <math>O(n^{1/2}) \;</math> на один запрос или обновление.''' | ||
== Применение == | == Применение == | ||
