68
правок
Изменения
Нет описания правки
{{Определение
|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...\ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
}}
[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
==Связь хроматического числа и хроматического многочлена==
*Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Поэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой. Однако задача о нахождении хроматического многочлена также не разрешима за полиномиальное время.
*В обратную сторону, т.е. если известно хроматическое число, построить хроматический многочлен не получится. Так как оно не дает почти никакой информации о структуре графа.
==Источники информации==
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
