Открытый урок математики на тему "Математическое кафе "Графы"

Разделы: Математика

Тип урока: урок изучения и первичного закрепления новых знаний.

Форма проведения: групповая работа.

Цели урока:

  1. Обучающие:
  • Знание. Знание определения, основных понятий и назначения графов.
  • Понимание. Умение приводить примеры графов в различных учебных предметах  (математика, информатика, химия, биология и др.) и повседневной жизни.
  • Применение. Умение применять графы при решении различных задач, умение записывать информацию в виде графов (семантические сети, деревья, ориентированные графы).
  • Анализ. Умение из множества предметов вычленить объекты, обозначить связи между ними.
  • Синтез. Умение делать выводы о значении теории графов для остальных предметов.
  1. Развивающие:Развитие внимания, восприятия, памяти, представления, воображение, понимания, речи, элементов творчества, умения учиться.
  2. Воспитательные:Воспитание интереса к учебе, повышение интереса к математике, воспитание математической культуры, культуры общения, социализация личности.

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

Дидактическое обеспечение:

  1. Плакат «Меню кафе».
  2. Плакат «Математический винегрет».
  3. Плакат «Использование графов в различных областях знаний»
  4. Плакат «Кёнигсбергские мосты».
  5. Плакат «Сегодня на уроке».

Индивидуальный раздаточный материал:

  1. Меню кафе (план урока).
  2. Папки-файлы для индивидуальных работ.
  3. Комплекты листов – заданий.
  4. Жетоны для оценивания урока.
  5. Фломастеры, маркеры.

План урока (меню кафе)

№

Этапы урока

Время

1

Организационный момент

2

2

Салат «Математический винегрет»

7

3

Первое блюдо

17

4

Математическая пауза

1

5

Второе блюдо

10

6

Напитки «Красочный коктейль»

3

7

Десерт

3

8

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

1

9

Итог урока

1

О, сколько нам открытий чудных
  Готовит просвещенья дух…
А.С.Пушкин.

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

Ход урока

1. Организационный момент.

Сегодня я хочу пригласить Вас в математическое кафе «Графы».  На доске висит плакат «Меню кафе», на столах у каждой группы тоже есть меню. Откройте и посмотрите сегодняшнее меню. Сегодня мы познакомимся с математическим понятием «граф»; рассмотрим примеры использования графов в различных областях знаний; задачи по теории графов. Работа на уроке будет проходить в группах. За ответы, активную работу Вы будете получать баллы (количество баллов соответствует количеству цветных магнитов на магнитной доске: красный – 1 балл, желтый – 2 балла, зеленый – 3 балла). В конце урока полученные баллы будут переведены в оценки. Надеюсь, что наша работа будет продуктивной. Математическое кафе открыто. Добро пожаловать!

2. Салат «Математический винегрет».

Начнем с разминки. На улице весна и всем нам не хватает витаминов, поэтому предлагаю Вам попробовать математический винегрет. Перед вами кроссворд. Работа по разгадыванию кроссворда будет проходить в группах. Если Вы правильно отгадаете кроссворд, то в выделенных буквах прочитаете имя известного математика. Время выполнения задания – 5 минут. Группа, отгадавшая кроссворд, поднимает и показывает  листок с ответом.

На доске висит плакат «Математический винегрет» (см. приложение 1).

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

На доске портрет Леонарда Эйлера. Что вы знаете о Леонарде Эйлере?

Историческая справка.

Леонард Эйлер (1707-1783) – математик, механик, физик и астроном. Ученый необычайной широты интересов. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и других, оказавших значительное влияние на развитие науки. Леонард Эйлер по происхождению швейцарец. В 1726г. был приглашен работать в Петербург, в 1727г. переехал жить в Россию. Являлся академиком, а затем почетным членом Петербургской академии наук.

3. Первое блюдо.

Деятельность учителя

Деятельность учеников

Оформление доски

Переходим к первому блюду. Я не случайно вспомнила о Леонарде Эйлере. Первая работа по теории графов принадлежит именно ему (1736), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. В начале 20 века наряду с термином «граф» употреблялись другие термины, например карта, комплекс, диаграмма, сеть, лабиринт.
Графами называются схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых. Точки называются вершинами графа, а отрезки – ребрами графа. Внимание на доску

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

