Задание №4198. На рисунке – схема дорог, связывающих пункты A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт H?

Задание №4198.
Анализ информации на схеме. ОГЭ по информатике

На рисунке – схема дорог, связывающих пункты A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт H?



Пояснение:
В данной задаче схема дорог представлена ориентированным графом.

Решим задачу, двигаясь от вершины А в город H и проставляя веса вершин — число путей из А в текущую вершину. При этом вес вершины А принимаем за 1 (существует только единственный способ попасть из вершины А в вершину А — оставаться на месте).


Следовательно, существует 1 + 8 = 9 различных путей из города А в город H.

Теоретическая информация:

Граф — информационная модель, на которой некоторые объекты изображены в виде вершин, а связи между — линиями.

Направленная линия (со стрелкой), соединяющая вершины графа, называется дугой. Граф называется ориентированным, если его вершины соединены дугами.

Ненаправленная линия (без стрелки), соединяющая вершины графа, называется ребром. Вершины неориентированного графа соединены ребрами.

Граф называется взвешенным, если его вершины или ребра характеризуются некоторой дополнительной информацией — весами вершин или ребер.

Показать ответ

Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке


Тест с похожими заданиями