Деревья Штейнера: различия между версиями

Деревья Штейнера (посмотреть исходный код)

13 байт убрано , 8 июня 2016

м

4430

правок

Версия от 20:36, 8 июня 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 20:38, 8 июня 2016 (просмотреть исходный код) 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>,