Занятие «Раскраски графов» факультативного курса «Элементы теории графов и ее приложения»
Граф G называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов красок так, что не найдется двух смежных вершин одного цвета. Наименьшее число г, такое, что граф. G является r-хроматическим, называется хроматическим числом графа X G. Полный «-вершинный граф G имеет хроматическое число, равное п, а всякое дерево имеет хроматическое число, равное двум. Соответствующая хроматическому числу раскраска вершин разбивает множество вершин графа на г подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.
С помощью алгоритма Магу—Вейсмана выполнить правильную раскраску вершин графа с минимальным количеством цветов. Составляем произведение Где — элемент матрицы инциденций графа G; , раскроем скобки и проведем преобразования по правилам алгебры логики типа: Скелет графа 2. Для каждого слагаемого преобразованного выражения запишем его дополнение до полной системы образующих Получили полный обзор всех максимальных пустых подграфов графа G. Упорядочим полученные множества вершин в порядке убывания их кардинальных чисел: 2. Припишем вершинам множества цвет «1». Удалим раскрашенные вершины из всех множеств и оставшиеся множества упорядочим в порядке убывания их мощности: 4.
- Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами».
- Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны. Понятие «граф» связано с понятием «графический», «графика».
- При решении практических задач с применением графов возникает необходимость в разбиении множества вершин графа на классы попарно несмежных между вершин. Довольно часто дополнительно требуется, чтобы таких классов было наименьшее число.
Алгоритм раскраски графа позволяет находить точное или приближенное значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин. Граф G называют r-хроматическим, если его вершины могут быть раскрашены с использованием r цветов красок так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, такое, что граф G является r-хроматическим, называется хроматическим числом графа G.
