---

---

Практика

Разберем примеры заданий из ЕГЭ прошлый лет.

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

По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. 

Сколько существует различных путей из города А в город М?

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

В данном задании схема довольно сложная, поэтому мы будем решать другим способом - подсчетом количества вариантов путей, но в обратном порядке. Так, из точки К и из точки Л в точку М существуют только по одному варианту, а из точки И уже есть 2 варианта (сумма вариантов из точки Л и из точки М).

 

 

 

Считаем дальше, количество путей из точки Ж такое же, как и из точки И, а количество путей из точек Е и З - 4 (сумм путей из точки Ж и из точки И).

 

 

Следующим этапом мы можем найти количество путей из точки В - 10 (Е-4 + Ж-2 + З-4).

Из точки Б - 14 путей (Е-4 + В-10).

Из точки Г также 14 способов (В-10 + З-4).

Из точки Д - 18 способов (Г-14 + З-4).

И, в итоге, из точки А существует 56 способов попасть в точку М (сумма вариантов из точек Б, В, Г, Д). 

Ответ: 56

Можно было считать и в прямом порядке - от пункта А к пункту М. Результат будет тем же.

Есть разновидность задач, когда не надо заходить в какой-то пункт. В этом случае лучше зачеркнуть все дороги ведущие в данный пункт и выходящие из него. 

Есть разновидность задач, в которых путь должен обязательно проходить через какой либо пункт. В этом случае также надо вычеркнуть дороги, но только те, которые проходят мимо заданного пункта.

А дальше считаем дороги также, как в примере.

Еще один совет: в 2021 году экзамен будет проходить в компьютерной форме, и чтобы удобнее было подсчитывать пути, подписывая их количество, можно воспользоваться инструментом Ножницы, вырезать картинку с экрана и в редакторе этого инструмента вписывать числа.

И, в заключение, рекомендую пройти онлайн-тест В15 на сайте К.Полякова (выбрать)