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

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

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

1. 1
   Рассмотрим возможные маршруты из A в D.
2. 2
   Прямой путь A–D имеет длину 5 км.$$5$$

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

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

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

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

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

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

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

1. 1
   Рассмотрим путь A–B–D: его длина равна сумме длин дорог A–B и B–D.$$2+2=4$$
2. 2
   Другой путь A–B–C–D имеет длину $2+5+1=8$. Пути через E также длиннее: A–E–B–D имеет длину $3+4+2=9$.

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

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

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

1. 1
   Рассмотрим путь A–B–C: он проходит по указанным дорогам и не повторяет пункты.$$2 + 3 = 5$$
2. 2
   Другой путь через D имеет длину не менее $4 + 5 + 3 = 12$ км, а путь A–B–E–C имеет длину $2 + 2 + 3 = 7$ км. Следовательно, кратчайшим является путь A–B–C.$$L_{\min} = 5$$

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

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

1. 1
   Так как путь должен проходить через C, рассматриваем маршруты от A до C и от C до F.
2. 2
   Из A в C можно проехать непосредственно по дороге длиной 2. Из C в F кратчайший допустимый путь проходит через D и E и имеет длину $1+2+1=4$.

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

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

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

1. 1
   Рассмотрим маршрут A–B–E–D. Он проходит через E, не повторяет пункты и имеет длину:$$5 + 2 + 3 = 10$$
2. 2
   Другой короткий маршрут A–C–E–D имеет длину 11. Маршруты с дополнительными пунктами имеют длину не менее 10 и не дают меньшего результата.

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

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

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

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

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

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

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

1. 1
   Из пункта A можно попасть в B по дороге длиной 2 км или в D по дороге длиной 4 км.
2. 2
   Маршрут A–B–D–C–E использует каждую вершину не более одного раза и имеет длину:$$2 + 1 + 3 + 2 = 8$$

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

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

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

1. 1
   Рассмотрим маршруты из A в E, проходящие через D и не повторяющие пункты.
2. 2
   Маршрут A–D–E имеет длину $8 + 2 = 10$.

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

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

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

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

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

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

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

1. 1
   Из пункта A можно попасть в B или C. Рассмотрим допустимые пути к E без повторного посещения пунктов.
2. 2
   Путь A–B–C–D–E имеет длину:$$4 + 1 + 3 + 1 = 9$$

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

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

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

1. 1
   Рассмотрим пути из A в D, не посещая один и тот же пункт дважды.
2. 2
   Путь A–B–C–D имеет длину:$$5 + 1 + 1 = 7$$

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

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

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

1. 1
   Рассмотрим маршруты из A в F без повторного посещения пунктов.
2. 2
   Маршрут A–B–C–E–F имеет длину:$$2 + 1 + 3 + 3 = 9$$

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

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

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

1. 1
   Рассмотрим возможные маршруты из A в F и вычислим их длины.
2. 2
   Непосредственная дорога A–F имеет длину 15 км. Маршрут A–B–C–D–F имеет длину:$$1 + 2 + 5 + 3 = 11$$

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

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

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

1. 1
   Рассмотрим путь через пункт B:$$A \to B \to E$$
2. 2
   Его длина равна сумме длин дорог от A до B и от B до E:$$2 + 2 = 4$$

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

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

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

1. 1
   Из пункта A можно попасть в B или C. Проверим пути к пункту D.
2. 2
   Путь через B имеет длину:$$A \to B \to D: 3 + 1 = 4$$

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

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

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

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

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

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

1. 1
   Рассмотрим возможные маршруты из A в D и сложим длины входящих в них дорог.$$A\text{–}E\text{–}D: 6 + 4 = 10$$
2. 2
   Маршрут через B и C имеет меньшую длину:$$A\text{–}B\text{–}C\text{–}E\text{–}D: 2 + 2 + 1 + 4 = 9$$

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

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

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

1. 1
   Чтобы попасть из A в F через E, рассмотрим допустимые маршруты без повторного посещения пунктов.
2. 2
   Маршрут A–B–C–D–E–F использует дороги длиной 1, 2, 1, 2 и 1 км.$$1+2+1+2+1=7$$

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

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

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

1. 1
   Пункт D соединён только с пунктом E, поэтому путь из B в D должен заканчиваться переходом E–D длиной 4 км.
2. 2
   Рассмотрим маршрут B–A–C–E–D. Все пункты в нём различны, а длина маршрута равна:$$1+2+1+4=8$$

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