Техника - молодёжи 1967-02, страница 46

НАК

РАСНРАСИТЬ

НАРТУ

В. СИМОН, инженер-архитектор

г. Сердловск

Сложно ли раскрасить контурную географическую карту? Казалось бы, нет ничего проще. Расирасим скачала какую-нибудь одну страну, затем другую, третью... Таким обрезом, чтобы два пограничных государства имели разные цвета. Ну, а теперь немного усложним вопрос. Можно ли по иоитуриой карте узнать, каково минимальное число красон, нужных для ее правильной раскраски? На первый взгляд подобный вопрос может заинтересовать лишь немногих специалистов-нвртографев. Но это ив тан. Ввдь любая часть плоскости (или поверхности), разбитая иа конечное число облествй, по сути дела, своеобразная карта. Шахматная доска, декоративное панно, рисунок париетного пола, листьев растений, растрескавшейся штунатурки, различных тканей и многое другое — все это марты (рис. 1). Сколько же нужно выбрать цветов для их раскраски?

Так праздный вопрос превращается * трудную математическую задачу.

ПРОБЛЕМА «ЧЕТЫРЕХ КРАСОК»

Каждая область карты окружена другими областями, своими ближайшими соседками. Будем называть их все вместе ячейкой кврты.

Центральная область ячейки — зто ядро, а окружающие его области — кольцо ячейнк. Это кольцо может состоять из четного или нечетного числа областей.

Очевидно, для раскраски любого замкнутого кольца с четным числом областей нужны две краски, а с нечетным числом областей — три краски (рис. 2). Отсюда вытекает такой вывод: любую ячейку любой нарты можно правильно раскрасить не более чем четырьмя различными красками (для кольца и ядра).

А как же карты в целом? Достаточно для них четырех нрасок? Может быть, для «связывания» ячеек е нарту потребуются еще дополнительные краски7

Рассмотрим наиболее сложный вариант, когда а карте есть ячейки с нечетными иольцами. Итак, расирасим одну из ячеек нарты. Примем за ядро второй ячейки любую иэ уже окрашенных ирайиих областей и раскрасим ее кольцо. За ядро следующей ячейки опять возьмем одну из окрашенных крайних областей к расирасим кольцо этой новой ячейки и т. д. Будем повторять этот прием до тех пор, пока не закончим раскраску всей карты. Следовательно, любую карту, нарисованную на плоскости, сколько бы е ией ни было областей к как бы зтк облвстк ии были расположены, всегда можно правильно раскрасить не более чвм четырьмя различными красиами (рис. 3).

Этот вывод ие нов. Еще давно на опыте люди заметили особенность раскраски нарт. Впервые же аопрос о «четырех красиах» был поставлен е 1840 году немецким математиком А. Мебиусом. Но ни Мебиус, ии другие ученые не могли найти решения этой проблемы. Так что вопрос о «четырех красках» остается открытым до сих пор.

НЕТ ИЛИ НЕЧЕТ?

Рассматривая различные карты, можно заметить, что некоторые иэ них можно правильно раскрасить тремя и даже

Йеумя красками. Чем же это вызвано? ля нарты важна ие только четность областей в иольце каждой ячейки, но и четность вершин или, другими словами, четность числа границ, сходящихся на каждой вершине. Так, например, ячейку, поназанную на рисунне 4, можно раснраенть тремя нраенвми, хотя е ев ноль-це нечетное число областей. Вкиою тому — четная вершиив «в», в которой сходятся четыре грвницы. Исходя на этого, разобьем все возможные нарты «по вершинам» на три группы — с четными вершинами, с нечетными вершинами, а также комбинированные нарты, в которых встречаются оба типа вершин.

КАРТЫ С ЧЕТНЫМИ ВЕРШИНАМИ

Классичесннй предстевитель нарт этой группы — шахматная доска, правда, ираиние ее вершины нечетные, но. поскольку они не влияют иа расираску, мы их не учитываем. Все прекрасно знают, иан раскрашена такая карта и сколько различных красой для нее требуется. Но если взять более сложную и запутанную карту с четными вершинами — например, карисоеаниую иа рисунне В, — то сразу определить число краем для ее правильной окрасни, пожалуй, будет трудновато.

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

При раеирасне нарты е четными вершинами нужно учитывать одно правило. Если, непрнмер, рвсирасить каную-либо одну as область, то тем самым автоматически распределяются цвета и для всех остальных областей. Поэтому расираску карты нужно делать с одного места, поетепекно, область эа областью. Если начать с двух мест, — скажем, с противоположных нраее, — то может случиться, что раскрашенные части ие «стыкуются» беэ дополнительных красон.

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

КАРТЫ С НЕЧЕТНЫМИ ВЕРШИНАМИ

Вторая группа «арт по сравнению с предыдущей более многообразна. Сюда относятся почти все географические карты, различные «парнетажи» (рисунки паркетных полов), некоторые геометрические орнаменты н другое, '

Особое место е этой группе занимают карты, состоящие нз областей с шестью вершинами и со сходящимися в этих вершинах тремя границами, С ними мы часто встречаемся в кашей практической деятельности. Их можно найти и в природе, Рисуннн пчелиных сотов, кирпичной нладки с расшитыми шаами, нвното-рых видов плиточных полов, литых чугунных решеток откосятся к этим кар-тем (рис. 6). Стрсптся они просто, Рисунок их экономичен и спокоен, «благороден» и монументален. Для раекрвеии кх достаточно трех различных нрвеон.

