Точный алгоритм раскраски графа с использованием метода включения-исключения: различия между версиями

Точный алгоритм раскраски графа с использованием метода включения-исключения (посмотреть исходный код)

8 байт убрано , 17 февраля 2014

нет описания правки

4430

правок

@@ Строка 19: / Строка 19: @@
 . <math>\chi(G) = min_{k \in \{1, ..., n\}} \bigg\{k: \sum_{X \subseteq V} (-1)^{|X|} s(X)^k > 0 \bigg\} \; </math>
-X(G)=     min     nk:   X (-l)lxls(X)k > 0 o :
+. Для k = 1, ..., k
-*6{i,..,»> *      £v	>
-к
+<math>P(G;k) = \sum_{r=1}^k \binom{k}{r} \bigg(\sum_{X \subseteq V} (-1)^{|X|} s_r(X) \bigg)</math>, (k = 1, 2, ..., n).
-к
-к
-к
-. Fork = 1;::: ;k,
-P(G; k) =
-E^
-r=1   r     XQV
-(k = 1,2,...,и).
 Время, необходимое для оценки этих выражений, зависит от 2n оценок s(X) и sr(X), соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений определяются 2n с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению