Тема 09. Анализ путей в графе

🏠 Главная / Теория / Тема 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 вершин) — можно перебрать все пути вручную и убедиться в правильности. Для большого — только метод накопления.

Назад к списку