Жадные алгоритмы аппроксимации: различия между версиями

Жадные алгоритмы аппроксимации (посмотреть исходный код)

154 байта добавлено , 23 апреля 2015

м

4430

правок

Версия от 23:54, 23 апреля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 23:59, 23 апреля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) Следующая правка →
Строка 165:		Строка 165:


	''Доказательство''. Поскольку все <math>y_1, ..., y_{j - 1} \;</math> являются связными, <math>y_j \;</math> может доминировать не более одного дополнительного связного компонента в подграфе, порожденном C~~,_i [ C~~*_x, относительно подграфа, порожденного c i — 1.		''Доказательство''. Поскольку все <math>y_1, ..., y_{j - 1} \;</math> являются связными, <math>y_j \;</math> может доминировать не более одного дополнительного связного компонента в подграфе, порожденном <math>C_{i - 1} \cup C^_{j - 1} \;</math> , относительно подграфа, порожденного <math>C_{i - 1} \;</math>. Следовательно, <math>\Delta_{y_j} p(C_i) - \Delta_{y_j} f(C_i \cup C^_{j - 1}) \le 1</math>.