Хромати́ческое число́ гра́фа — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается .
Определение править
Хроматическое число графа — минимальное число , такое что множество вершин графа можно разбить на непересекающихся классов :
таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.
Связанные определения править
- K-раскрашиваемый граф — граф, хроматическое число которого не превосходит . То есть его вершины можно раскрасить не более чем цветами так, что у любого ребра концы будут разного цвета.
- K-хроматический граф — граф, хроматическое число которого равно . То есть вершины графа можно раскрасить цветами так, что у любого ребра концы будут разного цвета, но так раскрасить цветами — уже нельзя.
Рёберная раскраска править
Хроматический класс графа — минимальное число цветов, в которые можно раскрасить ребра графа так, чтобы смежные ребра имели разные цвета. Обозначается . Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырёх красок. Реберная раскраска определяет 1-факторизацию графа.
Хроматический многочлен править
Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов , то оказывается, что эта функция всегда будет полиномом от . Этот факт был обнаружен Биркгофом и Льюисом[1] при попытке доказать проблему четырёх красок.
Хроматические многочлены некоторых графов править
Треугольник | |
Полный граф | |
Дерево с вершинами | |
Цикл | |
Граф Петерсена |
Нахождение хроматического многочлена произвольного графа править
Для графа-вершины хроматический многочлен равен
Хроматический многочлен графа равен произведению хроматических многочленов его компонент
Также существует рекуррентное соотношение — теорема Зыкова[2], так называемая формула удаления и стягивания
где и — смежные вершины, — граф, получающийся из графа путём удаления ребра а — граф, получающийся из графа путём стягивания ребра в точку.
Можно использовать эквивалентную формулу
где и — несмежные вершины, а — граф, получающийся из графа путём добавления ребра
Свойства хроматического многочлена править
Для всех целых положительных
Хроматическое число — наименьшее целое положительное , для которого
Степень хроматического многочлена равна количеству вершин:
Обобщения править
Также хроматическое число можно рассматривать для других объектов, например, для метрических пространств. Так, хроматическим числом плоскости называется минимальное число цветов , для которого существует такая раскраска всех точек плоскости в один из цветов, что никакие две точки одного цвета не находятся на расстоянии ровно 1 друг от друга. Аналогично для любой размерности пространства. Элементарно доказывается, что для плоскости , однако продвинуться дальше долгое время не удавалось. 8 апреля 2018 года, британский математик Обри ди Грей доказал, что [3][4]. Эта задача называется задачей Нелсона — Эрдёша — Хадвигера.
Значение для теории графов править
Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.
См. также править
Примечания править
- ↑ Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.
- ↑ Этот домен припаркован компанией Timeweb . Дата обращения: 4 июня 2017. Архивировано 28 мая 2017 года.
- ↑ de Grey, Aubrey D.N.J (2018-04-08), The chromatic number of the plane is at least 5, arXiv:1804.02385
- ↑ Владимир Королёв. Математикам не хватило четырех цветов для раскраски плоскости . nplus1.ru. Дата обращения: 11 апреля 2018. Архивировано 10 апреля 2018 года.
Литература править
- О. Оре. Теория графов. — М.: Наука, 1986.