Такая система называется деревом. В ней ни одного пути, который можно
— 63 —
было бы удалить без того, чтобы система не распалась. Ну, а теперь давай подумаем, нет ли чего-нибудь общего между двумя такими задачами: нарисовать уникурсальную фигуру одним росчерком и обойти лабиринт, у которого только один вход. Ты, я думаю, понимаешь, что любой лабиринт можно считать лабиринтом с одним входом, потому что всякий лабиринт мы всегда можем «обнести» еще одним «забором».
— Уж не знаю, — вымолвил не сразу Илюша. — Правда, быть может, если начертить план лабиринта не так, как мы его чертили до сих пор, а изображать линиями не стенки, а самые пути, как раз и получится такая фигура, которую нужно обойти или начертить…
— Постой, постой минуточку! — прервал Радикс его рассуждения. — А как ты полагаешь, нужно ли в таком случае вычерчивать точный план путей?
— Я должен быть точен в том смысле, чтобы на плане было то число перекрестков, какое есть на самом деле, и то же самое относительно путей между ними. А как именно я нарисую самые пути — это неважно, лишь бы не спутаться, куда какой из них ведет.
— Правильно, — резюмировал его собеседник. — Следовательно, вообще можно сказать, что ты интересуешься топологической схемой путей. Если ты представишь себе, что линии путей изображены нитками, которые связаны в узлах-перекрестках, то можешь как угодно деформировать, или видоизменять, «сетку путей» — топологическая схема останется не-
— 64 —
изменной. Ты только не должен рвать нитки, развязывать узлы или завязывать новые. Ну, а как же все-таки начертить такую фигуру?
В фигуру вставлен еще один ромб.
А теперь ромб вставлен по-другому.
— А вот тут, — признался Илюша, — я затрудняюсь: ведь в лабиринте может быть сколько хочешь всяких тройных и вообще нечетных перекрестков, то есть узлов… Как же с этим быть?
— Вот то-то и дело! — отвечал Радикс. — Это значит, что далеко не все лабиринты можно обойти, если ты решишь идти по каждому коридору только один раз. Но ведь это совсем не обязательно…
— Ну конечно! — радостно воскликнул Илюша. — Это как с моим тупиком, то есть я должен пройти именно по два раза по каждому коридору. Значит, и на чертеже лучше всего изобразить каждый коридор двумя линиями. А после этого все нечетные узлы станут четными, потому что они удвоятся: тройной, например, станет шестерным и так далее. И весь план лабиринта превратится в фигуру, у которой есть только одни четные узлы. А такую фигуру, как мы уже доказали, можно нарисовать одним росчерком.
Стало быть, всякий лабиринт можно обойти, проходя два раза по каждому из его коридоров. Вот это действительно замечательное доказательство!
— Нет сомнений, что это действительно доказательство, по только это еще не решение задачи лабиринта. И вот почему. Когда ты чертишь фигуру, тебе необходимо видеть ее всю, а иначе нельзя установить, правильно ли ты идешь и сохраняешь ли все время ее связ-
— 65 —
ность. В лабиринте совсем иное дело: там плана нет и ты не знаешь, каков он в целом, а значит, надо придумать такое правило для его обхода, которое дало бы возможность обойти любой лабиринт, не зная заранее, каковы его нескончаемые коридоры.
— Да, это правда, — согласился Илюша. — Только как?
— Ты что-то толковал насчет правила правой руки? — услышал он в ответ. — А теперь что ты о нем скажешь?
— Когда мне пришло в голову это правило, я думал о тупике, у которого имеются разветвления, а они, в свою очередь, тоже тупики. Если лабиринт построен по этому правилу, то я, конечно, обойдя два раза каждый коридор, обойду весь лабиринт, если нет петель. А если есть петли, то все, что приходится внутри петли, я могу пропустить.
— А что такое «петля», как ее можно обнаружить на схеме путей лабиринта, о которой мы только что говорили?
— Это на схеме будет замкнутый путь, кольцо, то есть круговой маршрут внутри лабиринта. Если я попал на такой маршрут, то могу вернуться к тому месту, где вступил на него с другой уже стороны, причем я приду туда по еще нехоженому пути. В тупиковом лабиринте таких замкнутых маршрутов нет.
— Правильно. Мы можем даже это свойство — отсутствие петель — принять за определение того, что такое тупиковый лабиринт. Теперь от простого случая попробуем перейти к более сложному. Скажи-ка, нельзя ли превратить какой-нибудь лабиринт с петлями в тупиковый и как это сделать?
— Если бы я был строителем этого лабиринта, то отметил бы все петли и перегородил их, чтобы нельзя было больше пройти по ним кругом.