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

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

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

1. 1
   Рассмотрим прямой путь A–G.$$25$$
2. 2
   Путь A–D–C–G имеет длину:$$12 + 2 + 10 = 24$$

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

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

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

1. 1
   Рассмотрим маршрут A–B–D–E–F:$$4 + 7 + 1 + 1 = 13$$
2. 2
   Другой возможный маршрут A–B–D–F имеет длину 14, а маршрут A–B–C–D–E–F — 14. Прямой путь A–F имеет длину 17.$$14 > 13,\quad 17 > 13$$

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

Сопоставление графа и таблицы

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем вершины графа с пунктами таблицы по структуре соединений: у каждой вершины учитываем количество дорог и их взаимное расположение.
2. 2
   После сопоставления определяем длины дорог из D в B и из F в A: 5 км и 53 км.

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

Сопоставление графа и таблицы

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем вершины графа со строками таблицы по числу соединений и значениям длин дорог.
2. 2
   После сопоставления определяем, что длина дороги из F в E равна 2 км, а длина дороги из B в D равна 8 км.$$2 + 8 = 10$$

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

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

1. 1
   Рассмотрим основные маршруты из A в F: прямой маршрут A—F, маршрут через C и маршрут через D.
2. 2
   Их длины равны соответственно $7$, $2+4=6$ и $1+4=5$.$$7;\quad 2+4=6;\quad 1+4=5$$

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

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

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

1. 1
   Из пункта A можно попасть только в пункт B по дороге длиной 1.
2. 2
   Из B в F можно двигаться, например, через D и E: B–D–E–F.

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

Сопоставление графа и таблицы

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Для сопоставления буквенных вершин графа с номерами в таблице сравниваем структуру соединений: число дорог и характер соседних вершин.
2. 2
   После восстановления соответствия находим в таблице протяжённости дорог из $C$ в $G$ и из $H$ в $E$: это $49$ км и $19$ км.$$49 + 19$$

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

Протяжённость дороги В—Ж

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем вершины графа с пунктами таблицы по структуре дорог: сравниваем количество рёбер и связи каждой вершины с соседними.
2. 2
   Для пунктов, соответствующих вершинам В и Ж, получаем нөмір 4 и 7.

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

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

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

1. 1
   Из пункта F можно попасть только в пункт E, поэтому любой путь из A в F должен заканчиваться переходом E–F длиной 5.$$d(F)=d(E)+5$$
2. 2
   Кратчайший путь из A в E проходит через D: сначала из A в D за 6, затем из D в E за 2.$$d(E)=6+2=8$$

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

Сопоставление графа и таблицы

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем буквенные вершины графа с номерами пунктов в таблице по структуре соединений: учитываем количество дорог, соединённых с каждой вершиной, и длины соответствующих дорог.
2. 2
   После сопоставления дорога из $G$ в $C$ имеет длину $13$ км, а дорога из $B$ в $D$ — длину $3$ км.$$13 + 3 = 16$$

Кратчайший путь по таблице

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

1. 1
   Из пункта A можно попасть только в пункт B по дороге длиной 4.
2. 2
   Из B выгоднее всего двигаться через D: длина дороги B–D равна 2.

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

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

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

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

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

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

1. 1
   Рассмотрим маршрут A—B—C—D—E—F.$$2+2+1+3+1=9$$
2. 2
   Другой короткий маршрут A—D—E—F имеет длину 10+3+1=14, а маршрут A—D—F — 10+5=15. Прямой путь A—F имеет длину 38.

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

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

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

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

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

Номера вершин графа

На рисунке изображена схема дорог Н-ского района, а в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Каждому…

1. 1
   По таблице определяем количество дорог, связанных с каждым номером: у 1, 2, 4 и 7 по три дороги, у 3, 5 и 6 — по две.
2. 2
   Сопоставляем степени вершин и взаимное расположение дорог на схеме с таблицей смежности. Населённому пункту C соответствует номер 4, а населённому пункту G — номер 7.

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

Протяжённость дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем вершины графа с номерами пунктов в таблице по количеству и взаимному расположению дорог.
2. 2
   Из этого сопоставления следует, что пункту А соответствует нөмір 4, а пункту Г — нөмір 7.

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

Длина дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Для каждой вершины графа сравниваем количество дорог и связи с соседними вершинами с данными таблицы.
2. 2
   После сопоставления буквенных обозначений графа с номерами пунктов таблицы вершины Г и Ж соответствуют пунктам 1 и 4.

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

Протяжённость дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сопоставляем буквенные вершины графа с номерами пунктов таблицы, сравнивая количество дорог, выходящих из каждой вершины, и связи между соседними вершинами.
2. 2
   После установления соответствия выясняется, что дорога из пункта А в пункт Г соответствует дороге, протяжённость которой в таблице равна 22 км.

Длина дороги между пунктами

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Для сопоставления графа и таблицы сравниваем степени вершин: количество дорог, выходящих из каждого пункта, а затем учитываем связи между соседними пунктами.
2. 2
   По структуре графа определяем нөмір пунктов таблицы, соответствующие вершинам Г и Д.

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

Длина дороги по графу

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от…

1. 1
   Сравниваем структуру графа с таблицей: для каждой вершины учитываем количество соединений и протяжённости дорог.
2. 2
   По совпадению структуры определяем нөмір пунктов, соответствующие вершинам Д и Е.

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