4501
правка
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 81: | Строка 81: | ||
Доказательство. Предположим, что 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>. Следовательно, | Доказательство. Предположим, что 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>, | ||