Задача: B3506E

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, И, К. Покаждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?  --- Номер задачи: B3506E 📚 # Тема 09. Анализ путей в графе На ОГЭ эта тема проверяет умение подсчитать количество различных путей из одной вершины в другую в ориентированном графе без циклов. --- ## 1. Основные понятия - **Ориентированный граф** — граф, где рёбра имеют направление (стрелки). - **Путь** — последовательность вершин, соединённых дугами в нужном направлении. - **Простой путь** — путь без повторений вершин. > **Важно:** В задачах ОГЭ граф всегда ориентированный и без циклов (DAG). Двигаться можно только по стрелкам! --- ## 2. Метод "накопления" (динамическое программирование) Это основной и самый надёжный метод. Не считаем пути вручную — вычисляем количество способов добраться до каждой вершины. **Алгоритм:** 1. В **начальную вершину** (откуда идём) записать **1**. 2. Для каждой следующей вершины V: сложить числа из всех вершин, из которых в V ведут стрелки. 3. Двигаться строго в порядке "от начала к концу" (топологический порядок). 4. Результат в **конечной вершине** — это и есть количество путей. --- ## 3. Пример **Граф:** А → Б, А → В, Б → В, Б → Г, В → Г, В → Д, Г → Д. | Вершина | Откуда приходят | Количество путей | |---------|----------------|-----------------| | **А** | — (начало) | **1** | | **Б** | А(1) | 1 | | **В** | А(1) + Б(1) | **2** | | **Г** | Б(1) + В(2) | **3** | | **Д** | В(2) + Г(3) | **5** | Из А в Д → **5** различных путей. --- ## 4. Усложнение: "путь обязательно проходит через X" **Алгоритм:** 1. Посчитать количество путей из **начала** в **X** (метод накопления). 2. Посчитать количество путей из **X** в **конец** (метод накопления). 3. **Перемножить** результаты. **Пример:** Сколько путей из А в Д проходит через В? - Из А в В: 2 пути (из примера выше). - Из В в Д: В → Д (1) + В → Г → Д (1) = 2 пути. - Ответ: 2 × 2 = **4** пути. --- ## 5. Усложнение: "путь НЕ проходит через Y" **Алгоритм:** 1. **Удалить** вершину Y и все стрелки, связанные с ней. 2. Применить метод накопления в изменённом графе. **Альтернативный способ:** Всего путей − Пути через Y = Пути **без** Y. --- ## 6. Усложнение: "путь проходит не более чем через K промежуточных вершин" Добавьте проверку: вести подсчёт только для путей длиной ≤ K+2 (считая начало и конец). Для задач такого типа можно использовать матрицу смежности и возводить её в степень — но на ОГЭ это редкость. --- ## 7. Типичные ошибки - **Двигаться против стрелок.** Строго по стрелкам! Если стрелка А → Б, то из Б в А нельзя. - **Не учесть все входящие стрелки.** Пропустить одну стрелку = неверный результат. - **Путать вершины и рёбра.** Путь — это последовательность вершин, а не рёбер. - **Пропустить вершину при накоплении.** Всегда обрабатывайте вершины в правильном порядке (от начала к концу). --- ## 8. Лайфхаки для ОГЭ > **Совет:** Всегда рисуйте граф заново, если он дан в виде таблицы. Со схемой намного проще работать. > **Совет:** Подписывайте числа прямо на вершинах графа. Так меньше шансов запутаться. > **Совет:** Проверка: число путей в конечной вершине никогда не может быть меньше числа прямых входящих стрелок. > **Совет:** Если граф маленький (4–5 вершин) — можно перебрать все пути вручную и убедиться в правильности. Для большого — только метод накопления.