4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 25: | Строка 25: | ||
Время, необходимое для оценки этих выражений, зависит от <math>2^n \; </math> оценок <math>s(X) \; </math> и <math>s_r(X) \; </math>, соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений соответствуют <math>2^n \; </math> с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению | Время, необходимое для оценки этих выражений, зависит от <math>2^n \; </math> оценок <math>s(X) \; </math> и <math>s_r(X) \; </math>, соответственно. Эти значения могут быть вычислены предварительно; время и объем памяти для этих вычислений соответствуют <math>2^n \; </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 | <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. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе. | ||
Строка 32: | Строка 32: | ||
Теорема 2. Для графа G с n вершинами значения | '''Теорема 2. Для графа G с n вершинами значения <math>\chi(G) \; </math> и <math>P(G; k) \; </math> могут быть вычислены со следующими затратами ресурсов: | ||
1. время и объем памяти | |||
2. время O(2 | 1. время и объем памяти <math>2^n n^{O(1)} \; </math>; | ||
2. время <math>O(2.2461^n) \; </math> и полиномиальный объем памяти.''' | |||
Оптимальную раскраску, дающую <math>\chi(G) \; </math>, можно найти с теми же затратами времени и объема памяти. | Оптимальную раскраску, дающую <math>\chi(G) \; </math>, можно найти с теми же затратами времени и объема памяти. |
правок