URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Родионов В.В. Методы четырехцветной раскраски вершин плоских графов
Id: 28906
 
111 руб.

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

URSS. 2005. 48 с. Мягкая обложка. ISBN 5-484-00127-7.

 Аннотация

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

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

Книга будет полезна научным работникам, студентам и аспирантам естественных вузов, знакомым с понятиями теории графов и занимающимся проблемами дискретной математики.


 Содержание

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

 Возникновение и постановка задачи

Посвящается памяти Виктора Павловича Черенина

По-видимому, впервые проблема четырех красок была поставлена немецким математиком А.Мебиусом (A.Mobius); имеются сведения об устном сообщении на лекциях в 1840 г. [2, 3]. Первоначально проблема формулировалась в терминах раскраски географической карты так, чтобы две любые страны, имеющие общую границу, не были окрашены двумя одинаковыми цветами.

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

В 1852 г. Френсис Гутри (Francis Guthrie), студент Де Моргана (De Morgan), профессора Университетского колледжа Лондона, раскрашивая карту графств Великобритании, заметил, что четырех красок достаточно для раскрашивания карты, какой бы сложной она не была. 23 октября того же года брат Гутри, Фредерик, задал такой вопрос Де Моргану, который сразу же заинтересовался им и сообщил о нем своим друзьям математику сэру У.Гамильтону (W.R.Hamilton) и философу У.Вевеллу (W.Whewell). В письме Гамильтону Морган изложил проблему, привел пример карты, требующей для раскраски четыре цвета, и поставил вопрос о том, можно ли предъявить карту, требующую для раскраски пять или более цветов.

В анонимной рецензии, написанной на самом деле Морганом, на книгу Вевелла "Философия открытия" содержится следующее любопытное замечание: "Стало быть, составителям карт с давних пор известно, что четырех разных цветов достаточно..., чтобы отметить (на карте) все необходимые различия".

Таким образом, впервые была опубликована постановка проблемы.

Действительно, например, в книге кандидата исторических наук Л.С.Чекина [9] упоминаются цветные карты: Туринская карта XII в. до н.э., карта Черного моря III в. н.э., карта Семена Ремизова 1700 г., в которой разными цветами раскрашены ареалы сибирских племен и народов, и другие. Но в те времена цвета не использовались для разграничения политических образований, и только с XVI в. цвета стали использовать по-современному, для обозначения территорий. Видимо, в то время картографов не интересовал вопрос о минимальном числе цветов для раскраски карт.

Проблему можно сформулировать в терминах графов, если заменить географическую карту графом, расположенным на плоскости (или, что равносильно, на сфере), и тогда вопрос заключается в такой раскраске граней графа наименьшим числом цветов, при которой любые две грани (страны), имеющие общее ребро, не раскрашиваются одинаково. Если построить двойственный граф, вершины которого соответствуют граням данного графа, а ребра соединяют вершины, соответствующие граням, имеющим общее ребро, то задача сводится к раскраске вершин плоского графа так, чтобы любая пара его смежных вершин раскрашивалась разными цветами, и в этом случае раскраска вершин графа называется правильной. Обозначим этот граф буквой G. Наименьшее число цветов, которыми можно раскрасить вершины графа называют хроматическим числом графа и обозначают через x(G). Ясно, что для непустого графа x(G) > 1. Доказано также, что для плоского графа 1 < chi(G) < 5. До настоящего времени высказывается гипотеза, что для любого плоского графа max x(G) = 4. Это справедливо и для планарного графа, поскольку планарный граф по определению изоморфен некоторому плоскому графу.


 Опечатки

Страница 12, строка снизу 12:

Напечатано: С -- постоянная порядка 106

Следует читать: С -- постоянная порядка 106

Страница 15, абзац 1, строка 4:

Напечатано: вершины

Следует читать: вершине

Страница 29, строка сверху 12:

Напечатано: Если начать раскраску графа другой вершины

Следует читать: Если начать раскраску графа с другой вершины

Страница 31, строка снизу 10:

Напечатано: Чаще всего это пара смежных вершин

Следует читать: Чаще всего это пары смежных вершин

Страница 38, абзац 1, строка 3:

Напечатано: раскраски плоского

Следует читать: раскраски вершин плоского

Страница 42, абзац 2, строка 3:

Напечатано: (10, 3)

Следует читать: (11, 2)

 
© URSS 2016.

Информация о Продавце