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

Перейти к навигации Перейти к поиску
Строка 23: Строка 23:
<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).
<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).


Время, необходимое для оценки этих выражений, зависит от <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> с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению


s(X) =
<math>s(X) = \begin{cases} 0, & если X = V \\ s \Big(X \cup \{ v \} \Big) + s\Big(X \cup \{ v \} \cup N(v)\Big) + 1; & \mbox{для }v \not\in X\mbox{ } \end{cases}</math>
0; ifX=V;
s(x U {v}) + s(x [ fvg [ N(v)\ + 1;     for v £ X ;


где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе.
где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе.
Источник — http://pco.iis.nsk.su/wega/index.php/Точный_алгоритм_раскраски_графа_с_использованием_метода_включения-исключения