Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.12.2007, 21:09
гость

 
Сообщений: n/a

Алгоритм раскраски графа
Помогите с алгоритмом. Для произвольного графа найти хроматическое число и раскраску.
  #2  
Старый 08.12.2007, 23:26
гость

 
Сообщений: n/a

Перебор с отсечениями.
  #3  
Старый 09.12.2007, 00:07
гость

 
Сообщений: n/a

А можно привести конкретный пример?
  #4  
Старый 09.12.2007, 00:45
гость

 
Сообщений: n/a

Для начала выдели связные компоненты графы и раскрашивай каждый из них по отдельности. Число цветов, наверное разумнее будет находить двоичным поиском - в худшем случае он лишь ненамного замедлит программу, но зато свободы в придумывании эвристик будет гораздо больше.

На каждом шаге двоичного поиска перед тобой будет стоять задача - можно ли раскрасить данный связный граф K цветами. Решай перебором - выбери нераскрашенную вершину, перебери цвет для нее, отличный от цветов смежных с ней уже-раскрашенных вершин, рекурсивно попытайся раскрасить оставшиеся вершины, если не получилось - откат, пробуй другой цвет. Выбирать вершину можно по разному, например можно взять ту, с которой связано наибольшее число нераскрашенных вершин. Или ту, для которой число цветов в которую ее можно раскрасить на данном шаге наименьшее. Если это число = 0 (т.е. ее соседи уже покрашены во все K цветов), можно прекратить перебор на этом шаге. Придумывай эвристики для своих конкретных графов чтобы сократить перебор, т.к. в общем случае задача NP-сложная и требует экспоненциального времени.
  #5  
Старый 09.12.2007, 12:24
гость

 
Сообщений: n/a

Кто-нибудь может дать ссылку на реализацию этого алгоритма на языке программирования, лучше на Паскале.
  #6  
Старый 07.10.2008, 02:33
гость

 
Сообщений: n/a

У меня такое же задание по курсачу. Я прочитал возможный алгоритм и пытаюсь его применять: Сначала нахожу максимальные внутренне устойчивые множества методом магу, потом специальным образом нахожу минимальное число таких множеств что бы всовокупности они содержали все элементы(вершины) графа.Но необычайно сложная проблема возникает с применением метода Магу так как там нужно перемножить (с использовыанием дерева) выражения: (ф+ы)(ы+ш)(ы+к)...где в скобках стоят переменные.Так что удачи!
  #7  
Старый 25.12.2010, 04:12
гость131

 
Сообщений: n/a

Зачем так усложнять методом Магу......
три цыкла и норм...)
курсак на 20 минут программинга).. Это если конкретный метод не был..указан
  #8  
Старый 29.12.2010, 13:01
гость_29_12_10

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Придумывай эвристики для своих конкретных графов чтобы сократить перебор.
У меня алгоритм - разбиение сначала на 2 множества, потом на 3 и т.д. может посоветуете эвристики
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
связность графа гость Графы 4 24.02.2008 20:35
минимальные циклы графа Alx Графы 2 03.12.2007 15:08
диаметр графа незарегистрированный Графы 3 06.06.2007 21:33
генерация планарного графа. Omnislash Графы 6 12.03.2007 00:14
связывание графа RiV Математические алгоритмы 1 29.01.2007 10:33