Точный алгоритм раскраски графа с использованием метода включения-исключения: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 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> с точностью до полиномиального множителя, поскольку они удовлетворяют соотношению | ||
s(X) = | s(X) = | ||
0; ifX=V; | 0; ifX=V; | ||
s(x U {v}) + s(x [ fvg [ N(v)\ + 1; for v £ X ; | s(x U {v}) + s(x [ fvg [ N(v)\ + 1; for v £ X ; | ||
где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе. | где N(v) – множество соседей вершины v в графе G. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе. | ||
| Строка 39: | Строка 41: | ||
Эти техники можно распространить на произвольные семейства подмножеств над совокупностью размера n, при условии, что членство в семействе можно определить за полиномиальное время. | Эти техники можно распространить на произвольные семейства подмножеств над совокупностью размера n, при условии, что членство в семействе можно определить за полиномиальное время. | ||
== Применение == | == Применение == | ||