Gr - результирующий
Gr - результирующий массив}
var Ws:Ss;
j:byte;
begin
Ws:=[ ];
for j:=1 to i-1 do {формируем множество цветов, в которые окрашены смежные вершины с меньшими номерами}
if A[j,i]=1 then Ws:=Ws+[Gr[j]];
j:=t;
repeat {поиск минимального номера цвета, в который можно окрасить данную вершину}
Inc(j);
until Not(j in Ws);
Color:=j;
end;
Пример. Получаем правильную раскраску: Gr[1]=1, Gr[2]=Gr[4]=2, Gr[3]=3, Gr[5]=4. Однако минимальной раскраской является: Gr[1]=1, Gr[2]=Gr[5]=2, и Gr[3]=Gr[4]=3, и хроматическое число графа равно трем.
3.8.2. Поиск минимальной раскраски вершин графа
Метод основан на простой идее[7], и в некоторых случаях он дает точный результат. Пусть получена правильная раскраска графа, q - количество цветов в этой раскраске. Если существует раскраска, использующая только q-1 цветов, то все вершины, окрашенные в цвет q, должны быть окрашены в цвет g, меньший q. Согласно логике формирования правильной раскраски вершина
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
