ОГЭ по информатике задание 11
Тема: «Моделирование. Количество путей в графе».
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
РЕШЕНИЕ
Это задание ОГЭ по информатике решается с помощью графов.
Граф — это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.Если ребра не имеют ориентации, граф называется неориентированным.
Нужно схематично отобразить все возможные варианты путей. Путь начинается с пункта А и заканчивается пунктом Л. На схеме от пункта А ведет дорога в пункты Б, В, Г, от пункта Б ведут дороги в пункты Д и В и.т.д
Все дороги должны заканчиваться пунктом Л. Теперь можно выделить все пункты Л и подсчитать их.Количество пунктов Л и будет ответом данной задачи. Л = 13.
Ответ: 13