Раскраска графа задачи
Вы точно человек?
На этом шаге мы рассмотрим алгоритмы закраски графа. Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными. С одной стороны, не известны алгоритмы их решения, сложность которых есть некоторая фиксированная степень от длины записи условий задачи так называемые полиномиальные алгоритмы. С другой стороны, нигде явно не выражены те потери, которые мы несем от отсутствия таких алгоритмов [1, с.
Существуют многочисленные практические приложения раскраски графов. Когда приложение моделируется как проблема с раскраской вершин графа, то вершины в каждом цветовом классе обычно представляют отдельные субъекты, которые не конкурируют или не конфликтуют друг с другом. Семь основных классов приложений, решаемых с помощью раскраски вершин 1—5 и рёбер 6—7 графов, следующие [1] :. Spectrum management , англ. Термин «распределение частот» объединяет разные типы задач, которые зачастую имеют разные цели и модели [2].
При решении практических задач с применением графов возникает необходимость в разбиении множества вершин графа на классы попарно несмежных между вершин. Довольно часто дополнительно требуется, чтобы таких классов было наименьшее число. В теории графов подобные задачи формулируются в терминах раскраски вершин графа. Исторически понятие хроматического числа возникло с проблемой четырех красок. Проблема возникла в математике в середине 19 века.
