68
правок
Изменения
Нет описания правки
{{main|Хроматический многочлен}}
{{Определение
|definition='''Хроматический многочлен ''' (англ. ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
}}
==Связь хроматического числа и хроматического многочлена==
*Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Поэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой.
*В обратную сторону, т.е. если известно хроматическое число, построить хроматический многочлен не получится. Так как оно не дает почти никакой информации о структуре графа.
==Примечания==
<references/>
