4488
правок
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
Строка 19: | Строка 19: | ||
1. <math>\chi(G) = min_{k \in \{1, ..., n\}} \bigg\{k: \sum_{X \subseteq V} (-1)^{|X|} s(X)^k > 0 \bigg\} \; </math> | 1. <math>\chi(G) = min_{k \in \{1, ..., n\}} \bigg\{k: \sum_{X \subseteq V} (-1)^{|X|} s(X)^k > 0 \bigg\} \; </math> | ||
2. Для k = 1, ..., k | |||
<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). | |||
P(G; k) = | |||
r=1 | |||
(k = 1,2,..., | |||
Время, необходимое для оценки этих выражений, зависит от 2n оценок s(X) и sr(X), соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений определяются 2n с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению | Время, необходимое для оценки этих выражений, зависит от 2n оценок s(X) и sr(X), соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений определяются 2n с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению |
правок