ок. Графы. Поиск количества путей
 Скачать 2.33 Mb.
|
Д. Муфаззалов) На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт Е и содержащих ровно семь пунктов, включая пункты А и Н? (Д. Муфаззалов) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, содержащих не менее семи городов, включая города А и М?  (Д. Муфаззалов) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. В ответе укажите первый в лексикографическом (алфавитном) порядке маршрут из города А в город Н, содержащий ровно восемь городов, включая города А и Н; города в маршруте указывайте заглавными буквами без разделителей.  (Д. Муфаззалов) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. В ответе укажите последний в лексикографическом (алфавитном) порядке маршрут из города А в город Н, не проходящий через город Е и содержащий ровно восемь городов, включая города А и Н; города в маршруте указывайте заглавными буквами без разделителей. (А. Богданов) На рисунке – схема дорог, связывающих города В, Г, Д, Е, Ё, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. В ответе укажите количество маршрутов из города В в город М, не проходящих через город Ё.  (И. Женецкий) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город О? Длиной пути считать количество дорог, составляющих этот путь.  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М, не проходящего через Ж? Длиной пути считать количество дорог, составляющих этот путь.  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город К? Длиной пути считать количество дорог, составляющих этот путь.  (ЕГЭ-2022) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (ЕГЭ-2022) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (ЕГЭ-2022) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (ЕГЭ-2022) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (ЕГЭ-2022) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Е, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (А. Калинин) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе З, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (А. Калинин) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе З, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (А. Калинин) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе Ж, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (А. Калинин) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе И, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М, проходящего одновременно через пункты В и З? Длиной пути считать количество дорог, составляющих этот путь.  (К. Багдасарян) На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе A, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза.  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного маршрута, начинающегося и заканчивающегося в пункте Ж и не проходящих дважды через один и тот же пункт? Длиной пути считать количество дорог, составляющих этот путь.  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Ж и не проходящих дважды через один и тот же пункт? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Г, не проходящих дважды через один и тот же пункт и не проходящих через город Б? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Ж, не проходящих дважды через один и тот же пункт и проходящих через город Г? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в городе Г и не проходящих дважды через один и тот же пункт?  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в городе Ж и не проходящих дважды через один и тот же пункт? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Ж, не проходящих дважды через один и тот же пункт и проходящих через пункт Б? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Г, не проходящих дважды через один и тот же пункт и проходящих через пункт Б?  (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Г, не проходящих дважды через один и тот же пункт и не проходящих через пункт З? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Г и не проходящих дважды через один и тот же пункт? (Е. Джобс) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Ж и не проходящих дважды через один и тот же пункт? (М. Шагитов) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Ж, не проходящих дважды через один и тот же пункт?  (М. Шагитов) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, начинающихся и оканчивающихся в пункте Ж, не проходящих дважды через один и тот же пункт?  (В. Петров) На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей ненулевой длины в город H?  (В. Петров) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей ненулевой длины в город М?  *(В. Петров) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей ненулевой длины в город П?  1 Такая процедура называется топологической сортировкой графа. 2 Источники заданий: Демонстрационные варианты ЕГЭ 2011-2016. Тренировочные работы МИОО и СтатГрад 2011-2013. Крылов С.С., Ушаков Д.М. ЕГЭ 2015. Информатика. Тематические тестовые задания. — М.: Экзамен, 2015. Ушаков Д.М. ЕГЭ-2015. Информатика. 20 типовых вариантов экзаменационных работ для подготовки к ЕГЭ. — М.: Астрель, 2014. Авторские разработки. http://kpolyakov.spb.ru |