4510
правок
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 97: | Строка 97: | ||
Следовательно, должно иметь место <math>A \backslash B \ne \empty \;</math> и <math>B \backslash A \ne \empty \;</math>. Запишем это как <math>A \backslash B = \{ x_1, ..., x_k \} \;</math> и <math>B \backslash A = \{ y_1, ..., y_h \} \;</math>. Тогда | Следовательно, должно иметь место <math>A \backslash B \ne \empty \;</math> и <math>B \backslash A \ne \empty \;</math>. Запишем это как <math>A \backslash B = \{ x_1, ..., x_k \} \;</math> и <math>B \backslash A = \{ y_1, ..., y_h \} \;</math>. Тогда | ||
<math>f(A \cup B) - f(A) - f(B) + f(A \cap B) = \sum^k_{i = 1} \sum^h_{j = 1} \Delta_{x_i} \Delta_{y_j} f(A \cup \{ x_1, ..., x_{i - 1} \} \cup \{ y_1, ..., y_{j - 1} \}) \le 0</math>, | <math>f(A \; \cup \; B) - f(A) - f(B) + f(A \; \cap \; B) = \sum^k_{i = 1} \sum^h_{j = 1} \Delta_{x_i} \Delta_{y_j} f(A \; \cup \; \{ x_1, ..., x_{i - 1} \} \; \cup \; \{ y_1, ..., y_{j - 1} \}) \le 0</math>, | ||
где <math>\{ x_1, ..., x_{i - 1} \} = \empty \;</math> для i = 1 и <math>\{ y_1, ..., y_{j - 1} \} = \empty \;</math> для j = 1. | где <math>\{ x_1, ..., x_{i - 1} \} = \empty \;</math> для i = 1 и <math>\{ y_1, ..., y_{j - 1} \} = \empty \;</math> для j = 1. | ||
Лемма 2. Определим f(H) = —mst(P : H). Тогда функция f является субмодулярной над множеством ребер E. | '''Лемма 2.''' Определим f(H) = —mst(P : H). Тогда функция f является субмодулярной над множеством ребер E. | ||
Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, | Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, | ||
+ mst(P : | <math>\Delta_x \Delta 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>. | ||
- (mst(P : H) - mst(P :H | |||
- mst(P :H | |||