В алгоритме рассматриваются
В алгоритме рассматриваются только вершины смежные с вершиной, окрашенной в максимальный цвет. Однако следует работать и с вершинами являющимися смежными для смежных. На рисунке приведены примеры графов и их раскраски. Первая цифра в круглых скобках обозначает значение цвета при правильной раскраске, вторая - при минимальной.
Для графов на первом и третьем рисунках алгоритм дает правильный результат. Для графа на втором рисунке необходимо просматривать вершины, не смежные для вершины с номером 6, а для этого необходимо модифицировать алгоритм. Самый интересный случай на последнем рисунке. Мы не можем получить минимальную раскраску с помощью рассмотренного алгоритма, хотя она, конечно, существует и совпадает с предыдущей.
3.8.3. Использование задачи о наименьшем покрытии
при раскраске вершин графа
При любой правильной раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, является независимым множеством. Поэтому раскраску можно понимать как
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
