Презентация на тему "Применение теории графов к решению лабиринтов"

Применение теории графов  к решению лабиринтов

Основные понятия теории  графов • Граф задается парой множеств G(V,R) • Вершины называются смежными, если  их соединяет ребро • Ребро и любая из двух вершин  называются инцидентными • Степень вершины – количество  инцидентных ей ребер • Вершины, не имеющие инцидентных  ребер, называются изолированными

Основные понятия теории  графов • Маршрут графа – последовательность  чередующихся вершин и ребер • Замкнутый маршрут (цикл)– маршрут, в  котором начальная и конечная вершины  совпадают • Простая цепь – маршрут, в котором все  ребра и вершины различны • Связный граф – граф, в котором каждая  вершина достижима из любой другой

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

Теорема Эйлера: • Связный граф является эйлеровым  тогда и только тогда, когда степень  каждой его вершины четная.

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

• Леонард Эйлер разрешил вопрос о выходах  из лабиринтов, применив к ним теорию  графов. Математик Эйлер провёл  исследования лабиринтов и пришёл к  заключению, что безвыходных лабиринтов  нет. • Лабиринт — это граф. Исследовать  граф — значит, найти в нём путь. • Лабиринты состоят из коридоров,  перекрёстков, тупиков, и пути в них можно  изобразить графами.

• Рёбра графов — это коридоры,  а вершины — входы, выходы,  перекрёстки и тупики. • Если схему лабиринта изобразить в  виде графа, то найти всевозможные  выходы из лабиринта будет просто.

Алгоритм • Расставим вершины графа ­  перекрёстки и тупики. • Зачеркнём  тупиковые вершины. • Прочертим рёбра графа

• Задача 1. Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву в поисках добычи. Чёрной линией изображён путь лисы. Обойдя все деревья по одному разу, она устала и легла отдохнуть под одним из деревьев (дерево загораживает лису и её не видно) Где сейчас лиса? Под каким деревом находится её нора? Сколько решений имеет задача?

Задача 1. Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву в поисках добычи. Чёрной линией изображён путь лисы. Обойдя все деревья по одному разу, она устала и легла отдохнуть под одним из деревьев (дерево загораживает лису и её не видно) Где сейчас лиса? Под каким деревом находится её нора? Сколько решений имеет задача?

Решение. Рассмотрим данный  рисунок как граф, у которого две  нечётные вершины, значит, нора  лисы находится в одной из них, а  сама лиса – во второй, или наоборот,  т.е. задача имеет два решения

Задача 2. На рисунке дан план дома. Разрывы в линиях обозначают двери. Маленькому мальчику захотелось за один обход пройти через все двери своего дома по одному разу. С какой комнаты мальчик мог начать свой путь?

1 4 2 3 5 6 7   8 9   10