План конспект урока на тему Графы. Применение графов при решении задач

Тема «ГРАФЫ. Решение задач с помощью графов»
Образовательные:
Формирование понятия «граф», рассмотреть его основные элементы: вершина, ребра. степень;
Формирование умения составлять граф по описанию отношений между предметами, применять при решении задач.
Развивающие:
Развивать логическое мышление, внимание, память, формировать умение планировать свою деятельность.
Формировать умения сотрудничать в паре, развитие познавательного интереса.
Воспитательные:
Воспитывать взаимопомощь, усидчивость, трудолюбие.
Совершенствовать умение сотрудничать при работе в группах и в парах.
Предметные:
Знать: понятие граф, элементы, степень графа; алгоритм построения эйлеровых графов.
Уметь: составлять граф по заданному описанию, применять при решении различных задач.
Личностные: мотивация к обучению; уметь проводить самооценку на основе критерия успешности учебной деятельности.
Метапредметные:
Коммуникативные –
Умение оформлять свои мысли в устной форме;
слушать и понимать речь других;
совместно договариваться о правилах поведения и общения в школе и следовать им.
Регулятивные –
умение ставить учебные цели.
Личностные – умение проводить самооценку на основе критерия успешности учебной деятельности.
Познавательные–
умение ориентироваться в своей системе знаний: отличать новое от уже известного с помощью учителя;
добывать новые знания: находить ответы на вопросы, используя учебник, свой жизненный опыт и информацию, полученную на уроке.

Структура урока
Организационный момент
Актуализация знаний.
Формулировка темы урока.
Формирование новых знаний и умений.
Закрепление новых знании
Физкульминутка
Историческая справка.
Применение теории графов различных сферах деятельности
8.Рефлексия

Ход урока.
1. Организационный момент. (слайд 1.)
- Здравствуйте ребята!
- «МАТЕМАТИКА» - это стройное, красивое здание, по этажам которого вы шагаете с 1-го класса. Сегодня вы пройдете очередной шаг по дороге знаний, и я с радостью помогу вам сделать этот шаг.
- Приготовьте тетрадь к работе, карандаши и линейки. Запишите в тетрадях число.
2. Актуализация знаний. (слайд 2.)

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

Параграф фотограф граффити
- Посмотрите внимательно на слова и давайте попробуем определить, какой слог встречается в каждом слове.?
- Правильно – слог Граф. Как вы думаете, что означает это слово? Какие ассоциации возникают у вас при этом слове.
(Выслушиваются ответы детей).
-Но у нас с вами урок математики. А как связать это слово с математикой? И главный вопрос математики - где его можно применить?
3. Формулировка темы урока.
-Решим небольшую задачу: У каждого из трех друзей: Васи, Миши, Коли есть свой шалаш. Они решили установить между собой связь с помощью проволочного телефона. Вопрос: какое наименьшее количество линий из проволоки им придется провести, чтобы каждый из них мог поговорить с каждым? (слайд 3.)
(Выслушиваются ответы детей)
-Молодцы! Конечно же 3 линии.
- Теперь давайте немного усложним задачу: К трем друзьям присоединился 4 друг и построил свой шалаш. Сколько же линий нужно провести в этом случае.
(Дается детям время на обсуждение. Выслушиваются разные мнения.)

- Давайте попробуем нарисовать эту задачу.
(Дети в тетрадях и ученик у доски выполняют рисунок.)
- А теперь посмотрим, что у нас с вами получилось?
(ответы детей: обозначили точками и соединили их линиями)
- Вот мы с вами граф и нарисовали. Давайте попробуем дать определение . (слайд 4,5.)
(Заслушиваются ответы детей)
-запишем в тетрадях тему урока «Графы»
4 Формирование новых знаний и умений.
Граф – это конечное множество точек, некоторые из которых соединены линиями.
Точки – называются вершинами, а соединяющие их линии (я не сказала отрезки) – ребрами.
- Давайте посчитаем сколько в полученном графе вершин и ребер. (слайд 6.)

Число ребер, выходящих из каждой вершины графа мы будем называть степенью этой вершины.
Если из вершины выходит нечетное число ребер – она будет называться нечетной, а если четное – четной. (слайд 7.)
- Назовите, пожалуйста, сколько ребер выходит из каждой вершины и назовите степень вершины каждого графа (дети отвечают на поставленный вопрос) (слайд 8.)

