Ручное решение
В ЕГЭ могут быть любые задания, составители на свое усмотрение могут выдать новые формулировки, поэтому ограничиваться решением только банка ФИПИ не стОит. Помимо ФИПИ, нужно прорешать и задания, которые выпадали на прошлых ЕГЭ, и задания уровня ЕГЭ, которые могут дать авторы КИМов впервые.
Прототип соответствие таблицы и схемы
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 На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Б и Е на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Ответ:
67
На схеме дорог подписываем, с каким количеством дорог соединяется каждая точка.
Г - 6 дорог, в таблице строка или столбец с 6 точками №3.
В и Ж - по 2 дороги, столбцы 4 и 5.
В остальных по 3 дороги. Но нам их надо как-то различать, поэтому дописываем маленькими цифрами, с какими именно дорогами соединяется точка.
Точки А и Д соединяются с двойками, то есть с №4 и 5 в таблице. Смотрим колонки №4 и 5. Там звездочки в №3 - но это Г (центр схемы), и в № 1 и 2, значит №1 и 2 - это А и Д.
Остались №6 и 7, это должны быть Б и Е. Проверим. Во-первых, они соединяются друг с другом, что по таблице тоже верно. Во-вторых, они не соединяются с В Ж. Все верно.
Ответ в порядке возрастания 67
Задача №2 На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта Б в пункт Д и из пункта В в пункт Е. В ответе запишите целое число.
Ответ:
22
На схеме возле каждой точки пишем кол-во дорог. Если оно одинаковое, подписываем мелкими цифрами, с какими именно дорогами соединяется.
А - 2 дороги, только один вариант, по таблице это №4.
№4 соединяется с №3 и №6 - это Б и В. Еще они соединяются между собой и с точками Д и Е.
Значит Д и Е это №1 и 2 по таблице, а длины дорог 14 и 8.
14 + 8 = 22 км
Ответ 22
Задача №3 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите сумму длин дорог из пункта Г в пункт Е и из пункта Д в З.
Ответ:
21
Задача №4 На рисунке справа изображена схема дорог N-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Е и В на схеме. В ответ запишите эти два номера в возрастающем порядке без пробелов и знаков препинания
Ответ:
24
Задача №5 На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта В в пункт С и из пункта G в пункт Н. В ответе запишите целое число.
Ответ:
61
Задача №6 На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта C в пункт D и из пункта E в пункт G. В ответе запишите целое число.
Ответ:
65
Задания уровня ЕГЭ (могут быть на следующем ЕГЭ)
Задача №1 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите длину дороги между пунктами Е и Ж. Передвигаться можно только по указанным дорогам.
Ответ:
14
Задача №2 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и E (при условии, что передвигаться можно только по построенным дорогам).
Ответ:
11
Вершина дерева - исходный пункт А. Закончить каждую ветку должны конечным пунктом Е. Пункты могут повторяться.
Это логически обрубленная версия. Видим по таблице, что пункт F соединяется с 3-мя точками. А на дереве только с двумя. Но при добавлении в дерево третьих точек очевидно, что путь в данном случае увеличится. А бывает и так, что уменьшится, так что проверяйте все варианты.
Задача №3 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами А и Б, если известно, что длина дороги между Г и Д меньше длины дороги между Г и Е. Передвигаться можно только по указанным дорогам.
Ответ:
10
Задача №4 На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите длину более длинной из дорог ЕЗ и ДЖ. В ответе запишите целое число.
Ответ:
28
Задача №5 На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Известно, что длина дороги БГ равна 17 км. Определите длину дороги ВИ. В ответе запишите целое число – длину дороги в километрах.
Ответ:
15
Задача №6 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой.. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите номера пунктов C и D, найденные номера запишите в порядке возрастания без разделителей. Например, если бы ответом были пункты П2 и П8, то в качестве ответа нужно было бы указать 28.
Ответ:
78
Задача №7 На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите протяженность маршрута FBCDEAGF. В ответе запишите целое число.
Ответ:
118
