Теория графов., Раскраска карты минимальным кол_вом цветов Опции

[-StrangerFX-]

Программа раскрашивания карты минимальным количеством цветов.

Исходные данные:

- Список регионов с указанием соседей каждого региона.

Выходные данные:

- Список регионов с приписанными им цветами.
- Общее число использованных цветов.

Требованния к фунуциональности:

- Эфективность решения.
- Наглядный вывод результата(раскраска карты).
- Опционально редактор карт(с возможностью рисовать мышью).

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

[Lapp]

Гость, ты много всего перечислил, и не совсем понятно, насколько тебя волнует основной алгоритм - процесс раскрашивания. Если волнует, то могу помочь с этим. Задача очень любопытная, меня заинтересовало уже то, что проблема четырех красок как раз не так давно была решена теоретически (с помощью компьютера, это как бы наглядный пример, как комп помогает в чистой математике), и захотелось самому прикоснуться..

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

const
  Nx=100;                           {максимальное число областей}

var
  N,                                {реальное число областей}
  i,j:integer;
  Col:array[1..Nx]of byte;          {массив цветов}
  Nn:array[1..Nx]of byte;           {сколько соседей у каждой области}
  Nei:array[1..Nx,1..Nx]of byte;    {массив соседей}
  Trace:array[1..Nx]of boolean;     {для отметки пройденных областей}
  Empty:set of byte;                {для очистки списка цветов}
  f:text;

const
  MaxCol:byte=0;

function Paint(m:byte):byte;
var
  i:integer;
  Used:set of byte;
begin
  Used:=Empty;                       {очищаем список использованных цветов}
  if Col[m]=0 then begin             {если область еще не покрашена..}
    Trace[m]:=false;                 {отмечаем пройденные области}
    for i:=1 to Nn[m] do if Trace[Nei[m,i]] then Include(Used,Paint(Nei[m,i]));   {опрашиваем цвета соседей}
    i:=1;
    while i in Used do Inc(i);       {выбираем первый цвет из свободных}
    if i>MaxCol then MaxCol:=i;      {запоминаем максимальный цвет (несущественно)}
    Col[m]:=i;                       {заполняем массив цветов областей}
    Paint:=i;
    Trace[m]:=true                   {необязательно}
  end
  else Paint:=Col[m]                 {если область уже покращена, просто возвращаем ее цвет}
end;

begin
  for i:=0 to 255 do Exclude(Empty,i);
  for i:=1 to Nx do begin
    Col[i]:=0;
    Trace[i]:=true
  end;
                                     {формат данных:}
                                     {число строк равно чилу областей}
                                     {первое число в строке - количество соседей области}
                                     {затем перечисляются соседи}
                                     {пустых строк не должно быть ни внутри, ни в конце}
  Assign(f,'reg_nei.dat');
  Reset(f);
  N:=0;
  while not EoF(f) do begin
    Inc(N);
    Read(f,Nn[N]);
    for i:=1 to Nn[N] do Read(f,Nei[N,i]);
    ReadLn(f)
  end;
  Close(f);

  Paint(1);                           {красим область 1}
  WriteLn('MaxCol = ',MaxCol);
  for i:=1 to N do Write('  ',Col[i]);
  WriteLn;
  ReadLn;
end.

А вот пример файла с областями, reg_nei.dat

Код

5 2 3 4 5 6
3 1 3 6
3 1 2 4
3 1 3 5
3 1 4 6
3 1 5 2

Это расположение представляет собой пятилепестковую ромашку . На нем (и на более простых) я проверял прогу. Вроде, не врет..