Точный алгоритм раскраски графа с использованием метода включения-исключения: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
== Основные результаты == | == Основные результаты == | ||
Отмечено, что <math>\chi(G) \; </math> и P(G;k) могут быть выражены при помощи формулы включения-исключения, члены которой определяются набором независимых множеств порожденных подграфов G. Пусть X | Отмечено, что <math>\chi(G) \; </math> и P(G;k) могут быть выражены при помощи формулы включения-исключения, члены которой определяются набором независимых множеств порожденных подграфов G. Пусть <math>X \subseteq V \; </math> и пусть <math>s(X) \; </math> – число непустых независимых подмножеств вершин, не пересекающихся с X; пусть <math>s_r(X) \; </math> обозначает число способов выбора r непустых независимых подмножеств <math>S_1, ..., S_r \; </math> (возможно, перекрывающихся с повторениями), не пересекающихся с X, таких, что <math>|S_1| + ... + |S_r| = |V| \; </math>. | ||