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

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

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

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

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

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

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

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

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

1. 1
   Сопоставляем буквенные вершины графа с номерами населённых пунктов по числу дорог и характеру их соединений.
2. 2
   При таком сопоставлении пункту Б соответствует номер 2, а пункту В — номер 6.

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

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

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

1. 1
   Из пункта A можно попасть только в пункт B по дороге длиной 3.
2. 2
   Рассмотрим маршрут A–B–D–E–F:$$3 + 2 + 3 + 5 = 13$$

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

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

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

1. 1
   Из таблицы видно, что прямой путь A–F имеет длину 6.
2. 2
   Рассмотрим маршрут A–B–C–F. Его длина равна сумме длин дорог на маршруте.$$1 + 2 + 1 = 4$$

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

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

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

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

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

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

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

1. 1
   По таблице восстанавливаем дороги между пронумерованными пунктами: $1\text{–}5$, $1\text{–}8$, $2\text{–}7$, $3\text{–}5$, $3\text{–}6$, $4\text{–}6$, $4\text{–}8$, $5\text{–}8$.
2. 2
   Сопоставляем структуру связей таблицы с графом и устанавливаем, какие номера соответствуют буквенным обозначениям вершин.

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

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

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

1. 1
   Рассмотрим маршрут A–B–D–C–E–G.$$5 + 8 + 2 + 4 + 5 = 24$$
2. 2
   Другие возможные маршруты имеют длину не менее 24: например, A–G имеет длину 25, а A–D–C–E–G — 25.

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

Схема железнодорожных станций

В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

1. 1
   Из таблицы выписываем все пары соседних станций и стоимость перевозки между ними.$$A\text{–}B=3,\ A\text{–}D=4,\ B\text{–}D=2,\ D\text{–}E=4,\ E\text{–}C=1$$
2. 2
   Сравниваем полученный набор рёбер и их весов с предложенными схемами.

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

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

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

1. 1
   Из пункта A в пункт F можно проехать напрямую по дороге длиной 5.
2. 2
   Также существует маршрут A—B—F. Его длина равна сумме длин дорог A—B и B—F.$$1 + 2 = 3$$

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

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

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

1. 1
   Проверим маршрут A–B–D–C–F–G.$$5+6+3+6+3=23$$
2. 2
   Другие очевидные маршруты длиннее: A–D–C–F–G имеют длину 24, A–D–C–E–G — 25, а прямая дорога A–G — 25.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. 1
   Из пункта A ведёт единственная дорога — в пункт B длиной 2.
2. 2
   Рассмотрим маршрут $A \to B \to D \to E \to F$:$$2 + 3 + 2 + 5 = 12$$

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

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

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

1. 1
   Из пункта A ведёт только дорога в пункт B, поэтому любой маршрут начинается с участка A–B длиной 7.$$A\to B: 7$$
2. 2
   Рассмотрим наиболее короткие продолжения маршрута от B до F: через D и E, через E напрямую, а также через C и E.$$B\to D\to E\to F: 7+4+4=15;\quad B\to E\to F: 12+4=16;\quad B\to C\to E\to F: 12+10+4=26$$

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

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

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

1. 1
   Сравниваем схему дорог с таблицей: для каждой вершины учитываем число соединённых с ней дорог и расположение соседних вершин.
2. 2
   После сопоставления буквенных обозначений графа с номерами пунктов из таблицы длина дороги из A в C составляет 8 км, а длина дороги из B в H — 13 км.

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

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

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

1. 1
   Сопоставляем вершины графа с номерами пунктов в таблице по числу соседей и длинам дорог. Для дорог G–B и C–A в таблице находятся значения 21 км и 2 км.
2. 2
   Вычисляем требуемую сумму протяжённостей:$$21 + 2 = 23$$

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

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

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

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

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

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

1. 1
   Рассматриваем схему как неориентированный граф: каждая вершина соответствует населённому пункту, а каждое значение в таблице — длине дороги между двумя пунктами.
2. 2
   Сопоставляем буквенные обозначения вершин на схеме с номерами пунктов в таблице по структуре связей: количеству дорог и их длинам.

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