Раскраска: различия между версиями

'''Раскраска''' (''[[Coloring, colouring]]'') — для некоторого [[граф|графа]] <math>\,G</math> и натурального числа <math>\,k</math> функция вида <math>f: \, V(G) \rightarrow \{1,2,...,k\}</math>, отображающая множество [[вершина|вершин]] в множество цветов. Иногда, чтобы подчеркнуть мощность множества цветов, говорят о ''вершинной <math>\,k</math>-раскраске'' или просто о ''<math>\,k</math>-раскраске''. Интерес представляют только те раскраски, при которых [[смежные вершины]] окрашиваются в различные цвета. Такие раскраски называются правильными. Поскольку функция <math>\,f</math> не обязательно сюръективна,  при <math>\,k</math>-раскраске фактически может быть использовано менее <math>\,k</math> цветов. Таким образом, правильную <math>\,k</math>-раскраску графа <math>\,G</math> можно рассматривать как разбиение множества вершин на не более чем <math>\,k</math> непустых классов, каждый из которых является независимым множеством.

<math>\,k</math>-раскрашиваемым, является [[NP-Полная задача|<math>\mathcal NP</math>-''полной'']].

==См. также==  

* ''[[Ациклическая раскраска]],''

* ''[[Полная раскраска]],''

* ''[[Последовательная раскраска]],''

* ''[[Правильная раскраска]],''

* ''[[Реберная k-раскраска|Реберная <math>\,k</math>-раскраска]].''

 

* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.