разбиение вершин
разбиение вершин графа на независимые множества. Если рассматривать только максимальные независимые множества, то раскраска - это не что иное, как покрытие вершин графа 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 * * *
Пример.
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
