4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 27: | Строка 27: | ||
<math>s(X) = \begin{cases} 0, & если X = V \\ s \Big(X \cup \{ v \} \Big) + s\Big(X \cup \{ v \} \cup N(v)\Big) + 1, & v \not\in X\ \end{cases}</math> | <math>s(X) = \begin{cases} 0, & если X = V \\ s \Big(X \cup \{ v \} \Big) + s\Big(X \cup \{ v \} \cup N(v)\Big) + 1, & v \not\in X\ \end{cases}</math> | ||
где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем | где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем выполнения и полиномиальным объемом памяти, описанных в литературе. | ||
Это дает нам следующие границы: | Это дает нам следующие границы: |
правок