Ручное решение
В ЕГЭ могут быть любые задания, составители на свое усмотрение могут выдать новые формулировки, поэтому ограничиваться решением только банка ФИПИ не стОит. Помимо ФИПИ, нужно прорешать и задания, которые выпадали на прошлых ЕГЭ, и задания уровня ЕГЭ, которые могут дать авторы КИМов впервые.
Прототип соответствие таблицы и схемы
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.1 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта К в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.
Ответ:
14
Для начала нужно указать у каждого пункта количество дорог, с которыми он соединяется. Далее мы смотрим на вертикальные столбики и подбираем к каждому пункту его номер: сколько дорог, столько цифр в столбике, смотрим на количество путей по таблице и сравниваем его с рисунком. Если пунктов с одинаковым количеством путей несколько, то находим сначала номера точек возле них и смотрим по таблице, какие из них имеют общую дорогу.
После этого находим в условии, между какими пунктами нам нужно узнать расстояние и смотрим их пересечение в таблице по номерам.
Б - 1
Е - 1
В - 4
А - 3 , в столбике 3 числа - П3
Г - 4
Д - 2 , в столбике 2 числа - П7
К - 1
П7 соединяется с П3 (это А) и П4 - это значит Г
По единице 3 пункта, но только один из них связан с П4 (Г) - значит К - это П6.
На пересечении П6-П4 цифра 14. Ответ 14.
1.2 На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
Ответ:
40
Укажем количество дорог к каждому пункту:
А - 2 дороги
Б - 2 дороги
В - 5 дорог
Г - 3 дороги
Д - 2 дороги
Е - 4 дороги
К - 2 дороги
Сопоставляем пункты с номерами:
В - 5 дорог, в вертикальном столбце "6" видим 5 дорог (чисел), значит "6" - это пункт В.
Г - 3 дороги, видим 3 числа в пункте "2", значит Г - это пункт "2"
Е - 4 дороги, видим 4 числа в пункте "4", значит Е - пункт "4".
Ищем расстояние между вторым и четвертым пунктами, по таблице это пересечение пункта "2" с "4", оно равно 40. Это и есть ответ.
2.1 В таблице содержатся сведения о дорогах между населёнными пунктами (звёздочка означает, что дорога между соответствующими городами есть). На рисунке справа та же схема дорог изображена в виде графа.
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населённых пунктов Б и Д в таблице. В ответе напишите два числа без разделителей: сначала для пункта Б, затем для пункта Д.
Ответ:
23
2.2 На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Б и Е на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Ответ:
67
На схеме дорог подписываем, с каким количеством дорог соединяется каждая точка.
Г - 6 дорог, в таблице строка или столбец с 6 точками №3.
В и Ж - по 2 дороги, столбцы 4 и 5.
В остальных по 3 дороги. Но нам их надо как-то различать, поэтому дописываем маленькими цифрами, с какими именно дорогами соединяется точка.
Точки А и Д соединяются с двойками, то есть с №4 и 5 в таблице. Смотрим колонки №4 и 5. Там звездочки в №3 - но это Г (центр схемы), и в № 1 и 2, значит №1 и 2 - это А и Д.
Остались №6 и 7, это должны быть Б и Е. Проверим. Во-первых, они соединяются друг с другом, что по таблице тоже верно. Во-вторых, они не соединяются с В Ж. Все верно.
Ответ в порядке возрастания 67
2.3 На рисунке справа изображена схема дорог N-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Е и В на схеме. В ответ запишите эти два номера в возрастающем порядке без пробелов и знаков препинания
Ответ:
24
2.4 В таблице содержатся сведения о дорогах между населёнными пунктами (звёздочка означает, что дорога между соответствующими городами есть). На рисунке справа та же схема дорог изображена в виде графа.
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населённых пунктов Ж и Д в таблице. В ответе напишите два числа без разделителей: сначала для пункта Ж, затем для пункта Д.
Ответ:
43
3.1 На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта Б в пункт Д и из пункта В в пункт Е. В ответе запишите целое число.
Ответ:
22
На схеме возле каждой точки пишем кол-во дорог. Если оно одинаковое, подписываем мелкими цифрами, с какими именно дорогами соединяется.
А - 2 дороги, только один вариант, по таблице это №4.
№4 соединяется с №3 и №6 - это Б и В. Еще они соединяются между собой и с точками Д и Е.
Значит Д и Е это №1 и 2 по таблице, а длины дорог 14 и 8.
14 + 8 = 22 км
Ответ 22
3.2 На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак
не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт В и из пункта Д в пункт Е.
В ответе запишите целое число.
Ответ:
23
П2 и П3 - это Б и Д, значит между ними 13, а оставшиеся цифры - это длины Б-В и Д-Е:
14+9=23
3.3 На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта В в пункт С и из пункта G в пункт Н. В ответе запишите целое число.
Ответ:
61
3.4 На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта C в пункт D и из пункта E в пункт G. В ответе запишите целое число.
Ответ:
65
3.5 На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта D в пункт F. В ответе запишите целое число.
Ответ:
74
4.1 На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта А в пункты В и Е.
В ответе запишите целое число.
Ответ:
13
5.1 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город К?
Ответ:
42
На ОГЭ были такие же задание.
Считаем стрелочки, ведущие в каждый город, начиная с А. В город А всего 1 путь (мы уже там), значит
А = 1
Теперь ищем города, в которые ведет только 1 стрелка - из А.
В город Б можем попасть только из А, значит
Б = 1
В город В из А и из Б
В=А+Б=1+1=2
Г=Б+В=1+2=3
Д=Г=3
З=Г=3 и так далее для каждой точки. Удобнее подписывать цифры прямо на рисунке.
Раз путь должен проходить через точку К, то ИМ и ЛМ вычеркиваем, то есть в счет не берем.
Получилось 42 пути.
5.2 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Д?
Ответ:
18
Особенность в том, что сначала придется зачеркнуть неиспользуемые дороги в начале пути, потому что через них нельзя попасть в Д.
Сначала определяем и вычеркиваем дороги, по которым мы точно не пойдем, если будем следовать через Д. Эти дороги в дальнейшем в расчет не берем, как будто этих стрелочек не существует.
6.1 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.
Ответ:
21
Из Е мы можем пойти в двух направлениях. Е - это и начальная точка (присваиваем ей 1), и конечная (посчитаем результат). Е всегда считаем за 1, хоть вправо идем, хоть влево, так как она начальная точка и не может быть промежуточной.
7.1 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.
Ответ:
9
Считаем сколько отрезков в самом длинном пути.
7.1 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.
Ответ:
9
В задачах такого типа решаем с конца пути. Вычеркиваем из двух возможных дорог между ближайшими точками короткий путь.
Сравниваем попарно близлежащие пути.
Из К в М 1 дорога, пока не трогаем.
Из Л в М 2 пути - ЛМ и ЛКМ, значит ЛМ вычеркиваем (будем писать -)
Из И в Л 1 дорога.
Из И в К 2 пути - ИК и ИЛК, значит ИК -
Из Е в И 2 дороги, ЕИ -
Из Ж в И 1 дорога.
Из З в И 2 дороги, ЗИ -
Из Д в З 3 пути, ДЗ -, ГЗ-
Из В в З 1 дорога.
Из В в Ж 2 пути, ВЖ -
БВ, БЕ, ЕЖ на этом этапе оставляем, там по 1 дороге.
Проверяем сочетание А с Б, В, Г и Д:
Из А в Б 1 дорога, пока не трогаем.
Из А в В 4 пути: АБВ, АВ, АГВ, АДГВ, значит оставляем только АДГВ, зачеркиваем АВ и АГ.
Делаем вывод, что возможные на данный момент пути сойдутся в точке Ж: это АБЕЖ, АБВЗЖ, АДГВЗЖ, последний длиннее, значит АБ - и БВ -.
ВЕ и ЕЖ тоже придется вычеркнуть, так как через Б мы не идем.
Остался самый длинный путь: АДГВЗЖИЛКМ
Задания уровня ЕГЭ (могут быть на следующем ЕГЭ)
Задача №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
