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

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

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




Возникновение и постановка задачи.
По-видимому, впервые проблема четырёх красок была поставлена немецким математиком А. Мёбиусом (A. Mobius); имеются сведения об устном сообщении на лекциях в 1840г. [2, 3]. Первоначально проблема формулировалась в терминах раскраски географической карты так, чтобы две любые страны, имеющие общую границу, не были окрашены двумя одинаковыми цветами. И тем не менее, в октябре 2002 г. в Великобритании отмечалось 150-летие проблемы четырех красок и 25-летие ее решения, данного К. Аппелем (К. Appel), У. Хакеном (W. Haken) и Дж. Кохом (J. Koch). В октябре того же года эти события отмечались в течение специальной праздничной недели, а в декабре в Информационном Бюллетене Европейского Математического общества появилась статья Р. Вильсона (R. Wilson) [7], краткое содержание которой излагается ниже.

Содержание.
1.Возникновение и постановка задачи.    
2.Краткая историческая справка.    
3.Раскраска простейших графов.
4.Окрестности вершин и их раскраска.             
5.Алгоритм раскраски вершин плоского графа и встречная раскраска.    
6.Перекраска вершин правильно раскрашенного графа.    
7.Достаточность условия правильной раскраски плоских графов.    
8.Оценка числа операций для раскраски вершин плоского графа.    
9.Раскраска графа, содержащего 139 вершин.    
Литература.    

Купить .









Теги: Родионов :: книги по математике :: математика :: теория графов :: дискретная математика