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

Если C является связным доминирующим множеством, то p(C) = q(C) = 1 и, следовательно, f(C) = 2. Напротив, предположим, что <math>f(C \cup \{ x \}) = 2</math>. Поскольку <math>p(C) \ge 1 \;</math> и <math>q(C) \ge 1 \;</math>, должно иметь место p(C) = q(C) = 1, из чего следует, что C является связным доминирующим множеством. Функция f обладает еще одним свойством на графе G, имеющем не менее трех вершин: если f(C) > 2, то существует <math>x \in V \;</math>, такое, что <math>f(C) - f(C \cup \{ x \} ) > 0</math>. Фактически, для <math>C \ne \empty \;</math>, поскольку G является связным графом, имеющим не менее трех вершин, должна существовать вершина x со степенью не ниже двух, и для такой вершины x выполняется <math>f(C \cup \{ x \}) < f(C)</math>. Для случая <math>C \ne \empty \;</math> рассмотрим связную компоненту подграфа, порожденного C. Обозначим как B его множество вершин, являющееся подмножеством C. Для каждой вершины y, смежной с B, в случае, если y смежна с вершиной, не смежной с B и не принадлежащей к C, то p(C [ fyg) < p(C) и q(C U yg) < q(C); если вершина y смежна с вершиной из множества C — B, то p(C U yg) < p(C) и q(C [ fyg) < q(C).