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

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

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

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

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

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

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

1. 1
   Из пункта A ведёт дорога только в пункт B, поэтому первый участок любого пути имеет длину 4 км.$$A \to B: 4$$
2. 2
   Рассмотрим путь через E и C: сначала из B в E, затем из E в C и из C в D.$$A \to B \to E \to C \to D: 4 + 1 + 2 + 1 = 8$$

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

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

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

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

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

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

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

1. 1
   Рассмотрим основные маршруты из A в F и вычислим их длины.
2. 2
   Через вершины B и D получаем маршрут A–B–D–F:$$3 + 4 + 6 = 13$$

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

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

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

1. 1
   Из пункта A можно попасть в B по дороге длиной 7 км или в C по дороге длиной 4 км.
2. 2
   Рассмотрим маршрут через C и B: A → C → B → E. Все пункты в нём различны, а его длина равна:$$4 + 2 + 5 = 11$$

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

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

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

1. 1
   Из пункта A ведёт дорога только в пункт B, поэтому маршрут начинается с участка A—B длиной 1 км.$$L_{AB}=1$$
2. 2
   Из пункта B до E можно добраться напрямую, через C или через D. Рассмотрим длины маршрутов:$$L_{A-B-E}=1+8=9;\quad L_{A-B-C-E}=1+4+4=9;\quad L_{A-B-D-E}=1+2+4=7$$

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

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

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

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

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

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

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

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

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

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

1. 1
   По таблице пункт B соединён только с пунктами A и D. Поэтому путь из A в D, проходящий через B, имеет вид A → B → D.
2. 2
   Длина дороги от A до B равна 1, а длина дороги от B до D равна 6.$$L = 1 + 6 = 7$$

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

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

1. 1
   Рассмотрим пути из A в E, проходящие через D и не содержащие повторяющихся вершин.
2. 2
   Путь A–D–E имеет длину:$$5+1=6$$

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

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

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

1. 1
   Рассмотрим маршрут A–B–D–E–F, в котором каждый населённый пункт посещается не более одного раза.$$2+3+2+4=11$$
2. 2
   Другие возможные маршруты имеют большую длину: например, A–D–E–F — $7+2+4=13$ км, а A–F — $15$ км. Следовательно, найденный маршрут является кратчайшим.

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

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

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

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

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

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

1. 1
   Из пункта A можно отправиться в B или C. Маршрут через B имеет длину $8 + 3 = 11$ до D.
2. 2
   Через C возможны, в частности, маршруты A—C—E—D и A—C—F—D.

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

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

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

1. 1
   Рассмотрим маршрут A–C–D–E–F.$$4 + 4 + 2 + 1 = 11$$
2. 2
   Другие возможные маршруты имеют большую длину: например, A–B–C–D–E–F равен $3 + 3 + 4 + 2 + 1 = 13$ км, а непосредственная дорога A–F имеет длину 18 км.

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

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

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

1. 1
   Из пункта A можно попасть в B или C. Рассмотрим маршрут через C и D:$$A \to C \to D \to E$$
2. 2
   Складываем длины дорог этого маршрута:$$4 + 3 + 1 = 8$$

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

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

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

1. 1
   Рассмотрим маршрут B–A–E–C–D. Он проходит по указанным дорогам, а каждый пункт посещается только один раз.$$2+1+1+2=6$$
2. 2
   Другой возможный короткий маршрут B–E–C–D имеет длину 7 км. Маршрут B–C–D имеет длину 7 км, а маршрут B–E–D — 8 км. Следовательно, минимальная длина равна 6 км.$$\min(6,7,7,8)=6$$

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

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

1. 1
   Рассмотрим путь A–E–D, который проходит через E и не повторяет пункты.$$A\text{–}E\text{–}D$$
2. 2
   Его длина равна сумме длин дорог A–E и E–D.$$5 + 5 = 10$$

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

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

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

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

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

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

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

1. 1
   Перечислим допустимые маршруты из A в F, проходящие через C, без повторного посещения пунктов: A–C–F, A–C–D–F, A–C–D–E–F, A–B–C–F и A–B–D–C–F.
2. 2
   Вычислим их длины:$$A\text{–}C\text{–}F: 4+6=10;\quad A\text{–}C\text{–}D\text{–}F: 4+1+6=11;\quad A\text{–}C\text{–}D\text{–}E\text{–}F: 4+1+2+1=8$$

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

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

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

1. 1
   Рассмотрим допустимый маршрут A–B–C–D–F, проходящий через C. Все пункты в нём различны.
2. 2
   Складываем длины дорог этого маршрута:$$3 + 1 + 2 + 6 = 12$$

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