ЕГЭОГЭЕНТ
РУҚА
ОГЭ · информатика · решения по теме

Решения заданий ФИПИ ОГЭ по информатике: «Графы и пути» — с ответами

Каждая задача темы из открытого банка ФИПИ — с ответом и первыми шагами разбора. Полное решение по шагам и официальный ключ — по ссылкам в карточке.

Задания без решений
171
решений с ответами
1 546
задач в предмете
9
страниц списка
141ФИПИ 741380№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Считаем количество путей из города А в каждую вершину, начиная с исходной вершины.$$N(А)=1$$
  2. 2
    В город Б ведёт один путь из А, а в город В — пути из А и Б.$$N(Б)=1,\quad N(В)=N(А)+N(Б)=1+1=2$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
142ФИПИ 7DCCC3№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    До городов Б и Г из города А существует по одному пути, а до города В ведут три пути: непосредственно из А, через Б и через Г.$$N(Б)=1,\quad N(Г)=1,\quad N(В)=1+1+1=3$$
  2. 2
    До города Д ведут пути из Б и В, а до города Е — пути из Г и В.$$N(Д)=N(Б)+N(В)=1+3=4,\quad N(Е)=N(Г)+N(В)=1+3=4$$

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе
143ФИПИ 82DBA4№ 9Повышенная

Подсчёт путей в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из…

  1. 1
    Рассмотрим пути, начинающиеся переходом из города А в город Б.$$4$$
  2. 2
    Из города Б можно попасть в К напрямую, через В, через Д. Через В возможны два продолжения: сразу в К или через Е в К. Итого из Б в К ведут 4 пути.$$1 + 1 + 1 + 1 = 4$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
144ФИПИ 8D5169№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А можно сразу попасть в Б, В и Г, поэтому количество путей до каждой из этих вершин: до Б — 1, до В — 1, до Г — 1.
  2. 2
    В город В также можно попасть через Г, поэтому всего путей до В: $1 + 1 = 2$.

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
145ФИПИ 937DB7№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А непосредственно можно попасть в Б, В и Г, поэтому в каждую из этих вершин ведёт по одному пути.$$N_{Б}=1,\quad N_{В}=1,\quad N_{Г}=1$$
  2. 2
    В город В ведут дороги из А, Б и Г. Поэтому количество путей в В равно трём.$$N_{В}=1+N_{Б}+N_{Г}=1+1+1=3$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
146ФИПИ B0C254№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А непосредственно ведут дороги в города Б, В и Г. Поэтому для Б и Г число путей равно 1.$$N_{Б}=1,\quad N_{Г}=1$$
  2. 2
    В город В ведут дороги из А, Б и Г. Следовательно, число путей до В равно сумме путей до этих городов.$$N_{В}=1+1+1=3$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
147ФИПИ B137FD№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А непосредственно можно попасть в города Б, В и Г. Число путей до них: в Б — 1, в Г — 1, в В — 2 (напрямую из А и через Г).$$N_{Б}=1,\quad N_{Г}=1,\quad N_{В}=1+N_{Г}=2$$
  2. 2
    В город Д можно попасть только из Б, поэтому число путей до Д равно 1.$$N_{Д}=N_{Б}=1$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
148ФИПИ B3506E№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А можно попасть непосредственно в города Б, В и Г, поэтому количество путей в них равно соответственно 1, 2 и 1: в В ведут пути из А и Б.$$N_{Б}=1,\quad N_{В}=N_{А}+N_{Б}=2,\quad N_{Г}=1$$
  2. 2
    В город И ведут дороги из В и Г, в город Д — из В, а в город Е — из Г.$$N_{И}=N_{В}+N_{Г}=3,\quad N_{Д}=N_{В}=2,\quad N_{Е}=N_{Г}=1$$

Ещё 1 шаг — в полном решении

Решение полностьюОтветРешать самому3 шага в разборе
149ФИПИ B71485№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из…

  1. 1
    Присвоим городу А одно начальное значение: существует один пустой путь, начинающийся в А.$$N(А)=1$$
  2. 2
    Посчитаем количество путей до вершин, расположенных левее: $N(Б)=1$, $N(В)=N(А)+N(Б)=2$, $N(Д)=1$.

Ещё 5 шагов — в полном решении

