Геометрическая постановка задачи о лабиринтах

Вопрос о лабиринтах интересовал в свое время многих. Возможно ли построить "безвыходный" лабиринт, в котором найти путь к центру и выход было бы только делом случая, а не точного математического расчета? Ответ можно найти в теории графов.

Изучение свойств графов восходит к работам выдающегося математика XVIII века Леонарда Эйлера.

Результаты произведенных в этом отношении изысканий привели исследователей к заключению, что безвыходных лабиринтов не существует!

Лабиринт – это граф. Аллеи, дорожки, коридоры лабиринта – это ребра графа, а входы, выходы, перекрестки и тупики – вершины. Исследовать лабиринт – это найти путь в этом графе.

Решение (т. е. маршрут, ведущий к цели) каждого лабиринта может быть найдено одним из трех сравнительно простых методов:

1. Метод правой/левой руки.
2. Метод замазывания тупиков.
3. Волновой метод.

Эйлер установил четыре основных правила, которые применимы к графам:

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

ЛИТЕРАТУРА И ИНТЕРНЕТ-ИСТОЧНИКИ

1. ru.wikipedia.org
2. http://nlo-mir.ru/palnetazemla/6815-tajny-labirintov.html

3. http://nlo-mir.ru/palnetazemla/6815-tajny-labirintov.html

4. http://www.intuit.ru/studies/courses/58/58/lecture/1714

Метод одной руки

Метод замазывания тупиков

Понятие лабиринта

1. Запутанная сеть дорожек, ходов, сообщающихся друг с другом помещений [первонач. в Древней Греции и Египте большое здание со сложно расположенными переходами].
2. Сложное, запутанное расположение, сочетание чего-н. Л. улиц. Л. мыслей.
3. Внутреннее ухо (специальное). /Словарь С.И.Ожегова/.

Волновой метод

Суть метода: каждый уровень помечается числом, на 1 больше предыдущего. Реализуется такой метод с помощью очереди.

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