4446
правок
Полностью динамическая связность высоких степеней в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность высоких степеней в планарных графах (посмотреть исходный код)
Версия от 17:21, 17 июля 2014
, 17 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
'''Теорема 2. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнение запросов на проверку 3-реберной и 4-реберной связности графа возможно выполнить за время O( | '''Теорема 2. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнение запросов на проверку 3-реберной и 4-реберной связности графа возможно выполнить за время <math>O(n^{1/2}) \; </math> на одно обновление; проверку 3- или 4-реберной связности двух вершин возможно выполнить за время <math>O(n^{1/2} \; )</math> на одно обновление или запрос.''' | ||
'''Теорема 3. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 3-вершинной связности графа либо проверку принадлежности двух вершин к одной и той же 3-вершинно-связной компоненте, возможно выполнить за амортизированное время O( | '''Теорема 3. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 3-вершинной связности графа либо проверку принадлежности двух вершин к одной и той же 3-вершинно-связной компоненте, возможно выполнить за амортизированное время <math>O(n^{1/2}) \; </math> на один запрос или обновление.''' | ||
Границы, определяемые этими теоремами, улучшены по сравнению с границами для графов общего вида, представленными в статье | Границы, определяемые этими теоремами, улучшены по сравнению с границами для графов общего вида, представленными в статье «[[Полностью динамическая связность высоких степеней]]». | ||
== Применение == | == Применение == | ||