Теория
Граф
Граф — вершины (пункты) и рёбра (дороги). Ориентированный граф — рёбра со стрелкой (дорога только в одну сторону).
Список рёбер задаёт, откуда куда есть дорога. Таблица расстояний = матрица смежности: число — длина ребра, пусто — дороги нет.
Приём 1. Сколько путей из А в конечную вершину
- В старт А записываем 1 путь.
- Для каждой вершины: число путей = СУММА путей всех вершин, откуда в неё ведёт ребро.
- Считаем в топологическом порядке (сначала те, для которых все входящие уже посчитаны).
- Пример: А=1, Б=1, В=1, Г=1, Д=1, Е=1+1+1=3, Ж=3+1+1=5 → ответ 5.
Приём 2. Кратчайший путь по таблице
- Выписать все простые маршруты от пункта к пункту (узел не проходить дважды).
- Сложить длины рёбер каждого маршрута.
- Выбрать наименьшую сумму.
Совет: перебирай маршруты системно, чтобы не пропустить короткий неочевидный.
Разбор заданий
Дороги между городами А, Б, В, Г, Д, Е заданы списком (все дороги односторонние, проезд только в указанном направлении):
из А — в Б, Г
из Б — в В, Г, Д, Е
из В — в Г, Д
из Г — в Д
из Д — в Е
Сколько существует различных путей из города А в город Е?
Показать решение
Идём по городам по порядку: в А — 1 путь, а для каждого следующего города складываем числа путей во все города, из которых в него ведёт дорога.
Число путей: А = 1, Б = 1, В = 1, Г = 3, Д = 5, Е = 6.
В Е получается 6.
Ответ: 6.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 7 | 2 | 6 | ||
| B | 7 | 3 | |||
| C | 3 | 4 | 6 | ||
| D | 2 | 4 | |||
| E | 6 | 6 |
Определите длину кратчайшего пути между пунктами B и C. Передвигаться можно только по указанным дорогам. Каждый пункт можно посетить только один раз.
Показать решение
Из пункта B ведут дороги: B—A = 7 км, B—C = 3 км.
Перебираем возможные маршруты от B до C и складываем длины дорог:
B → C: 3 км (прямая дорога) ← кратчайший
B → A → D → C: 7 + 2 + 4 = 13 км
B → A → E → C: 7 + 6 + 6 = 19 км
Кратчайший путь — 3 км.
Ответ: 3.
Частые вопросы
Что нужно знать по теме «Граф» для ОГЭ по информатике?
Ключевые понятия и правила темы разобраны выше по шагам. Ниже — примеры заданий ОГЭ этого типа с полным разбором. Всё выверено под спецификацию и демоверсию ФИПИ-2026.
Где потренироваться в заданиях по теме «Граф»?
В тренажёре Совелия — задачи этого типа с мгновенной проверкой, подсказками и разбором именно твоей ошибки. Бесплатно, без рекламы, прогресс сохраняется.
Задания соответствуют ОГЭ-2026?
Да. Теория и задачи выверены по спецификации и демонстрационным вариантам ФИПИ 2026 года; правильность решений проверена независимым пересчётом по эталону.