English Version Русская версия
ОПИСАНИЕ

Турсунбай кызы Ырысгуль
Институт Систем Информатики им. А.П.Ершова СО РАН, , ryskul@gorodok.net

О раскраске графов

Задача раскраски вершин графа является одной из самых основных и наиболее изученных задач в теории графов. Изучение задачи о 4-х красках для плоских графов порождал интерес ещё более 150 лет тому назад. Характерной особенностью этих задач является существование объектов, которые по каким-либо причинам не могут быть объединены в одну группу. К задачам раскраски сводятся многие вопросы, возникающие при планировании производства, составлении расписаний, хранении и перевозке товаров, автоматизации проектирования и динамическом распределении памяти ЭВМ и т.д. имеющие широкое теоретическое и прикладное значение. Поскольку задача определения хроматического числа принадлежит классу полиномиально полных задач, исследования в этой области ведутся в разных направлениях.
ame_В данной работе исследованы теоретические вопросы, возникающие в указанном направлении изучения задачи раскраски. Рассматриваются также задачи, связанные с некоторыми известными обобщениями задачи раскраски.
Раскраской графа G называется такое приписывание цветов его вершинам V(G), что никакие две смежные ве?шины не получают одинакового цвета. Хроматическое число c (G) графа G определяется как наименьшее количество цветов, необходимых для раскраски G, а раскраска G c (G) цветами называется оптимальной раскраской графа G. Задача раскраски графа заключается в нахождении оптимальной раскраски.
ame_Результаты обзора литературы, посвященной алгоритмам раскраски графов, могут быть резюмированы следующим образом:
1. Все известные точные алгоритмы раскраски характеризуются чрезвычайно быстрым ростом времени реализации и объема запоминаемой информации при увеличении размерности решаемых задач, что позволяет использовать эти алгоритмы лишь для раскраски графов с числом вершин в пределах сотни.
2. Ни один из имеющихся приближенных алгоритмов раскраски не гарантируе близости найденного решения к оптимальному. Это объясняется принципиальными причинами: даже задача раскраски вершин графа в число красок, гарантировано меньшее удвоенного хроматического числа, является NP – трудной.
Принципиальные трудности, которые возникают при раскраске графа и нахождении его хроматического числа выну?дают, во-первых, найти и исследовать практически интересные классы графов, для которых задача раскраски полиномиально разрешима, и, во-вторых, вычислить или оценить хроматическое число графа с помощью других, более легко вычисляемых характеристик графа.
Наиболее интересным и практически важным классом, для которого задача раскраски полиномиально разрешима, является класс совершенных графов. С другой стороны, этот класс содержит множество практически интересных подклассов, для которых найдены эффективные алгоритмы раскраски.

информационные
спонсоры:
 
cпонсоры:

О CISCO