Лабиринт. Задача прохождения лабиринта.

Выстроив дом лабиринтом с глухими стенами и крышей,
Дедал – тогда замечательный гений в строительном деле –
Здание вывел, в котором особых примет не имелось,
Длинный же ряд коридоров кривых в направлениях разных
Цепью тянущийся, только лишь путал пытливые взоры.
…Дедал пути без числа в своем зданье устроил,
Так что сам затруднялся пробраться к наружному входу.
Овидий.

Содержание.
Введение
1. Семью кругами к тайне
1.2. Большой каменный дом
1.3. Непреходящий символ
1.4. Как сразиться с Минотавром
1.5. Дорога без конца
2. Геометрическая постановка задачи о лабиринтах.
3. Решение задачи.
Литература.

Введение
Лабиринт - архитектурное сооружение, сконструированное таким образом, что, однажды попав в него, невозможно или очень трудно выбраться обратно; иногда это парк или сад, созданный по тому же принципу. В древних текстах упоминается пять великих лабиринтов: Египетский, расположенный, по Плинию, под озером Моэрис, два Великих лабиринта в Кноссе и Гортане, греческий на острове Лемнос и этрусский в Клюзиуме. Лабиринт - это мир, Вселенная, непостижимость, движение. Непрерывная линия лабиринта означает вечность, бесконечную длительность, бессмертие.
Лабиринт символизирует движение Солнца, его восход и закат, весеннее освобождение.

Введение
Лабиринт как символ Пути выражает идею движения человека к истине, это то, что вынуждает человека двигаться, выводит из состояния инертности. Прохождение через лабиринт - это обновление, новое рождение.
Древние греки связывали происхождение его названия labyrinthos с Критом. Характерный для критского религиозного культа топор с двойным лезвием назывался "лабрис". Эти слова родственны и происходят от доиндоевропейского слова, означавшего "камень". Лабиринт выражает идею круговорота "жизнь-смерть-жизнь" и имеет отношение к символизму пещеры, путешествия в иной мир; к погребальным обрядам и обрядам инициации, которые часто проводились в пещерах.

Введение
Другим названием лабиринта, широко распространенным в Западной Европе, было "троя". Вергилий упоминает об обрядовых играх, называемых "Троя", обязательным элементом которых были запутанные танцевальные движения. Танцы-лабиринты, или тройские танцы и игры, символизируют трудную дорогу, испытания при движении к центру. Эта символика связана с "Танцем Журавля", описание которого есть у Плутарха.
Так, представляется вопрос: есть ли безвыходные лабиринты, или в каждом лабиринте, руководствуясь общими известными правилами, можно разобраться, свободно войти в него, посетить любую данную в нем точку и затем выйти обратно?

1. Семью кругами к тайне
Первые похожие на лабиринт наскальные рисунки появились на Земле еще в каменном веке.
Большинство древних «классических» лабиринтов создавалось по одинаковому, вполне определенному шаблону с одной-единственной очень извилистой тропой, ведущей от входа к центру. Таковы сохранившиеся до наших дней петроглифы в виде лабиринтов, обнаруженные в Галисии, на северо-западе Испании, глиняные таблички с изображением лабиринтов, найденные в греческом городе Пилосе, возраст которых
3 000 лет, рисунки лабиринтов, нацарапанные на руинах в турецком Гордионе, относящиеся к 750 году до н. э.

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

1. Семью кругами к тайне
Иначе устроены ходы головоломки, именуемые на английский манер «мейзами» (maze). Мейзы по своему строению более изощренные и запутанные фигуры, нежели лабиринты. Как правило, в таких головоломках заложены несколько дорог к цели, два или более входов и выходов, дорожки сообщаются между собой и образуют развилки. Создатели выстроили сложные задачи: выбрать правильный вход, угадать направление на развилке или не попасть дважды на одну и ту же дорожку. Идея мейзов представляет собой результат освоения математической науки.

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

1.2. Большой каменный дом
Таково буквальное значение греческого слова labyrinthos. Оно как нельзя лучше подходит Кносскому дворцу на острове Крит, слава о котором живет уже более трех тысяч лет благодаря мифу о Тесее и Минотавре. Лабиринт, построенный, афинским зодчим Дедалом по приказу царя Миноса, представлял собой подземную сеть туннелей, которые вели в обиталище чудовищного человекобыка — Минотавра.

