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

Перейти к навигации Перейти к поиску
Строка 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; & \mbox{для }v \not\in X\mbox{ } \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. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем исполнения и полиномиальным объемом памяти, описанных в литературе.
Строка 32: Строка 32:




Теорема 2. Для графа G с n вершинами значения x(G) и P(G, k) могут быть вычислены со следующими результатами:
'''Теорема 2. Для графа G с n вершинами значения <math>\chi(G) \; </math> и <math>P(G; k) \; </math> могут быть вычислены со следующими затратами ресурсов:
1. время и объем памяти 2n nO(1);
 
2. время O(2:2461n) и полиномиальный объем памяти.
1. время и объем памяти <math>2^n n^{O(1)} \; </math>;
 
2. время <math>O(2.2461^n) \; </math> и полиномиальный объем памяти.'''


Оптимальную раскраску, дающую <math>\chi(G) \; </math>, можно найти с теми же затратами времени и объема памяти.
Оптимальную раскраску, дающую <math>\chi(G) \; </math>, можно найти с теми же затратами времени и объема памяти.
Источник — http://pco.iis.nsk.su/wega/index.php/Точный_алгоритм_раскраски_графа_с_использованием_метода_включения-исключения