![Информационные модели Графы. Поиск количества путей Учитель информатики МОБУ «Сенькинская средняя общеобразовательная школа» Скворцова Ольга Валерьевна](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_0.jpg)
Информационные модели
Графы. Поиск количества путей
Учитель информатики
МОБУ «Сенькинская средняя общеобразовательная школа»
Скворцова Ольга Валерьевна
![13-е задание: «Информационные модели» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_1.jpg)
- 13-е задание: «Информационные модели» Уровень сложности — повышенный, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 3 минуты. Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)
![Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть: N R = N X + N Y + N Z где N R — это количество путей из вершины A в вершину R Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути. Часто задачи с графами целесообразней решать с конца.](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_2.jpg)
- Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
N R = N X + N Y + N Z
где N R — это количество путей из вершины A в вершину R
- Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
- Часто задачи с графами целесообразней решать с конца.
![Типичные ошибки](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_3.jpg)
Типичные ошибки
- "Игнорирование указаний в условии задания, что путь должен включать (или не включать) заданные промежуточные вершины"
![Подсчёт путей с избегаемой вершиной 1.На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_4.jpg)
Подсчёт путей с избегаемой вершиной
1.На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?
![2. На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_5.jpg)
2. На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П. Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?
![Подсчёт путей с обязательной и избегаемой вершинами 3. На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г и НЕ проходящих через город З?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_6.jpg)
Подсчёт путей с обязательной и избегаемой вершинами
3. На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г и НЕ проходящих через город З?
![Подсчет путей 4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_7.jpg)
Подсчет путей
4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
![Подсчёт путей с обязательной вершиной 5. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_8.jpg)
Подсчёт путей с обязательной вершиной
5. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?
![6. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город В? Демо 2021](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_9.jpg)
6. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город В?
Демо 2021
![7. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Л? Пробный 2021](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_10.jpg)
7. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Л?
Пробный 2021
![Наибольшая длинна 8. На рисунке - схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ? 2020](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_11.jpg)
Наибольшая длинна
- 8. На рисунке - схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ?
2020
![Самостоятельно На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_12.jpg)
Самостоятельно
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
![На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М . По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г ?](http://fsd.mir-olymp.ru/html/2023/12/17/i_657f256e6ae0d/img_phpiPgLag_13.jpg)
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М . По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г ?