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

Теорема (о пяти красках)
Каждый планарный граф можно так раскрасить, используя пять цветов, что любые две смежные вершины будут окрашены в разные цвета.


Теорема (о четырех красках)
Каждый планарный граф можно так раскрасить, используя четыре цвета, что любые две смежные вершины будут окрашены в разные цвета.
Отметим самую известную интерпретацию проблемы о четырех красках. Пусть имеется географическая карта. Можно ли, используя только 4 краски, изобразить эту карту так, чтобы соседние страны (имеющие общую границу) были окрашены в разный цвет? Понятно, что в соответствующем графе вершинами являются страны, а смежными вершинами являются соседние страны. Ясно, что полученный граф является планарным, и после 1976 г. ответ на этот вопрос является положительным.
Раскраска ребер
Заметим, что в теории графов ставится часто вопрос о реберной раскраске графов, когда цвета назначаются ребрам. Какое минимальное число цветов (это число иногда называют реберно-хроматическим) нужно, чтобы раскрасить ребра графа так, что любые 2 смежных ребра (т.е. 2 ребра, имеющих общую вершину) были бы окрашены в разный цвет? Для реберно-хроматического числа графа справедлива гораздо более точная оценка, чем для просто хроматического числа, а именно, верна следующая, в какой-то степени удивительная, теорема.
Теорема Визинга. Если в графе максимальная степень вершин равна , то реберно-хроматическое число равно либо r, либо r +1.
Заметим, что до сих пор нет «хороших» критериев для графов, когда же именно реберно-хроматическое число равно r, а когда r + 1.
Раскраска ребер (или реберная раскраска) называется правильной, если любые два ребра, имеющие общую вершину, окрашены в разные цвета. Минимальное число цветов, необходимое для правильной раскраски ребер графа , называется хроматическим индексом графа и обозначается через .
Очевидно, что простейший алгоритм нахождения реберно-хроматического числа (и соответствующей раскраски ребер) состоит в следующем: по данному графу строим так называемый двойственный граф: ребра графа соответствуют вершинам нового (двойственного) графа, причем, если 2 ребра имеют общую вершину, то они являются смежными и в двойственном графе соединены ребром. После этого раскрашиваем наилучшим образом вершины двойственного графа и, переходя к «старому» графу, получаем (одну из возможных) наилучших реберных раскрасок графов.
В заключение отметим, что реберная раскраска часто применяется при конструировании различных устройств, где провода, соединяющиеся в одной вершине, должны (для удобства) иметь разные цвета.