Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.
Алгоритм раскраски графа, Хроматическое число и раскраска |
Алгоритм раскраски графа, Хроматическое число и раскраска |
npl |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.
|
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ну если произвольный - то без шансов. Общего полиномиального решения нет, насколько я знаю. Пробуй жадные подходы какие-нибудь, с итерационным приближением к оптимальному решению. Например, так.
|
Текстовая версия | 4.05.2024 17:37 |