Алгоритмы раскраски графа

• Номер работы:
  374344
• Раздел:
  Все работы   →   Рефераты и реферативные задания   →   Математика (ВСЕ направления)
• Год подготовки:
  16.11.2015
• Объем работы:
  14 стр.
• Выдержка из работы:
  Введение
  
  Так называемая задача «раскраски графа» взяла свое начало от известной задачи о раскраске географической карты. Суть ее состоит в том, чтобы определить, как нужно раскрасить карту, изображающую на плоской или сферической поверхности различные страны и границы между ними, если известно, что соседние страны нельзя закрашивать одним цветом.
  Эту задачу математики пытались решить в течение почти 100 лет. Они пытались доказать результат, известный под названием задачи (или гипотезы) о четырех красках (гипотеза — теорема, являющаяся предположительно верной, практически подтверждаемая большим числом случаев, но не имеющая полного формального доказательства): “для раскраски карты на плоской или сферической поверхности достаточно четырех цветов”.
  В 1976 г. эта теорема была доказана с помощью использования ЭВМ которая чисто комбинаторным способом проверила огромное число вариантов рисунков [Appel и Haken, 1976].
  .........
  Понятие алгоритма раскраски графа
  
  Алгоритм раскраски графа позволяет находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.
  Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на r подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.
  ......