Использование графов при решении задач ОГЭ
статья по информатике и икт (9 класс) на тему

Использование графов при решении задач ОГЭ

Задача 11

Рассмотрим задачу № 11 из Демонстрационного варианта 2017 г. по Информатике

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По

каждой дороге можно двигаться только в одном направлении, указанном

стрелкой. Сколько существует различных путей из города А в город К?

При решении удобно построить дерево цепочек путей из города А в город К. Всего существует 4 направления из пункта А

Строим 1 цепь начиная с верхней части схемы. Мы видим, что цепочка разветвляется из города Б. Строим все цепочки путей из данного города и видим, что таких цепочек 4

A→Б→Е→К

              В→К

                     Г→К

                            Ж→К

Причем делаем пометку о том, что из пункта В получается 3 цепочки, а из пункта Г- 2 цепочки.

Продолжаем строить граф по второму пути.

А→В

У нас уже есть результат этого решения. Это 3 цепочки.

Следующий по плану у нас третий путь.

А→Г

У нас также есть результат этого решения. Это 2 цепочки.

И наконец последний 4 путь из пункта А в пункт Д

А→Д→Г→ 2 цепочки

              Ж→К

Всего по 4 пути получилось 3 цепочки. 

Складываем количество цепочек по всем четырем направлениям:4+3+2+3=12

Следовательно, наш ответ 12.

Задача 3

Рассмотрим задачу № 3 из Демонстрационного варианта 2017 г. по Информатике

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

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

1) 4               2) 5             3) 6                  4) 7

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

1 путь

A→В→С→D

                     E

Первый путь - это путь ABCE = 2+1+2=5

2 путь

A→C→D

              E  

Второй путь ACE=5+2=7

3 путь

А →D→C→E

Третий путь ADCE=1+3+2=6

Следовательно, длина кратчайшего пути между пунктами A и Е это первый путь 5

Правильный ответ номер 2