РЕШЕНИЕ ЗАДАЧ ПО КОМБИНАТОРИКЕ С ПОМОЩЬЮ ТЕОРИИ ГРАФОВ
план-конспект занятия (6 класс) по теме

Разработка  занятия математического кружка по теме:  

«Моты Эйлера. Фигуры одним росчерком».

(математика , 6 класс)

Оборудование и материалы для занятия – презентация, созданная в программе Power Point 2003; мультимедийный проектор; компьютер; карточки с домашним заданием.

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

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

Ход занятия

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

Не отрывая карандаш от бумаги, и не проводя по одной линии дважды, начертить «открытый конверт» (рис.21)

. рис.21

2. Объяснение нового материала.

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

Условимся называть точки, в которых сходится четное количество линий, четными, а точки, в которых сходится нечетное число линий, - нечетными. Например, у «открытого конверта» две нижние вершины являются нечетными, а остальные - четные.

Получаем следующие  признаки вычерчивания фигур одним росчерком:

а)  если нечетных точек в фигуре нет, то ее можно начертить одним росчерком, начиная вычерчивать с любого места;

б)  если в фигуре две нечетные точки (если фигура имеет нечетную точку, то она всегда имеет и вторую нечетную точку), то ее можно начертить одним росчерком, начав вычерчивание в одной из нечетных точек и закончив в другой;

в)  если в фигуре более двух нечетных точек, то ее нельзя вычертить одним росчерком.

Например, «открытый конверт» можно начертить непрерывной линией, т. е. не отрывая карандаша от бумаги, так как у него две нечетных вершины; начинать вычерчивание необходимо в одной из нечетных вершин.

3. Упражнения на закрепление.

а) Вычерчивание фигур

1) Определите, какие из фигур, изображенных на рис. 22 можно начертить, не отрывая карандаш, от бумаги (и не проводя по одной линии дважды).

2) Нарисуйте те фигуры (см. рис. 22), которые можно начертить одним росчерком.

                                 в)

рис.22

Ответ: а) можно, б) нельзя, в) можно, г) можно, д) можно, е) можно, ж) можно.       

       3) Только что приобретенные вами знания имеют порой любопытное применение. Великий математик Л. Эйлер в 1736 г. занимался решением такой своеобразной задачи:  В Кенигсберге река, омывающая два острова, делится на два рукава, через которые перекинуто семь мостов (рис. 23). Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?

Схема мостов Кёнигсберга

    рис. 23

Сообщение ученика сопровождается презентацией (историческая справка).

Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года: "Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство... После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может".   К концу 19 века в Кёнигсберге было построено 7 основных мостов. Примерно в эти же годы составлена классическая задача о семи  мостах Кёнигсберга. Надо было пройти по всем городским мостам не проходя по одному из них  дважды.

ЛАВОЧНЫЙ мост (Kraemer-Brucke). Этот мост был построен в 1286 году. Само название моста говорит само за себя. Площадь, которая прилегала к нему, была местом оживлённой торговли. Он связывал два средневековых города Альтштадт и Кнайпхоф. Построен он был сразу же в камне. В 1900 году он был перестроен и сделан разводным. По мосту стали ходить трамваи. Во время войны он был сильно разрушен, но восстановлен, пока в 1972 году не был демонтирован.

ЗЕЛЁНЫЙ мост (Gruene-Brucke). Вторым по счету был построен Зелёный мост. Этот мост связал остров Кнайпхоф с южным берегом Прегеля. В 1907 году мост был перестроен, средний пролёт стал разводным и по нему стали ходить трамваи. Во время войны этот мост сильно пострадал, был восстановлен, а в 1972 году - демонтирован.

В 1972 году вместо Зелёного и Лавочного мостов был построен Эстакадный мост.        

ПОТРОХОВЫЙ мост (Koettel-Brucke). Третий мост был построен в 1377 году. Он соединил город Кнайпхоф с пригородом Форштадт. Этот мост был наполовину каменным, а пролёты - деревянные настилы. В 1621 году, во время сильного наводнения, мост сорвало и унесло в реку. Мост возвратили на место. В 1886 году его заменили новым, стальным, трёхпролётным, разводным. По нему тоже ходили трамваи. В 1945 году этот мост был разрушен.

КУЗНЕЧНЫЙ мост (Schmiede-Brucke). Этот мост был построен в 1397 году и соединял город Альтштадт на северном берегу с островом Кнайпхоф. Название моста характерно для средневекового города, так как кузнецы играли тогда важную роль и были всеми уважаемы. Этот мост тоже был с каменными опорами и деревянными пролётами. В 1896 году его перестроили, пролёты его стали стальными, а вот трамвайные пути обошли стороной. Во время войны он был разрушен.  В советское время около опор моста находился плавучий ресторан.

