Ориентированные и неориентированные графы план Введение Основные определения

Теорема. Если максимальная степень вершин в графе равна , то хроматическое число этого графа не превосходит + 1. При этом хроматическое число графа равно + 1 только в двух случаях: во-первых, если граф является полным и, во-вторых, если = 2 и при этом данный граф содержит контур нечетной длины (такой граф изображен на рис. 5, максимальная степень его вершин – 2, а хроматическое число – 3). Во всех остальных случаях хроматическое число графа не превосходит максимальной степени вершин.



Рис. 4 Рис. 5


Примечание. Оценка хроматического числа, даваемого этой теоремой, является достаточно грубой. Особенно наглядно это выглядит на примере дерева, для которого степень вершин может быть как угодно велика, а хроматическое число равно 2.
Рассматриваемые вопросы связаны с известной проблемой четырех красок. Для того чтобы ее сформулировать, нам понадобятся еще несколько определений.
Граф называется плоским, если он нарисован на плоскости, причем любые 2 ребра могут пересекаться только в вершине.
Графы называются изоморфными, если существует такая нумерация вершин в этих графах, что они имеют одну и ту же матрицу смежности (фактически изоморфные графы – это одинаковые графы, которые отличаются только другим изображением).
Граф называется планарным, если он изоморфен плоскому графу. Таким образом, планарный граф можно изобразить на плоскости как плоский. На рис. 6 изображены 2 изоморфных (одинаковых) графа, причем первый из них планарный, а второй является плоским.



Рис. 6

Можно доказать (это не совсем простая теорема), что хроматическое число планарных графов меньше или равно 5. Однако Августом де Морганом (1850) была выдвинута гипотеза о том, что хроматическое число планарных графов меньше или равно 4. Этой проблеме было посвящено огромное число математических работ. В конце концов, удалось свести эту проблему к исследованию верности этой гипотезы для достаточно большого числа типов графов ( 30 тыс.), что и было сделано с помощью компьютеров (1976). Гипотеза о четырех красках оказалась справедливой, а сама проблема перешла в задачу об упрощении доказательства гипотезы о четырех красках.