Раскраска вершин графа
Двудольные графы и раскраски
Жадная раскраска в теории графов — раскраска вершин неориентированного графа , созданная жадным алгоритмом , который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов. Корона полный двудольный граф K n , n с удалёнными рёбрами совершенного паросочетания является особенно плохим случаем для жадного алгоритма — если в последовательности вершин поместить подряд две вершины, принадлежащие удалённому ребру из паросочетания, жадный алгоритм использует n цветов, в то время, как оптимальным числом для такого графа является два цвета.
В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W. Adams, P. An Introduction to Groebner Basis параграф 2. Для начала обсудим все необходимые понятия.
Раскраска графа — это не более чем простой способ маркировки компонентов графа, таких как вершины, ребра и области, при некоторых ограничениях. На графике нет двух смежных вершин, смежных ребер или смежных областей, окрашенных минимальным количеством цветов. Это число называется хроматическим числом, а граф называется правильно окрашенным графом.
