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

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

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



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

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


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

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

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

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

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

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

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

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


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