Все изученные понятия вывешиваются на специальный плакат «Сегодня на уроке»

Примеры графов:

  • схема метро;
  • генеалогическое древо;
  • кристаллическая решетка;
  • электрическая схема и другие.

(примеры графов приведены на плакате)

 

Плакат «Использование графов в различных областях знаний»
(см. приложение 2). После каждого изучения нового понятия или утверждения на специальном плакате появляется соответствующее слово или формула

Придумайте свои примеры графов (за каждый правильный ответ – 1 балл)

В качестве примеров ученики могут привести следующие примеры: схема автомобильных дорог, тепло- и электросети, дерево каталогов и другие.
За правильный ответ – 2 балла

 

Рассмотрим задачу: 5 друзей при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Обменяйтесь, пожалуйста, рукопожатиями. Сколько всего рукопожатий было сделано? Решение демонстрируется на специальной доске.
Изобразите в тетради 5 точек: А, Б, В, Г, Д.

Нулевой граф
Неполный граф
Полный граф

Ученики в группах обмениваются рукопожатиями.
Звучат гипотезы о количестве рукопожатий.
Параллельно с записью на доске ученики ведут запись в рабочей тетради

 

Сколько всего рукопожатий было сделано?
Если подвести итог, то можно утверждать: если полный граф имеет n вершин, то количество ребер будет равно n×(n-1)/2

Всего было сделано 10 рукопожатий.
Формулу записывают в рабочую тетрадь

 

Задача о Кёнигсбергских мостах.
Бывший Кёнигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз.
Схема города изображена на плакате (см. приложение № 2) и на листе с заданием

 

Плакат «Кёнигсбергские мосты» (см. приложение 2)

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

Учащиеся предлагают разные гипотезы.
Гипотеза: нужного решения нет.
Начертить схему в тетради

 

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

  • из любой вершины графа должен существовать путь по его ребрам в любую другую вершину (такой граф называется связным):
  • из каждой вершины должно выходить четное количество ребер

Запись в тетради

 

Замкнутый путь, проходящий по одному разу по всем ребрам графа, называют с тех пор эйлеровым циклом.
В 1859 году английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр (12-гранник), в вершинах которого вбиты гвоздики. Возьмите на столах макеты додекаэдров. Каждая из 20 вершин была помечена названием одного из крупных городов мира. Требовалось найти замкнутый путь, проходящий по ребрам додекаэдра и позволяющий побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики. Замкнутый путь по ребрам графа, проходящий по одному разу через все его вершины, называют гамильтоновым циклом. В отличие от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.
Путем в графе из одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами. При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута – конец пути. Циклом называется путь, в котором совпадают начало с концом

Определения записываются в рабочей тетради

 

Задача 1. Приведите примеры маршрутов из А в H в следующем графе (см. приложение 3). Приведите примеры циклов

Например, ADGH, AEFCDGH, ABCEH

Граф изображается на доске (подготовительная работа перед уроком)

Какой граф называется связным? (1 балл за правильный ответ)

Например, CFEC, ADCFEA

 

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.
Примеры:

  • генеалогическое древо;
  • дерево каталогов;
  • модель управления предприятием, учебным заведением и т.д.;
  • библиотечный каталог

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

 

Задача 2. Изобразите на плоскости 4 точки. Изобразите все возможные деревья, вершинами которых являются данные точки (За каждый правильный ответ – 1 балл)

Возможные варианты ответов:

 

Если подвести итог, то можно утверждать.
Утверждение: Дерево с n вершинами имеет n-1 ребро.
Изобразить построенное дерево можно в любом направлении – это уже дело эстетического вкуса разработчика модели

 

 

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

Учащиеся работают самостоятельно в группах, по окончании один человек из группы  демонстрирует результат на доске

 

4. Математическая пауза.

Подведём промежуточный итог. Подсчитывается число очков, полученных каждой группой.

5. Второе блюдо.

Деятельность учителя

