ВОЛШЕБНЫЙ ДВУРОГ
Шрифт:
Теперь разорвем наш мост посредине. Подумай над таким вопросом: давай заполним разрыв моста какой-нибудь фигурой, то есть вставим в уникурсальную фигуру с двумя нечетными узлами еще одну связную фигуру, и разберемся, какую фигуру и как можно вставить.
– 62 -
Только с четными узлами или с двумя нечетными (стр. 65)? Это особенная геометрия. Она называется геометрия положения или топология. Вот тебе, кстати, прекрасная фигурка. Попробуй нарисовать ее одним росчерком. Ее придумал когда-то геометр Листинг.
–
– Далеко не одна.
– А почему этот ваш командор еще и Кандидат Тупиковых Наук? Что это за науки?
– Ну, в лабиринте ты видел немало тупиков. Это они самые.
– А почему он Магистр Деревьев?
– Если из твоего первого чертежа с двумя ромбами я уберу мост, система путей потеряет связность, будет опять два отдельных ромба - и все. Линию, которая соединяет два узла, мы называем путем, а если путь имеет то свойство, что при удалении его система теряет связность и распадается, то мы такой путь и называем мостом. Может существовать система, состоящая только из тупиков и мостов.
Фигура Листинга.
– 63 -
Такая система называется деревом. В ней ни одного пути, который можно было бы удалить без того, чтобы система не распалась. Ну, а теперь давай подумаем, нет ли чего-нибудь общего между двумя такими задачами: нарисовать уникурсальную фигуру одним росчерком и обойти лабиринт, у которого только один вход. Ты, я думаю, понимаешь, что любой лабиринт можно считать лабиринтом с одним входом, потому что всякий лабиринт мы всегда можем "обнести" еще одним "забором".
– Уж не знаю, - вымолвил не сразу Илюша.
– Правда, быть может, если начертить план лабиринта не так, как мы его чертили до сих пор, а изображать линиями не стенки, а самые пути, как раз и получится такая фигура, которую нужно обойти или начертить...
– Постой, постой минуточку!
– прервал Радикс его рассуждения.
– А как ты полагаешь, нужно ли в таком случае вычерчивать точный план путей?
– Я должен быть точен в том смысле, чтобы на плане было то число перекрестков, какое есть на самом деле, и то же самое относительно путей между ними. А как именно я нарисую самые пути - это неважно, лишь бы не спутаться, куда какой из них ведет.
– Правильно, - резюмировал его собеседник.
– Следовательно, вообще можно сказать, что ты интересуешься топологической схемой путей. Если ты представишь себе, что линии путей изображены нитками, которые связаны в узлах-перекрестках, то можешь как угодно деформировать, или видоизменять, "сетку путей" - топологическая схема останется неизменной.
– 64 -
Ты только не должен рвать нитки, развязывать узлы или завязывать новые. Ну, а как же все-таки начертить такую фигуру?
В фигуру вставлен еще один ромб.
А теперь ромб вставлен по-другому.
– А вот тут, - признался Илюша, - я затрудняюсь: ведь в лабиринте может быть сколько хочешь всяких тройных и вообще нечетных перекрестков, то есть узлов... Как же с этим быть?
– Вот то-то и дело!
– отвечал Радикс.
– Это
– Ну конечно!
– радостно воскликнул Илюша.
– Это как с моим тупиком, то есть я должен пройти именно по два раза по каждому коридору. Значит, и на чертеже лучше всего изобразить каждый коридор двумя линиями. А после этого все нечетные узлы станут четными, потому что они удвоятся: тройной, например, станет шестерным и так далее. И весь план лабиринта превратится в фигуру, у которой есть только одни четные узлы. А такую фигуру, как мы уже доказали, можно нарисовать одним росчерком.
Стало быть, всякий лабиринт можно обойти, проходя два раза по каждому из его коридоров. Вот это действительно замечательное доказательство!
– Нет сомнений, что это действительно доказательство, по только это еще не решение задачи лабиринта. И вот почему. Когда ты чертишь фигуру, тебе необходимо видеть ее всю, а иначе нельзя установить, правильно ли ты идешь и сохраняешь ли все время ее связность.
– 65 -
В лабиринте совсем иное дело: там плана нет и ты не знаешь, каков он в целом, а значит, надо придумать такое правило для его обхода, которое дало бы возможность обойти любой лабиринт, не зная заранее, каковы его нескончаемые коридоры.
– Да, это правда, - согласился Илюша.
– Только как?
– Ты что-то толковал насчет правила правой руки?
– услышал он в ответ.
– А теперь что ты о нем скажешь?
– Когда мне пришло в голову это правило, я думал о тупике, у которого имеются разветвления, а они, в свою очередь, тоже тупики. Если лабиринт построен по этому правилу, то я, конечно, обойдя два раза каждый коридор, обойду весь лабиринт, если нет петель. А если есть петли, то все, что приходится внутри петли, я могу пропустить.
– А что такое "петля", как ее можно обнаружить на схеме путей лабиринта, о которой мы только что говорили?
– Это на схеме будет замкнутый путь, кольцо, то есть круговой маршрут внутри лабиринта. Если я попал на такой маршрут, то могу вернуться к тому месту, где вступил на него с другой уже стороны, причем я приду туда по еще нехоженому пути. В тупиковом лабиринте таких замкнутых маршрутов нет.
– Правильно. Мы можем даже это свойство - отсутствие петель - принять за определение того, что такое тупиковый лабиринт. Теперь от простого случая попробуем перейти к более сложному. Скажи-ка, нельзя ли превратить какой-нибудь лабиринт с петлями в тупиковый и как это сделать?
– Если бы я был строителем этого лабиринта, то отметил бы все петли и перегородил их, чтобы нельзя было больше пройти по ним кругом.
– Превосходно. Ну вот и расскажи мне подробно, как бы ты на месте строителя лабиринта все это сделал.
– Раньше всего, конечно, я бы достал план лабиринта и на нем начертил бы дорогу, начиная от входа и все дальше в глубь лабиринта. Каждый раз у кольцевого маршрута отмечал бы, что здесь ставлю перегородку... Ну, где бы ее поставить? Поставим в том конце кольцевого коридора, где он выводит опять к моим старым следам. Если так сделать, каждая петля станет тупиком, стало быть, я пройду ее всю, дойду до перегородки, поверну обратно, выйду из этого нового тупика и пойду дальше по основной дороге. Да буду посматривать, не набреду ли еще на петлю, которую надо перегородить. Когда я пройду таким образом на плане весь лабиринт...