Алгоритм раскраски графа, Хроматическое число и раскраска |
Алгоритм раскраски графа, Хроматическое число и раскраска |
npl |
9.12.2007 12:49
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.
|
Michael_Rybak |
9.12.2007 15:37
Сообщение
#2
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ориентировочные размеры графа?
|
npl |
9.12.2007 16:27
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
Граф произвольный.
|
Michael_Rybak |
9.12.2007 16:34
Сообщение
#4
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ну если произвольный - то без шансов. Общего полиномиального решения нет, насколько я знаю. Пробуй жадные подходы какие-нибудь, с итерационным приближением к оптимальному решению. Например, так.
|
npl |
9.12.2007 17:14
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
А нет на Паскале?
Добавлено через 5 мин. Хотя бы для графа с несколькими вершинами. |
Michael_Rybak |
9.12.2007 17:37
Сообщение
#6
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Для графа с несколькими вершинами - полным перебором.
Кода у меня нет. |
npl |
9.12.2007 17:39
Сообщение
#7
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
Дайте кто-нибудь ссылку, пожалуйста!
|
Michael_Rybak |
9.12.2007 17:51
Сообщение
#8
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Может и сдать за тебя?
|
npl |
9.12.2007 18:42
Сообщение
#9
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
Сдавать не надо, дайте ссылку с описанием метода решения.
|
Michael_Rybak |
9.12.2007 19:16
Сообщение
#10
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Пытаешься раскрасить в один цвет; если не получилось - в два; если не получилось - в три, и т.д.
Чтобы раскрасить в k цветов, используешь такую схему. Фиксируешь порядок обхода вершин. Идешь в первую вершину, даешь ей цвет 1. Идешь во вторую, и даешь ей такой наименьший цвет, который не вызовет конфликтов. Идешь в третью, и т.д. Если на очередном ходу цвет выбрать не получается, откатываешь к предыдущей вершине, и выбираешь для нее следующий цвет, который не вызовет конфликтов. Если и для нее возможные цвета кончились - откатываешь дальше, и т.д. Если всем вершинам назначены цвета - задача решена. Рекурсивная процедура будет выглядеть примерно так: procedure visit(i: integer); |
npl |
9.12.2007 19:31
Сообщение
#11
|
Новичок Группа: Пользователи Сообщений: 21 Пол: Мужской Реальное имя: http://npfiles.ru Репутация: -1 |
Я так понял, что граф представляется в виде матрицы.
Добавлено через 3 мин. И там где решение найдено, нужно вывести матрицу? |
Michael_Rybak |
9.12.2007 20:36
Сообщение
#12
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
да.
|
Текстовая версия | 21.09.2024 18:27 |