4430
правок
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 102: | Строка 102: | ||
'''Лемма 2.''' Определим f(H) = | '''Лемма 2.''' Определим f(H) = -mst(P : H). Тогда функция f является субмодулярной над множеством ребер E. | ||
Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, | Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, | ||
| Строка 109: | Строка 109: | ||
Пусть T – минимальное остовное дерево для несвязанных полюсов после стягивания каждого ребра H в точку. T содержит путь | Пусть T – минимальное остовное дерево для несвязанных полюсов после стягивания каждого ребра H в точку. T содержит путь <math>P_x \;</math>, соединяющий две конечные точки x, и путь <math>P_y \;</math>, соединяющий две конечные точки y. Пусть <math>e_x (e_y) \;</math> – самое длинное ребро пути <math>P_x (P_y) \;</math>. Тогда | ||
mst(P : H) - mst(P :H | |||
mst(P : H) — mst(P : H | <math>mst(P : H) - mst(P : H \; \cup \; x) = length(e_x)</math>; | ||
<math>mst(P : H) - mst(P : H \; \cup \; y) = length(e_y)</math>. | |||
Значение <math>mst(P : H) — mst(P : H \; \cup \; x \; \cup \; y)</math> можно вычислить следующим образом: выберем самое длинное ребро e' из <math>P_x \cup P_y</math>. Заметим, что <math>T \cup x \cup y - e'</math> содержит уникальный цикл Q. Выберем самое длинное ребро e'' из <math>(P_x \cup P_y) \cap Q</math>. Тогда | |||
<math>mst(P : H) - mst(P : H \cup x \cup y) = length(e') + length(e'')</math>. | |||
Теперь, чтобы показать субмодулярность f, достаточно доказать неравенство | |||
(2) <math>length(e_x) + length(e_y) \ge length(e') + length(e'')</math>. | |||