I. Постановка проблемной ситуации.

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

Попробуйте нарисовать “открытый конверт”.
Как вы видите, что у некоторых получается, а у некоторых нет. Почему это происходит? Как правильно рисовать, чтобы получилось? И для чего она нужна? Чтобы ответить на эти вопросы, я расскажу вам, один исторический факт.

Город Кенигсберг (после мировой войны он называется Калининград) стоит на реке Преголь. Некогда там было 7 мостов, которые связывали между собой берега и два острова. Жители города заметили, что они никак не могут совершить прогулку по всем семи мостам, пройдя по каждому из них ровно один раз. Так возникла головоломка: “можно ли пройти все семь кенигсбергских мостов ровно один раз и вернуться в исходное место?”.

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

В 1735 году эта задача стала известна Леонарду Эйлеру. Эйлер выяснил, что такого пути нет, т. е. доказал, что эта задача неразрешима. Конечно, Эйлер решил не только задачу о кенигсбергский мостах, а целый класс аналогичных задач, для которых разработал метод решения. Можно заметить, что задача состоит в том, чтобы по карте провести маршрут – линию, не отрывая карандаша от бумаги, обойти все семь мостов и вернуться в начальную точку. Поэтому Эйлер стал рассматривать вместо карты мостов схему из точек и линий, отбросив мосты, острова и берега, как не математические понятия. Вот что у него получилось:

А, В – острова, M, N – берега, а семь кривых – семь мостов.

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

Докажем неразрешимость нашей задачи.
Как видим, в нашем графе все вершины нечетные. Для начала докажем, что, если обход графа начинается не с нечетной точки, то он обязательно должен закончится в этой точке

Рассмотрим для примера вершину с тремя линиями. Если мы по одной линии пришли, по другой вышли, и по третьей опять вернулись. Все дальше идти некуда ( ребер больше нет). В нашей задаче мы сказали, что все точки нечетные, значит, выйдя из одной из них, мы должны закончить сразу в трех остальных нечетных точках, чего не может быть.
До Эйлера ни кому в голову не приходило, что головоломка о мостах и другие головоломки с обходом контура, имеет отношение к математике. Анализ Эйлера таких задач “является первым ростком новой области математики, сегодня известной под названием топология”.

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

II. Признаки вычерчивания графа.

1. Если в графе нет нечетных точек, то ее можно нарисовать одним росчерком, не отрывая карандаша от бумаги, начиная с любого места.
2. Если в графе две нечетные вершины, то ее можно начертить одним росчерком, не отрывая карандаша от бумаги, причем вычерчивать нужно начинать в одной нечетной точке, а закончить в другой.
3. Если в графе более двух нечетных точек, то ее нельзя начертить одним росчерком карандаша.

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

Закрепим полученные знания. Определите, какие фигуры можно построить, а какие нельзя.

а) Все точки четные, поэтому эту фигуру можно построить, начиная с любого места, например:

б) В этой фигуре две нечетные точки, поэтому ее можно построить не отрывая, карандаша от бумаги, начиная с нечетной точки.
в) В этой фигуре четыре нечетные точки, поэтому ее нельзя построить.
г) Здесь все точки четные, поэтому ее можно построить, начиная с любого места.

Проверим, как вы усвоили новые знания.

III. Самостоятельная работа по карточкам с индивидуальными заданиями.

Задание: проверить, можно ли совершить прогулку по всем мостам, пройдя по каждому из них ровно один раз. И если можно, то нарисовать путь.

IV. Итоги занятия.