5. Закрепление новых знаний. (слайд 9.)
Задача №3 . Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?
- Что же нам необходимо сделать, чтобы решить эту задачу?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
[ Cкачайте файл, чтобы посмотреть картинку ]
--Опять, что мы с вами нарисовали?
Задача №4. (слайд 10.)
Допустим, что у вас в понедельник 4 урока: русский язык, математика, история и технология. Сколькими способами можно составить расписание из 4 предметов, если первым уроком должна быть математика и предметы не повторяются.
-Как же нам можно решить эту задачу?
(Выслушиваются ответы детей).

-- Отличается ли данный граф от- предыдущих? (слайд 11.)
Он имеет внешнее сходство с деревом, поэтому он так и называется - граф-дерево. Дерево – это очень простой граф, все вершины которого соединены так, что ни одна часть не является замкнутой линией.
--А скажите, пожалуйста, а на каком-нибудь другом уроке вы встречаетесь с граф- деревом?
(Выслушиваются ответы детей).

6. Физкульминутка (гимнастика для глаз)
7. Историческая справка. (слайд 12.)
[ Cкачайте файл, чтобы посмотреть картинку ]
Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог. 
Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. В 1736 году. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. Задач вида «одним росчерком» (слайд 13.)
8. Практическая работа. (слайд 14.)
-У меня в руках 2 картинки: домик и прямоугольник, в котором проведены диагонали.
-А теперь я попрошу вас вспомнить – рисовали ли вы «домик», не отрывая карандаш от бумаги?
У вас на листочках эти фигуры. Ваша задача: выяснить, можно ли нарисовать эти фигуры, не отрывая карандаш от листа.

Кто смог нарисовать эти фигуры?
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Такими графы названы в честь учёного Леонарда Эйлера. (слайд 15.)
Алгоритм решения
определить степень каждой вершины;
посчитать количество нечётных вершин;
сделать выводы:
а) заданный обход возможен, если
- все вершины чётные (его можно начать с любой вершины);
- две вершины нечётные (его нужно начать с одной из нечётных вершин);
б) заданный обход невозможен, если нечётных вершин больше двух;

Задача.
Можно ли нарисовать эти фигуры, не отрывая карандаш от бумаги.
[ Cкачайте файл, чтобы посмотреть картинку ][ Cкачайте файл, чтобы посмотреть картинку ]
4 . Задача о мостах. (слайд 16.)
При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии.
[ Cкачайте файл, чтобы посмотреть картинку ]

Решение: Однако число линий для каждой точки на схеме является нечетным. Следовательно, задача не имеет решения.
Задача: (слайд 17.)
Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается.




7. Применение теории графов различных сферах деятельности. (слайды 18-24.)
Теория графов сейчас одна из самых развиваемых частей математики, так как современная жизнь требует появление новых профессий. Одна из них – специалист по логистике. (Приложение 3.) Менеджер по логистике занимается доставкой товаров, грузов, планирует транспортные маршруты, рассчитывает стоимость перевозок, организует хранение товаров, грузов и т.д. Одна из главных задач специалиста по логистике - анализ ситуации, поэтому он должен уметь хорошо считать, владеть теорией графов.
Типичными графами на картах города являются схемы движения городского транспорта, изображения железных дорог, схемы авиалиний, которые часто вывешивается в аэропортах. Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы. Графы есть и на картах звездного неба.





Графы применяются в различных отраслях науки. Например:
А) Графы и история.
Историк прослеживает родословные связи по генеалогическому дереву.
Генеалогическое дерево А.С. Пушкина.
[ Cкачайте файл, чтобы посмотреть картинку ]

Вершины – члены рода, а связывающие их отрезки – отношения родственности.  Б) Графы и физика

Инженер чертит схемы электрических цепей. Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

8.Рефлексия
Чтобы вы могли глубже оценить свою деятельность и вклад в урок предлагаю закончить следующие фразы
Сегодня на уроке я узнал
Сегодня на уроке мне понравилось
Сейчас мое настроение .
Спасибо за урок.