1.2. Большой каменный дом
В 1900—1930 годах английский археолог Артур Эванс, проводя раскопки в Кносе, открыл царский дворец колоссальных размеров, основная часть которого была построена более чем за 1 500 лет до н. э. Сегодня грандиозное сооружение площадью около 16 тыс. м2, состоящее из сотен причудливо расположенных помещений, изобилующее коридорами и переходами, размещенными на разных уровнях залами и уводящими глубоко под землю лестницами, интерпретируется археологами как прототип легендарного лабиринта Минотавра.

1.2. Большой каменный дом
Кносский дворец сильно пострадал во время извержения вулкана на острове Фера около 1450 года до н. э., а после пожара, произошедшего примерно в 1380 году до н. э., был окончательно заброшен. В настоящее время некоторые из помещений реконструированы. В результате оказалось, что план дворца не соответствует классической модели с семью дорожками.

1.2. Большой каменный дом
Есть основания полагать, что в виде классического лабиринта возводили и крепостные стены городов. Так, устроение легендарной Трои, осаду которой ахейским войском принято относить к 1250—1220 годам до н. э., долгое время ассоциировалось с лабиринтом. По одной из версий, стены этого древнего города действительно напоминали лабиринт. По образу лабиринта были построены защитные стены города Шимангада, современного Непала. Этот неприступный город пал под ударами мусульманских войск в 1325 году только после того, как предатель указал неприятелю слабое место в крепостных стенах.

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

1.4. Как сразиться с Минотавром
Лабиринт в христианской философии и архитектуре становится метафорой материального мира, проходя через который человек должен сразиться с Минотавром — Сатаной. В лабиринте соблазнов и грехов человек, подобно Тесею, может уповать только на собственную стойкость и спасительную нить Ариадны — Веру. К XII веку доминирующим в христианской традиции становится лабиринт с одиннадцатью дорожками — это число для средневекового христианина символизировало понятие «грех». Великолепные лабиринты, выложенные цветными камнями, керамической плиткой, мрамором, порфиром, украшали полы храмов в Шартре, Павии, Пьяченце, Амьене, Реймсе, Сент-Омере, Риме.

1.4. Как сразиться с Минотавром
Многие из них были декорированы аллегорическими изображениями Тесея и Минотавра, сценами из Священного писания. Назначение большинства церковных лабиринтов остается неясным. Высказываются предположения, что некоторые из них могли использоваться для правильного определения дня Пасхи. Известно, что лабиринты в соборах Шартра, Реймса, Арраса и Санса стали своеобразной имитацией паломнического пути в Палестину и порой назывались «Путь в Иерусалим». В те времена для большинства верующих поход на Святую землю был невозможен, и они совершали его в символической форме — проходили весь церковный лабиринт на коленях, читая молитвы.

1.4. Как сразиться с Минотавром
Искусство создания лабиринтов начало претерпевать значительные изменения с расширением представлений человека о мире. Постепенно исчезают лабиринты, в которых все заранее предопределено и путь возможен только по одной, раз и навсегда проложенной дорожке. На смену им приходят все более сложные, с многочисленными вариантами проходов, где человек сам выбирает путь среди запутанных тропинок и тупиков. Подобные лабиринты из живой изгороди стали непременной деталью многих садов и парков Европы, превратившись в весьма популярное развлечение для аристократии.. Прогулка по лабиринту, созданному в 1669 году в версальском саду, считалась увлекательным путешествием.

Лабиринт, высаженный в 1670 году в саду виллы Альтьери в Риме, стал излюбленной забавой Папы Климента X, которому нравилось наблюдать за попытками своих слуг отыскать выход. До наших дней сохранился знаменитый лабиринт в Хемптон-Корте, устроенный в 1690 году для Вильгельма Оранского. По старинным гравюрам был восстановлен великолепный образец лабиринта в саду Тюдоров в Хэтфилд-Хауз в Хетфордшире, по-прежнему поражает извилистостью троп лабиринт из лавровых кустов в Глендерген-Хауз в Корнуолле, высаженный в 1833 году. Сегодня лабиринты, все более усложняясь, создаются на основе математических моделей и теорий.
1.4. Как сразиться с Минотавром

