# разбиение вершин

разбиение вершин графа на независимые множества. Если рассматривать только максимальные независимые множества, то раскраска - это не что иное, как покрытие вершин графа G множествами этого типа. В том случае, когда вершина принадлежит не одному максимальному независимому множеству, допустимы различные раскраски с одним и тем же количеством цветов. Эту вершину можно окрашивать в цвета тех множеств, которым она принадлежит. Исходным положением метода является получение всех максимальных независимых множеств и хранение их в некоторой матрице M (N*W), где W - количество максимальных независимых множеств. Элемент матрицы M[i,j] равен единице, если вершина с номером i принадлежит множеству с номером j, и нулю в противном случае. Если затем каждому столбцу поставить в соответствие единичную стоимость, то задача раскраски не что иное, как поиск минимального количества столбцов в матрице M, покрывающих все ее строки. Каждый столбец соответствует определенному цвету. 1 2 3 4 5 1 1 1 0 0 0 2 1 0 0 1 0 3 0 0 1 0 0 4 0 0 1 1 1 5 0 1 0 0 1 A * * * B * * * Пример.

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа