4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 15:19, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
Из инварианта (2) следует, что максимальное число уровней равно <math>L \le \mathcal {b} log_2 \; n \mathcal {c}</math>. | Из инварианта (2) следует, что максимальное число уровней равно <math>L \le \mathcal {b} log_2 \; n \mathcal {c}</math>. | ||
Заметим, что при вставке новой дуги ей присваивается уровень 0. Затем ее уровень может быть увеличен не более <math>\mathcal {b} log_2 \; n \mathcal {c}</math> раз вследствие последовательности удалений дуг. Когда удаляется дуга e = (v, w) уровня <math>\ell (e) \; </math>, алгоритм ищет дугу замены с максимально высоким уровнем, если такая существует. В силу инварианта (1) такая дуга замены имеет уровень | Заметим, что при вставке новой дуги ей присваивается уровень 0. Затем ее уровень может быть увеличен не более <math>\mathcal {b} log_2 \; n \mathcal {c}</math> раз вследствие последовательности удалений дуг. Когда удаляется дуга e = (v, w) уровня <math>\ell (e) \; </math>, алгоритм ищет дугу замены с максимально высоким уровнем, если такая существует. В силу инварианта (1) такая дуга замены имеет уровень <math>\ell \le \ell (e) \; </math>. Следовательно, процедура замены <math>Replace((u, w), \ell (e)) </math> вызывается с параметрами <math>e \; </math> и <math> \ell (e)</math>. Далее будут вкратце описаны операции, выполняемые этой процедурой. | ||
<math>Replace((u, w), \ell ) \; </math> находит дугу замены самого высокого уровня, не превышающего <math>\ell \;</math>, если такая существует. Если на уровне <math>\ell \;</math> такой дуги не существует, имеет место один из двух вариантов: если <math>\ell > 0 \;</math>, алгоритм рекурсивно переходит на уровень <math>\ell - 1 \;</math>; в противном случае <math>\ell = 0 \;</math>, и удаление дуги (v, w) разделяет деревья v и w в графе G. | |||
Во время поиска на уровне I подходящим образом выбранные древесные и недревесные дуги могут быть перемещены на более высокий уровень следующим образом. Пусть Tv и Tw – деревья в лесу Fi, полученные после удаления дуги (v, w), и пусть, без ограничения общности, Tv меньше Tw. Тогда Tv содержит не более и/2 вершин, поскольку Tv [ Tw [ f(v, w)g было деревом на уровне I и выполняется инвариант (2). Следовательно, дуги уровня I в Tv могут быть перемещены на уровень I + 1 с сохранением инвариантов. Наконец, одна за дугой посещаются недревесные дуги, инцидентные Tv: если дуга соединяет Tv и Tw, то дуга замены найдена и поиск останавливается; в противном случае ее уровень увеличивается на 1. | Во время поиска на уровне I подходящим образом выбранные древесные и недревесные дуги могут быть перемещены на более высокий уровень следующим образом. Пусть Tv и Tw – деревья в лесу Fi, полученные после удаления дуги (v, w), и пусть, без ограничения общности, Tv меньше Tw. Тогда Tv содержит не более и/2 вершин, поскольку Tv [ Tw [ f(v, w)g было деревом на уровне I и выполняется инвариант (2). Следовательно, дуги уровня I в Tv могут быть перемещены на уровень I + 1 с сохранением инвариантов. Наконец, одна за дугой посещаются недревесные дуги, инцидентные Tv: если дуга соединяет Tv и Tw, то дуга замены найдена и поиск останавливается; в противном случае ее уровень увеличивается на 1. | ||
