Посвящается памяти
Виктора Павловича Черенина
По-видимому, впервые проблема четырех красок была поставлена немецким математиком А.Мебиусом (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) |
2023. 720 с. Твердый переплет. 16.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |