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

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

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

1. 1
   В город A ведёт начальный путь, поэтому считаем количество путей из A к каждой вершине.$$N_A = 1$$
2. 2
   В город B ведёт один путь из A, а в город C — один путь из A.$$N_B = 1,\quad N_C = 1$$

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

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

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

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

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

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

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

1. 1
   Считаем начальную вершину A источником: в неё ведёт один начальный путь, поэтому $N_A=1$.$$N_A=1$$
2. 2
   В вершины B, C и D ведут пути непосредственно из A, поэтому $N_B=N_C=N_D=1$.

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

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

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

1. 1
   Перечислим пути, начинающиеся с перехода A → B: A–B–E–G, A–B–G, A–B–C–G и A–B–C–D–F–G. Всего 4 пути.$$4$$
2. 2
   Пути, начинающиеся с перехода A → C: A–C–G и A–C–D–F–G. Всего 2 пути.$$2$$

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

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

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

1. 1
   Из города A начинается один путь. До города B можно добраться двумя способами: непосредственно из A и через C.$$N_A=1,\quad N_C=1,\quad N_B=N_A+N_C=2$$
2. 2
   До города D ведут пути только из B, а до E — также только из B.$$N_D=N_B=2,\quad N_E=N_B=2$$

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

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

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

1. 1
   Из города А начинаются пути через города Б, В и Г. Перечислим все маршруты, которые заканчиваются в городе К.
2. 2
   После учёта направлений стрелок и исключения повторных маршрутов получаем шесть различных путей из А в К.

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

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

1. 1
   Из города A есть один начальный путь: $N_A=1$. В город E ведёт один путь из A, поэтому $N_E=1$.
2. 2
   В город D можно попасть из A или E: $N_D=N_A+N_E=1+1=2$.

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

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

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

1. 1
   Начинаем с города А: в него входит начальная точка одного пути, поэтому число путей в А равно 1.$$N_A=1$$
2. 2
   Последовательно вычисляем число путей в остальных городах по направлениям стрелок.$$N_{Б}=1, N_{В}=N_A+N_{Б}=2, N_{Г}=N_A+N_{В}=3$$

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

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

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

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

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

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

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

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

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

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

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

1. 1
   До вершин B, F и E из A существует по одному пути: $A \to B$, $A \to F$, $A \to E$.
2. 2
   До E можно попасть из A, а также через B и F. Поэтому количество путей в E равно $1 + 1 + 1 = 3$.

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

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

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

1. 1
   Из города F в G ведёт один путь, поэтому число путей из F равно 1. Из E можно попасть в F, значит из E также 1 путь.
2. 2
   Из D можно попасть в E или F: $1 + 1 = 2$ пути. Из C можно попасть в E или непосредственно в G: $1 + 1 = 2$ пути.

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

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

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

1. 1
   В городе А находится один начальный путь: из А начинаются все маршруты.$$A=1$$
2. 2
   Рассчитаем количество путей до вершин первого уровня.$$Б=1,\quad В=A+Б=2,\quad Г=A+В=3,\quad Д=A=1$$

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

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

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

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

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

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

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

1. 1
   Обозначим через $N_X$ количество путей из города А в город $X$. Для начальной вершины $N_{\text{А}}=1$.
2. 2
   Последовательно подсчитываем количество путей до промежуточных городов: $N_{\text{Б}}=1$, $N_{\text{В}}=2$, $N_{\text{Г}}=3$, $N_{\text{Д}}=1$, $N_{\text{Е}}=3$, $N_{\text{Ж}}=4$.

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

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

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

1. 1
   Из города A выходят дороги в города B, E, F и G.$$N_A = 1$$
2. 2
   Через B существует один путь к C, а затем к D: A–B–C–D.

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

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

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

1. 1
   Из A непосредственно выходят пути в C, B и D. Поэтому число путей в C и B равно 1, а в D — 3: из A, через C и через B.$$N_C=1,\quad N_B=1,\quad N_D=1+1+1=3$$
2. 2
   В E можно попасть только из C, поэтому число путей в E равно 1. В F ведут пути из B и D.$$N_E=1,\quad N_F=N_B+N_D=1+3=4$$

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

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

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

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

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

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

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

1. 1
   До вершин B и E из A и B соответственно ведёт по одному пути.$$N_B = 1,\quad N_E = 1$$
2. 2
   В вершину D ведут пути из A, B и E.$$N_D = 1 + 1 + 1 = 3$$

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

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

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

1. 1
   Обозначим через $N_X$ количество путей из А в вершину $X$. Для начальной вершины $А$ имеем $N_A=1$. По схеме $N_Б=1$, поэтому $N_В=N_A+N_Б=2$.
2. 2
   Рассчитаем количества путей в остальных вершинах: $N_Г=N_A+N_В+N_Д=1+2+1=4$, $N_Е=N_Б+N_В=1+2=3$, $N_Ж=N_Д=1$.

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