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

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

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

4430

правок

@@ Строка 8: / Строка 8: @@
-Жадный алгоритм A:
+'''Жадный алгоритм A:'''
-C;;
-whilef(C) > 2 do
+<math>C \leftarrow \empty</math>
-выбрать вершину x так, чтобы максимизировать /(C)-/(CU fxg) и C       C[ fxg; output C
+'''while''' <math>f(C) > 2 ;\ </math> '''do'''
+выбрать вершину 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(u, v) 2 E j и 2 C или v 2 Cg. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2.