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

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

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

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

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

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

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

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

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

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

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

1. 1
   Рассмотрим маршруты из A в F, проходящие через C и не содержащие повторяющихся пунктов.
2. 2
   Маршрут A–C–F невозможен, так как дороги C–F нет. Для маршрута через D получаем длину $A\text{–}B\text{–}C\text{–}D\text{–}F$:$$2+2+1+6=11$$

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

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

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

1. 1
   Рассмотрим маршрут B → C → D → A → E. Все необходимые дороги указаны в таблице, а пункты не повторяются.$$2 + 2 + 1 + 4 = 9$$
2. 2
   Другие возможные маршруты имеют большую длину: например, B → A → E составляет $6 + 4 = 10$ км, а B → D → E — $5 + 6 = 11$ км.

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

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

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

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

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

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

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

1. 1
   Рассмотрим основные маршруты из A в D, не посещая ни один пункт повторно.
2. 2
   Через B получаем маршрут A–B–D длиной $8 + 3 = 11$ км.

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

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

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

1. 1
   Рассмотрим возможные пути из A в C без повторного посещения пунктов.$$A\text{–}C: 7,\quad A\text{–}B\text{–}C: 2+5=7$$
2. 2
   Путь через пункт D имеет длину $4+2=6$ км.$$A\text{–}D\text{–}C: 4+2=6$$

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

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

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

1. 1
   Рассмотрим путь $A \to C \to D \to E \to F$.$$5 + 1 + 2 + 1 = 9$$
2. 2
   Другой близкий по длине путь $A \to B \to D \to E \to F$ имеет длину 10 км, а прямой путь $A \to F$ — 15 км. Следовательно, минимальная длина равна 9 км.$$\min(9, 10, 15) = 9$$

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

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

1. 1
   Из пункта A ведёт дорога только в пункт B, поэтому любой маршрут начинается с ребра A–B длиной 3 км.$$L_{AB}=3$$
2. 2
   Рассмотрим маршрут A–B–C–E.$$L_{ABCE}=3+1+3=7$$

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

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

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

1. 1
   Пункт B исключаем из рассмотрения. Из A можно отправиться в C или сразу в F.
2. 2
   Путь A–F напрямую имеет длину 15 км.

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

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

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

1. 1
   Из пункта A можно попасть в пункты C и D. Из пункта D есть прямая дорога в E.
2. 2
   Рассмотрим маршрут A—D—E: его длина равна сумме длин дорог A—D и D—E.$$2 + 4 = 6$$

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

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

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

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

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

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

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

1. 1
   Перечислим допустимые маршруты из B в D, не посещая пункты повторно. Например, маршрут B–A–C–E–D имеет длину:$$2+2+1+4=9$$
2. 2
   Другие возможные маршруты длиннее: B–A–E–D имеет длину $2+4+4=10$, а B–C–E–D — $5+1+4=10$.

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

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

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

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

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

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

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

1. 1
   Из пункта A можно попасть в пункты B, C и E. Проверим возможные короткие маршруты к E.
2. 2
   Прямой путь A–E имеет длину 4 км, путь A–B–E — $1 + 3 = 4$ км, а путь A–C–E — $1 + 1 = 2$ км.$$1 + 1 = 2$$

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

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

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

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

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

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

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

1. 1
   Рассмотрим возможные маршруты из A в F и вычислим их длины.$$A\mathbin{-}F: 15$$
2. 2
   Маршрут через C и D имеет длину:$$A\mathbin{-}C\mathbin{-}D\mathbin{-}F: 5 + 5 + 3 = 13$$

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

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

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

1. 1
   Рассмотрим маршрут A → E → B → C → D. Все пункты в нём посещаются не более бір раза.$$A\to E\to B\to C\to D$$
2. 2
   Сложим длины входящих в маршрут дорог.$$4+2+2+3=11$$

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

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

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

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

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

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

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

1. 1
   Из пункта A в пункт E можно попасть через пункт C. Рассмотрим основные допустимые маршруты без повторного посещения пунктов.$$A\to C\to E: 5+2=7$$
2. 2
   Маршрут через B имеет длину:$$A\to B\to C\to E: 2+1+2=5$$

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