Задание №2782.
Анализ информации, представленной в виде схем. ОГЭ по информатике
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Ж?
Пояснение:
В данной задаче схема дорог представлена ориентированным графом.
Решим задачу, двигаясь от вершины А в город К через город Ж и проставляя веса вершин — число путей из А в текущую вершину. Пути, не проходящие через город Ж, зачеркнуты на рисунке красным цветом. При этом вес вершины А принимаем за 1 (существует только единственный способ попасть из вершины А в вершину А — оставаться на месте).
Следовательно, существует 11 + 11 = 22 различных путей из города А в город К, проходящих через город Ж.
Теоретическая информация:
Граф — информационная модель, на которой некоторые объекты изображены в виде вершин, а связи между — линиями.
Направленная линия (со стрелкой), соединяющая вершины графа, называется дугой. Граф называется ориентированным, если его вершины соединены дугами.
Ненаправленная линия (без стрелки), соединяющая вершины графа, называется ребром. Вершины неориентированного графа соединены ребрами.
Граф называется взвешенным, если его вершины или ребра характеризуются некоторой дополнительной информацией — весами вершин или ребер.
Показать ответ
Источник: ОГЭ-2021. Информатика: 20 тренировочных вариантов. Д.М. Ушаков
Сообщить об ошибке
Тест с похожими заданиями
Анализ информации, представленной в виде схем. ОГЭ по информатике
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Ж?
Пояснение:
В данной задаче схема дорог представлена ориентированным графом.
Решим задачу, двигаясь от вершины А в город К через город Ж и проставляя веса вершин — число путей из А в текущую вершину. Пути, не проходящие через город Ж, зачеркнуты на рисунке красным цветом. При этом вес вершины А принимаем за 1 (существует только единственный способ попасть из вершины А в вершину А — оставаться на месте).
Следовательно, существует 11 + 11 = 22 различных путей из города А в город К, проходящих через город Ж.
Теоретическая информация:
Граф — информационная модель, на которой некоторые объекты изображены в виде вершин, а связи между — линиями.
Направленная линия (со стрелкой), соединяющая вершины графа, называется дугой. Граф называется ориентированным, если его вершины соединены дугами.
Ненаправленная линия (без стрелки), соединяющая вершины графа, называется ребром. Вершины неориентированного графа соединены ребрами.
Граф называется взвешенным, если его вершины или ребра характеризуются некоторой дополнительной информацией — весами вершин или ребер.
Показать ответ
Источник: ОГЭ-2021. Информатика: 20 тренировочных вариантов. Д.М. Ушаков
Сообщить об ошибке
Тест с похожими заданиями