1.5. Дорога без конца
Главной неразгаданной загадкой древнего символа остается его происхождение. Так и не смогли объяснить возникновение, распространение по всему миру затейливого рисунка извилистой дорожки. Возможно, этот образ был подсказан самой природой — спиралевидные и лабиринтные формы характерны для раковин некоторых моллюсков, различимых в колонии кораллов, подземных ходов муравейников. Быть может, древние художники, часто рисовавшие простые спирали и извилистые линии, постепенно совершенствуя и усложняя эти геометрические фигуры, тем самым пришли к символу лабиринта.

1.5. Дорога без конца
На роль его «прародителей» претендуют и наскальные изображения концентрических колец в виде чаши или углубления, распространенные вдоль всего Атлантического побережья Европы. Ряд исследователей полагают, что эволюция именно этих форм привела к возникновению символа лабиринта. Наконец, высказываются предположения, что лабиринтный рисунок мог появиться при попытках древнего человека изобразить сложное движение солнца и планет.

1.5. Дорога без конца
История лабиринта по-прежнему не закончена. Его дороги, словно бесконечная лента времени, стремятся все дальше, уводя человека к неведомой цели, которая тем желаннее, чем менее предсказуем путь в лабиринте.

Суеверия из лабиринта
В древности изображение лабиринта считали прекрасным оберегом. Так, индейские племена тохоно и пима из американского штата Аризона и сегодня, как и тысячи лет назад, плетут корзины из сухих стеблей, корней и листьев растений, растущих в пустыне, и украшают их узором-лабиринтом с целью защитить себя от злых духов. В Пакистане и Исландии символы лабиринта вырезают на самом высоком дереве в саду, чтобы отпугивать воришек. В Шри-Ланке узор лабиринта вплетают в ткань для одеял и в основу ивовых корзин; в Скандинавии и Индии выкладывают лабиринт из камней в пустынных местах или на побережье, если хотят исполнения своего заветного желания. Считается, что лабиринт в обмен на исполненную мечту отнимает у человека семь лет жизни.

Суеверия из лабиринта
- Отправляясь в опасное место, можно попробовать нарисовать узор лабиринта на ладони. И беда обойдет вас стороной.
- В лабиринт не берут детей до семи лет и стариков, перешедших 70-летний рубеж. Лабиринт якобы может отнять души тех и других.
- Не ходят в лабиринт и беременные женщины - есть примета, что иначе ребенок может запутаться в пуповине.
- Злых духов, обитающих в лабиринте, можно обмануть, если надеть на себя чужие вещи. Так, если вы заблудились в лабиринте, поменяйтесь со своим спутником одеждой, и выход скоро найдется.
- В переходах лабиринта и на его фоне лучше не фотографироваться, могут начаться неприятности в жизни и проблемы с памятью и зрением.
- Если, стоя в центре лабиринта, загадать желание, а потом быстро найти выход, можете считать, что ваше желание быстро исполнится.
- Чтобы избежать коварства лабиринта, нужно оставить какую-нибудь вещь в дар, например, бросить монетку.

Суеверия из лабиринта
Нет на земле более загадочных построек, чем лабиринты. Они манят, запутывают, пугают и даже могут довести до отчаяния тех, кто в них оказывается. С лабиринтами связано немало мистических поверий. Взять хотя бы такое; войдя в лабиринт, человек попадает в "мир иной" и может лишиться жизни.
Ученые предполагают, что разгадка кроется в устройстве лабиринта, в его переходах и ловушках. Попадая в них, человек терял ориентацию и тут же впадал в панику! В древности лабиринты использовали, чтобы сводить с ума неугодных людей, а для пущего устрашения переходы "украшали" человеческими костями, изображениями демонов и прочей нечисти. Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута.

2. Геометрическая постановка
задачи о лабиринтах.
Аллеи, дорожки, коридоры, галереи лабиринта тянутся, изгибаясь во все стороны, перекрещиваются, расходятся во всевозможных направлениях, образуют тупики и т.д. Мы, для большей ясности, все перекрестки обозначим точками, а все аллеи, дорожки и коридоры – отрезками.
Все точки и линии образуют, таким образом, геометрическую сеть, или лабиринт. Таким образом, может быть поставлена общая задача о лабиринтах, которую требуется решить и доказать: «Безвыходных лабиринтов нет».

