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

№

Этапы урока

Время

1

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

2

2

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

7

3

Первое блюдо

17

4

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

1

5

Второе блюдо

10

6

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

3

7

Десерт

3

8

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

1

9

Итог урока

1

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

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

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

Переходим к первому блюду. Я не случайно вспомнила о Леонарде Эйлере. Первая работа по теории графов принадлежит именно ему (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. Между городами А и В имеется сеть дорог, и на некоторых из них движение одностороннее. Кроме того задана пропускная способность каждой дороги (в тыс. машин в час). Какой максимальный поток машин возможен из А в В и из В в А?
Сколько машин может выехать из А и сколько может въехать в В?
Сколько машин может выехать из В и въехать в А?

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

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

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

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

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

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