Информационные модели. Графы. Поиск количества путей. Задание 13

1. Задание 13. Информационные модели

Графы. Поиск количества путей

2.

• 13-е задание: «Информационные модели»
Уровень сложности — повышенный,
Требуется использование
специализированного программного
обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
Проверяемые элементы содержания: Умение
представлять и считывать данные в разных
типах информационных моделей (схемы,
карты, таблицы, графики и формулы)

3.

• Если в город R из города A можно добраться только
из городов X, Y и Z, то количество различных путей
из города A в город R равно сумме числа различных
путей проезда из A в X, из A в Y и из A в Z, то есть:
NR = NX + NY + NZ
где NR — это количество путей из вершины A в
вершину R
• Число путей не бесконечно, исключением является
только граф, в котором есть циклы – замкнутые
пути.
• Часто задачи с графами целесообразней решать с
конца.

4. Типичные ошибки

• "Игнорирование указаний в условии
задания, что путь должен включать (или не
включать) заданные промежуточные
вершины"

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

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

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

пункта А в пункт П, не
проходящих через пункт Е?

7. 3. На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Подсчёт путей с обязательной и избегаемой вершинами
3. На рисунке представлена схема дорог. По каждой дороге можно двигаться
только в одном направлении, указанном стрелкой. Сколько существует
различных путей из города А в город К, проходящих через город Г и НЕ
проходящих через город З?

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

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

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

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

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

только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город В?
Демо 2021

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

только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Л?
Пробный 2021

12. Наибольшая длинна

8. На рисунке - схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По
каждой дороге можно двигаться в одном направлении, указанном стрелкой.
Какая наибольшая длина пути из А в М ?
2020

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

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

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

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