Раскраска: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Раскраска''' (''Colouring'') - для некоторого графа <math>G</math> и натурального числа <...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Раскраска''' (''Colouring'') - | '''Раскраска''' (''[[Colouring]]'') - | ||
для некоторого графа <math>G</math> и натурального числа <math>k</math> функция | для некоторого [[граф|графа]] <math>G</math> и натурального числа <math>k</math> функция | ||
вида <math>f: \, V(G) \rightarrow \{1,2,...,k\}</math>, отображающая | вида <math>f: \, V(G) \rightarrow \{1,2,...,k\}</math>, отображающая | ||
множество вершин в множество цветов. Иногда, чтобы | множество [[вершина|вершин]] в множество цветов. Иногда, чтобы | ||
подчеркнуть мощность множества цветов, говорят о ''вершинной | подчеркнуть мощность множества цветов, говорят о ''вершинной | ||
<math>k</math>-раскраске'' или просто о ''<math>k</math>-раскраске''. Интерес | <math>k</math>-раскраске'' или просто о ''<math>k</math>-раскраске''. Интерес | ||
представляют только те раскраски, при которых смежные | представляют только те раскраски, при которых [[смежные вершины]] окрашиваются в различные цвета. Такие раскраски | ||
вершины окрашиваются в различные цвета. Такие раскраски | |||
называются правильными. Поскольку функция <math>f</math> не обязательно | называются правильными. Поскольку функция <math>f</math> не обязательно | ||
сюръективна, при <math>k</math>-раскраске фактически может быть | сюръективна, при <math>k</math>-раскраске фактически может быть | ||
| Строка 14: | Строка 13: | ||
каждый из которых является независимым множеством. | каждый из которых является независимым множеством. | ||
Задача выяснения, является ли данный неориентированный граф | Задача выяснения, является ли данный [[неориентированный граф]] | ||
<math>k</math>-раскрашиваемым, является <math>\ | <math>k</math>-раскрашиваемым, является [[NP-Полная задача|<math>\mathcal NP</math>-''полной'']]. | ||
Она остается <math>\ | Она остается <math>\mathcal NP</math>-''полной'' даже | ||
при фиксированном <math>k=3</math>. | при фиксированном <math>k=3</math>. | ||
См. также ''Ациклическая раскраска, Полная раскраска, Последовательная раскраска, Правильная раскраска, Реберная <math>k</math>-раскраска''. | ==См. также== | ||
''[[Ациклическая раскраска]], [[Полная раскраска]], [[Последовательная раскраска]], [[Правильная раскраска]], [[Реберная k-раскраска|Реберная <math>k</math>-раскраска]]''. | |||
==Литература== | ==Литература== | ||
[Лекции] | [Лекции] | ||
Версия от 15:16, 15 января 2010
Раскраска (Colouring) - для некоторого графа [math]\displaystyle{ G }[/math] и натурального числа [math]\displaystyle{ k }[/math] функция вида [math]\displaystyle{ f: \, V(G) \rightarrow \{1,2,...,k\} }[/math], отображающая множество вершин в множество цветов. Иногда, чтобы подчеркнуть мощность множества цветов, говорят о вершинной [math]\displaystyle{ k }[/math]-раскраске или просто о [math]\displaystyle{ k }[/math]-раскраске. Интерес представляют только те раскраски, при которых смежные вершины окрашиваются в различные цвета. Такие раскраски называются правильными. Поскольку функция [math]\displaystyle{ f }[/math] не обязательно сюръективна, при [math]\displaystyle{ k }[/math]-раскраске фактически может быть использовано менее [math]\displaystyle{ k }[/math] цветов. Таким образом, правильную [math]\displaystyle{ k }[/math]-раскраску графа [math]\displaystyle{ G }[/math] можно рассматривать как разбиение множества вершин на не более чем [math]\displaystyle{ k }[/math] непустых классов, каждый из которых является независимым множеством.
Задача выяснения, является ли данный неориентированный граф [math]\displaystyle{ k }[/math]-раскрашиваемым, является [math]\displaystyle{ \mathcal NP }[/math]-полной. Она остается [math]\displaystyle{ \mathcal NP }[/math]-полной даже при фиксированном [math]\displaystyle{ k=3 }[/math].
См. также
Ациклическая раскраска, Полная раскраска, Последовательная раскраска, Правильная раскраска, Реберная [math]\displaystyle{ k }[/math]-раскраска.
Литература
[Лекции]