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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Раскраска''' (''[[Colouring]]'') -
'''Раскраска''' (''[[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>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>-''полной'']].
<math>\,k</math>-раскрашиваемым, является [[NP-Полная задача|<math>\mathcal NP</math>-''полной'']].
Она остается <math>\mathcal NP</math>-''полной'' даже
Она остается <math>\mathcal NP</math>-''полной'' даже
при фиксированном <math>k=3</math>.
при фиксированном <math>k=3</math>.


==См. также==
==См. также==  
''[[Ациклическая раскраска]], [[Полная раскраска]], [[Последовательная раскраска]], [[Правильная раскраска]], [[Реберная k-раскраска|Реберная <math>k</math>-раскраска]]''.
* ''[[Ациклическая раскраска]],''
* ''[[Полная раскраска]],''
* ''[[Последовательная раскраска]],''
* ''[[Правильная раскраска]],''
* ''[[Реберная k-раскраска|Реберная <math>\,k</math>-раскраска]].''
==Литература==
==Литература==
[Лекции]
 
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Навигация