ДЕРЕВЯННЫЙ мост (Holz- Brucke).  Этот мост был построен в 1404 году и связал остров Ломзе ( ныне остров Октябрьский) и город Лёбенихт. До этого на северном берегу Нового Прегеля существовала паромная переправа, но, а название уму дали по названию материала, из которого он был сделан. Таким он простоял 500 лет, и только в 1904 году был заменён новым, а вот название осталось прежним. Очень интересно оформление чугунного ограждения моста - были использованы лесные сюжеты. Мост тоже был разводным, по нему ходили трамваи, во время войны был разрушен, но очень быстро восстановлен.  Мост существует и функционирует до сих пор, правда разводной механизм пришёл в негодность.

МЕДОВЫЙ мост (Hoenig-Brucke). На острове Ломзе перед Медовым мостом находилась площадь - Бычий рынок. На площади стояли фахверковые склады, а за ними особняки с садами. Здесь же находился дом, где жил Кант ( 1775 - 1783 г.), чтобы Канту попасть на работу, ему достаточно было перейти Медовый мост и свернуть направо, там находился университет "Альбертина". В 1882 году мост был полностью перестроен, средний пролёт стал разводным, перила изготовила фирма "Кузнеца на Печатной". В таком виде мост сохранился до наших дней. Это был последний, седьмой мост, который фигурирует в задаче Эйлера.

Составим схему к решению задачи (рис.4). Из рисунка видно, что у полученной фигуры четыре нечетные вершины, следовательно, ее нельзя построить, не пройдя по одной линии дважды, а значит, нельзя пройти по мостам так, чтобы не пройти по одному и тому же два раза.

рис. 24

В процессе решения задач математики заметили, что удобно изображать объекты точками,      

 а отношения между ними отрезками или дугами.

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

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

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

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

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

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

Сообщение ученика сопровождается презентацией (историческая справка).

Но история о семи мостах Кёнигсберга имеет свое продолжение:       В 1905 году в Кенигсберге был поострен еще один мост. История кайзера Вильгельма: Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была не решаемой. К всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок.

4) Решите задачу с девятью мостами, аналогичную предыдущей по условию и требованию (рис. 25)

   рис. 25

    Решение.

Составим схему, аналогичную предыдущей задаче (рис. 26). Из рисунка видно, что у полученной фигуры две нечетные вершины, следовательно, ее можно построить, не отрывая карандаша от бумаги, а значит, можно пройти по мостам, не пройдя по одному и тому же два раза, начиная, например, с одного из мостов островка Е.

рис.26

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

   рис.27

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

     рис. 28

 Поэтому в этом графе существует эйлеров путь, а значит, его (т.е. птицу) можно нарисовать одним росчерком. Нечетные вершины: две. Так как количество нечетных вершин = 2, то птицу можно нарисовать одним росчерком. Начать путь нужно в одной нечетной вершине, а закончить в другой.

4  Домашнее задание:

1 . Начертить фигуры одним росчерком карандаша (там, где это возможно).

рис. 29

2.  Через реку, омывающую шесть островов, перекинуто семнадцать мостов (рис. 30). Можно ли обойти все эти мосты, не побывав ни на одном из них более одного раза?

рис. 30

5) Итог. 

         На этом занятии были рассмотрены графы, которые тесно связаны с историей о мостах Кёнигсберга.  С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач. Сегодня мы с вами познакомились еще с одним методом решения задач с помощью графов. Мы  убедились, что теория графов позволяет быстро и изящно решать задачи, которые весьма трудно решить другими методами и позволяет решить не только одну отдельно взятую задачу, но и находить методы решения целого класса задач.

«Литература»

1. Приложение к газете «Первое сентября» «Математика» № 10,16, 25, 1998;
2. Тюрин Ю.Н. и др. Теория вероятностей  и статистика / Ю.Н.Тюрин, А.А.Макаров, И.Р.Высоцкий, И.В.Ященко. – 2-е изд., переработанное. – М.:МЦНМО: ОАО «Московские учебники», 2008. – 256 с.
3. Шеврин Л.Н., Гейм А.Г. и др, «Учебник-собеседник для 6 класса общеобразовательных учреждений, - 4 издание переработанное - М.: «Просвещение», 2001. – 288 с.: ил.
4. О.С. Медведева. Психолго-педагогические основы обучения математике. Теория,  методика, практика/ М.:БИНОМ. Лаборатория знаний, 2011. – 204 с.: ил. – (Педагогическое образование)
5. Внеклассная работа. Обучение элементам теории графов в 4-6 классах./      О.И.Мельников, В.В.Куприянович. – М.: Просвещение, 2000г.120 с.;