I. Постановка проблемной ситуации.
Наверное, все помнят с детства, что очень популярна была следующая задача: не отрывая карандаша от бумаги и не проводя по одной линии дважды, начертить “открытый конверт”:
Попробуйте нарисовать “открытый
конверт”.
Как вы видите, что у некоторых получается, а у
некоторых нет. Почему это происходит? Как
правильно рисовать, чтобы получилось? И для чего
она нужна? Чтобы ответить на эти вопросы, я
расскажу вам, один исторический факт.
Город Кенигсберг (после мировой войны он называется Калининград) стоит на реке Преголь. Некогда там было 7 мостов, которые связывали между собой берега и два острова. Жители города заметили, что они никак не могут совершить прогулку по всем семи мостам, пройдя по каждому из них ровно один раз. Так возникла головоломка: “можно ли пройти все семь кенигсбергских мостов ровно один раз и вернуться в исходное место?”.
Попробуйте и вы, может у кого-нибудь получится.
В 1735 году эта задача стала известна Леонарду Эйлеру. Эйлер выяснил, что такого пути нет, т. е. доказал, что эта задача неразрешима. Конечно, Эйлер решил не только задачу о кенигсбергский мостах, а целый класс аналогичных задач, для которых разработал метод решения. Можно заметить, что задача состоит в том, чтобы по карте провести маршрут – линию, не отрывая карандаша от бумаги, обойти все семь мостов и вернуться в начальную точку. Поэтому Эйлер стал рассматривать вместо карты мостов схему из точек и линий, отбросив мосты, острова и берега, как не математические понятия. Вот что у него получилось:
А, В – острова, M, N – берега, а семь кривых – семь мостов.
Теперь задача такая – обойти контур на
рисунке так, чтобы каждая кривая проводилась
ровно один раз.
В наше время такие схемы из точек и линий стали
называть графами, точки называют вершинами
графа, а линии – ребрами графа. В каждой вершине
графа сходится несколько линий. Если число линий
четно, то вершина называется четная, если число
вершин нечетно, то вершина называется нечетной.
Докажем неразрешимость нашей задачи.
Как видим, в нашем графе все вершины нечетные. Для
начала докажем, что, если обход графа начинается
не с нечетной точки, то он обязательно должен
закончится в этой точке
Рассмотрим для примера вершину с тремя
линиями. Если мы по одной линии пришли, по другой
вышли, и по третьей опять вернулись. Все дальше
идти некуда ( ребер больше нет). В нашей задаче мы
сказали, что все точки нечетные, значит, выйдя из
одной из них, мы должны закончить сразу в трех
остальных нечетных точках, чего не может быть.
До Эйлера ни кому в голову не приходило, что
головоломка о мостах и другие головоломки с
обходом контура, имеет отношение к математике.
Анализ Эйлера таких задач “является первым
ростком новой области математики, сегодня
известной под названием топология”.
Топология – это раздел математики,
изучающий такие свойства фигур, которые не
меняются при деформациях, производимых без
разрывов и склеивания.
Например, с точки зрения топологии, круг, эллипс,
квадрат и треугольник обладают одинаковыми
свойствами и являются одной и той же фигурой, так
как можно деформировать одну в другую, а вот
кольцо к ним не относится, так как, чтобы его
деформировать в круг, необходима склейка.
II. Признаки вычерчивания графа.
1. Если в графе нет нечетных точек, то ее можно нарисовать одним росчерком, не отрывая карандаша от бумаги, начиная с любого места.
2. Если в графе две нечетные вершины, то ее можно начертить одним росчерком, не отрывая карандаша от бумаги, причем вычерчивать нужно начинать в одной нечетной точке, а закончить в другой.
3. Если в графе более двух нечетных точек, то ее нельзя начертить одним росчерком карандаша.
Вернемся к нашей задаче с открытым конвертом. Подсчитаем количество четных и нечетных точек: 2 нечетные и 3 четные, значит, эту фигуру можно начертить одним росчерком, причем начать нужно в нечетной точке. Попробуйте, теперь у всех получилось?
Закрепим полученные знания. Определите, какие фигуры можно построить, а какие нельзя.
а) Все точки четные, поэтому эту фигуру можно построить, начиная с любого места, например:
б) В этой фигуре две нечетные точки,
поэтому ее можно построить не отрывая, карандаша
от бумаги, начиная с нечетной точки.
в) В этой фигуре четыре нечетные точки, поэтому ее
нельзя построить.
г) Здесь все точки четные, поэтому ее можно
построить, начиная с любого места.
Проверим, как вы усвоили новые знания.
III. Самостоятельная работа по карточкам с индивидуальными заданиями.
Задание: проверить, можно ли совершить прогулку по всем мостам, пройдя по каждому из них ровно один раз. И если можно, то нарисовать путь.
IV. Итоги занятия.