Задание 3. Графы. Оптимальный маршрут. ЕГЭ 2020 по информатике

Зная скорость (по данным графа) и средней скорости (по данным таблицы), определим примерное время в пути между всеми соседними пунктами.

За наименьшее время можно преодолеть расстояние между пунктами БЗ.

Обратим вниматние на то, что по условию задачи наш маршрут обязательно должен проходить через пункт Е. При этом важно так же обратить внимание на то, что от нас не требуется проходить пункты в алфавитном порядке. Кратчайший путь, удовлетворяющий условиям задачи, будет таким: A-E-C-F. 8+4+2=14

На основе данных таблицы построим граф путей из пункта 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.

На основании данных графа выпишем, сколько дуг выходит из каждой вершины графа: 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.

По рисунку определяем, что в графе есть только одна вершина В, из которой выходит пять дорог. Следовательно, в таблице вершине В соответствует строка, содержащая пять значений — П3.

В графе есть только одна вершина Г, из которой выходят три дороги. Следовательно, в таблице вершине Г соответствует строка, содержащая три значения — П5.

В графе есть три вершины Ж, Б и Д, из которых выходят по три дуги. Из них только вершина Д не имеет прямого пути в вершину В. Следовательно, в таблице вершине Д соответствует строка П1, содержащая два значения, среди которых нет ни одного на пересечении со столбцом П3 (В).

Из вершины Ж выходит ровно два пути в уже определённые нами вершины В (П3) и Г (П5). Следовательно, этой вершине в таблице соответствует строка П6. Оставшаяся строка, содержащая два значения П7 соответствует вершине Б.

Из вершины А выходят четыре дороги, и из неё выходит прямая дорога в Б (П7). Следовательно, вершине А соответствует строка П2. Но тогда вершине Е — П4.

По условию требуется определить длину дороги из пункта В (П3) в пункт Е (П4). В таблице на пересечении строки П4 и столбца П3 находится значение 16.