4501
правка
Жадные алгоритмы аппроксимации: различия между версиями
Перейти к навигации
Перейти к поиску
м
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 18:01, 23 апреля 2015
, 23 апреля 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
выбрать вершину x так, чтобы максимизировать <math>f(C) - f(C \cup \{ x \} )</math> и <math>C \leftarrow C \cup \{ x \}</math>; вывести C. | выбрать вершину x так, чтобы максимизировать <math>f(C) - f(C \cup \{ x \} )</math> и <math>C \leftarrow C \cup \{ x \}</math>; вывести C. | ||
Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг | Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг <math>\{ (u, v) \in E | u \in C </math> или <math> v \in C \}</math>. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2. | ||