ФИПИ тапсырмаларының шешімдері ОГЭ по информатикаға: «Графы и пути» — жауаптарымен

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно…

1. 1
   Рассмотрим маршруты из A в D, не посещая один и тот же пункт повторно.
2. 2
   Маршрут $A \to B \to C \to D$ имеет длину:$$2 + 1 + 5 = 8$$

Ещё 4 қадам — толық шешімде

Кратчайший путь через C

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт…

1. 1
   Рассмотрим путь A–C–B–E. Он проходит через C и посещает каждый пункт не более бір раза.$$4 + 2 + 4 = 10$$
2. 2
   Другой возможный путь A–C–D–E имеет длину 12 км. Также возможен путь A–B–C–D–E длиной 17 км. Минимальная длина равна 10 км.$$\min(10, 12, 17) = 10$$

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно…

1. 1
   Рассмотрим путь A—B—C—D—E—F. Он проходит по всем указанным дорогам и не посещает пункты повторно.$$3+1+1+2+2=9$$
2. 2
   Другие возможные пути имеют большую длину: например, A—C—D—E—F равен $5+1+2+2=10$ км, а прямой путь A—F равен 15 км. Следовательно, кратчайшим является путь через B, C, D и E.$$9<10<15$$

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и D при условии, что передвигаться можно…

1. 1
   Рассмотрим основные маршруты из A в D и сложим длины входящих в них дорог.$$A\text{–}C\text{–}D: 1 + 1 = 2$$
2. 2
   Другие возможные маршруты длиннее: A–B–D имеет длину 7, A–B–C–D — 5, A–E–D — 9.

Ещё 1 қадам — толық шешімде

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно…

1. 1
   Рассмотрим путь B–A–C–D–E. Все необходимые дороги указаны в таблице, и каждый пункт посещается только один раз.$$B\to A\to C\to D\to E$$
2. 2
   Сложим длины дорог этого пути:$$2 + 1 + 1 + 2 = 6$$

Ещё 1 қадам — толық шешімде

Кратчайший путь через вершину

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых указана в таблице. Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C…

1. 1
   Рассмотрим допустимый путь A–B–C–D–E–F, проходящий через C. Его длина:$$3+2+1+1+2=9$$
2. 2
   Другой возможный путь A–B–C–E–F имеет длину $3+2+3+2=10$ км. Путь A–B–C–D–E–F короче, поэтому он является кратчайшим.$$9<10$$

Кратчайший путь в графе

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно…

1. 1
   Рассмотрим возможные маршруты из A в D, не посещая ни один пункт более бір раза.
2. 2
   Для маршрута A–B–E–D длина равна сумме длин дорог A–B, B–E и E–D:$$2 + 1 + 1 = 4$$

Ещё 1 қадам — толық шешімде

Кратчайший путь между пунктами

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно…

1. 1
   Из пункта B есть дорога только в пункт C, поэтому маршрут начинается с перехода B → C длиной 4 км.$$L_{BC}=4$$
2. 2
   Из C можно попасть в A или D. Маршрут через A и D до E имеет длину:$$L_{BCADE}=4+1+2+1=8$$

Ещё 1 қадам — толық шешімде

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

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

1. 1
   До городов Б и Г из города А ведёт по одному пути.$$N_{Б}=1,\quad N_{Г}=1$$
2. 2
   До города В можно добраться напрямую из А, через Б или через Г.$$N_{В}=1+N_{Б}+N_{Г}=1+1+1=3$$

Ещё 2 қадам — толық шешімде

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

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

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

Ещё 3 қадам — толық шешімде

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

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

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

Ещё 1 қадам — толық шешімде

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

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

1. 1
   В город Б ведёт один путь из А, поэтому число путей в Б равно 1.
2. 2
   В город В ведут пути из А и Б: 1 + 1 = 2.

Ещё 5 қадам — толық шешімде

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

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

1. 1
   Из города А есть один путь в город Б и один путь в город Г.$$N(А)=1$$
2. 2
   В город Б ведут пути из городов А и Г, а в город В — путь из города Г.$$N(Б)=N(А)+N(Г)=2, N(В)=N(Г)=1$$

Ещё 3 қадам — толық шешімде

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

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

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

Ещё 4 қадам — толық шешімде

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

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

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

Ещё 3 қадам — толық шешімде

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

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

1. 1
   Начинаем с вершины А и рассматриваем ориентированные рёбра схемы слева направо. Для каждой вершины записываем число путей из А, используя правило сложения: число путей в вершину равно сумме чисел путей в её предшественники.$$N(v)=\sum_{u\to v}N(u)$$
2. 2
   Последовательно заполняем значения для всех вершин графа, не проходя по одному и тому же пути повторно.

Ещё 1 қадам — толық шешімде

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

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

1. 1
   Из города A можно попасть в B или F.
2. 2
   Из B в D существует только путь B → C → D, то есть 1 путь.

Ещё 3 қадам — толық шешімде

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

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

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

Ещё 2 қадам — толық шешімде

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

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

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

Ещё 2 қадам — толық шешімде

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

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

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

Ещё 4 қадам — толық шешімде