2. Геометрическая постановка
задачи о лабиринтах.
Эйлер установил четыре основных правила, которые применимы к сетям.
Число нечётных узлов должно быть чётным или равным нулю.
Если сеть не имеет нечётных узлов, её можно пройти по объемлющему маршруту, начав с любого узла, причём всякий такой маршрут является замкнутым.
Если сеть содержит только два нечётных узла, её можно пройти по объемлющему маршруту, который начинается в одном из этих узлов, а заканчивается в другом.
Маршрут, начинающийся в чётном узле, не может быть объемлющим.
Часто (но не всегда) лабиринт содержит один нечётный узел на входе, а другой в цели. Если все остальные узлы чётные, можно пройти по всему лабиринту от входа до цели, не заходя в один и тот же коридор два раза. Если же лабиринт содержит хотя бы ещё один нечётный узел, по крайней мере по одной ветви придётся пройти дважды.

2. Геометрическая постановка
задачи о лабиринтах.
Алгоритм прохождения лабиринта по Эйлеру будет выглядеть примерно таким образом:

3. Решение задачи.
Правило 1.
Отправляемся по дороге от начального пункта (первого перекрестка) и идем по какой угодно дороге, пока не приходим в тупик или к новому перекрестку. Тогда
1*. Если пришли в тупик, то возвращаемся назад и пройденный путь должен быть уже отброшен, так как мы его прошли 2 раза (туда и обратно).
2*. Если приходим к новому перекрестку, то направляемся по новому произвольному пути, не забывая каждый раз отметить поперечной чертой путь, по которому мы прибыли, и путь, по которому отправились дальше.

3. Решение задачи.
Как это показано на рисунке 1, где мы движемся в направлении f, приходим к пересечению путей и берем направление g. Мы следуем указанному выше правилу всякий раз, когда приходим на перекресток, на котором мы еще не были. Но однажды мы попадем на перекресток, на котором мы уже были. Здесь есть два случая:
мы приходим по дороге, уже раз пройденной нами;
мы приходим по новому пути, еще не отмеченному чертой.

3. Решение задачи.
Правило 2.
Прибыв на уже известный нам перекресток по новой дороге, надо тотчас повернуть назад, предварительно отметив этот путь двумя чертами (прибытие и обратное отправление). Как это показано на рисунке 2.

3. Решение задачи.
Правило 3.
Если мы приходим на известный нам перекресток таким путем, каким мы уже прошли раз раньше, то отметить этот путь второй чертой и отправиться дальше путем, которым мы еще не шли, если только такой существует. Этот случай изображен на рисунке 3.

3. Решение задачи.
Но если такого пути нет, то выбираем дорогу, по которой мы прошли только один раз. Этот случай изображен на рисунке 4.
Придерживаясь точно указанных правил, мы необходимо обойдем 2 раза все линии сети и придем в точку отправления..

3. Решение задачи.
Итак, можно пройти каждую линию лабиринта дважды и прийти в исходную точку, если:
Выходя из точки отправления А, мы ставим начальную черту;
Прохождение через перекресток по одному из предыдущих 3-х правил каждый раз добавлять две поперечные черты на линиях, которые сходятся в этой точке;
В любой момент прохождения лабиринта, перед прибытием на какой либо перекресток или после отправления от него, начальный перекресток имеет нечетное число черточек, а всякий другой перекресток имеет их четное число.
В любой момент до или после прохода через перекресток, начальный перекресток имеет только один путь, обозначенный только одной чертой. Всякий же иной из посещенных уже перекрестков может иметь только два пути, обозначенных одной чертой.
После полного обхода лабиринта у всех перекрестков все пути должны иметь по две черты.

3. Решение задачи.
Пусть, наконец, мы будем вынуждены закончить путь и возвратиться в пункт А. Назовем последнюю линию АZ, т.е. она ведет из перекрестка Z в начальный А. Этот путь необходимо будет тем самым, которым мы отправились первый раз из А, иначе путь можно было бы продолжить. И если мы теперь принуждены вернуться в точку исхода, значит,
что из перекрестка Z
нет уже никакого другого
пути, который не был бы уже
два раза пройден.

3. Решение задачи.
Итак, при последнем возвращении в А все пути в Z должны быть отмечены двумя чертами. Аналогично это можно доказать и для предыдущего перекрестка У и для всех остальных. Предположение доказано и задача решена.
Этот изящный способ задачи дал инженер М. Тремо.
Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Правило это прекрасно подходит для того, чтобы не заблудиться в лабиринте, но если необходимо пройти все дорожки лабиринта, то это правило не подходит. В иных лабиринтах и вовсе это правило не применимо, т.к. многие линии сети замкнуты и не имеют дополнительных выходов.

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