Цели урока:
- дидактические: ввести понятие «граф»; рассмотреть примеры использования графов в различных областях знаний; отрабатывать умение решать текстовые задачи на применение теории графов
- развивающие: развитие внимания, памяти, логического мышления, аргументированной математической речи;
- воспитательные: воспитывать чувства уверенности, последовательности, дисциплинированности, умение слушать.
Оборудование: проектор, экран, раздаточный материал (Приложение 1), презентация (Приложение 2)
Ход урока
1. Организационный момент
Сегодня мы познакомимся с математическим понятием «граф»; рассмотрим примеры использования графов в различных областях знаний; задачи по теории графов. Работа на уроке будет проходить в группах. Надеюсь, что наша работа будет продуктивной.
2. Этап усвоения новых знаний
1. Рассмотрим задачу. В первенстве класса по настольному теннису 6 участников: Артем, Булат, Влад Батыршин, Глеб, Дмитрий и Ермошин Влад. Первенство проводится по круговой системе– каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Артем сыграл с Булатом, Глебом и Ермошиным; Булат, как уже говорилось, с Артемом и еще с Глебом; Влад – с Глебом, Дмитрием и Ермошиным; Глеб – с Артемом и Булатом; Дмитрий – с Владом и Ермошин – с Артемом и Владом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение демонстрируется на доске. Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участником уже сыграли между собой, то будем соединять изображающие их точки отрезками. Получается схема, которая называется графом.
2. Определение. Графом называют конечное множество точек, которые соединены отрезками прямых. Точки называются вершинами графа, а отрезки – ребрами графа.
Прежде всего стоит сказать о том, что графы, о которых пойдет речь, к аристократам былых времен никакого отношения не имеют. Наши "графы" имеют корнем греческое слово "графо", что значит "пишу". Тот же корень в словах "график", "биография", "голография", география.
Точки А, Б, В, Г, Д, Е называются вершинами графа, соединяющие их отрезки – ребрами графа.
Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом. Ребер у этого графа осталось 8. Значит, осталось провести 8 игр.
Сейчас почти в любой отрасли науки и техники встречаешься с графами.
Внимание на доску.
Примеры графов:
- схема метро;
- генеалогическое древо;
- кристаллическая решетка;
- электрическая схема и другие.
Придумайте свои примеры графов.
В качестве примеров ученики могут привести следующие примеры: схемы железных и автомобильных дорог, тепло– и электросети, дерево каталогов, планы выставок и другие.
Графы широко используются в современной математике и программировании. С теорией графов связаны не только математические головоломки, но и такие серьезные науки, как теория отношений и теория групп. Графы находят все новые приложения в теории планирования и управления, теории расписаний, социологии, математической лингвистике, биологии и медицине.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез, это сравнительно молодая наука: во времена Ньютона такой науки еще не было, хотя и были "генеалогические деревья", представляющие собой разновидности графов.
3. Этап закрепления новых знаний
1. Рассмотрим задачу: 5 друзей при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Обменяйтесь, пожалуйста, рукопожатиями. Сколько всего рукопожатий было сделано?
Решение демонстрируется на доске. Задача легко решается с помощью теории графов.
Изобразите в тетради 5 точек: А, Б, В, Г, Д.
Сколько всего рукопожатий было сделано?
К решению можно прийти чисто логически. Но графы придали наглядность, упростили решение.
Если подвести итог, то можно утверждать: если полный граф имеет n вершин, то количество ребер будет равно n(n - 1)/2.
2. Хочу предложить вам решить задачу – загадку. Перед вами граф – "распечатанное письмо". Попробуйте начертить этот граф не отрывая карандаша от бумаги и не проводя по одной линии дважды.
Тот, у кого получилось, может выйти к доске и записать маршрут обхода.
В какой вершине вы начали движение? В какой закончили? (Начала в А, закончила в Е)
Есть другие варианты? (Да, я начал в Е, закончил в А)
Не расстраивайтесь. Мы сейчас с вами выведем алгоритм для решения этой задачи. Для этого нам нужно будет перенестись на более чем 200 лет назад и оказаться вместе с великим математиком Леонардом Эйлером в городе Кенигсберге (сейчас этот город называется Калининград).
На доске портрет Леонарда Эйлера. Что вы знаете о Леонарде Эйлере?
3. Историческая справка (сообщение ученика)
Леонард Эйлер (1707-1783) – математик, механик, физик и астроном. Ученый необычайной широты интересов. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и других, оказавших значительное влияние на развитие науки. Леонард Эйлер по происхождению швейцарец. В 1726г. был приглашен работать в Петербург, в 1727г. переехал жить в Россию. Являлся академиком, а затем почетным членом Петербургской академии наук.
Первая работа по теории графов принадлежит именно ему (1736), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. В начале 20 века наряду с термином «граф» употреблялись другие термины, например карта, комплекс, диаграмма, сеть, лабиринт.
4. Задача о Кёнигсбергских мостах.
Бывший Кёнигсберг расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз. До Эйлера никто не мог этого сделать, но и доказать, что это невозможно, тоже ни у кого не получалось. Как поступил Эйлер?
Попробуйте найти нужный ответ и выдвиньте свою гипотезу. Через 3 минуты слушаем гипотезы.
Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход он начертил упрощенную схему мостов. Получился граф, вершины которого – части города, разделенные рекой, а ребра – мосты.
Попробуйте провести линии по всем ребрам -"мостам", не отрывая карандаша от бумаги. У кого получилось? Таких нет? У Эйлера тоже не получилось.. А вы знаете почему? Оказывается все дело в числе ребер, сходящихся в вершине. Давайте посчитаем, сколько ребер сходится в каждой вершине графа. Напишите рядом с каждой вершиной число, отражающее количество ребер, в ней сходящихся, и назовем вершину четной или нечетной в зависимости от того, какое число, четное или нечетное, стоит рядом. Итак, в вершине А сходится 5 ребер, в вершине В-3, в вершине С-3, в вершине Д-3. Какими являются все эти вершины? (Нечетными.)
Леонард Эйлер сформулировал правило:
Обход возможен:
- ЕСЛИ все вершины – четные, и его можно начать с любого участка.
- ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных вершин.
Обход невозможен если нечетных вершин больше 2.
Во время прогулки по городу нельзя пройти по всем семи мостам, проходя по каждому только один раз.
5. Давайте вернемся к задаче "распечатанное письмо" и применим правило Эйлера.
– Сколько ребер сходится в каждой вершине? (В вершине А сходится 3 ребра, в вершине В-4, в вершине С-2, в вершине Д-4.)
– Что вы скажите о четности вершин в этом графе? ( Три вершины – четные, две – нечетные.)
– Как нужно совершить обход этого графа, согласно правилу Эйлера? (Начать обход в одной из нечетных вершин А или Е, а завершить в другой.)
6. Вычерчивание фигур одним росчерком
Итак, мы увидели, что на языке теории графов каждая решенная задача выглядит как задача изображения "одним росчерком" графа, представленного на рисунке.
Теперь нам нетрудно будет разобраться и показать, какую из любых данных фигур можно вычертить одним росчерком, без повторения линий, а какую нет. Каждую из задач подобного рода можно свести к разобранной уже нами Эйлеровой задаче о мостах.
Например, на рисунке изображена птица.
Взяв за вершины графа точки пересечения линии, получим 7 вершин, только две из которых имеют нечетную степень.
Поэтому в этом графе существует эйлеров путь, а значит, птицу можно нарисовать одним росчерком.
Нечетные вершины: две.
4. Итог урока
Учитель выясняет у детей, на все ли вопросы они получили интересующие их ответы, а также сообщает, что с остальными видами задач знакомство будет продолжено на следующем уроке.
- Белая шляпа – мыслим фактами, цифрами
- Желтая шляпа – позитивное мышление (что именно было полезно, хорошо и т.д., почему)
- Черная шляпа- противоположность желтой шляпе (что было трудно, неясно, негативно и т.д., почему)
- Красная шляпа – эмоциональное состояние (грусть, радость, интерес, удивление, агрессия, раздражение)
- Зеленая шляпа – творческое мышление (что можно изменить, применить, усовершенствовать и т.д.)
- Синяя шляпа – философская, обобщающая.
На сегодняшнем уроке мы познакомились с основными понятиями теории графов, примерами графов и их использованием в различных областях знаний, а также применением графов при решении различных задач.
5. Домашнее задание
- Изобразите свое генеалогическое дерево.
- Можно ли фигуру, изображенную на рисунке, нарисовать одним росчерком? (решить с помощью графа)