НГУ
http://forum.nsu.ru/

О раскраске вершин графа
http://forum.nsu.ru/viewtopic.php?f=24&t=13848
Страница 1 из 1

Автор:  freeneutron [ Сб авг 26, 2006 1:59 pm ]
Заголовок сообщения:  О раскраске вершин графа

Существует ли алгоритм вычисления хроматического числа графа?

Автор:  freeneutron [ Вс авг 27, 2006 9:29 pm ]
Заголовок сообщения: 

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

Автор:  Алексей Тамаревский [ Пн сен 04, 2006 12:55 am ]
Заголовок сообщения: 

Я пользовался таким. Берем перебираем количество цветов (от одного и до количества вершин графа). На выбранном количестве, пытаемся закрасить (перебор с отсечениями) граф в такое количество цветов.

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

Автор:  andrewM [ Пт сен 08, 2006 2:38 am ]
Заголовок сообщения: 

freeneutron
Можете глянуть в книге Н.Кристофидеса "Теория графов. Алгоритмический подход". Раскраски там довольно подробно описаны. (книга в Инете есть :))

Автор:  OrionII [ Чт фев 15, 2007 12:29 am ]
Заголовок сообщения: 

Эффективного алгоритма нет - это переборная задача.

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/