открытый урок Грфы
план-конспект урока

Тема: Графы. Использование графов для решения прикладных задач в агрономии

Цели:

- Предметные:

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

- Личностные:

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

- Метапредметные: развитие универсальных учебных действий

Регулятивные:

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

Коммуникативные:

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

Познавательные:

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

Тип урока: обобщения и систематизации знаний, проблемноориентированый

Виды работ: фронтальная беседа, работа в группах, обсуждение, доклады, тест.

Оборудование: доска, презентация, раздаточный материал.

ПЛАН УРОКА

1. Организационный момент, приветствие - 2 минуты
2. Проверка домашнего задания – 1 минута;
3. Доклад историческая справка 3 минуты;
4. Новый материал 6 минут
5. Постановка проблемы – 2 минуты;
6. Анализ проблемной ситуации и возможные пути ее решения – 1 минуты;
7. Актуализация опорных знаний, умений, навыков, которые потребуются для решения поставленных задач на уроке - 5 минуты;
8. Возврат к проблемной ситуации с задачей и обсуждение способов решения – 2 минуты;
9. Решение задачи – 10 минут;
10. Анализ результатов - 3 минуты;
11. Тест 6 минут;
12. Подведение итогов урока - 2 минуты;
13. Домашнее задание - 2 минуты;

ХОД УРОКА

1/Приветствие. Здравствуйте, ребята!

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

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

3/Доклад

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

4/ материал

Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами.

Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.

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

Количество ребер, выходящих из одной вершины, называют степенью этой вершины.

Свойства графов:

Граф может быть пустым, то есть не содержать ни одной вершины или ребра.

Граф может быть ориентированным, когда ребра имеют направление, или неориентированным, когда ребра не имеют направления.

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

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

Граф может быть ациклическим, когда в нем нет циклов, или циклическим, когда в нем есть циклы.

В любом графе есть по крайней мере две вершины, имеющие одинаковую степень.

Сумма степеней всех вершин графа равна удвоенному числу его ребер.

5/Постановка проблемы.

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

Задача 1. На рисунке справа изображена схема дорог Коломенского района от мест сбора зерна с полей во время сбора урожая до элеватора, схема изображена в виде графа; в таблице

слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Рис. 4: Граф дорог Коломенского района.

Так как таблицу и схему рисовали независимо друг от друга, то нумерация пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б(сбор зерновых) в пункт В(элеватор). В ответе запишите целое число — так, как оно указано в таблице.

6/Анализ проблемной ситуации и возможные пути ее решения

На слайде вопросы:

- Можем ли мы сразу решить эту задачу, только посмотрев на схему? (ожидаемый ответ: нет)

- Что нам мешает решить задачу? (ожидаемый ответ: слишком много возможных вариантов, нужно проследить каждый маршрут, в которых легко запутаться)

- А что из изученного нами поможет решить эту задачу? (Ожидаемый ответ: графы)

Совершенно верно, данная схема представляет собой граф дорог. И тема нашего урока «Решение задач с помощью графов»

Давайте с вами вспомним, что же такое граф и какие бывают графы.

7/Актуализация (фронтальный опрос):

На слайде вопросы к актуализации.

- Что такое граф?

- Из каких объектов состоит граф? (Ожидаемый ответ: ребра, вершины)

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

- Наш граф является взвешенным или нет? (Ожидаемый ответ: взвешенным)

- Что является весом ребер в графе? (Ожидаемый ответ: время пути между пунктами в минутах)

- Чем отличается ориентированный граф, от неориентированного? (Ожидаемый ответ: в ориентированных графах указывается направление пути)

- Наш граф является ориентированным или нет? (Ожидаемый ответ: неориентированным)

- Что такое дерево? (Ожидаемый ответ: Дерево – это граф, представленный в виде иерархической системы)

8/Возврат к проблемной ситуации и обсуждения способа ее решения

Вернемся к нашей задаче и посмотрим на нее внимательно. Как можно решить эту задачу?

9/Решение. Из рисунка видно, что у вершины Е есть ровно один сосед — вершина Д, причём

никакая другая вершина не обладает таким свойством. Найдём в таблице вершину с единственным соседом. Это вершина П3, а её сосед — П4. Следовательно, П3 = Е, П4 = Д. Точно так же

мы замечаем, что только В и П5 имеют по четыре соседа. Следовательно, П5 = В. У вершины

Д есть ещё один сосед, помимо В и Е, — это вершина Г. Третьим соседом вершины П4 является

П2, значит, П2 = Г. Наконец, мы заметим, что только А и П6 имеют по два соседа, поэтому

П6 = А. Остаётся только одна нерассмотренная вершина, следовательно, П1 = Б.

Итак, мы доказали, что П1 = Б, П5 = В. Следовательно, длина дороги из Б в В равна 8.

Ответ: 8.

10/Анализ результатов

Зачитывает один из учеников, что у него получилось Результат записывается на доске.

Учитель: У всех так получилось? Есть те, у кого получились другие варианты? Кто не успел выполнить задание?

На слайде демонстрируются правильные результаты:

11/Тест

1) Конечная совокупность вершин, некоторые из которых соединены ребрами – это

