Раздел внеклассная работа ;Применение графов к решению задач. (конспект занятия)
план-конспект урока по математике (5 класс)

Тема: «Применение графов к решению задач»

Дмитриева Елена Александровна, учитель математики,

г. Москва, школа №962

Раздел: внеклассная работа по математике в 5-6 классах

Цель занятия:

1. научить учащихся видеть граф в условии задачи и грамотно переводить условие на язык теории графов;
2. дать теорию;
3. показать учащимся, как графы облегчают решение задачи, делая его простым, наглядным, доступным.

Ход занятия

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

Задача

Я задумала число. Если его разделить на 2, полученное частное уменьшить в 3 раза, а потом результат разделить на 5, и, наконец, полученное частное уменьшить в 10 раз, то получится число 1.

Решение

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

1∙10=10; 10∙5=50; 50∙3=150; 150∙2=300

2 способ

Видно, что решать задачу следует с конца, заменяя каждое действие на обратное ему.

Ответ: 300.

Задача

Несколько друзей встретились на автовокзале, чтобы поехать за город. При встрече все они поздоровались друг с другом за руку. Сколько друзей поехало за город, если всего было 10 рукопожатий.

Решение

Выполним рисунок. Точки будут изображать друзей, а отрезки – рукопожатия.

Мы видим, что встретились 5 друзей.

Фигуры, получившиеся при решении этих 2-х задач, состоят из точек и линий, соединяющих эти точки. Такую фигуру называют графом. Линии называют ребрами, точки – вершины. В графе необязательно, чтобы каждая вершина была соединена с остальными.

Например

Если в графе ни одна часть не является замкнутой линией, то такой граф называют деревом.

Графы помогают решать задачи.

2. Решение задач

№1. В первом матче футболисты «Факела» забили в ворота противника половину мечей, забитых или во втором матче и ещё один мяч. Во втором матче они забили вдвое меньше мячей, чем в третьем матче, и ещё один мяч. Сколько мячей забили футболисты за 3 матча?

Решение

№2. Дядя Петя принёс корзину груш на базар. Первому покупателю он продал половину всех груш и ещё 1 грушу. Второму – половину остатка и ещё 1 грушу, третьему – половину нового остатка и ещё одну грушу и т.д. Последнему седьмому покупателю он также продал половину оставшихся груш и еще 1 грушу, причем оказалось, что он продал все груши. Сколько груш принёс дядя Петя на базар?

Решение

1. Составим граф

Решаем обратно.

Ответ: 254 груши.

№3 На вопрос путника «Сколько у тебя в стаде голов скота?» - пастух ответил: «Если к моему стаду добавить одну корову, то третью часть всего стада составляли бы овцы и козы. Если бы к имеющимся овцам и козам добавить одну овцу, то седьмую часть их составляли бы козы, в которых третья часть есть лишь один маленький козлёнок». Сколько голов скота было бы в стаде?

Решение

Составим граф к условию задачи.

Решаем обратно:

Ответ: 59 голов.

№4. В таблице приведены расстояния между четырьмя поселками. Если пересечение строки и столбца пусто, то между поселками дороги нет. Изобразите схематически приведенную дорожную систему. С помощью графа определите кратчайший путь из A в D.

Решение

Поставим произвольно точки по количеству A, B, C и D.

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

Из A в D существуют два пути:

A – B – C – D = 3 + 4 + 6 = 13

A – B – D = 3 + 8 = 11 – кратчайший путь из A в D.

№5. Сколько существует трехзначных чисел, составленных из цифр 8, 5, 4, при условии, что каждая цифра используется только один раз?

Решение

Составим граф.

Получим следующие числа: 854, 845, 584, 548, 485, 458.

№6. Из города M в город N ведут три дороги, а из города N в город C – четыре дороги. Сколькими способами можно проехать из M в C?

Решение

Представим условие задачи в виде графов.

Возьмём одну дорогу из M в N. Её можно проложить до C 4 разными способами. Тоже самое можно сделать с каждой из 2-х других дорог, ведущих из M в N. Всего из M в C через N можно проехать 3 ∙ 4 = 12 способами.

№7. Клоуны Бам, Бим и Бом вышли на арену в красной, синей и зелёной рубашках. Их туфли тоже были этих 3-х цветов. Туфли и рубашка Бима были одного цвета. На Боме не было ничего красного. Туфли Бама были синие, а рубашка нет. Каких цветов были туфли и рубашка у Бома и Бима?

Решение

Ответ: Бом – зеленые туфли и синяя рубашка, Бам – синие туфли и зеленая рубашка.

№8. Три друга после школы едут домой на различном транспорте: автобус, троллейбус и трамвай. Однажды после уроков Алеша пошел провожать своего друга до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крикнул из окна: «Боря, ты забыл в школе тетрадку!».

Решение

Нарисуем граф.

3. Задание на дом

Использование теории графов для решения заданий ЕГЭ.

Между населенными пунктами A, B, C, D, E и F построены дороги, протяженность которых приведена в таблице (отсутствие числа означает, что прямой дороги нет). Определить длину кратчайшего пути между пунктами E и F (передвигаться можно только по построенным дорогам).

Список литературы

1. Лекции по теории графов / Емилечев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, 1990. – 384 с.
2. Оре О. Графы и их применение / Пер. с англ. Л. И. Головиной ; под ред. И. М. Яглома. — М. : Мир, 1965. — 175 с.
3. Конечные графы и сети / Басакер Р., Саатл Т. – М.: Наука, 1973. – 363 с.
4. Робин Уилсон. Введение в теорию графов. // СПб: ООО «Диалектика», 2019. — 240 с.
5. Татт У. - Теория графов / Пер. с англ. - М.: Мир, 1988. - 424 с.
6. Задачи для внеклассной работы по математике в V—VI классах: Пособие для учителей/ Сост, В. Ю. Сафонова. Под ред. Д. Б. Фукса, А. Л. Гавронского. - М.: МИРОС, 1993.— 72 с
7. Германович П.Ю. Сборник задач по математике на сообразительность. Пособие для учителей. - М.: УЧПЕДГИЗ, 1960. — 224 c.
8. Гарднер М. Есть идея – М.: Мир, 1982. – 304 с.
9. Решу ОГЭ, сайт Д. Гущина - URL: https://oge.sdamgia.ru/
10. Зубелевич Г.И. Сборник московских математических олимпиад. – М.: Просвещение, 1980.
11. Севрюков, П. Ф. Подготовка к решению олимпиадных задач по математике / П. Ф. Севрюков. — Изд. 2-е. — М.: Илекса; Народное образование; Ставрополь: Сервисшкола, 2009. - 112 с.