НГУ

Форумы НГУ
Текущее время: Чт ноя 21, 2019 10:54 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: О раскраске вершин графа
СообщениеДобавлено: Сб авг 26, 2006 1:59 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср авг 23, 2006 11:32 am
Сообщения: 3
Существует ли алгоритм вычисления хроматического числа графа?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс авг 27, 2006 9:29 pm 
Не в сети
Редкий гость

Зарегистрирован: Ср авг 23, 2006 11:32 am
Сообщения: 3
Я нашел информацию о хроматическом полиноме. Его коэффициенты являются функциями на множестве графов, а количество его нулей равно хроматическому числу. Если кто занет другой способ, напишите, пожалуйста.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 04, 2006 12:55 am 
Не в сети
Редкий гость

Зарегистрирован: Ср июн 21, 2006 12:49 am
Сообщения: 14
Я пользовался таким. Берем перебираем количество цветов (от одного и до количества вершин графа). На выбранном количестве, пытаемся закрасить (перебор с отсечениями) граф в такое количество цветов.

Получилось -- останавливаемся.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 08, 2006 2:38 am 
Не в сети
Редкий гость

Зарегистрирован: Вт июн 27, 2006 6:10 pm
Сообщения: 3
freeneutron
Можете глянуть в книге Н.Кристофидеса "Теория графов. Алгоритмический подход". Раскраски там довольно подробно описаны. (книга в Инете есть :))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 15, 2007 12:29 am 
Не в сети
Частый гость

Зарегистрирован: Сб июн 10, 2006 12:05 am
Сообщения: 83
Откуда: Евгений
Эффективного алгоритма нет - это переборная задача.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB