4430
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 22:13, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Инвариант (1) следует интерпретировать следующим образом. Пусть <math>(u, v) \; </math> – недревесная дуга уровня <math>\ell (u, v) \; </math>; пусть <math>u \cdot \cdot \cdot v \; </math> – уникальный путь между u и v в F (такой путь существует, поскольку F является остовным лесом графа G). Пусть e – любая дуга из пути <math>u \cdot \cdot \cdot v \; </math>, а <math>\ell (e) \; </math> – уровень этой дуги. В силу инварианта (1), <math>\ell (e) \ge \ell (u, v) \; </math>. Поскольку это выполняется для каждой дуги пути, а по построению <math>F_{\ell(u, v)}</math> содержит все древесные дуги уровня более или равного <math>\ell (u, v) \; </math>, то весь путь содержится в <math>F_{\ell(u, v)}</math>; иначе говоря, u и v являются связанными в <math>F_{\ell(u, v)}</math>. | Инвариант (1) следует интерпретировать следующим образом. Пусть <math>(u, v) \; </math> – недревесная дуга уровня <math>\ell (u, v) \; </math>; пусть <math>u \cdot \cdot \cdot v \; </math> – уникальный путь между u и v в F (такой путь существует, поскольку F является остовным лесом графа G). Пусть e – любая дуга из пути <math>u \cdot \cdot \cdot v \; </math>, а <math>\ell (e) \; </math> – уровень этой дуги. В силу инварианта (1), <math>\ell (e) \ge \ell (u, v) \; </math>. Поскольку это выполняется для каждой дуги пути, а по построению <math>F_{\ell(u, v)}</math> содержит все древесные дуги уровня более или равного <math>\ell (u, v) \; </math>, то весь путь содержится в <math>F_{\ell(u, v)}</math>; иначе говоря, u и v являются связанными в <math>F_{\ell(u, v)}</math>. | ||
Из инварианта (2) следует, что максимальное число уровней равно L < | Из инварианта (2) следует, что максимальное число уровней равно <math>L \le \mathcal {b} log_2 \; n \mathcal {c}</math>. | ||
Заметим, что при вставке новой дуги ей присваивается уровень 0. Затем ее уровень может быть увеличен не более | Заметим, что при вставке новой дуги ей присваивается уровень 0. Затем ее уровень может быть увеличен не более <math>\mathcal {b} log_2 \; n \mathcal {c}</math> раз вследствие последовательности удалений дуг. Когда удаляется дуга e = (v, w) уровня <math>\ell (e) \; </math>, алгоритм ищет дугу замены с максимально высоким уровнем, если такая существует. В силу инварианта (1) такая дуга замены имеет уровень I < l{e). Следовательно, процедура замены Replace((u, w),l(e)) вызывается с параметрами e и l(e). Далее будут вкратце описаны операции, выполняемые этой процедурой. | ||
Replace((u, w), I) находит дугу замены самого высокого уровня l< £, если такая существует. Если на уровне I такой дуги не существует, имеет место один из двух вариантов: если £ > 0, алгоритм рекурсивно переходит на уровень I — 1; в противном случае 1 = 0, и удаление дуги (v, w) разделяет деревья v и w в графе G. | Replace((u, w), I) находит дугу замены самого высокого уровня l< £, если такая существует. Если на уровне I такой дуги не существует, имеет место один из двух вариантов: если £ > 0, алгоритм рекурсивно переходит на уровень I — 1; в противном случае 1 = 0, и удаление дуги (v, w) разделяет деревья v и w в графе G. | ||