Урок по теме "Графы"

ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ И НАУКИ  БРЯНСКОЙ ОБЛАСТИ Государственное бюджетное профессиональное образовательное учреждение «Брянский строительный колледж имени профессора Н.Е. Жуковского» МЕТОДИЧЕСКАЯ РАЗРАБОТКА  ОТКРЫТОГО УЧЕБНОГО ЗАНЯТИЯ  Учебной дисциплины Математика по специальности 21.02.08 Прикладная геодезия                                                                             Разработал преподаватель              _____________                  Н.С.Власова                                                                                                    (подпись) Согласовано председатель ПЦК                              _____________               О.В.Симакова                                                                                      (подпись) Брянск 2019 Технологическая карта учебного занятия № 32 Дата проведения: 27.02.2019 Учебная дисциплина: Математика Индекс: 21.02.08 Прикладная геодезия Тема: Практическое занятие по теме «Построение графов» Вид занятия (тип урока): урок закрепления знаний Место проведения: ГБПОУ «БСК им. профессора Н.Е.Жуковского» Время проведения:10­50­ 12­25 Цель   занятия:  Проверить   усвоение   материала   и   закрепить   полученные   знания   при выполнении практических заданий  и решении задач в  форме игры. Студент должен: знать: ­понятие «граф», «ориентированный граф», элементы графа,степень вершины ит.д. ­способы геометрического представления различных видов графов ­примеры применения и использования графов в различный областях знаний, уметь: ­строить любой граф по заданным параметрам, ­ решать прикладные задачи с использованием теории графов. Межпредметные связи:    информационные технологии Информатика Теория вероятности Дискретная математика Оснащение: ­ПЭВМ ­ мультимедийный проектор ­интерактивная доска Используемые источники: Основная:    Спирина М.С. Дискретная математика: Учебник для студ. учреждений сред. проф. образования. – М.: Издательский центр “Академия”. 2017. Дополнительная: Березина Л.Ю. Графы и их применение: пособие для учителей. –М.:  Просвещение, 1979. Хронокарта занятия: я 5 м е р в л э   . 1 № 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 2. 2. 3.2 3.2 3.3 3.3 3.4 пр пр пр 4 4 5.1 5.1 5.2 6,7 8,9 Вопросы для самоконтроля: 1. Что такое граф? 2. Какой граф называется ориентированным? 3. Чем отличается взвешенный граф? 4. Как определить четность\нечетность вершины? 5. Какой вид графов называется Эйлеровым? 6. Что такое дерево? Лес? 7. Какой граф является циклом? 8. Какая вершина называется концевой? 9. Что такое лист? 10. Какой граф можно назвать путем? Самостоятельная работа студента: 1. Решение кроссвордов по группам с последующей проверкой на  слайде 2.  Составление генеалогического дерева своей семьи 3. Этап : «Найди пару» Конспект учебного занятия. Ход урока 1. Организационный момент Приветствие. Объявление темы урока, целей урока (отметить отсутствующих). ­ Сегодня у нас  завершающее занятие в данном разделе– «Основы теории  графов»., которое по традиции является практическим. Но пройдет оно немного  в нетрадиционной форме. Цель занятия – повторение и обобщение полученных ранее знаний по разделу  «Основы теории графов». Мы вспомним основные понятия теории графов,  свойства, характеристики, виды графов. Сегодня мы проведем наше занятие в  виде игры, которая состоит из 3 этапов. Итак, начнем игру! Эпиграфом к нашему занятию, хотелось бы привести слова Александра  Даниловича Александрова­ ( 22 июля 1912 — 27 июля 1999) — советский и  российский математик, физик, философ;  : Инженер, не владеющий  математическими методами, ­ это не инженер, а монтёр… Инженер в полном  смысле этого слова немыслим без знания математики. Ничего нельзя сделать без  математики: мост построить нельзя, плотину – нельзя, гидростанцию – нельзя.  Сокращать объём преподавания математики – преступление! Надо изучать её  как можно в большем объёме, а главное – как можно основательнее.   2. Актуализация знаний  (слайд 3­11) Повторить основные понятия, необходимые для дальнейшей работы. 3. Основной этап урока . Игра Этап 1 «Истина или ложь» Вам даются утверждения и необходимо определить истинно оно или ложно.  Ответ нужно пояснить.  1. Является ли данный граф деревом? (слайд 12) ^     Ответ: ложь, т.к. дерево – это связный граф не содержащий циклов      2. Ребро ab – это петля? (слайд 13) Ответ: ложь, т.к. петлей называется ребро у которого начало и конец совпадают.  Петля это ребро сс ^ 3. Кратчайший путь из вершины а в вершину d равен 6? (Слайд 14) Ответ: ложь, т.к. кратчайший путь из вершины а в вершину    ^ 4. Лист – это ребро, объединяющее две вершины? (слайд 15)  d   равен 5 Ответ: ложь, т.к. лист ­ концевая вершина дерева (    v  1,    ^ 5. Данный граф является звездным? ( слайд 16)    v  6)  v  3,   v  5,    Ответ: истина, т.к. звездный граф – это граф, в котором одна из вершин является концевой для всех ребер. ^ 6. Данный граф является полным? ( слайд 17) Ответ: истина, т.к. полный граф – это такой граф, между любыми двумя  вершинами которого есть ребро. ^ 7. Данный граф является транспортной сетью?( слайд 18) Ответ: ложь, т.к. транспортная сеть это ориентированный граф ^ 8. Ребра ab и bd кратные ( слайд 19) Овтет: ложь, т.к. кратными называются два ребра, принадлежащие одной и той  же паре вершин. ^ 9. Вершинная раскраска данного графа верная( слайд 20) Ответ: истина, т.к. раскраской графа называется такое приписывание цветов его  вершинам, что никакие две смежные вершины не получают одинаковый цвет. 3.2 Индивидуальное задание Прежде, чем перейти к следующему этапу, мне бы хотелось немного отойти в  сторону от намеченного плана. ­Скажите, в какой еще сфере жизни мы не можем обойтись без графов? Я немного подскажу, эта сфера связана с историей... (составление  генеалогических деревьев) Я предлагаю сейчас двум желающим занять отдельные места и в течение часа  (или меньше) попробовать составить генеалогическое дерево своей семьи . 3.3 Этап 2. Решим несколько задач у доски, есть желающие? Задача №1  (слайд 21) В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода.  Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между  кувшином и сосудом с квасом, в банке не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. Куда налита каждая жидкость?   Моло ко Лимона д Квас Вода Бутыл ка Стакан Кувши н Банка - - + - + - - - - - - + - + - - Задача №2.(слайд 24) Между девятью планетами солнечной системы установлено  космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:  Земля – Меркурий,  Плутон – Венера, Земля – Плутон,  Плутон – Меркурий,  Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер;  Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли  до Марса? Решение: Задача №3.  (Слайд 26) В первенстве класса по настольному теннису 6 участников: Артем, Булат, Влад  Батыршин, Глеб, Дмитрий и Ермошин Влад.  Первенство проводится по круговой системе– каждый из участников играет с  каждым из остальных один раз. К настоящему моменту некоторые игры уже  проведены: Артем сыграл с Булатом, Глебом  и  Ермошиным; Булат, как уже  говорилось, с Артемом и еще с Глебом; Влад – с Глебом, Дмитрием  и   Ермошиным; Глеб – с Артемом и Булатом; Дмитрий – с Владом и  Ермошин – с  Артемом и Владом.  Сколько игр проведено к настоящему моменту и сколько еще осталось? Решение: Изобразим данные задачи в виде схемы. Участников будем изображать точками:  Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участником уже сыграли  между собой, то будем соединять изображающие их точки отрезками.  Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим еще один граф с теми же  вершинами, но ребрами будем соединять тех участников, которые еще не играли  друг с другом. Ребер у этого графа осталось 8. Значит, осталось провести 8 игр. Итак, мы решили с вами довольно современную задачу. Согласны? Но данные задачи возникали достаточно давно, давайте приведем примеры,  которые вставали перед математиками несколько веков назад. Теория графов содержит большое количество нерешённых проблем и пока не  доказанных гипотез, это сравнительно молодая наука: во времена Ньютона такой науки еще не было, хотя и были "генеалогические  деревья", представляющие  собой разновидности графов. 3.4 Исторический экскурс Примерами таких задач являются 3 самые распространенные задачи:   Задача о трех колодцах  Задача о семи мостах  Задача о четырех красках  Давайте подробно разберем каждую из них, для чего у нас есть заранее  подготовленные выступления. Демонстрируются 3 презентации, подготовленные Фроленковым А, Яценковым  Д, и Картуниным С. (дополнить рассказ ученика, если не скажет данные факты. Прогуляться по городским мостам предложили и Эйлеру. После безуспешной  попытки совершить нужный обход он начертил упрощенную схему мостов.  Получился граф, вершины которого – части города, разделенные рекой, а ребра – мосты. Попробуйте провести линии по всем ребрам ­"мостам", не отрывая карандаша от  бумаги. У кого получилось? Таких нет?  У Эйлера тоже не получилось.. А вы  знаете почему? Оказывается все дело в числе ребер, сходящихся в вершине.  Давайте посчитаем, сколько  ребер сходится в каждой вершине графа. Напишите рядом с каждой вершиной число, отражающее количество ребер, в ней  сходящихся, и назовем  вершину четной или нечетной в зависимости от того,  какое число, четное или нечетное, стоит рядом. Итак, в вершине А сходится 5  ребер, в вершине В­3, в вершине С­3, в вершине Д­3. Какими являются все  эти  вершины? (Нечетными.) Леонард Эйлер сформулировал правило: Обход возможен:  ЕСЛИ все вершины – четные, и его можно начать с любого участка.  ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных вершин. Обход невозможен если нечетных вершин больше 2. Во время прогулки по городу нельзя пройти по всем семи мостам, проходя по  каждому только один раз.) 4.Практическая работа (слайд 27 )  Сейчас, в продолжение последнего выступления, мы также решим несколько  похожих задач. ­Вы   видите   на   слайде   2   картинки:   домик   и   прямоугольник,   в котором проведены диагонали.           ­А теперь я попрошу вас вспомнить – рисовали ли вы «домик»,  не отрывая карандаш от бумаги?                  Ваша задача: выяснить,   можно ли нарисовать эти фигуры, не отрывая карандаш от листа.          Кто смог нарисовать эти фигуры? Как называется   граф, который можно нарисовать, не отрывая карандаша от  бумаги ? ( эйлеровым) .  1. Повторим алгоритм решения 1. определить степень каждой вершины; 2. посчитать количество нечётных вершин; 3. сделать выводы: а) заданный обход возможен, если ­ все вершины чётные (его можно начать с любой вершины); ­ две вершины нечётные (его нужно начать с одной из нечётных вершин); б) заданный обход невозможен, если нечётных вершин больше двух;       Задача. (слайд 28)   Можно ли нарисовать эти фигуры, не отрывая карандаш от бумаги. 5.1 3 Этап. Групповая работа. Необходимо решить 6 кроссвордов, работая в мини­группе по 2­3 чел.  После чего мы узнаем 6 основных понятий из раздела. Вариант 1 м а т р и ц а 3 4 8 6 10 1 9 7 5 2 ПО ГОРИЗОНТАЛИ: 3. Число (g) графа, которое показывает минимальное количество ребер, которое  необходимо изъять из графа, чтобы он стал деревом? 8. Линия, связывающая между собой вершины графа? 9. Вершина в самой верхней части каждого дерева? 10. Свойство вершин, при котором две вершины принадлежат одному и тому же  ребру? ^     ПО ВЕРТИКАЛИ: 1. Вершина, в которую входят дуга в транспортной сети? 2. Путь из корня в лист? 4. Числовая характеристика, одинаковая для всех изоморфных графов? 5. Число ребер, инцидентных данной вершине? 6. Совокупность вершин и ребер? 7. Точка, где могут сходиться/выходить рёбра и/или дуги? Вариант 2 е в о д е р 1 6 10 4 9 5 3 7 2 8 ПО ГОРИЗОНТАЛИ: 3. Бродячий торговец или агент по сбыту в задаче о нахождении кратчайшего  пути в графе? 4. Замкнутая цепь? 7. Граф, который можно уложить на плоскости, т.е. если его можно нарисовать  на этой поверхности так, чтобы ребра графа при этом не пересекались? 10. Приписывание цветов вершинам графа, в котором никакие две смежные  вершины не получают одинаковый цвет? ^     ПО ВЕРТИКАЛИ: 1. Граф, состоящий из одной вершины? 2. Что образуют узлы одного уровня в дереве? 5. Граф, между любыми двумя вершинами которого есть ребро? 6. Граф, содержащий кратные ребра? 8. Ребро в орграфе? 9. Совокупность вершин и ребер? Вариант 3 1 3 2 в е р ш и н а 4 9 5 6 7 8 1 0 ПО ГОРИЗОНТАЛИ: 3. Граф, содержащий кратные ребра? 4. Совокупность вершин и ребер? 7. Длина наибольшей ветви? 8. Линия, связывающая между собой вершины графа? 9. Путь из корня в лист? 10. Свойство вершин, при котором две вершины принадлежат одному и тому же  ребру? ^     ПО ВЕРТИКАЛИ: 1. Ребро в орграфе? 2. Характеристика графа, которая определяет, имеют ли ребра направление? 5. Вершина, из которой выходит дуга в транспортной сети? 6. Чередующаяся последовательность вершин и ребер, в которой любые два  соседних элемента инцидентны? Вариант 4 3 р е б р о 1 2 5 6 8 1 0 9 7 4 ПО ГОРИЗОНТАЛИ: 3. Дуга, поток по которой равен ее пропускной способности? 7. Каждая вершина дерева? 8. Вершина в самой верхней части каждого дерева? 9. Что образуют узлы одного уровня в дереве? 10. Совокупность вершин и ребер? ^     ПО ВЕРТИКАЛИ: 1. Граф, в котором число ребер и число вершин бесконечно? 2. Чередующаяся последовательность вершин и ребер, в которой любые два  соседних элемента инцидентны? 4. Свойство вершин, при котором две вершины принадлежат одному и тому же  ребру? 5. Вершина, из которой выходит дуга в транспортной сети? 6. Приписывание цветов вершинам графа, в котором никакие две смежные  вершины не получают одинаковый цвет? р а с к р а с к а Вариант 5 1 4 3 2 5 6 7 8 1 0 ПО ГОРИЗОНТАЛИ: 9 4. Вершина не инцидентная никакому ребру? 6. Совокупность вершин и ребер? 7. Характеристика графа, которая определяет, все ли вершины связаны? 10. Отношение эквивалентности в графе, характеристика графа? ^     ПО ВЕРТИКАЛИ: 1. Замкнутая цепь? 2. Характеристика графа, которая определяет, имеют ли ребра направление? 3. Чередующаяся последовательность вершин и ребер, в которой любые два  соседних элемента инцидентны? 5. Ребро, у которого начало и конец совпадают? 8. Путь из корня в лист? 9. Каждая вершина дерева? 5.2 Этап 3 «Найди пару»  (слайд 29) С этими понятиями мы встречались в процессе изучении раздела. Ваша цель  сейчас расположить полученные понятия в порядке, который соответствует  последовательности изучения материала. Найдите соответствующий ему  рисунок. Вернемся к нашим новоиспеченным «историкам» и посмотрим, какие же  деревья их семей у них получились. (к доске выходят одновременно два студента, прикрепляют к доске  ватманы и в двух словах описывают, что у них получилось). 6. Применение теории графов   различных сферах деятельности.  (слайды  16­ 18.)       Теория графов сейчас одна из самых развиваемых частей математики, так  как современная жизнь требует появление новых профессий. Одна из них  – специалист по логистике.  Менеджер по логистике занимается доставкой  товаров, грузов, планирует транспортные маршруты, рассчитывает стоимость  перевозок, организует хранение товаров, грузов и т.д. Одна из главных задач  специалиста по логистике ­ анализ ситуации, поэтому он должен уметь хорошо  считать, владеть теорией графов.        Типичными графами на картах города являются схемы движения городского транспорта, изображения железных дорог, схемы авиалиний, которые часто  вывешивается в аэропортах. Графом является и система улиц города. Его  вершины – площади и перекрестки, а ребра – улицы. Графы есть и на картах  звездного неба. Графы применяются в различных отраслях науки. Например: Историк прослеживает родословные связи по генеалогическому дереву. А) Графы и история. Генеалогическое дерево А.С. Пушкина.  Вершины – члены рода, а связывающие их отрезки – отношения родственности.                                                    Б) Графы и физика Инженер чертит схемы электрических  цепей. Еще недавно одной из наиболее  сложных и утомительных задач для  радиолюбителей было конструирование  печатных схем 7. Подведение итогов За этот урок мы повторили и обобщили полученные ранее знания. Мы вспомнили  основные определения теории графов, а также свойства, характеристики, виды  графов. И мне хочется надеяться, что этот урок принес вам большую пользу и  когда вы встретитесь с этими понятиями на других дисциплинах,  то смело и легко  будете решать эти задачи.  Особенно хочется отметить за активное участие ..., все остальные тоже хорошо  отвечали, поэтому получают пятерки. … были менее активны и получают за урок   Всем спасибо! 8. Домашнее задание.  По   данным   понятиям   составить   мини­лекцию   по   разделу   «   Основные   понятия теории графов» 9.Общая оценка всего занятия. Преподаватель вместе со студентами дает общую оценку занятия, работы всей группы. Студенты   поднимают   таблички   со   смайликами,   выражающими   их   состояние после занятия. Обсуждаются удачные и неудачные моменты и если есть грустные или злые смайлики, выясняем причину такого настроения.  Преподаватель всех благодарит за участие и сообщает о завершении занятия. Список литературы. 1. Спирина М.С. Дискретная математика: Учебник для студ. учреждений сред.  проф. образования. – М.: Издательский центр “Академия”. 2004. 2. Березина Л.Ю. Графы и их применение: пособие для учителей. –М.:  Просвещение, 1979.