Алгоритм окраски графика
От Wiki http://en.wikipedia.org/wiki/Graph_coloring
В его самой простой форме это - способ окрасить вершины графика таким образом, что никакие две смежных вершины не совместно используют тот же цвет; это называют окраской вершины. Точно так же край, окрашивающий, присваивает цвет каждому краю так, чтобы никакие два смежных края не совместно использовали тот же цвет, и поверхность, окрашивающая плоского графика, присваивает цвет каждой поверхности или региону так, чтобы никакие две поверхности, которые совместно используют границу, не имели тот же цвет.
Данный 'n' окрашивает и 'm' вершины, как легко алгоритм окраски графика может быть реализован на языке программирования?
Язык никакой барьер.
Просто мозговой тизер.
(Примите График, и объекты вершины существуют),
Править:
После чтения Wiki проблема полна NP
Время для пересматривания книг математики :)
мое плохое.
прошу прощения.
Просто любопытный,
Это попробовали? как в записи программ для того же?
Я слышал, что это используется в оптических сетях?
Разве это не подобно кубу, окрашивающему??
(минимальное количество цветов для окраски поверхностей куба так, чтобы никакие две стороны не совместно использовали тот же цвет?)
3 ответа
Если вам даны 2 цвета, а график двухцветный (т.е. это двудольный граф ), тогда вы можете сделать это за полиномиальное время довольно тривиально.
Я дал псевдокод в качестве ответа на этот вопрос: Алгоритм раскраски графа: типичная задача планирования .
Как уже упоминалось, общая проблема np-полная. Двудольные графы можно раскрасить всего в 2 цвета.
Также верно, что планарные графы (графы, которые не содержат K3,3 или K5 в качестве подграфов, согласно теореме Куратовского) можно раскрасить в 4 цвета.
Это полная проблема NP, прочтите статью в Википедии для получения дополнительной информации о различных методах решения.