ФИПИ тапсырмаларының шешімдері ЕГЭ по информатикаға: «Графы и пути» — жауаптарымен

Длина дороги между пунктами

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

1. 1
   Сопоставляем буквенные обозначения вершин графа с номерами пунктов в таблице по структуре соединений. Пунктам В и Г соответствуют номера 2 и 5.
2. 2
   На пересечении строки 2 и столбца 5 таблицы находим протяжённость дороги.$$L_{2,5}=3$$

Кластеризация звёздных точек

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Необходимо разбить множество точек на непересекающиеся непустые кластеры так, чтобы точки каждого кластера лежали…

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

Ещё 3 қадам — толық шешімде

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

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

1. 1
   Обозначим через $N(X)$ количество путей из города А в город $X$. Для начального города $N(А)=1$.
2. 2
   Для каждого следующего города используем правило: количество путей в него равно сумме количеств путей в города, из которых в него направлены дороги.$$N(X)=\sum_{Y\to X}N(Y)$$

Ещё 1 қадам — толық шешімде

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

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

1. 1
   Каждый путь из А в М, проходящий через К, однозначно состоит из двух частей: пути из А в К и пути из К в М.$$N_{A\to M\ через\ K}=N_{A\to K}\cdot N_{K\to M}$$
2. 2
   Подсчитываем число направленных путей по схеме динамически: для каждой вершины складываем количества путей, ведущих в неё из предыдущих вершин. После этого перемножаем результаты для участков А–К и К–М.$$N_{A\to K}\cdot N_{K\to M}=42$$

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

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

1. 1
   Представим города и дороги в виде ориентированного графа. Для каждого города вычисляем длину самого длинного пути из города А.
2. 2
   При переходе по дороге из города $X$ в город $Y$ значение увеличивается на одну дорогу: $d(Y)=\max(d(Y),d(X)+1)$.

Ещё 1 қадам — толық шешімде

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

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

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

Ещё 1 қадам — толық шешімде

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

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

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

Ещё 2 қадам — толық шешімде

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

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

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

Ещё 1 қадам — толық шешімде

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

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

1. 1
   Каждый путь из А в М, проходящий через К, однозначно состоит из пути из А в К и пути из К в М.$$N_{A\to M\ через\ K}=N_{A\to K}\cdot N_{K\to M}$$
2. 2
   Для каждой вершины схемы последовательно подсчитываем количество путей, приходящих в неё, учитывая только дороги, направленные к этой вершине. Отдельно получаем количества путей из А в К и из К в М.

Ещё 1 қадам — толық шешімде

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

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

1. 1
   Любой путь из А в М, проходящий через Г, однозначно разбивается на путь из А в Г и путь из Г в М.
2. 2
   Подсчитаем по схеме число путей из А в Г: их 4.

Ещё 2 қадам — толық шешімде

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

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

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

Ещё 1 қадам — толық шешімде

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

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

1. 1
   Рассматриваем дороги как рёбра ориентированного графа. Сначала подсчитываем количество направленных путей из города А в город Ж.
2. 2
   Затем независимо подсчитываем количество направленных путей из города Ж в город М.

Ещё 2 қадам — толық шешімде

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

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

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

Ещё 1 қадам — толық шешімде

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

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

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

Ещё 1 қадам — толық шешімде

Длина максимального пути

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

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

Ещё 1 қадам — толық шешімде

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

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

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

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

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

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

Ещё 1 қадам — толық шешімде

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

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

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

Подсчёт путей в дорожной схеме

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

1. 1
   Представим схему дорог в виде ориентированного графа: города являются вершинами, а дороги — направленными рёбрами.
2. 2
   Обозначим через $f(X)$ количество путей из города А в город X. Для города А принимаем $f(А)=1$ — это начальная точка маршрута.

Ещё 2 қадам — толық шешімде

Длина максимального пути

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

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

Ещё 1 қадам — толық шешімде