Раскраска

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Задача выяснения, является ли данный неориентированный граф \,k-раскрашиваемым, является \mathcal NP-полной. Она остается \mathcal NP-полной даже при фиксированном \,k=3.

См. также

Литература

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