4431
правка
Точный алгоритм раскраски графа с использованием метода включения-исключения: различия между версиями
Перейти к навигации
Перейти к поиску
м
Точный алгоритм раскраски графа с использованием метода включения-исключения (посмотреть исходный код)
Версия от 14:23, 1 октября 2023
, 1 октября 2023нет описания правки
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. Эти значения могут быть также вычислены при помощи алгоритмов с экспоненциальным временем выполнения и полиномиальным объемом памяти, описанных в литературе. | ||
Это дает нам следующие границы: | Это дает нам следующие границы: | ||