Презентация Решение задач по теме Графы. Поиск путей с применением опорных схем

Простой и наглядный способ решения задач из тестов ЕГЭ и ГИА по теме «Графы. Поиск путей» с применением опорных схем. 

Предложенные в 2012 году ФИПИ для исследования задачи с применением теории графов показались ученикам, которые сдают в этом году экзамен в форме ЕГЭ и ГИА, достаточно сложными даже для высокого уровня заданий.  Те решения задач по этой теме, которые предлагались нам другими авторами были хороши, но детей из обычных общеобразовательных классов они тоже не устроили – не привыкли они к простой и красивой академичности изложения материала. Понадобились более наглядные и привычные способы решения задач.  Учитель, готовивший учеников к экзамену, предпринял такую попытку, и она оказалась удачной – ученики с увлечением стали рисовать несложные схемы-решения и «как орешки щёлкать задачи» по этой теме.  Попробуйте и вы.

Решение задач по теме «Графы. Поиск путей» с применением опорных схем

Автор: учитель информатики и ИКТ МОУ СОШ №58

г. Нижнего Новгорода Иванцова Светлана Анатольевна

2012 г.

Задача 1:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение (опорная схема):

Пусть П А – путь из города А . Соответственно, П Х – путь из некого города Х .

Идея метода: заменять пути П Х на те, которые ближе к городу А (см. схему на следующем слайде). Начнем движение с конца маршрута (с города К ), к которому ведут четыре пути: П И , П Д , П Ж , П Е

В город И есть только один путь – из города Д , поэтому заменяем путь П И на тот, который ближе к городу А , т.е. на П Д . Отметим: П И = П Д

Также поступаем в направлении города Е : П Е = П Г = П А

В город Ж ведут два пути: П В и П Е . Мы уже выполнили замену: П Е = П Г = П А

В город В ведут три пути, для некоторых из которых уже возможна замена: П Б = П А , П А , П Г = П А . Следовательно, путь П В = 3* П А . В город Д идут два пути, для которых уже есть замена: П Б = П А и П В = 3* П А . Посчитаем пути П А .

Количество различных путей из города А равно 2*4* П А + 3* П А + П А + П А = 13

Продолжение:

Количество различных путей из города А равно: 2*4* П А + 3* П А + П А + П А = 13 Ответ: 13

К

П И = П Д П Д П Ж П Е = П Г = П А

2*П Д

П В

П Е = П Г = П А

2*(П Б = П А П В = 3* П А ) П Б = П А П А П Г = П А

3* П А

Задача 2:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение (опорная схема):

Пусть П А – путь из города А . Соответственно, П Х – путь из некого города Х .

Идея метода: заменять пути П Х на те, которые ближе к городу А (см. схему на следующем слайде). Начнем движение с конца маршрута (с города К ), к которому ведут четыре пути: П Е , П Ж , П З , П И

В город Е есть только один путь – из города Б , поэтому заменяем путь П Е на тот, который ближе к городу А , т.е. на П Б . Отметим: П Е = П Б . Следуя тому же правилу, делаем вывод: П Е = П Б = П А . По аналогии - в направлении города И : П И = П Д = П А

Также поступаем в направлении города Ж : П Ж = П В

В город В ведут три пути: П Б , П А , П Г , причём П Б = П А , а П Г = 2* П А

В город З ведут два пути: П Г и П Ж , для каждого из которых уже можно выполнить замену: П Г = 2* П А и П Ж = П В = 4* П А . На схеме считаем пути П А .

Количество различных путей из города А равно: П А + П А + П А + 2* П А + 2* П А + 4* П А + П А = 12

Продолжение:

К

П Е = П Б = П А П Ж = П В П З П И = П Д = П А

П Г = 2* П А

П Ж = П В = 4* П А

П Б = П А П А П Г

П А = П Д

Количество различных путей из города А равно: П А + П А + П А + 2* П А + 2* П А + 4* П А + П А = 12

Ответ: 12

2* П А