4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 14:03, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
Для выполнения систематического поиска дуг замены алгоритм присваивает каждой дуге e уровень <math>\ell (e) \; </math> и на основе этих уровней поддерживает множество под-лесов остовного дерева F: для каждого уровня i лес <math>F_i</math> является под-лесом, порожденным древесными дугами уровня выше или равного i. Обозначив за L максимальный уровень дуги, получаем следующее: | Для выполнения систематического поиска дуг замены алгоритм присваивает каждой дуге e уровень <math>\ell (e) \; </math> и на основе этих уровней поддерживает множество под-лесов остовного дерева F: для каждого уровня i лес <math>F_i \; </math> является под-лесом, порожденным древесными дугами уровня выше или равного i. Обозначив за L максимальный уровень дуги, получаем следующее: | ||
<math>F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L.</math> | <math>F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L.</math> | ||
| Строка 27: | Строка 27: | ||
Вначале все дуги имеют уровень 0; затем уровни прогрессивно увеличиваются, но никогда не уменьшаются. Изменения уровней дуг выполняются таким образом, чтобы поддерживать следующие инварианты, которые очевидным образом выполняются в начале процесса. | Вначале все дуги имеют уровень 0; затем уровни прогрессивно увеличиваются, но никогда не уменьшаются. Изменения уровней дуг выполняются таким образом, чтобы поддерживать следующие инварианты, которые очевидным образом выполняются в начале процесса. | ||
Инвариант ( | '''Инвариант (1)''': F – максимальный остовный лес графа G, если уровни дуг интерпретировать как их веса. | ||
Инвариант (1) следует интерпретировать следующим образом. Пусть (u, v) – недревесная дуга уровня | '''Инвариант (2)''': Число вершин каждого дерева <math>F_i</math> не превышает <math>n/2^i \; </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>. Поскольку это выполняется для каждой дуги пути, а по построению F^U;V) содержит все древесные дуги уровня более l(u, v), то весь путь содержится в F^U;V); иначе говоря, u и v являются связанными в F^uv). | |||
Из инварианта (2) следует, что максимальное число уровней равно L < blog2 nc. | Из инварианта (2) следует, что максимальное число уровней равно L < blog2 nc. | ||