1матрица

2 граф

3 петля

2) Как называется таблица, в которой хранится информация об узлах и связях графа?

1 Двумерная матрица

2 весовая матрица

3 матрица смежности

3) Что означает единица на главной диагонали смежной матрицы?

1 Между узлами нет связи

2 Между узлами есть связь

3 Имеется петля

4) Какой граф называют взвешенным?

1 Построенный с помощью дуг

2 Построенный с помощью ребер

3 На ребрах несущий дополнительную информацию

5) Если для каждого ребра в графе указанно направление, то граф

1 Ориентированный

2 Весовой

3 Содержит петлю

Ответы 1) – 2 2) – 3 3) – 3 4) – 3 5) – 1

12/Подведение итогов и оценивание

Рефлексия - Понравились вам задачи? - оценивание

Закончить наш урок я хочу словами Бернара Вербера «Дорога, которая раньше была почти непроходимой, теперь кажется лёгкой: все препятствия, однажды преодолённые, нам уже не страшны». Я надеюсь, что знания полученные сегодня на уроке помогут вам в будущей работе.

13/осталось домашнее задание. (раздаточный материал)

Задача 2. Между пунктами животноводческое хозяйство «Ступино», молокозаводом «Непецино», и магазинами молочной продукции в г. Коломна (A, B, C, D, E, F, G) построены дороги, протяжённость

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

пунктами нет.

Определите длину кратчайшего пути между пунктами животноводческое хозяйство «Ступино» и молокозаводом «Непецино», ( A и G )(при условии, что передвигаться можно только по построенным дорогам).

Решение. Для наглядности изобразим граф в виде рисунка (см. рис. 5). Сразу видно, что есть

путь из A в G из одного ребра длины 25. Поищем более короткие пути. Поскольку длины всех

рёбер положительны, то кратчайший путь не может содержать циклов. Кратчайший путь из A

в B имеет длину 5 (это одно ребро), так как любое другое выходящее из A ребро имеет большую

длину. Кратчайший путь из A в D имеет длину 12 (тоже одно ребро), так как единственный

альтернативный путь A → B → D имеет длину 13. Поэтому кратчайший путь из A в C имеет

длину 14 (A → D → C). Из C в G ведут три пути (без циклов): путь C → E → G длины 9, путь

C → G длины 10 и путь C → F → G длины 15. Кратчайший из них имеет длину 9. Поэтому

длина кратчайшего «обходного» пути из A в G равна 14 + 9 = 23 < 25. Значит, кратчайший

путь из A в G имеет длину 23.

Ответ: 23.

Самостоятельная работа.

Упражнение 1. Неориентированный граф задан в виде рисунка и в виде таблицы. Установите

соответствие между вершинами этих представлений графа.

Рис. 8: Граф из упражнения 1.

Упражнение 2. Нагруженный неориентированный граф задан в виде рисунка и в виде таблицы. Чему равна длина ребра, соединяющего вершины B и D?

Рис. 9: Граф из упражнения 2.

Упражнение 3. Неориентированный граф задан таблицей. Найдите длину кратчайшего пути

из вершины A в вершину D.

Рис. 10: Граф из упражнения 3.

Упражнение 4. Ориентированный граф задан таблицей. Найдите длины кратчайших путей

из B в E и из E в B.

Рис. 11: Граф из упражнения 4.

14/Проверка задания 2 минуты;

Указания к упражнениям.

Упражнение 1.

Используйте метод из решения задачи 1.

Может оказаться, что на некотором шаге не удаётся найти две соответствующие друг другу вершины. Тогда нужно попытаться использовать дополнительную информацию. Например, если оказалось, что вершины А, Б совпадают с вершинами П1, П2 (без учёта порядка), а вершины А, В — с вершинами П2, П3 (тоже без учёта порядка), то А = П2, так как только эти две вершины встречаются по два раза.

Ответ: A = 2, B = 5, C = 4, D = 7, E = 1, F = 3, G = 6.

Упражнение 2.

В задаче не требуется установить соответствие между вершинами. Нужно лишь найти длину ребра, соединяющего B и D. Само ребро не обязательно определяется однозначно.

Ответ: 5.

Упражнение 3. Используйте тот же метод, что и в задаче 2: последовательно вычислять

длины кратчайших путей из A до других вершин.

Ответ: 20.

Упражнение 4. Используйте тот же метод, что и в задаче 2. Единственное отличие состоит в

том, что теперь граф ориентированный, поэтому по рёбрам можно идти лишь в одну сторону.

Следовательно, длины кратчайших путей из B в E и из E в B могут быть разными.

Ответ: из B в E 10, из E в B 7.

Упражнение 5.

а) Используйте алгоритм.

б) Если пути не проходят через L, то L с входящими в неё и выходящими из неё рёбрами можно

удалить из графа. После этого нужно решить задачу для оставшегося графа.

в) Используйте алгоритм и теорему об умножении.

г) Используйте ту же идею, что и в алгоритме для поиска числа всех путей. Нужно запоминать

только те пути, длина которых максимальна.

Ответ: а) 59; б) 8; в) 15; г) 12 путей длины 7