Решение задач с помощью графов

Решение задач с помощью графов 5 класс.

Цели:

Образовательные:

• закрепить понятие графа и отработать навыки использования графов для решения задач;

• проверить уровень усвоения понятия графа через умение применять имеющиеся знания для решения новых задач.

Развивающие:

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

• формировать активный познавательный интерес к предмету.

Воспитательная:

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

ПЛАН УРОКА

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

2. Проверка домашнего задания

"Жизнь украшается двумя вопросами: занятием математикой и ее преподаванием" Пуассон С.II.

Изучение математики осуществляется в процессе решения задач и упражнений.

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

Начнем с домашней задачи на проценты

5 литров сливок с содержанием жира 35% смешали с 4 литрами 20% сливок и к смеси добавили 1 литр чистой воды. Какой жирности получилась смесь?

1. 5∙ 0,35 = 1,75 литров жира в 5 литрах сливок

2. 4∙ 0,20 = 0,8 литров жира в 4 литрах

3. 1,75 + 0,8 = 2,55 литров жира в смеси

4. 5 + 4+1 = 10 литров смесь

5. 2,55: 10 = 0,255 литров = 25,5% жирность смеси

3 Устный счет

Проведем игру: „Лучший счетчик „(на оценку).

Выберите по 2 счетчика с каждого ряда.

Еще Песталоцци говорил: „Счет и вычисления — основа порядка в голове„

Выясним — Кто из вас правильно ответит на большее количество вопросов. Ребята, помогайте — считайте правильные ответы своих ребят.

Игра «Счетчик»

1) Физик, устав, лег спать в 10 часов вечера; предварительно завел будильник на 12 часов следующего дня. Сколько часов он успел проспать, прежде чем будильник его разбудит? [ 2]

2) Сколько месяцев в году содержат по 30 дней? (Все, кроме февраля).

3) Вот вам 3 пилюли - сказал доктор. Принимайте по 1 через каждые полчаса. На сколько вам хватит прописанных доктором пилюль? (1ч.)

4) Какой будет остаток от деления произведения на 6

( 67*669*6668)/6

67=1 (Мод 6) (Это задание на арифметику остатков)

1*3*2=6=0 (Мод 6)

5) Найди остаток от деления на 5 следующей суммы (7+56+558+5558)/5

(2+1+3+3)=9=4 (Мод 5)

6) Решить ур — е: (((х+2)/4)-2)*6=12 [14]

7) Найди число, если 3% от него 24 [800]

8) 17.2% от 50 [8.6]

9) 3000% от 50 [1500]

10) Найди процентное отношение чисел 48 к 16 [300%]

12 к 60 [20%]

11) Вычислите 0.1% от 700 [0.7]

Победили все, потому что все участвовали вместе с ними и проверяли правильность ответов.

4)Выдающаяся женщина - математик Ковалевская подчеркивала: „У математиков

существует свой язык — это формулы„

Задачи, решаемые с конца

(сценка) „Крестьянин и черт„:

Идет крестьянин и плачется: „Эхма! Жизнь моя горькая! Заела нужда совсем! Вот в кармане только несколько грошей медных болтается, да и те сейчас нужно отдать. И как это у других бывает, что на всякие деньги они еще деньги получают? Право, хоть бы кто помочь мне захотел„.

Только успел это сказать, как глядь, а перед ним черт стоит.

-Что ж, - говорит, - если хочешь, я тебе помогу. И это совсем нетрудно. Вот видишь этот мост через реку?

-Вижу! — говорит крестьянин, а сам заробел.

-Ну, так стоит тебе перейти только через мост — у тебя будет вдвое больше денег, чем есть. Перейдешь назад, опять станет вдвое больше, чем было. И каждый раз, как ты будешь переходить мост, у тебя будет вдвое больше денег, чем было до этого перехода.

-Ой ли? — говорит крестьянин.

-Верное слово! — уверяет черт. — Только, чур, уговор! За то, что я тебе удваиваю деньги, ты каждый раз, перейдя через мост, отдавай мне по 24 копейки. Иначе не согласен.

-Ну, что же, это не беда! — говорит крестьянин. — Раз деньги все будут удваиваться, так отчего же 24 копейки тебе каждый раз не отдать? Ну- ка, попробуем!

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

Сколько же у крестьянина было денег сначала?

1. ((х 2 — 24) 2 — 24) 2 — 24 = 0 х= 21

Если после последнего перехода у крестьянина оказалось 24, то до того было 12, к ним прибавим 24, ( которые он отдал) получим 36 значит до второго перехода было 38 коп. К ним прибавил 24 получим 42, значит было 21 коп.

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

5. Задачи на графы.

Теория графов находит применение, не только в математике, но например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Первый тип задач

«Кто играет Ляпкина-Тяпкина?»

В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Всё началось с Ляпкина-Тяпкина. — Ляпкин-Тяпкин буду я! - решительно заявил Гена.

— Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима.

— С раннего детства мечтал воплотить этот образ на сцене.

— Ну, хорошо, согласен уступить роль, если мне дадут сыграть Хлестакова,- проявил великодушие Гена.

— ...А мне — Осипа, - не уступил ему в великодушии Дима. — Хочу быть Земляникой или Городничим, - сказал Вова.

— Нет, городничим буду я, - хором закричали Алик и Боря. — Или Хлестаковым, - добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны? (Мы не спрашиваем, будут ли довольны зрители.)

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

Гена Дима Вова Боря Алик

Городничий

Лячпкин- Хлестаков Осип Земляника

Тяпкин

Сделать это легко. Достаточно заметить, в вершины 3 и 4 ведет по одному ребру, из вершин ДиВ соответственно. Это означает, что Осипа (вершина 3) должен играть Дима (кто же еще), а Землянику-Вова. Вершина 1- Ляпкин- Тяпкин-соединена ребрами с Г и Д. Ребро 1- Д отпадает, так как Дима уже занят, остается ребро 1- Г, Ляпкина- Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребра А — 5 и Б- 2,либо ребра А-2 и Б-5. В первом случае Алик будет играть Городничего, а Боря-Хлестакова, во втором случае наоборот. Как показывает наш граф, других решений задача не имеет.

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

Одним из крупнейших математиков XVIII века был Леонард Эйлер. Он родился в швейцарском городе Базеле, где в 15 лет закончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения.

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

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

1. Известен анекдот: Некто давал 1000000 рублей каждому, кто начертит следующую фигуру.

Требование: одним непрерывным росчерком т. е. не отнимая пера или карандаша от бумаги и не удваивая ни одной линии.

2
. Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из

двух рогов Луны знак, представленный на рисунке. Как он это делал, подумай дома, пронумеруйте точки.

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

4. Муха забралась в банку из-под сахара . Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 рёбер куба, не проходя дважды по одному ребру, Подпрыгивать и перелетать с места на места на место не разрешается.

(рис. 4)

Нивен отмечал: „Математику нельзя изучать, наблюдая как это делает сосед „

6. Домашнее задание: Можно ли фигуры, изображенные на рисунках, нарисовать одним росчерком? (решить с помощью графа)

Итог урока:

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

Поучительная сторона этих задач состоит в исследовании, возможно или нет решение данной задачи, прежде чем приниматься за само решение.

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

А в заключение хочу сказать следующие слова: «В задачах, которые ставит перед нами жизнь, экзаменатором является сама природа.