Задание 3. Графы. Оптимальный маршрут. ЕГЭ 2020 по информатике
Средний процент выполнения: 93.8%
Ответом к заданию 3 по информатике может быть цифра (число) или слово.
Задачи для практики
Задача 1
На рисунке изображена схема дорог N-го района в виде графа. Рядом с дугами отмечены расстояния между населенными пунктами (в км). В таблице содержатся сведения о средней скорости движения автомобилей по этим дорогам (в км/ч).
| А | Б | В | Г | Д | Е | Ж | З | |
| А | - | - | 80 | 60 | - | - | - | 40 |
| Б | - | - | - | 20 | - | - | 50 | 80 |
| В | 80 | - | - | - | - | 60 | - | 30 |
| Г | 60 | 20 | - | - | 90 | - | - | - |
| Д | - | - | - | 90 | - | - | 40 | - |
| Е | - | - | 60 | - | - | - | 70 | 60 |
| Ж | - | 50 | - | - | 40 | 70 | - | - |
| З | 40 | 80 | 30 | - | - | 60 | - | - |
Определите, между какими соседними пунктами можно преодолеть расстояние за наименьшее время. В ответе запишите две буквы — названия пунктов (в алфавитном порядке, без пробелов и запятых).
Решение
Зная скорость (по данным графа) и средней скорости (по данным таблицы), определим примерное время в пути между всеми соседними пунктами.
| Соседние пункты | Расстояние, км | Скорость, км/ч | Время, ч (приближённо) |
| АВ | 200 | 80 | ≈ 2, 5 |
| АГ | 140 | 60 | ≈ 2, 3 |
| АЗ | 180 | 40 | ≈ 4, 5 |
| БГ | 280 | 20 | ≈ 14 |
| БЖ | 120 | 50 | ≈ 2, 4 |
| БЗ | 160 | 80 | ≈ 2, 0 |
| ВЕ | 180 | 60 | ≈ 3, 0 |
| ВЗ | 120 | 30 | ≈ 4, 0 |
| ГД | 280 | 90 | ≈ 3, 1 |
| ДЖ | 120 | 40 | ≈ 3, 0 |
| ЕЖ | 160 | 70 | ≈ 2, 3 |
| ЕЗ | 200 | 60 | ≈ 3, 3 |
За наименьшее время можно преодолеть расстояние между пунктами БЗ.
Задача 2
Между населёнными пунктами A, B, C, D, E и F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между соответствующими пунктами нет.)
| A | B | C | D | E | F | |
| A | - | 2 | 5 | 3 | 8 | - |
| B | 2 | - | - | - | - | 3 |
| C | 5 | - | - | - | 4 | 2 |
| D | 3 | - | - | - | - | - |
| E | 8 | - | 4 | - | - | 10 |
| F | - | 3 | 2 | - | 10 | - |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E (при условии, что передвигаться можно только по построенным дорогам).
Решение
Обратим вниматние на то, что по условию задачи наш маршрут обязательно должен проходить через пункт Е. При этом важно так же обратить внимание на то, что от нас не требуется проходить пункты в алфавитном порядке. Кратчайший путь, удовлетворяющий условиям задачи, будет таким: A-E-C-F. 8+4+2=14
Задача 3
Между населёнными пунктами A, B, C, D, E и F построены дороги, протяжённость которых приведена в таблице. (Прочерк в таблице означает, что прямой дороги между соответствующими пунктами нет.)
| A | B | C | D | E | F | |
| A | - | 5 | - | - | - | 18 |
| B | 5 | - | 4 | - | 2 | - |
| C | - | 4 | - | 6 | 10 | |
| D | - | - | 6 | - | - | 3 |
| E | - | 2 | - | - | - | 10 |
| F | 18 | - | 10 | 3 | 10 | - |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C (при условии, что передвигаться можно только по построенным дорогам).
Решение
На основе данных таблицы построим граф путей из пункта A в пункт E (без возвратов в уже пройденный пункт). При построении графа будем учитывать кратчайший путь, проходящий через пункт C до рассматриваемого пункта, отбрасывая более длинные пути. Около каждой дуги графа будем указывать длину соответствующего пути.
По первой строке таблицы определяем, что из пункта A можно попасть в один из пунктов: B или F. Так как по условию задачи путь должен проходить через пункт C, то остаётся только путь AB.
Далее, из пункта B (без возврата) можно попасть в пункты C и E. Из E можно попасть только в пункт F. Так как путь ABEF не содержит пункт C, то его можно исключить из рассмотрения. Из C — в F и D.
Из D можно попасть только в пункт F.
Путь из A в F, проходящий через вершины BCD, короче пути, проходящего через вершины BC (18 < 19). Следовательно, длина кратчайшего пути между пунктами A и F, проходящего через пункт C, равна 18.
Задача 4
На рисунке изображена схема дорог N-го района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | |
| П1 | - | - | - | - | 10 | - | 16 | - |
| П2 | - | - | - | - | 15 | - | - | 11 |
| П3 | - | - | - | 11 | 18 | 12 | - | 24 |
| П4 | - | - | 11 | - | 20 | 9 | - | - |
| П5 | 10 | 15 | 18 | 20 | - | - | 19 | - |
| П6 | - | - | 12 | 9 | - | - | 14 | - |
| П7 | 16 | - | - | - | 19 | 14 | - | - |
| П8 | - | 11 | 24 | - | - | - | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Б в пункт Ж. В ответе запишите целое число — так, как оно указано в таблице.
Решение
На основании данных графа выпишем, сколько дуг выходит из каждой вершины графа: A — 3, Б — 5, В — 4, Г — 3, Д — 2, Е — 2, Ж — 2, З — 3.
В графе есть только одна вершина Б, из которой выходят пять дорог. Следовательно, в таблице вершине Б соответствует строка, содержащая пять значений — П5.
В графе есть только одна вершина, из которой выходят четыре дороги. Следовательно, в таблице вершине В соответствует строка, содержащая четыре значения — П3.
В графе есть три вершины Д, Е и Ж, из которых выходит по две дуги. Из них только вершина Е не имеет общей дуги с вершиной Б.
Следовательно, в таблице вершине Е соответствует строка П1, содержащая два значения, среди которых нет ни одного на пересечении со столбцом П8 (Е).
Из вершины Ж выходит ровно два пути в уже определённые нами вершины Е (П8) и Б (П5). Следовательно, этой вершине в таблице соответствует строка П2.
Оставшаяся строка, содержащая два значения П1, соответствует вершине Д.
Из вершины А выходит три дуги, и она не связана общей дугой с вершиной Б (П5). Следовательно, вершине А соответствует строка П6.
Вершина З связана дугами с вершинами А (П6), В (П3) и Б (П5). Значит, вершине З соответствует строка П4, а вершине Г — П7.
По условию требуется определить длину дороги из пункта Б (П5) в пункт Ж (П2). В таблице на пересечении строки П2 и столбца П5 находится значение 15.
Задача 5
На рисунке изображена схема дорог N-го района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | - | 18 | - | 15 | - | - | - |
| П2 | 18 | - | 19 | 14 | - | - | 12 |
| П3 | - | 19 | - | 16 | 17 | 22 | 15 |
| П4 | 15 | 14 | 16 | - | 14 | - | - |
| П5 | - | - | 17 | 14 | - | 14 | - |
| П6 | - | - | 22 | - | 14 | - | - |
| П7 | - | 12 | 15 | - | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число так, как оно указано в таблице.
Решение
По рисунку определяем, что в графе есть только одна вершина В, из которой выходит пять дорог. Следовательно, в таблице вершине В соответствует строка, содержащая пять значений — П3.
В графе есть только одна вершина Г, из которой выходят три дороги. Следовательно, в таблице вершине Г соответствует строка, содержащая три значения — П5.
В графе есть три вершины Ж, Б и Д, из которых выходят по три дуги. Из них только вершина Д не имеет прямого пути в вершину В. Следовательно, в таблице вершине Д соответствует строка П1, содержащая два значения, среди которых нет ни одного на пересечении со столбцом П3 (В).
Из вершины Ж выходит ровно два пути в уже определённые нами вершины В (П3) и Г (П5). Следовательно, этой вершине в таблице соответствует строка П6. Оставшаяся строка, содержащая два значения П7 соответствует вершине Б.
Из вершины А выходят четыре дороги, и из неё выходит прямая дорога в Б (П7). Следовательно, вершине А соответствует строка П2. Но тогда вершине Е — П4.
По условию требуется определить длину дороги из пункта В (П3) в пункт Е (П4). В таблице на пересечении строки П4 и столбца П3 находится значение 16.
Задача 6
Между населёнными пунктами A, B, C, D, E и F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
| A | B | C | D | E | F | |
| A | - | 12 | - | 14 | - | 38 |
| B | 12 | - | - | 8 | 17 | - |
| C | - | - | - | 10 | - | - |
| D | 14 | 8 | 10 | - | 8 | - |
| E | - | 17 | - | 8 | - | 12 |
| F | 38 | - | - | - | 12 | - |
Решение
Задача 7
Между населёнными пунктами A, B, C, D, E и F построены дороги, протяжённость которых приведена в таблице. (Прочерк в таблице означает, что прямой дороги между соответствующими пунктами нет.)
| A | B | C | D | E | F | |
| A | - | - | 9 | 11 | - | - |
| B | - | - | 5 | 3 | - | 9 |
| C | 9 | 5 | - | - | 6 | - |
| D | 11 | 3 | - | - | - | 9 |
| E | - | - | 6 | - | - | 7 |
| F | - | 9 | - | 9 | 7 | - |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Решение
Задача 8
Между населёнными пунктами A, B, C, D, E и F построены дороги, протяжённость которых приведена в таблице. (Прочерк в таблице означает, что прямой дороги между соответствующими пунктами нет.)
| A | B | C | D | E | F | |
| A | - | 7 | - | - | - | 16 |
| B | 7 | - | 4 | - | 3 | - |
| C | - | 4 | - | 8 | 4 | |
| D | - | - | 8 | - | - | 2 |
| E | - | 3 | - | - | - | 9 |
| F | 16 | - | 4 | 2 | 9 | - |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Решение
Задача 9
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
| A | B | C | D | E | |
| A | - | 7 | 11 | - | - |
| B | 7 | - | 3 | 9 | - |
| C | 11 | 3 | - | 5 | - |
| D | - | 9 | 5 | - | 3 |
| E | - | - | - | 3 | - |
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, указанным в таблице.
Решение
Задача 10
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | - | 21 | 20 | - | 18 | 30 | 18 |
| П2 | 21 | - | - | 22 | 24 | - | - |
| П3 | 20 | - | - | - | 16 | - | 25 |
| П4 | - | 22 | - | - | 34 | 28 | - |
| П5 | 18 | 24 | 16 | 34 | - | - | - |
| П6 | 30 | - | - | 28 | - | - | - |
| П7 | 18 | - | 25 | - | - | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.Определите, в какой пункт ведёт самая короткая дорога из пункта А. В ответе запишите букву соответствующего пункта.
Решение
Задача 11
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | - | 18 | - | 15 | - | - | - |
| П2 | 18 | - | 20 | 24 | - | - | 22 |
| П3 | - | 20 | - | 16 | 27 | 22 | 15 |
| П4 | 15 | 24 | 16 | - | 14 | - | - |
| П5 | - | - | 27 | 14 | - | 18 | - |
| П6 | - | - | 22 | - | 18 | - | - |
| П7 | - | 22 | 15 | - | - | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.Определите, в какой пункт ведёт самая короткая дорога из пункта А. В ответе запишите букву соответствующего пункта.
Решение
Задача 12
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | - | 20 | - | 20 | - | 25 | - |
| П2 | 20 | - | 15 | - | 20 | - | - |
| П3 | - | 15 | - | - | 20 | 25 | - |
| П4 | 20 | - | - | - | - | 30 | 15 |
| П5 | - | 20 | 20 | - | - | 45 | |
| П6 | 25 | - | 25 | 30 | 45 | - | 20 |
| П7 | - | - | - | 15 | - | 20 | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами Б и Г. Передвигаться можно только по указанным дорогам. В ответе запишите целое число.
Решение
Задача 13
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | - | 20 | - | 10 | - | 25 | - |
| П2 | 20 | - | 15 | - | 20 | - | - |
| П3 | - | 15 | - | - | 20 | 25 | 30 |
| П4 | 10 | - | - | - | - | 30 | - |
| П5 | - | 20 | 20 | - | - | 45 | |
| П6 | 25 | - | 25 | 30 | 45 | - | 20 |
| П7 | - | - | 30 | - | - | 20 | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами Е и Г. Передвигаться можно только по указанным дорогам. В ответе запишите целое число.
Решение
Задача 14
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | |
| П1 | - | 31 | 26 | - | 15 | - |
| П2 | 31 | - | 19 | - | 17 | 24 |
| П3 | 26 | 19 | - | 21 | 18 | 20 |
| П4 | - | - | 21 | - | - | 11 |
| П5 | 15 | 17 | 18 | - | - | - |
| П6 | - | 24 | 20 | 11 | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт В. В ответе запишите целое число так, как оно указано в таблице.
Решение
Задача 15
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | |
| П1 | - | - | - | 9 | 12 | - |
| П2 | - | - | - | 27 | - | 19 |
| П3 | - | - | - | - | 31 | - |
| П4 | 9 | 27 | - | - | 16 | 35 |
| П5 | 12 | - | 31 | 16 | - | 23 |
| П6 | - | 19 | - | 35 | 23 | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.Определите, какова длина дороги из пункта Г в пункт Д. В ответе запишите целое число так, как оно указано в таблице.
Решение
Задача 16
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | |
| П1 | - | - | 15 | 10 | - | - |
| П2 | - | - | - | 9 | 11 | - |
| П3 | 15 | - | - | 8 | - | 10 |
| П4 | 10 | 9 | 8 | - | 15 | 9 |
| П5 | - | 11 | - | 15 | - | - |
| П6 | - | - | 10 | 9 | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Д в пункт Е. В ответе запишите целое число так, как оно указано в таблице.
Решение
Задача 17
На рисунке изображена схема дорог Н-ского района в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | |
| П1 | - | 16 | - | - | - | - |
| П2 | 16 | - | - | 14 | 22 | - |
| П3 | - | - | - | 8 | 11 | 28 |
| П4 | - | 14 | 8 | - | 9 | 24 |
| П5 | - | 22 | 11 | 9 | - | - |
| П6 | - | - | 28 | 24 | - | - |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт А. В ответе запишите целое число так, как оно указано в таблице.
Решение
Задача 18
На рисунке изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | - | * | * | ||||
| 2 | - | * | * | * | * | ||
| 3 | - | * | * | ||||
| 4 | * | * | - | * | |||
| 5 | * | * | - | * | |||
| 6 | * | * | * | - | * | ||
| 7 | * | * | * | * | - |
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам E и D на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Решение
Задача 19
На рисунке изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | - | * | * | * | * | ||
| 2 | * | - | * | ||||
| 3 | * | - | * | * | |||
| 4 | - | * | * | ||||
| 5 | * | * | * | - | |||
| 6 | * | * | - | ||||
| 7 | * | * | - |
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам E и D на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Решение
Задача 20
На рисунке изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | - | * | * | ||||
| 2 | - | * | * | * | |||
| 3 | * | - | * | * | * | ||
| 4 | * | * | - | ||||
| 5 | * | - | * | ||||
| 6 | * | * | - | ||||
| 7 | * | * | * | - |
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер.Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам G и B на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.