Точный алгоритм раскраски графа с использованием метода включения-исключения: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 15: | Строка 15: | ||
Теорема 1. Пусть G – граф с n вершинами. 1. | '''Теорема 1.''' Пусть G – граф с n вершинами. | ||
1. <math>\chi(G) = min_{k \in \{1, ..., n\}} \bigg\{k: \sum_{X \subseteq V} (-1)^{|X|} s(X)^k > 0 \bigg\} \; </math> | |||
X(G)= min nk: X (-l)lxls(X)k > 0 o : | X(G)= min nk: X (-l)lxls(X)k > 0 o : | ||
*6{i,..,»> * £v > | *6{i,..,»> * £v > | ||