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

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

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

4551

правка

@@ Строка 95: / Строка 95: @@
-Следовательно, должно иметь место <math>A \backslash B \ne \empty \;</math> и <math>B \backslash A \ne \empty \;</math>. Запишем это как A \ В = {xx,... , xk} и В \ A = {yx, :::;yhg. Тогда
+Следовательно, должно иметь место <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>,
-Q
-f(AUB)-f(A)-f(B)
+где <math>\{ x_1, ..., x_{i - 1} \} = \empty \;</math> для i = 1 и <math>\{ y_1, ..., y_{j - 1} \} = \empty \;</math> для j = 1.
-к      h
- ^yjf(   A [fx 1 • • - xi-i i=1 j=1
-<o;
- _ig = ;  □
-где fx 1..: x,_ig = для i = 1 и forj=1.