Рисование фигур одним росчерком. Графы

Во многих ситуациях удобно изображать объекты точками, а связи между ними - линиями или стрелками. Такой способ представления называется графом. Впервые (в 1936 г. ) термин <<граф>> ввёл венгерский математик Денеш Кениг, назвав графами любой набор точек (вершин), некоторые из которых соединены между собой линиями (ребрами). Например, схема движения транспорта - это граф. Такие схемы можно увидеть на вокзалах, в метро, в городских троллейбусах и трамваях. На них остановки - вершины графа, а линии, соединяющие остановки, - рёбра.

Рассмотрим некоторые понятия, связанные с графами, на пример следующей задачи. Пример 1. Требуется, не отрывая руки от бумаги и не проводя по линии дважды, начерти фигурую Используя теорию графов , можно сказать решается или нет задача. Количество ребер, исходящих из одной его вершины, назовём степенью этой вершины. Будем говорить, что вершина чётная, если её степень чётная, и что вершина нечётная - в противоположном случае. Мы имеем 9 ребёр, 3 вершины степени5 и одна степени 3, т. е. 4 нечётные вершины. По свойству графов, установленным Л. Эйлером, если на фигуре (графе) больше двух нечётных вершин, то её нельзя нарисовать одним росчерком.

Пример2: Можно ли привязать к гвоздям А, В,С,Д,К,М верёвку так, как на не разрезая её на части и не сдваивая?

Решаем по принципу графов. Из вершин А, В, С и Д исходят по 3 ребра, а из вершин М и К - по 5. Все вершины нечётные. Значит, привязать верёвку так, как требуется в задачи, невозможно.

Пример 3: Дан кусок проволоки длиной120см. можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см.

У куба вершин, из каждой вершины выходят по 3 ребра. Значит все вершины нечетные. Каркас куба без наложения на рёбра сделать нельзя.

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

Запомним ещё одно свойство графов: связный граф только с двумя нечётными вершинами можно начертить одним росчерком, при этом движение нужно начать с одной из нечётных вершин и закончить в другой.

Пример4: изображен план здания. Требуется из комнаты №20 пройти все комнаты так, чтобы через каждую дверь пройти только один раз. В какой комнате закончится обход? (стрелочками обозначены двери).

Построим граф, соответствующий данной ситуации. Точки- комнаты, отрезки - двери. Посмотрим, какие вершины нечётные. Это вершины 20 и 23. Значит, если мы начнем движение из комнаты 20, то закончим в комнате 23.