Деятельность учеников

Оформление доски

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

 

 

Граф, у которого все ребра имеют направления, называется ориентированным или орграфом. На них удобно рассматривать транспортные задачи.
Приведите примеры ориентированных графов.

Определение записать в тетрадь

 

Задача 4. Между городами А и В имеется сеть дорог, и на некоторых из них движение одностороннее. Кроме того задана пропускная способность каждой дороги (в тыс. машин в час). Какой максимальный поток машин возможен из А в В и из В в А?
Сколько машин может выехать из А и сколько может въехать в В?
Сколько машин может выехать из В и въехать в А?

Из А может выехать в час 7 тыс. машин, но въехать в В в час могут лишь 4 тыс. из них. Однако, 4 тыс. машин в час остальные дороги в состоянии пропустить.
С другой стороны, из В в А могут выехать 3 тыс. машин в час, однако въехать в А за час смогут лишь 2 тыс. Поток в 2 тыс. машин из В в А остальные дороги смогут пропустить.

Плакат «Ориентирован-ные графы» (см. приложение 4).

Задача 5. Результаты соревнования, в котором участвовали 6 команд, представлены ориентированным графом на рисунке (стрелка направлена в сторону проигравшей команды). Какая команда победила? См. лист с заданием № 4.
Сколько игр сыграла каждая команда?
Сколько побед и поражений было у каждой команды?

Каждая команда сыграла 4 игры.

команда
А

победы
3

поражения
1

В

2

2

C

2

2

D

2

2

E

1

3

Победила команда А.

Плакат «Ориентирован-ные графы».

6. Напитки «Красочный коктейль».

Задача, о которой я хочу вам рассказать, ведет свою историю с 1852 г. Однажды английский студент Френсис Гутри раскрашивал карту Великобритании. Возьмите лист с заданием № 6. Каждое графство он выделял цветом. К сожалению, выбор красок у него был невелик, и приходилось их использовать повторно. Гутри старался, чтобы два графства, имеющие общий участок границы, были окрашены в разные цвета. Это занятие заставило его задуматься о том, какого наименьшего числа красок достаточно для раскрашивания любой карты. Гутри считал, что четырех красок всегда хватит, но доказать это не мог. Проблема некоторое время активно обсуждалась среди лондонских студентов, а потом о ней забыли. В 1879 г. известный английский математик Артур Кэли опубликовал эту задачу в первом томе «Трудов Королевского общества», и она получила широкую известность (для примера можно использовать карту Англии или другого государства).

Со временем интерес к «проблеме четырех красок» рос, но она не поддавалась усилиям даже выдающихся математиков. В 1890г. английский математик Перси Хивуд доказал, что пяти красок хватит для раскрашивания любой карты. В 1968г. было доказано, что карту, на которой обозначено меньше 40 стран, всегда можно раскрасить с помощью четырех красок.

Наконец, в 1976г. американские математики Кеннет Аппель и Вольфганг Хакен решили эту задачу с помощью компьютера. Они разбили все карты на 2000 типов. Компьютер по составленной ими программе исследовал, может ли в рассматриваемом типе карт найтись такая, для которой недостаточно четырех красок. С тремя типами карт компьютер на справился, и над ними пришлось потрудиться самим математикам. Получив ответ «нет» для всех 2000 типов, исследователи объявили, что проблема четырех красок решена. Почтовое отделение при университете, в котором работали Аппель и Хакен, в тот день гасило марки на письмах штемпелем со словами: «Четырех красок достаточно».

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

7. Десерт.

Подсчитаем баллы, полученные каждой группой. Полученное количество баллов переведем в оценки. Выставление оценок. Все учащиеся награждаются сладкими подарками.

8. Домашнее задание.

  • Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту предприятие А установило отношения со всеми другими предприятиями; Б установило с Г и Д; В установило со всеми предприятиями, кроме предприятия Е. Сколько вершин и сколько ребер имеет полученный граф?
  • Сколько ребер будет иметь полный граф, если у него: а) 10; б) 17 вершин?
  • Изобразите свое генеалогическое дерево.

9. Итог урока.

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