Задачи раскраски графа

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

Двудольные графы и раскраски

В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W. Adams, P. An Introduction to Groebner Basis параграф 2.

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

На этом шаге мы рассмотрим алгоритмы закраски графа. Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными. С одной стороны, не известны алгоритмы их решения, сложность которых есть некоторая фиксированная степень от длины записи условий задачи так называемые полиномиальные алгоритмы.

Похожие статьи

• Дизайн услуги разработки - Дизайн, услуги дизайна, дизайн полиграфии, дизайнерские
• Задачи связанные с углами - Задания 6. Планиметрия: задачи, связанные с углами Решения ЕГЭ-2024
• Закрытая беседка своими руками с поэтапными фотографиями
• Фото дома майкл джексон - Фотографии Майкла Джексона. Часть 1 Форум - Форум