Задачи на раскраску графа
Занятие «Раскраски графов» факультативного курса «Элементы теории графов и ее приложения»
В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W. Adams, P. An Introduction to Groebner Basis параграф 2. Для начала обсудим все необходимые понятия. Пусть — это некоторое множество, а — множество, состоящее из неупорядоченных пар элементов множества.
На этом шаге мы рассмотрим алгоритмы закраски графа. Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными. С одной стороны, не известны алгоритмы их решения, сложность которых есть некоторая фиксированная степень от длины записи условий задачи так называемые полиномиальные алгоритмы. С другой стороны, нигде явно не выражены те потери, которые мы несем от отсутствия таких алгоритмов [1, с. Разумеется, есть лишь конечное число ситуаций, которые надо рассмотреть, чтобы найти хроматическое число n -вершинного графа.
- Считается, что вершины, принадлежащие одному и тому же подмножеству V i , выкрашены при этом в один и тот же цвет i.
- Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами».
- Алгоритм раскраски графа позволяет находить точное или приближенное значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин. Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов красок так, что не найдется двух смежных вершин одного цвета.
Математическая модель — граф очень компактная и удобная в использовании при решении множества практических задач. От конфигурации сетей и распределения потоков информации, поиска кратчайших путей между двумя точками плоскости или пространства до составления планов и расписаний. Родоначальником теории графов считается Леонард Эйлер.
