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

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

249 байт добавлено , 2 июня 2016

4551

правка

@@ Строка 78: / Строка 78: @@
-Лемма 1. Функция f является субмодулярной в том и только том случае, если для любых A С E и различных x, y 2 E — A,
+'''Лемма 1.''' Функция f является субмодулярной в том и только том случае, если для любых <math>A \subset E \;</math> и различных <math>x, y \in E - A \;</math> выполняется
-(1)
-AxAyf(A)<0.
+(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>В \cap C = A \;</math>. Следовательно, должно иметь место
+<math>f(A \cup \{ x, y \}) - f(A \cup \{ x \}) - f(A \cup \{ y \})  + f(A) \le 0 \;</math>,
-Доказательство. Предположим, f является субмодулярной. Положим B = A [ fxg и C = A U yg. Тогда B[ C = A[ A[ fx; yg и В \ C = A. Следовательно, должно иметь место
-f(A [ fx; yg) - f(A [ fxg) - f(A U yg) + f(A) < 0 ;
 это означает, что соотношение (1) верно.
@@ Строка 145: / Строка 148: @@
 Рисунок 2.
 == Применение ==