Наряду с этими «благородными» картами во второй группе немало «каверзных» карт. Построить некоторые из них — задача нелегкая. Например, попытаемся составить карту из областей с тремя вершинами, в каждой из которых сходятся три границы. Поначалу дело пойдет быстро, но ногдв в пешей карте окажется уже три области, возникает первое затруднение- иак присоединить четвертую область? (рис, 7-а). Единственный выход — это нольцеоб-

Вазиая область (рис. 7-б). А мак дальше? я тую область вообще нельзя присоединить н нарте! Но, отзывается, все же можно продолжить наше построение. Составим рядом новую карту иэ тех же областей, и ее четаертой, нольцвобраэной областью охватим заодно и первую марту В рееультате м получим единую нарту с восемью областями (рис. 7-в). Такую уловку можно применить сколько угодно раз, и в нашей нертв будет любое иратиов четырем число областей. Для раскраски ее потребуется максимальное число — четыре различные краски.

Карту е нечетными вершинами нельзя вычертить одним духом, не «трыеая иа рандашв от бумаги и не проходя две аэа по одной и той же линии. А как же комбинированные карты? В их состав входят элементы предыдущих групп, поэтому свойства таких карт на разных участках рвэлнчны. На рисунне 8 показана одна иэ многочисленных комбинированных карт. Для ее расирасни потребуется либо три. либо четыре различные краенк.

И так, для любой нарты нужно всего четыре краски. А если определить, и какой группе относктсл карта, то, возможно, хватит и трех, а то и двух нрасок.

СОДЕРЖАНИЕ

Г. ПОКРОВСКИЙ, проф. —Взрыв —

созидатель озер и морей 2

B. ЛУКАЧЕР — Робот-скандалист 3 Ю. ФИЛАТОВ — Словоохотливый

робот.........3

А. КРУЗЕ, В. КРАКОВСКИИ. инженеры — Мир без ножниц 5 Летопись великого пятидесятилетня .........7

Б. ЩЕРБАКОВ — Старая Москва 7 М. ВОВНЕВА, нанд. фнлос. наук —

Человек еще удивит мир . 6 Ю. ШИЛЕИКИС — В поисках антимира ........10

1817-1867 ...... 12.28,31

Литературная страничка .... 13 Время искать и удивляться 13

Короткие корреспонденции ... 14 Готовность — наивысшая

1 Так ковалось оружие победы 16

2 Ракетно-ядерное, реактивное 18

3 Иа истории оружия русского 22 Л. ИТЕЛЬСОН, доктор пед. наук —

Дискуссия о мышлении . . 24

C. ГАНСОВСКИИ — Летящие сквозь мгновенье ..... 20

Антология таинственных случаев

Загадка Семлевекого оаера 29 Вокруг земного шара .... 32

A. СтАХОВ, инж. — Катастрофа века ....... .34

Ю БЛИНОВ, канд. техн. неук.

B. СЛАДКОВ, инж — Гравитация

строит ледяные .замки ... 36 Шоферские байки 36

А. ДОБРОТВОРСКИИ. инж. — Доклад МО— «Безрасходная» турбина? — это возможно . 37

КлуО «ТМ»........36

Б. СИМОН, ииж.-арх. — Как раскрасить карту.....40

ОБЛОЖКА художников: 1-я стр. —

A. Победикекого, 2 я стр. — И. Покровского, 3-я и 4 я стр. — Н. Беч-нанова.

ВКЛАДКИ художников- 1-я стр. — Р. Авотинв, 2 л стр, — Л. Рындича, 3-я стр. — И. Рушвва, 4-я стр. —

B. Иванова. Макет Н. Перовой.

ГЛАВНЫЙ РЕДАКТОР В. Д. ЗАХАРЧЕНКО

Редколлегия: М. Г. АНАНЬЕВ, К. А. БОРИН. В. В. ГОЛУБОВСКИИ, К. А. ГЛАДКОВ (научный редактор). В. В. ГЛУХОВ, П. И. ЗАХАРЧЕНКО. О- С ЛУПАНДИН. И. Л МИТРАКОВ. А П. МИЦКЕВИЧ. Г. И. НЕКЛЮДОБ. В. И. ОРЛОВ, В. Д. ПЕКБЛИС,

А. Н. ПОБЕДИНСКИИ. Г. И. ПОКРОВСКИИ. Г С ТИТОВ. И. Г ШАРОВ. И. М. ЭМАНУЭЛЬ Адрес редакции: Москва. А 30 Сущевская, 21 Тел Д 1-15-00. доб. 4-66: Д 1-86-41' Д 1-08-01 Рукописи не ПО.'ШПЯНЩЮТС! Художественный редактор Н. Вечнаное. Технический редактор J1- БуДОва

Издательство ЦК БЛКСМ «Молодая гвардил Т01147 Подп. к печ. 16/1 1967 г. Бумага 61Х90'/е. Печ. л. 5,5(5.5). Уч.-изд. л. 9,3. Тираж 1 150 000 экз. Заказ 25В6. Цена 20 коп С набора типографии «Красное зиамя» отпечатано в Первой Образцовой типографии имени А. А. Жданова Главполитафпрома Комитета по печати при Совете Министров СССР. Москва. Ж-54, Валовая. 26. Заказ 1067. Бкладки отпечатаны на Чеховском полиграфкомбннате Главполиграфпромб Комитета по печати при Совете Министров СССР, г. Чехов Московской об^рсти.

wvvw.ianko.front.ru