Алгоритм раскраски графа, Хроматическое число и раскраска Опции

[npl]

Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.

[Michael_Rybak]

Ориентировочные размеры графа?

[npl]

Граф произвольный.

[Michael_Rybak]

Ну если произвольный - то без шансов. Общего полиномиального решения нет, насколько я знаю. Пробуй жадные подходы какие-нибудь, с итерационным приближением к оптимальному решению. Например, так.

[npl]

А нет на Паскале?

Добавлено через 5 мин.
Хотя бы для графа с несколькими вершинами.

[Michael_Rybak]

Для графа с несколькими вершинами - полным перебором.

Кода у меня нет.

[npl]

Дайте кто-нибудь ссылку, пожалуйста!

[Michael_Rybak]

Может и сдать за тебя?

[npl]

Сдавать не надо, дайте ссылку с описанием метода решения.

[Michael_Rybak]

Пытаешься раскрасить в один цвет; если не получилось - в два; если не получилось - в три, и т.д.

Чтобы раскрасить в k цветов, используешь такую схему. Фиксируешь порядок обхода вершин. Идешь в первую вершину, даешь ей цвет 1. Идешь во вторую, и даешь ей такой наименьший цвет, который не вызовет конфликтов. Идешь в третью, и т.д. Если на очередном ходу цвет выбрать не получается, откатываешь к предыдущей вершине, и выбираешь для нее следующий цвет, который не вызовет конфликтов. Если и для нее возможные цвета кончились - откатываешь дальше, и т.д.

Если всем вершинам назначены цвета - задача решена.

Рекурсивная процедура будет выглядеть примерно так:

procedure visit(i: integer);
begin
  if i = n + 1 then
    // решение найдено! выводим
  else begin
    for c := 1 to k // k - количество цветов
      if (ни одна из вершин, смежных с i, не покрашена в цвет с) then
        color[i] := c;
        visit(i + 1);
      end;
  end;
end;

[npl]

Я так понял, что граф представляется в виде матрицы.

Добавлено через 3 мин.
И там где решение найдено, нужно вывести матрицу?

[Michael_Rybak]

да.

[united pharmacy lasix no precrcr]

Mail Order Macrobid Visa Accepted Free Shipping

[Edwardgramn]

Перед реализацией, все автомобили проходят предпродажную подготовку - полировку, химчистку, мойку, компьютерную и техническую диагностику.
Мы сотрудничаем со многими ведущими банками России, поэтому вы сможете выбрать подходящие условия по кредитованию для себя.

[finasteride 5mg without a prescr]

Cialis Compresse Prezzo