IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Алгоритм раскраски графа, Хроматическое число и раскраска
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 21
Пол: Мужской
Реальное имя: http://npfiles.ru

Репутация: -  -1  +


Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ориентировочные размеры графа?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 21
Пол: Мужской
Реальное имя: http://npfiles.ru

Репутация: -  -1  +


Граф произвольный.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


Новичок
*

Группа: Пользователи
Сообщений: 21
Пол: Мужской
Реальное имя: http://npfiles.ru

Репутация: -  -1  +


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

Добавлено через 5 мин.
Хотя бы для графа с несколькими вершинами.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Кода у меня нет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 21
Пол: Мужской
Реальное имя: http://npfiles.ru

Репутация: -  -1  +


Дайте кто-нибудь ссылку, пожалуйста!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Может и сдать за тебя?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 21
Пол: Мужской
Реальное имя: http://npfiles.ru

Репутация: -  -1  +


Сдавать не надо, дайте ссылку с описанием метода решения.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Чтобы раскрасить в 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;
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 21
Пол: Мужской
Реальное имя: http://npfiles.ru

Репутация: -  -1  +


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

Добавлено через 3 мин.
И там где решение найдено, нужно вывести матрицу?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


да.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.09.2020 16:37
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name