← На главную ОГЭ 🎮 К заданию

📚 Теория: Задание 9 ОГЭ — Анализ схем и графов

🔀 Что такое ориентированный граф?

Ориентированный граф (орграф) — это набор вершин, соединённых направленными рёбрами (стрелками). Каждое ребро имеет направление: от одной вершины к другой.

В задании 9 ОГЭ граф представлен схемой, где вершины обозначены русскими буквами (А, Б, В, Г, ...), а стрелки показывают возможные направления движения.

А Б В Г Д Е

Важно: В задачах ОГЭ первая вершина (обычно А) не имеет входящих рёбер, а последняя — исходящих. Это означает, что движение возможно только от начала к концу графа.

🧮 Метод подсчёта путей

Для подсчёта количества путей из начальной вершины в конечную используется метод динамического программирования.

📐 Основной принцип

Количество путей в вершину равно сумме количеств путей во все вершины, из которых есть ребро в данную.

N(X) = Σ N(Y), где Y → X
N(X) — количество путей в вершину X
Сумма берётся по всем вершинам Y, из которых есть ребро в X

📝 Алгоритм решения

  1. Для начальной вершины (А) количество путей = 1
  2. Для каждой следующей вершины считаем количество путей как сумму путей всех вершин-предшественников
  3. Записываем полученные значения в вершины
  4. Ответ — число в конечной вершине

📋 Типы задач

🔢 Общее количество путей

Найти количество путей из начальной вершины в конечную. Стандартный подсчёт суммы путей для каждой вершины.

✅ Пути через вершину

Найти количество путей, которые проходят через указанную вершину. Умножаем количество путей до вершины на количество путей от неё до конца.

❌ Пути не через вершину

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

✏️ Примеры решения задач

Пример 1: Общее количество путей

Условие: На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?

А Б В Г Д Е
Решение:

Шаг 1: N(А) = 1 (начальная вершина)

Шаг 2: Вершина Б — один вход из А
N(Б) = N(А) = 1

Шаг 3: Вершина В — один вход из А
N(В) = N(А) = 1

Шаг 4: Вершина Г — входы из Б и В
N(Г) = N(Б) + N(В) = 1 + 1 = 2

Шаг 5: Вершина Д — один вход из Б
N(Д) = N(Б) = 1

Шаг 6: Вершина Е — входы из Г и Д
N(Е) = N(Г) + N(Д) = 2 + 1 = 3

Ответ: 3

Пример 2: Пути через вершину

Условие: На рисунке — схема дорог. Сколько существует путей из А в Ж, которые проходят через город Г?

А Б В Г Д Е Ж
Решение:

Сначала подсчитаем количество путей до каждой вершины:
N(А) = 1
N(Б) = N(А) = 1
N(В) = N(А) = 1
N(Г) = N(Б) + N(В) = 1 + 1 = 2
N(Д) = N(В) = 1
N(Е) = N(Г) = 2
N(Ж) = N(Г) + N(Д) + N(Е) = 2 + 1 + 2 = 5 путей всего

Используем формулу:
N(через Г) = N(А→Г) × N(Г→Ж)

Шаг 1: N(А→Г) = 2

Шаг 2: N(Г→Ж) — пути от Г до Ж
Считаем от Г как от начальной вершины:
N(Г) = 1, N(Е) = N(Г) = 1, N(Ж) = N(Г) + N(Е) = 1 + 1 = 2

Шаг 3: N(через Г) = 2 × 2 = 4

В тренажёре у самой вершины Г подписываем 2 (пути от А), а числа 1 и 2 (у Е и Ж) — это уже пути от Г как от новой начальной вершины.

Ответ: 4

Пример 3: Пути не через вершину

Условие: Используя граф из примера 2, сколько существует путей из А в Ж, которые НЕ проходят через город Г?

Решение:

Используем формулу:
N(не через Г) = N(всего) - N(через Г)

Шаг 1: N(всего) = 5 (см. пример 2)

Шаг 2: N(через Г) = 4 (см. пример 2)

Шаг 3: N(не через Г) = 5 - 4 = 1

Это путь А→В→Д→Ж (единственный путь, не проходящий через Г)

Ответ: 1

⚠️ Частые ошибки

💡 Полезные советы

Советы для решения

  • Сразу подписывайте количество путей прямо на схеме рядом с вершинами
  • Для путей через вершину: сначала найдите все пути до этой вершины, затем — от неё до конца
  • Проверяйте: сумма путей через вершину и не через неё должна равняться общему числу путей
  • Если граф сложный, используйте таблицу для записи промежуточных результатов

🎯 План решения задачи

  1. 📝 Внимательно рассмотрите схему графа
  2. 🔢 Определите начальную и конечную вершины
  3. 📊 Для каждой вершины определите, откуда можно в неё прийти
  4. ✏️ Подсчитайте количество путей для каждой вершины от начала к концу
  5. ✅ Запишите ответ