4501
правка
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 64: | Строка 64: | ||
Если множество <math>\mathcal{F} \;</math> состоит из всех полных компонентов размером не более 3, этот жадный алгоритм дает на выходе 3-ограниченное дерево Штейнера, введенное Зеликовским [14]. Если <math>\mathcal{F} \;</math> состоит из всех трехлучевых звезд и всех ребер, где трехлучевая звезда представляет собой дерево с 3 листьями и центральной вершиной, то жадный алгоритм дает на выходе итеративное 1-дерево Штейнера. Интересный факт, на которой обратили внимание Ду и коллеги [ ], заключается в том, что функция gain(<math>\cdot</math>) является субмодулярной над всеми полными компонентами размера не более 3, но не является субмодулярной над всеми трехлучевыми звездами и всеми ребрами. | Если множество <math>\mathcal{F} \;</math> состоит из всех полных компонентов размером не более 3, этот жадный алгоритм дает на выходе 3-ограниченное дерево Штейнера, введенное Зеликовским [14]. Если <math>\mathcal{F} \;</math> состоит из всех трехлучевых звезд и всех ребер, где трехлучевая звезда представляет собой дерево с 3 листьями и центральной вершиной, то жадный алгоритм дает на выходе итеративное 1-дерево Штейнера. Интересный факт, на которой обратили внимание Ду и коллеги [9], заключается в том, что функция gain(<math>\cdot</math>) является субмодулярной над всеми полными компонентами размера не более 3, но не является субмодулярной над всеми трехлучевыми звездами и всеми ребрами. | ||
| Строка 76: | Строка 76: | ||
'''Лемма 1.''' Функция f является субмодулярной в том и только том случае, если для любых <math>A \subset E \;</math> и различных <math>x, y \in E - A \;</math> выполняется | '''Лемма 1.''' Функция f является субмодулярной в том и только том случае, если для любых <math>A \subset E \;</math> и различных <math>x, y \in E - A \;</math> выполняется соотношение | ||
(1) <math>\Delta_x \; \Delta_y \; f(A) \le 0</math> | (1) <math>\Delta_x \; \Delta_y \; f(A) \le 0</math> | ||
Доказательство. Предположим, что f является субмодулярной. Положим <math>B = A \cup \{ x \} \;</math> и <math>C = A \cup \{ y \} \;</math>. Тогда <math>B \cup C = A \cup A \cup \{ x, y \} \;</math> и <math> | Доказательство. Предположим, что f является субмодулярной. Положим <math>B = A \cup \{ x \} \;</math> и <math>C = A \cup \{ y \} \;</math>. Тогда <math>B \cup C = A \cup A \cup \{ x, y \} \;</math> и <math>B \cap C = A \;</math>. Следовательно, должно иметь место | ||
<math>f(A \cup \{ x, y \}) - f(A \cup \{ x \}) - f(A \cup \{ y \}) + f(A) \le 0 \;</math>, | <math>f(A \cup \{ x, y \}) - f(A \cup \{ x \}) - f(A \cup \{ y \}) + f(A) \le 0 \;</math>, | ||
| Строка 104: | Строка 104: | ||
Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, | Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, | ||
<math>\Delta_x \ | <math>\Delta_x \Delta_y f(H) = -mst(P : H \; \cup \; x \; \cup \; y) + mst(P : H \; \cup \; x) + mst(P : H \; \cup \; y) - mst(P : H) = (mst(P : H) - mst(P : H \; \cup x \; \cup \; y)) - (mst(P : H) - mst(P : H \; \cup \; x)) + (mst(P : H) - mst(P : H \; \cup \; y))</math>. | ||
| Строка 114: | Строка 114: | ||
Значение <math>mst(P : H) | Значение <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>. | <math>mst(P : H) - mst(P : H \cup x \cup y) = length(e') + length(e'')</math>. | ||