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

В. В. Родионов МЕТОДЫ ЧЕТЫРЕХЦВЕТНОЙ РАСКРАСКИ ВЕРШИН ПЛОСКИХ ГРАФОВ МОСКВА URSS  ББК 22. 174 22. 18 Родионов Владимир Васильевич Методы четырехцветной раскраски вершин плоских графов. — М. : КомКнига, 2005. - 48 с. ISBN 5-484-00127-7 В настоящей книге рассматриваются проблема четырех красок и вопросы ее возникновения, постановки и решения. Вначале дается историческая справка, содержащая различные, в том числе противоположные суждения по данным вопросам. Излагается предпринятая автором попытка решения задачи о раскраске вершин произвольного графа. В основе такого решения лежит утверждение, что окрестность вершины графа раскрашивается не более чем четырьмя красками. Это утверждение используется, например, при встречной раскраске, когда часто возникает ситуация, при которой две смежные вершины должны раскрашиваться одной краской. Показано, как можно преодолеть такую ситуацию, и, таким образом, свести, например, задачу раскраски географической карты к раскраске вершин двойственного графа. Доказано необходимое и достаточное условие раскраски двойственного графа не более чем четырьмя красками. Приводится линейная относительно числа вершин графа оценка числа операций для правильной раскраски вершин произвольного плоского графа. Книга будет полезна научным работникам, студентам и аспирантам есте- ственных вузов, знакомым с понятиями теории графов и занимающимся пробле- мами дискретной математики. Текст опубликован в авторской редакции. Издательство «КомКнига». 117312, г. Москва, пр-т 60-летия Октября. 9. Подписано к печати 17. 06. 2005 г. Формат 60x90/16. Печ. л. 3. Зак. № 105. Отпечатано в ООО «ЛЕНАНД». 117312, г. Москва, пр-т 60-летия Октября, д. 11А, стр. 11. ISBN 5-484-00127-7 © КомКнига, 2005 3365 ID 28906  Посвящается памяти Виктора Павловича Черенина 1. Возникновение и постановка задачи По-видимому, впервые проблема четырёх красок была по- ставлена немецким математиком А. Мёбиусом (A. Mobius); име- ются сведения об устном сообщении на лекциях в 1840г. [2, 3]. Первоначально проблема формулировалась в терминах раскраски географической карты так, чтобы две любые страны, имеющие общую границу, не были окрашены двумя одинаковыми цветами. И тем не менее, в октябре 2002 г. в Великобритании отмеча- лось 150-летие проблемы четырех красок и 25-летие ее решения, данного К. Аппелем (К. Appel), У. Хакеном (W. Haken) и Дж. Ко- хом (J. Koch). В октябре того же года эти события отмечались в течение специальной праздничной недели, а в декабре в Инфор- мационном Бюллетене Европейского Математического общества появилась статья Р. Вильсона (R. Wilson) [7], краткое содержание которой излагается ниже. В 1852 г. Френсис Гутри (Francis Guthrie), студент Де Мор- гана (De Morgan), профессора Университетского колледжа Лон- дона, раскрашивая карту графств Великобритании, заметил, что четырех красок достаточно для раскрашивания карты, какой бы сложной она не была. 23 октября того же года брат Гутри, Фреде- рик, задал такой вопрос Де Моргану, который сразу же заинтере- совался им и сообщил о нем своим друзьям математику сэру У.