Методы четырехцветной раскраски вершин плоских графов

Родионов В.В.5-484-00127-7

В настоящей книге рассматриваются проблема четырех красок и вопросыее возникновения, постановки и решения. Вначале дается историческая справка,содержащая различные, в том числе противоположные суждения по даннымвопросам. Излагается предпринятая автором попытка решения задачи о раскраскевершин произвольного графа. В основе такого решения лежит утверждение, чтоокрестность вершины графа раскрашивается не более чем четырьмя красками.Это утверждение используется, например, при встречной раскраске, когда частовозникает ситуация, при которой две смежные вершины должны раскрашиватьсяодной краской. Показано, как можно преодолеть такую ситуацию, и, такимобразом, свести, например, задачу раскраски географической карты к раскраскевершин двойственного графа.Доказано необходимое и достаточное условие раскраски двойственногографа не более чем четырьмя красками. Приводится линейная относительночисла вершин графа оценка числа операций для правильной раскраски вершинпроизвольного плоского графа.