Раскраска графа — это не более чем простой способ маркировки компонентов графа, таких как вершины, ребра и области, при некоторых ограничениях. На графике нет двух смежных вершин, смежных ребер или смежных областей, окрашенных минимальным количеством цветов. Это число называется хроматическим числом, а граф называется правильно окрашенным графом.
Двудольные графы и раскраски
Двудольные графы, критерий двудольности. Вершинные и реберные раскраски графа. Простейшие свойства раскрасок. Теорема Брукса. Совершенные графы.
Алгоритм раскраски графа позволяет находить точное или приближенное значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин. Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов красок так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G. Задача нахождения хроматического числа графа называется задачей о раскраске или задачей раскраски графа.
Категория: Математика. Похожие презентации:. Раскраска графов. Тема 3. Основные понятия. Хроматическое число 2.