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