Изменения
Нет описания правки
{{Определение
|definition= Правильной раскраской графа <tex>G(V,E)</tex> называется такое отображение <tex>\phi</tex> из множества вершин '''<tex>V''' </tex> в множество красок { <tex>c_1...c_t</tex> } что для любых двух смежных вершин '''<tex>u''' </tex> и '''<tex>v''' </tex> выполняется <tex>\phi(u)\ne\phi(v)</tex>.Так же её называют <tex>t</tex>-раскраской.
}}
Раскраской графа чаще всего называют именно правильную раскраску. Так же её называют t-раскраской.
== Хроматическое число ==
{{Определение
|definition= Хроматическим числом <tex>\chi(G)</tex> графа <tex>G(V,E)</tex> называется такое минимальное число <tex>t</tex>, для которого существует <tex>t</tex>-раскраска графа.
}}
== Хроматические числа различных графов ==
1) ''<tex>1''</tex>-хроматические графы - это нулевые графы и только они. <tex>\chi(O_{n}) = 1</tex>.
2) <tex>\chi(K_{n}) = n</tex> - хроматическое число полного графа равно ''<tex>n''</tex>.
3) <tex>\chi(C_{n}) =
</tex>
4) ''<tex>G'' </tex> - дерево, тогда <tex>\chi(G) = 2</tex>
== Хроматическая функция ==
{{Определение
|definition=<tex>P(G,t)</tex> - число способов раскрасить граф ''<tex>G'' </tex> в ''<tex>t'' </tex> цветов.
}}
