Ручное решение

В ЕГЭ могут быть любые задания, составители на свое усмотрение могут выдать новые формулировки, поэтому ограничиваться решением только банка ФИПИ не стОит. Помимо ФИПИ, нужно прорешать и задания, которые  выпадали на прошлых ЕГЭ, и задания уровня ЕГЭ, которые могут дать авторы КИМов впервые.

Прототип соответствие таблицы и схемы

1. Считаем, сколько дорог выходит из пунктов в таблице и на схеме, и сопоставляем
2. Для удобства зачеркиваем, использованные элементы (пункты и дороги) из таблицы
3. Подписываем пункты на схеме.

Прототип таблица без схемы

1) Корень дерева кратчайшего пути – это вершина графа, из которой начинается этот путь. (Задается в условии)
2) От вершины рисуем все возможные дороги, куда есть возможность попасть.
3) Около каждой дороги пишем ее вес.
4) Продолжаем пункты 2-3 до тех пор, пока каждая ветвь не будет иметь листок окончания пути.
Примечание. В дереве может быть несколько одинаковых вершин.
5) В каждой ветви считаем сумму всех весов. Наименьшая сумма – результат.

Алгоритм Дейкстры

1) Рисуем граф и отмечаем начальную и конечную вершины.
2) У начальной вершины ставим временную метку – 0. У остальных – бесконечность.
3) У вершины Х рассматриваем соседние ей вершины, считая новую временную метку: (метка у вершины Х)+(вес ребра между Х и рассматриваемой вершиной Y)
4) Если новая временная метка Y <старая временная метка Y, то зачеркиваем старую и пишем новую.
5) Временная метка вершины X превращается в постоянную.
6) Повторяем пункты 3-5, до тех пор, пока не останется временных меток вовсе.
7) Постоянная метка у конечной вершины – значение кратчайшего пути.

Прототипы заданий, которые встречались на реальных ЕГЭ

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

Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Б и Е на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

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

Определите, какова сумма протяжённостей дорог из пункта Б в пункт Д и из пункта В в пункт Е. В ответе запишите целое число.

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

В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите сумму длин дорог из пункта Г в пункт Е и из пункта Д в З.

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

Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Е и В на схеме. В ответ запишите эти два номера в возрастающем порядке без пробелов и знаков препинания

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

Определите, какова сумма протяжённостей дорог из пункта В в пункт С и из пункта G в пункт Н. В ответе запишите целое число.

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

Определите, какова сумма протяжённостей дорог из пункта C в пункт D и из пункта E в пункт G. В ответе запишите целое число.

Задания уровня ЕГЭ (могут быть на следующем ЕГЭ)

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

Определите длину дороги между пунктами Е и Ж. Передвигаться можно только по указанным дорогам.

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

Определите длину кратчайшего пути между пунктами A и E (при условии, что передвигаться можно только по построенным дорогам).

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

В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами А и Б, если известно, что длина дороги между Г и Д меньше длины дороги между Г и Е. Передвигаться можно только по указанным дорогам.

Задача №4 На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите длину более длинной из дорог ЕЗ и ДЖ. В ответе запишите целое число.

Задача №5 На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Известно, что длина дороги БГ равна 17 км. Определите длину дороги ВИ. В ответе запишите целое число – длину дороги в километрах.

Задача №6 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой.. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите номера пунктов C и D, найденные номера запишите в порядке возрастания без разделителей. Например, если бы ответом были пункты П2 и П8, то в качестве ответа нужно было бы указать 28.

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

Определите протяженность маршрута FBCDEAGF. В ответе запишите целое число.