Волшебный двурог

— Да очень просто: взять ее за конец и вытащить.

— Но ведь у тебя у выхода оба конца, то есть и начало и конец. Нельзя ли за оба конца взяться сразу?

— Из тупика можно, конечно, вытащить за оба конца…

Ах да, она и тут ведь лежит как в тупике! Ну разумеется, можно за оба конца тянуть.

— То-то и есть! А если бы ты бродил по лабиринту как попало, то за оба конца мог бы и не вытащить. Положим теперь, что ты уже дошел до центра лабиринта и надо идти назад. Не помогла бы тебе еще раз нить, то есть не смогла ли бы она указать, как сократить обратный путь?

— Если бы я, находясь в центре, натянул нить, прикрепленную у выхода, до отказа, наматывая ее на моток, то вытянул бы ее из всех лишних петель и тупиков и нашел бы самый короткий путь из центра к выходу.

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

— Тогда ничего другого не остается, как отмечать каким-нибудь способом на перекрестках те коридоры, по которым я прошел. Я бы ставил черточку на стенке того коридора, по которому пришел на перекресток, и на стенке того, по которому

— 69 —

Топологическая схема его путей.

Уникурсальная фигура обхода.

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

— Допустим, что ты ставишь эти черточки. Ну, а как же ими надо пользоваться?

— Основное правило такое: каждый раз, когда я прихожу на перекресток, где уже был, я должен возвращаться обратно,

—70—

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

Этот коридор меня и поведет по правильному пути.

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

Схема обхода лабиринта УУУ.

Придя в В по пути № 3, я вижу по отметкам, что уже был на перекрестке В, и поэтому возвращаюсь по тому же коридору путем № 4, чем погашается весь участок ВС по пути № 3-4. Так как в С я вижу теперь свободные коридоры, то выбираю один из них (№ 5), избегая пока коридора СВ, по которому я пришел в С первый раз. Из D я выбираю произвольный путь, например № 6, и, наткнувшись в С на свои отметки, возвращаюсь тем же коридором (путь № 7) в D, откуда одним из свободных коридоров (№ 8) попадаю в Е. Избрав путь № 9, я обязан вернуться тем же коридором (путь № 10) и теперь неизбежно попадаю в центр лабиринта (путь № 11 и 12), откуда возвращаюсь ко входу по единственной оставшейся дороге (№ 13, 14, 15, 16).

— 71 —

Схема превращения лабиринта УУУ в дерево.

ли случиться так, что тебе и обратно идти некуда будет и нехоженых коридоров больше нет, а отмеченных по одному разу — несколько, и ты не знаешь, какой выбрать?

— Нет, так случиться не может: ведь я пройти сквозь перекресток, придя по свободному коридору, не могу — в этом-то и заключается суть главного правила. Если я стою и размышляю, куда дальше идти, это значит, что я вернулся по тому самому коридору, который выбрал для того, чтобы уйти с перекрестка: теперь он отмечен уже двумя черточками. Значит, надо найти коридор с одной черточкой. Это будет первый коридор, по которому я пришел, и эта одна черточка указывает обратный путь. Если я очень устану прежде, чем обойду весь лабиринт, то могу по этому признаку в любой момент выбрать правильный путь для возвращения к выходу. С нитью это совсем просто: если натянуть ее, она пройдет через каждый перекресток, который мне необходимо пройти при возвращении по своим следам; один конец будет тянуться ко мне, а другой — к выходу.

— А теперь, — сказал Радикс, — рассмотрим еще раз наш способ двойного обхода в несколько иной форме. Ты помнишь, что мы с тобой говорили о дереве, когда толковали об уникурсальных кривых?

— Помню. Дерево — это такая связная фигура, которая состоит только из мостов и тупиков.

— Верно. Ну, а чем же отличается схема путей лабиринта от дерева?

— В лабиринте могут найтись петли, то есть замкнутые пути, а в дереве, как и в настоящем, ветки обратно в ствол его не врастают.

А если мы этот чертеж развернем:

— Вот именно! Но представь себе, что тебе пришлось повстречаться как раз с таким деревом-уродом, у которого некоторые ветки вросли обратно своими концами в ствол и

— 72 —

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

— Взял бы пилу или топор, залез на это дерево и стал отделять приросшие концы веток друг от друга и от ствола.

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

Начерти-ка сам схему путей этого лабиринта и схему его обхода!

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

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