4551
правка
Полностью динамические минимальные остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:40, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Инвариант (3) может использоваться для доказательства утверждения, что среди всех ребер замены ребро с минимальным весом будет находиться на максимальном уровне. Пусть <math>e_1 \; </math> и <math>e_2 \; </math> – два ребра замены с <math>w(e_1) < w(e_2) \; </math>; пусть <math>C_i \;</math> – цикл, порожденный <math>e_i \;</math> в F, i = 1, 2. Поскольку F – минимальный остовный лес, <math>e_i \; </math> имеет максимальный вес среди всех ребер в <math>C_i \;</math>. В частности, поскольку, согласно предположению, <math>w(e_1) < w(e_2) \; </math>, <math>e_2 \; </math> также имеет максимальный вес среди ребер в цикле <math>C = (C_1 \cup C_2) \setminus (C_1 \cap C_2)</math>. В силу инварианта (3), ребро <math>e_2 \; </math> имеет минимальный уровень в C, что доказывает, что <math>\ell (e_2) \le \ell (e_1) \; </math>. Таким образом, рассмотрение недревесных ребер от максимального до минимального уровня является корректным. | Инвариант (3) может использоваться для доказательства утверждения, что среди всех ребер замены ребро с минимальным весом будет находиться на максимальном уровне. Пусть <math>e_1 \; </math> и <math>e_2 \; </math> – два ребра замены с <math>w(e_1) < w(e_2) \; </math>; пусть <math>C_i \;</math> – цикл, порожденный <math>e_i \;</math> в F, i = 1, 2. Поскольку F – минимальный остовный лес, <math>e_i \; </math> имеет максимальный вес среди всех ребер в <math>C_i \;</math>. В частности, поскольку, согласно предположению, <math>w(e_1) < w(e_2) \; </math>, <math>e_2 \; </math> также имеет максимальный вес среди ребер в цикле <math>C = (C_1 \cup C_2) \setminus (C_1 \cap C_2)</math>. В силу инварианта (3), ребро <math>e_2 \; </math> имеет минимальный уровень в C, что доказывает, что <math>\ell (e_2) \le \ell (e_1) \; </math>. Таким образом, рассмотрение недревесных ребер от максимального до минимального уровня является корректным. | ||
Заметим, что вначале ребру присваивается уровень 0. Затем его уровень может быть увеличен не более | Заметим, что вначале ребру присваивается уровень 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>. Далее будут вкратце описаны операции, выполняемые этой процедурой. | ||
Replace((u, w), | <math>Replace((u, w), \ell (e)) \; </math> находит ребро замены самого высокого уровня, не превышающего <math>\ell \;</math>, если такое существует, рассматривая ребра в порядке увеличения веса. Если на уровне <math>\ell \;</math> такого ребра не существует, имеет место один из двух вариантов: если <math>\ell > 0 \;</math>, алгоритм рекурсивно переходит на уровень <math>\ell - 1 \;</math>; в противном случае <math>\ell = 0 \;</math>, и удаление ребра (v, w) разделяет деревья v и w в графе G. | ||
Можно показать, что Replace возвращает ребро замены с минимальным весом максимально возможного уровня, что обосновывает следующую лемму: | Можно показать, что Replace возвращает ребро замены с минимальным весом максимально возможного уровня, что обосновывает следующую лемму: | ||