 Алгоритм раскраски графа, Хроматическое число и раскраска |
| npl |
 9.12.2007 12:49
Сообщение
#1
|
|
Новичок  Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация:  -1   |
Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.
|
   |
 
|
  |
Ответов
| Michael_Rybak |
9.12.2007 16:34
Сообщение
#2
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ну если произвольный - то без шансов. Общего полиномиального решения нет, насколько я знаю. Пробуй жадные подходы какие-нибудь, с итерационным приближением к оптимальному решению. Например, так.
|
|
|
|
Сообщений в этой теме
npl Алгоритм раскраски графа 9.12.2007 12:49
Michael_Rybak Ориентировочные размеры графа? 9.12.2007 15:37 npl Граф произвольный. 9.12.2007 16:27 npl А нет на Паскале?
Добавлено через 5 мин.
Хотя б... 9.12.2007 17:14 Michael_Rybak Для графа с несколькими вершинами - полным перебор... 9.12.2007 17:37 npl Дайте кто-нибудь ссылку, пожалуйста! 9.12.2007 17:39 Michael_Rybak Может и сдать за тебя? 9.12.2007 17:51 npl Сдавать не надо, дайте ссылку с описанием метода р... 9.12.2007 18:42 Michael_Rybak Пытаешься раскрасить в один цвет; если не получило... 9.12.2007 19:16 npl Я так понял, что граф представляется в виде матриц... 9.12.2007 19:31
Michael_Rybak да. 9.12.2007 20:36 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 27.07.2025 14:43 |