Аноним

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

Материал из WEGA
Строка 90: Строка 90:




Напротив, предположим, что свойство (1) выполняется для любых A С E и различных x, y 2 E A. Рассмотрим два подмножества A, B of E. Если А С B или B С A, тогда тривиально получается
Напротив, предположим, что свойство (1) выполняется для любых <math>A \subset E \;</math> и различных <math>x, y \in E - A \;</math>. Рассмотрим два подмножества A, B множества E. Если <math>A \subseteq B \;</math> или <math>B \subseteq A \;</math>, тогда тривиально получается
f(A) + f(B) > f( U В) + f( П В) :
 
<math>f(A) + f(B) \ge f(A \cup B) + f(A \cap B) \;</math>.
   
   
О
 
Следовательно, должно иметь место A n B ф и В \ А ф 0. Запишем это как A \ В = {xx,... , xk} и В \ A = {yx, :::;yhg. Тогда
Следовательно, должно иметь место <math>A \backslash B \ne \empty \;</math> и <math>B \backslash A \ne \empty \;</math>. Запишем это как A \ В = {xx,... , xk} и В \ A = {yx, :::;yhg. Тогда
О
О
   
   
4551

правка