Решение полностьюОтветРешать самому7 шагов в разборе
150ФИПИ B898C4№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А непосредственно можно попасть в Б, В и Г. Поэтому количество путей в эти вершины соответственно равно 1, 1 и 1.
  2. 2
    В город В также ведёт дорога из Г, поэтому количество путей из А в В равно $1 + 1 = 2$.

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
151ФИПИ B91954№ 9Повышенная

Подсчёт путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Из города А можно попасть в города Б и Г.
  2. 2
    Через город Б проходят четыре пути в город К: через Д, непосредственно в К, через В и К, через В и Е в К.

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
152ФИПИ B97cA2№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из…

  1. 1
    Начинаем с города А: количество путей до него равно 1. По схеме последовательно получаем: до Б — 1, до Г — 1, до В — $1 + 1 + 1 = 3$, до Д — 1, до Ж — 1.
  2. 2
    Для города Е складываем количества путей из В, Д и Ж: $3 + 1 + 1 = 5$.

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
153ФИПИ B9A72D№ 9Повышенная

Пути в ориентированном графе

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

  1. 1
    Начинаем с вершины A: количество путей в A равно 1. Тогда в B и G попадает по одному пути, а в E напрямую из A попадает один путь.$$N_A=1,\quad N_B=1,\quad N_G=1$$
  2. 2
    В вершину E ведут дороги из A, B и G, поэтому количество путей в E равно трём.$$N_E=N_A+N_B+N_G=1+1+1=3$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
154ФИПИ C520BE№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А…

  1. 1
    Посчитаем количество путей из города А до промежуточных городов по схеме.$$N(Б)=1,\quad N(В)=1,\quad N(Д)=1$$
  2. 2
    В город Г можно попасть непосредственно из А или через В либо Д. Поэтому количество путей до Г равно трём.$$N(Г)=1+1+1=3$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
155ФИПИ c5B2c0№ 9Повышенная

Количество путей в графе

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

  1. 1
    В город A имеется один начальный путь: путь нулевой длины.$$A=1$$
  2. 2
    Рассчитаем количество путей до промежуточных городов по направлениям стрелок.$$B=1,\quad E=1,\quad G=A+E=1+1=2$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
156ФИПИ c6457A№ 9Повышенная

Количество путей в графе

На рисунке дана схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из…

  1. 1
    Начинаем с города А: в него входит один нулевой путь, поэтому далее считаем количество путей до каждой вершины.$$N(А)=1$$
  2. 2
    По направлениям дорог получаем значения для первых вершин.$$N(Б)=1,\quad N(Г)=1,\quad N(В)=N(А)+N(Г)=2$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
157ФИПИ c7D32F№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из…

  1. 1
    Из города А выходит один путь, поэтому число путей в А равно 1.
  2. 2
    Последовательно подсчитаем пути до промежуточных городов: Б — 1, Д — 1, В — 2, Г — 2.

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе
158ФИПИ c7D45c№ 9Повышенная

Количество путей в графе

На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных…

  1. 1
    Граф ориентированный и не содержит циклов, поэтому количество путей можно вычислять последовательно, начиная с города А.
  2. 2
    Для каждой вершины число путей из А равно сумме чисел путей во всех вершинах, из которых в неё направлены дороги.

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
159ФИПИ D7BA1E№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в…

  1. 1
    Перечислим пути, начинающиеся переходом из А в Б:$$А\to Б\to Д\to К;\quad А\to Б\to В\to К$$
  2. 2
    Путь, начинающийся переходом из А в В, единственный:$$А\to В\to К$$

Ещё 2 шага — в полном решении

Решение полностьюОтветРешать самому4 шага в разборе
160ФИПИ DD0BB6№ 9Повышенная

Количество путей в графе

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А…

  1. 1
    В город А ведёт 1 начальный путь. В города Б и Д можно попасть из А, поэтому в каждый из них ведёт по 1 пути.$$N_{А}=1,\quad N_{Б}=1,\quad N_{Д}=1$$
  2. 2
    В город В ведут дороги из А и Б.$$N_{В}=N_{А}+N_{Б}=1+1=2$$

Ещё 3 шага — в полном решении

Решение полностьюОтветРешать самому5 шагов в разборе

Те же задачи без решений, с фильтрами по сложности и типу ответа, — список заданий. Другой предмет — в каталоге.