Решения заданий ФИПИ ЕГЭ по информатике: «Графы и пути» — с ответами

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схема дорог задаёт ориентированный граф: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Для каждого города вычисляем максимальную длину пути из А: при переходе по одной дороге увеличиваем длину пути на 1 и сохраняем максимум.

Ещё 1 шаг — в полном решении

Пути через город Д

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассматриваем только ориентированные дороги, поэтому переходы выполняются исключительно в направлении стрелок.
2. 2
   Сначала подсчитываем количество различных путей из города А в город Д, последовательно суммируя количества путей в каждой вершине.

Ещё 2 шага — в полном решении

Пути через город В

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассмотрим только пути, проходящие через город В. Каждый такой путь однозначно разбивается на путь из А в В и путь из В в М.$$N = N_{А\to В} \cdot N_{В\to М}$$
2. 2
   Подсчётом по схеме получаем, что произведение количества вариантов первой и второй частей пути равно 8.$$N = 8$$

Пути через город Д

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Д, однозначно состоит из пути из А в Д и пути из Д в М.
2. 2
   По схеме дорог подсчитываем число направленных путей на каждом участке, последовательно складывая количества путей, ведущих в вершину.

Ещё 1 шаг — в полном решении

Пути через город К

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассмотрим только направленные дороги и будем подсчитывать пути в порядке продвижения по схеме.
2. 2
   Сначала определяем количество различных путей из города А в город К.

Ещё 3 шага — в полном решении

Пути через заданную вершину

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Для каждой вершины ориентированного графа последовательно подсчитывают количество путей из исходной вершины, складывая количества путей во всех предшествующих вершинах.
2. 2
   Отдельно подсчитывают число путей из А в К и число путей из К в М. Каждый путь из А в М, проходящий через К, однозначно раскладывается на эти две части.

Ещё 1 шаг — в полном решении

Пути через город Д

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Д, однозначно представляется как путь из А в Д и путь из Д в М.
2. 2
   По схеме дорог подсчитываем количество направленных путей на каждом участке графа. Произведение количества путей из А в Д и из Д в М даёт общее число путей через Д.

Ещё 1 шаг — в полном решении

Пути через заданный город

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Так как все дороги имеют направление, количество путей до каждой вершины удобно считать последовательно: число путей в вершину равно сумме чисел путей в её предшественники.$$N(X)=\sum N(P_i)$$
2. 2
   Путь из А в М, проходящий через Л, состоит из двух независимых частей: пути из А в Л и пути из Л в М. Поэтому их количества перемножаются.$$N_{A\to M\ через\ Л}=N_{A\to Л}\cdot N_{Л\to M}$$

Ещё 1 шаг — в полном решении

Пути через город Ж

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Ж, однозначно разбивается на путь из А в Ж и путь из Ж в М.
2. 2
   Для каждой вершины схемы последовательно подсчитываем число путей из А, используя правило: число путей в вершину равно сумме чисел путей во все непосредственно предшествующие вершины.

Ещё 2 шага — в полном решении

Подсчёт путей в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных…

1. 1
   Рассматриваем ориентированный граф дорог и ищем замкнутые пути, начинающиеся и заканчивающиеся в городе Е. Путь нулевой длины не учитывается.
2. 2
   При переборе маршрутов соблюдаем направление каждой дороги, не используем город Е как промежуточную вершину и не посещаем ни один промежуточный город более одного раза.

Ещё 1 шаг — в полном решении

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схему дорог рассматриваем как ориентированный граф. Для каждого города вычисляем длину самого длинного пути из города А до него.
2. 2
   Если в город ведут дороги из нескольких городов, выбираем максимальную длину пути до начального города этой дороги и прибавляем одну дорогу.

Ещё 1 шаг — в полном решении

Пути через город Л

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Так как каждый рассматриваемый путь проходит через город Л, его можно единственным образом разделить на путь из А в Л и путь из Л в М.
2. 2
   Для каждой вершины схемы последовательно подсчитываем число путей из А: число путей в вершину равно сумме чисел путей в неё из всех соседних вершин, из которых ведут стрелки.

Ещё 1 шаг — в полном решении

Пути через заданный город

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Каждый путь из А в М, проходящий через Ж, однозначно разбивается на путь из А в Ж и путь из Ж в М.$$N = N_{А\to Ж} \cdot N_{Ж\to М}$$
2. 2
   Подсчитываем по направленным рёбрам схемы количество путей на каждом из двух участков и перемножаем полученные значения.$$N_{А\to Ж} \cdot N_{Ж\to М} = 20$$

Пути через город Ж

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Для каждого города на схеме подсчитываем количество путей из А, используя сумму количеств путей из городов, из которых в него ведут дороги.
2. 2
   Определяем количество путей из А в Ж и количество продолжений из Ж в М.

Ещё 1 шаг — в полном решении

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схема дорог задаёт ориентированный граф: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Начинаем с города А и для каждого достижимого города фиксируем максимальное количество дорог в пути из А. При переходе по очередной дороге длина пути увеличивается на 1.

Ещё 1 шаг — в полном решении

Длина пути в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Представим города вершинами ориентированного графа, а дороги — его рёбрами. Двигаемся только по направлению стрелок.
2. 2
   Для каждой вершины вычисляем длину максимального пути из А: при переходе по одной дороге длина пути увеличивается на 1. Последовательно просматривая вершины схемы, получаем максимальную длину пути до города М.

Ещё 1 шаг — в полном решении

Подсчёт путей в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных…

1. 1
   Представим схему дорог в виде ориентированного графа: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Перебираем все пути, которые начинаются в Е, заканчиваются в Е, имеют ненулевую длину и не проходят через Е до последней вершины.

Ещё 2 шага — в полном решении

Самый длинный путь в графе

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схему дорог рассматриваем как ориентированный граф: города являются вершинами, а дороги со стрелками — ориентированными рёбрами.
2. 2
   Для каждой вершины последовательно определяем максимальную длину пути из города А. При переходе по очередной дороге длина пути увеличивается на одну.

Ещё 1 шаг — в полном решении

Самый длинный путь

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого…

1. 1
   Схему дорог представляем в виде ориентированного графа: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Для каждого города вычисляем максимальное количество дорог в пути из города А. При переходе по дороге значение увеличивается на 1; если в город ведут несколько путей, выбираем максимальное значение.

Ещё 1 шаг — в полном решении

Подсчёт путей через город

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует…

1. 1
   Рассмотрим только пути, проходящие через город В. Каждый такой путь однозначно разбивается на путь из А в В и путь из В в М.$$N = N_{А\to В} \cdot N_{В\to М}$$
2. 2
   Последовательно подсчитаем количество путей по направлению стрелок, суммируя значения для всех входящих в город дорог. По схеме получаем 12 путей из А в В.$$N_{А\to В} = 12$$

Ещё 2 шага — в полном решении