Решение задач с применением графа

ВИЗИТНАЯ КАРТОЧКА УРОКА

Структура урока:

Ход урока

1.Организационный момент. Здравствуйте, друзья. Сегодня хотелось начать наш урок со слов Шарля де Голля, французского генерала второй мировой войны и выдающегося политика. "Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов!".

2. Постановка проблемы. Формулирование условия задачи и предложение решить ее сразу (1 мин).

Говоря о выборе путей, предлагаю вам решить следующую задачу:

Предлагайте решения (учащиеся предлагают решения задачи: методом рассуждения).

3. Анализ проблемной ситуации и возможные пути ее решения (2 мин)

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

В геометрии, при решении некоторых задач удобно использовать чертежи (слайд задача показывается в текстовом виде, затем в графическом). А что в информатике позволяет представить условия задачи в графическом виде? (графы). Вспомним, что такое графы. Где в повседневной жизни мы можем столкнуться с графами (навигаторы в машинах, при построении маршрутов на уроках географии, при поездках,

4. Актуализация опорных знаний, умений, навыков, которые потребуются для решения поставленных задач на уроке (5 мин).

Граф - это множество точек или вершин и линий или ребер, соединяющих между собой все или часть этих точек. Граф - это информационная модель объекта или системы объектов.

Какие виды графов вы знаете?

ориентированные (графы, ребрам которых присвоено направление), неориентированные (графы, ребрам которых направление не присвоено). А сейчас давайте с вами определим тему нашего урока, для этого я предлагаю вам следующие высказывания:

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

«Когда человек не знает, к какой пристани он держит путь, для него ни один ветер не будет попутным.» Сенека

«От великого до смешного один шаг, но от смешного уже нет пути к великому.»

Лион Фейхтвангер

«Ковыляющий по прямой дороге опередит бегущего, который сбился с пути.» Фрэнсис Бэкон.

«Три пути у человека, чтобы разумно поступать: первый, самый благородный, – размышление; второй, самый легкий, – подражание; третий, самый горький, – опыт.»

5. Формулирование темы урока учащимися самостоятельно (1 мин)

Т.е. тема урока определение путей или если говорить точнее "Пути в графах".

6. Возврат к проблемной ситуации с задачей и актуализация целей и задач на предстоящем уроке. Учащиеся сами формулируют цели и задачи (1 мин). А цели и задачи урока следующие (учащиеся предлагают):

как преобразовать информацию, представленню в табличной форме в граф;

какопределить все пути в графе;

какопределить кратчайший путь.

7. Разбор задачи с таблицей и преобразование ее в граф. Обход графа и поиск всех возможных путей с вычислением длины пути (15 мин)

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

Проанализируем таблицу.

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

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

(строим все направления).

Определим пути в графе и расстояние, пройденное на этом пути. После просмотра всех путей и нахождения их длин, определяем, что кратчайшим путем будет ABDCE.

8. Постановка задачи из демоверсии и ее решение учащимися у доски (5 мин).

Пожалуйста, еще одна подобная задача, желающий выйти и решить ее на доске (выходит учащийся).

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

Указываем все пути в алфавитном порядке:

1.ABCDF - 14 км

2.ABCEF - 15 км

3.ACDF - 13 км

4.ACEF - 14 км

5.AF - 15 км

9. Демонстрация задачи из демоверсии ОГЭ 2017 года без решения (1 мин)

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

Проведем анализ данной таблицы.

Мы видим, что из точки А мы можем попасть только в В и в точку F ведет только один путь из точке Е. Фактические решение задачи сводится к нахождению кратчайшего пути из В вE, что упрощает решение данной задачи.

10. Выполнение самостоятельной работы по карточкам(10 мин)

11. Подведение итогов урока (2 мин)

На сегодняшнем уроке мы с вами вспомнили, что такое граф и типы графов

научились строить графы и определять пути в нем на основе табличной модели;

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

Выставление оценок учащимся на основе их самооценки и оценок учителя.

13. Домашнее задание (1 мин)

Домашнее задание указано на доске. Выпишите себе условие задачи в тетради.

Приложение 1

1.Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це:

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

 1) 5

2) 6

3) 7

4) 8

2.Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це:

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

 1) 6

2) 7

3) 8

4) 9

3.Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це:

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

 1) 6

2) 7

3) 8

4) 9

4.Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це:

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

 1) 6

2) 7

3) 8

4) 9

5.Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны до­ро­ги, про­тяжённость ко­то­рых (в ки­ло­мет­рах) при­ве­де­на в таб­ли­це:

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

1) 4

2) 5

3) 6

4) 7

15.У Кати Ев­ту­шен­ко род­ствен­ни­ки живут в 5 раз­ных го­ро­дах Рос­сии. Рас­сто­я­ния между го­. ро­да­ми вне­се­ны в таб­ли­цу:

 Катя пе­ре­ри­со­вала её в блок­нот в виде графа. Счи­тая, что де­воч­ка не ошиб­лась при ко­пи­ро­ва­нии, ука­жи­те, какой граф у Кати в тет­ра­ди.

 1)

2)

3)

4)